Lista de probleme 38

Un șir format din 2•n numere naturale se numește paritar dacă fiecare dintre primii săi n termeni fie are aceeași paritate cu oricare dintre ultimii săi n termeni, fie este strict mai mic decât oricare număr de paritate diferită aflat printre aceștia. Dându-se un șir de 2•n numere naturale, să se afișeze mesajul DA, în cazul în care șirul aflat în fișier este paritar, sau mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.

În vacanța de iarnă Adelina a decis să renunțe la teme și a ales să citească o parte din cărțile aduse de Moș Crăciun: cele cu teme istorice sau SF. Pe măsură ce citea își nota în caiet datele calendaristice ale acelor evenimente care au impresionat-o. După vacanță îi povestește colegului de bancă despre aceste evenimente și remarcă faptul că unele date calendaristice au o formă specială, de palindrom: citite de la dreapta la stânga reprezintă aceeași dată ca atunci când se citesc obișnuit, de la stânga la dreapta. Pentru cele n date calendaristice din agenda Adelinei numărați și afișați câte date palindromice au fost găsite iar apoi precizați secolele cu cele mai multe date palindromice.

Tomi este primarul ales în orașul Bittown. În oras sunt N locuitori și fiecare are un gard format din exact 60 de scânduri, fiecare dintre ele fiind vopsită în alb sau negru. Fiecare gard este codificat de Tomi printr-un număr natural a cărui reprezentare binară reproduce configurația gardului, de la stânga spre dreapta, scândurile negre fiind asimilate cu bitul 1 iar cele albe cu bitul 0. Astfel, ca exemplu, gardul care are doar ultimele două scânduri vopsite în negru va fi codificat de Tomi cu numărul 3. Tomi decide să-și construiască un gard care să fie reprezentativ pentru Bittown, adică să respecte toate regulile următoare:
1. Gardul primarului Tomi trebuie să aibă exact 60 de scânduri;
2. Trebuie să existe cel puțin K locuitori în Bittown care constată că pentru toate scândurile negre din gardul propriu, scândurile situate pe aceeași poziție în gardul primarului Tomi sunt vopsite tot în negru;
3. Numărul reprezentând codul gardului primarului Tomi trebuie să fie minim posibil.

Dându-se cele N numere din șir să se determine:

• Câte numere din șirul inițial nu au nevoie de transformare (conțin doar cifre distincte)?
• Câte numere va conține șirul după realizarea tuturor operațiilor de unire?
• Care este numărul maxim de cifre ale unui număr din noul șir și câte numere au acest număr maxim de cifre?

Dându-se numărul N, determinați:

• Numărul divizorilor lui N;
• Numărul maxim de apariții ale unei valori calculate în timpul jocului prin formulele descrise;
• Numerele căsuțelor ocupate, în timpul jocului, de pionul câștigătorului în ordinea în care acestea sunt vizitate.

Gigel a descărcat pe telefon un joc nou. Jocul are mai multe camere. Pentru a trece dintr-o cameră a jocului în următoarea cameră este nevoie de o cheie potrivită, care va deschide ușa ei. La începutul jocului se cunosc două chei digitale, ce reprezintă două numere naturale. Cu aceste chei se vor deschide ușile primelor două camere. Cunoscând primele două chei ale jocului, notate x și y, să se obțină și să se afișeze șirul format din cheile camerelor din joc, în ordinea utilizării lor, până la terminarea jocului.

Robotul Vasile s-a angajat la un depozit de pixuri. Aici pixurile sunt ambalate în cutii. Există N tipuri de cutii; într-o cutie de tipul i (1 ≤ i ≤ N) sunt ambalate exact nr[i] pixuri (nr[1] ≤ nr[2] ≤ ... ≤ nr[N]). În depozit există un număr atât de mare de cutii de fiecare tip încât Vasile poate utiliza oricâte cutii doreşte, de orice tip. Sarcina robotului Vasile este să livreze pixurile comandate de diferite firme de birotică. El nu ştie câte pixuri va avea de livrat la următoarea comandă, dar ştie că vor fi cel mult Vmax pixuri. Ca urmare, pentru a fi eficient, robotul Vasile vrea să îşi pregătească în camera de livrare un număr minim de cutii de pixuri astfel încât să poată livra orice număr de pixuri cuprins între 1 şi Vmax folosind cutiile pregătite, evident, fără a deschide cutiile. Scrieţi un program care citeşte valorile N, nr[1], nr[2], … nr[N] şi Vmax și determină numărul minim de cutii pe care robotul Vasile trebuie să le pregătească în camera de livrare astfel încât să poată livra orice număr de pixuri cuprins între 1 şi Vmax, fără a deschide nicio cutie.

Alexandru și Tudor au inventat un joc numit Jocul Divizorilor. La acest joc, fiecare dintre cei doi jucători extrage un șir format din n numere. Alexandru este jucătorul cu numărul 1 si Tudor este jucătorul cu numărul 2. Pentru fiecare număr x din șir, se obține divizorul său prim care are puterea cea mai mare denumit p-divizor; dacă numărul x are mai mulți divizori primi care au aceeași putere maximă, atunci p-divizorul este divizorul prim cel mai mare dintre aceștia. Astfel, p-divizorul numărului 36 este 3, p-divizorul numărului 12 este 2, p-divizorul numărului 30 este 5. Scrieţi un program care citește numărul n, cele n numere din șirul lui Alexandru, apoi cele n numere din șirul lui Tudor și determină numărul de ordine al câștigătorului jocului, punctajul câștigătorului jocului și cel mai mare număr dintre toate numerele câștigătoare din joc.