Lista de probleme 184

Banda piraţilor din Caraibe a pus la cale o nouă aventură! Căpitanul Jack se trezeşte prins într-o intrigă care îi va solicita din plin abilităţile şi inteligenţa. Deoarece el are o datorie de sânge faţă de legendarul Davey Jones, căpitanul corabiei fantomatice Olandezul Zburător, este
nevoit să-i cedeze acestuia o parte din ultima captură de diamante. Diamantele sunt depozitate în cufere şi trebuie să fie păzite foarte bine până în momentul în care Jack îşi va achita datoria.
El hotărăşte ca fiecare cufăr să fie păzit de câte doi piraţi şi pentru aceasta îşi organizează oamenii astfel:

• piraţi care vor forma rânduri;
• piraţi aşezaţi în formaţiuni circulare.

În ambele situaţii va fi aşezat câte un cufăr între oricare doi piraţi alăturaţi. În momentul în care corabia lui Davey Jones acostează la ţărm, acesta îi cere lui Jack să-şi plătească datoria astfel: „Alege N dintre piraţii tăi. Aceştia vor încărca pe corabie toate cuferele păzite doar de ei. Ai grijă ca numărul cuferelor să fie cel mai mare posibil! ”

Cunoscând numărul piraţilor şi modul lor de organizare în formaţiuni, scrieţi un program care să determine numărul maxim de cufere care pot fi încărcate pe corabie de cei N piraţi aleşi.

Se consideră două numere naturale impare p şi q şi A={1,2,3,4,5,. . .,p*q} mulţimea tuturor numerelor naturale cuprinse între 1 şi p*q.

Să se scrie un program care determină p mulţimi, notate A1, A2,…, Ap cu proprietăţile:

• Numărul de elemente ale fiecărei mulţimi Ai, 1 ≤ i ≤ p, este egal cu q;
• Ai ∩ Aj = ∅ , 1≤i<j≤p;
• A1 ∪ A2 ∪ ... ∪ Ap = A;
• Sumele elementelor fiecărei mulţimi Ai, 1≤i≤p, sunt egale.

Se consideră un șir A cu N elemente întregi nenule. Numim secvență a șirului A orice succesiune de elemente aflate pe poziții consecutive în șir: Ai, Ai+1, …, Aj cu 1 ≤ i < j ≤ N. Prin lungimea secvenței înțelegem numărul de elemente care o compun.

Pentru orice secvenţă Ai, Ai+1, …, Aj, vom numi split-point un indice k, i ≤ k < j, care împarte secvența în două subsecvențe nevide: Ai, Ai+1, …, Ak, respectiv Ak+1, Ak+2, …, Aj.

Fie Dmax valoarea absolută maximă a diferenței sumelor elementelor celor două subsecvențe separate de un split-point, luând în considerare toate secvenţele Ai,Ai+1,…,Aj posibile şi fie Lmax lungimea maximă a unei secvenţe caracterizată de valoarea Dmax.

Cunoscând N şi valorile elementelor şirului A, să se determine Dmax şi Lmax.

Fie n și p două numere naturale.

Notăm cu A(n,p) mulțimea tuturor numerelor naturale cu proprietățile :

• sunt mai mari sau egale cu 2 și mai mici sau egale cu n;
• descompunerea lor în factori primi conține doar exponenți mai mici sau egali cu p.

Să se scrie un program care citește două numere naturale n și p și determină cardinalul mulțimii A(n,p).

Aţi auzit despre Nessie? Este un pleziozaur misterios care trăieşte în adâncurile lacului Loch Ness din munţii Scoţiei. Cu mulţi ani în urmă el a fost zărit pentru prima oară la suprafaţa lacului, iar de atunci, spre desfătarea turiştilor, el îşi face apariţia în mod periodic.

Nessie ştie de la managerii Loch Ness care este programul de vizitare a lacului pentru un interval de N zile. Mai exact, el cunoaşte datele primei și ultimei zile de şedere în preajma lacului pentru fiecare turist.

Contractul pe care Nessie l-a semnat cu managerii prevede faptul că fiecare dintre turişti trebuie să aibă posibilitatea să-l zărească, însă doar de departe şi doar o singură dată, deoarece Nessie intenţionează să rămână în continuare misterios. Pot exista zile fără turişti şi în aceste zile Nessie profită de fiecare dată ca să iasă la suprafaţa lacului.

Cunoscând prima şi ultima zi de şedere pentru fiecare turist, şi numărul total de zile prevăzute în contract, determinaţi numărul maxim de ieşiri la suprafaţa lacului, pe care Nessie le poate face, astfel încât fiecare turist să-l zărească o singură dată.

Pentru un număr oarecare X, natural, să se calculeze a X-a zecimală a numărului rațional \( \frac {1} {2 ^ X} \).

Pe o tablă de joc cu N linii și M coloane se află un roboțel pe poziția 1,1. El știe să meargă doar pe conturul tablei (prima și ultima linie, respectiv prima și ultima coloană). Robotul dorește să ajungă pe poziția N, M dar nu este așa simplu. Pe tabla de joc se află Q bare de lungimi infinite. Barele sunt fixate în colțul din dreapta jos a unor căsuțe. La început, o bară se poate afla fie în poziție verticală, fie în poziție orizontală. Robotul poate schimba orientarea acestor bare din poziție verticală în poziție orizontală și invers. El nu poate trece printr-o bară.
De exemplu, dacă avem N=4, M=4, Q=1 și bara se află la coordonatele 3,3 în poziție verticală, robotul nu poate ajunge la căsuțele de pe coloana 4. Dar dacă el învârte bara poate merge pe coloana 4, apoi pentru a merge pe linia 4 poate să învârtă bara din nou.

Această soluție nu este optimă deoarece robotul putea ajunge în poziția 4,4 învârtind o singură dată bara. Mai întâi se poziționează pe linia 4, apoi învârte bara și se duce pe coloana 4.

Să se afle numărul minim de rotiri ale barelor pentru ca robotul să ajungă din poziția 1,1 în poziția N,M, mergând numai în dreapta și în jos.

Războiul intergalactic a început, iar extratereștrii au invadat deja planeta noastră. Misiunea ta este să salvezi toți locuitorii planetei cât mai repede cu putință!

Într-un hambar vechi, ai găsit un robot proiectat special pentru amplasarea de bombe nucleare și totodată o hartă a planetei sub formă de dreptunghi împărțită în N x M zone pătratice dispuse pe N linii și M coloane, de dimensiune 1. Pe hartă sunt reprezentate și pozițiile extratereștrilor (xi,yi), unde xi reprezintă indicele de linie, iar yi reprezintă indicele de coloană al extraterestrului i. De asemenea, robotul poate amplasa bombe în orice poziție de pe hartă, iar la declanșarea lor, acestea distrug orice extraterestru de pe aceeași linie sau de pe aceeași coloană cu ele.

Din păcate, robotul nu este echipat decât cu o singură bombă. Datoria ta este să-i transmiți robotului coordonatele x y unde să amplaseze bomba, astfel încât toți extratereștrii să fie distruși. Poți să salvezi planeta? Timpul se scurge! Tic, tac, tic, tac…

Chris vă propune un joc cu becuri.

• în joc sunt n becuri
• inițial toate cele n becuri au culoarea albastru
• fiecare bec poate avea doar două culori: roșu sau albastru
• se efectuează n parcurgeri, pentru k de la 1 la n. La parcurgerea de rang k, se schimbă culoarea fiecărui bec situat pe poziţii având indicii multipli de k, din roşu în albastru şi invers.

Știind numărul n de becuri, să se afișeze numărul de becuri care au culoarea roșie după terminarea jocului.

Pe un teren dreptunghiular de dimensiuni m şi n, din loc în loc sunt plantaţi copaci. Pentru fiecare copac se cunosc rândul şi coloana pe care este plantat, între ei fiind spaţii neplantate. Doi copaci se consideră consecutivi dacă mergând pe coloane, numai de la nord către sud, între ei sunt doar spaţii neplantate.

Să se determine cea mai mare distanţă dintre doi copaci consecutivi şi toate perechile de copaci între care există această distanţă.