Lista de probleme 10

Cei care au văzut filmul Nemuritorul, ştiu că fraza cu care nemuritorii încep lupta este “Nu poate să rămână decât unul singur”. Să încercăm să simulăm povestea nemuritorilor.

Într-o zonă dreptunghiulară formată din n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m) se află maxim n•m-1 nemuritori. Doi nemuritori vecini se “luptă” între ei şi cel care pierde lupta este eliminat. “Lupta” constă în săritura unuia dintre nemuritori peste celălalt, dacă această săritură se poate face. Săritura se poate face pe orizontală sau verticală şi nemuritorul peste care s-a sărit dispare. Prin vecin al nemuritorului din poziţia (i,j) înţelegem un nemuritor din una dintre poziţiile (i-1,j), (i+1,j), (i,j-1), (i,j+1). Deci, după luptă nemuritorul din câmpul (i,j) se va găsi în una dintre poziţiile: (i-2,j), (i+2,j), (i,j-2) sau (i,j+2), dacă această poziţie este liberă şi este în interiorul zonei.

Se cere să se determine o succesiune a luptelor ce pot fi purtate, astfel încât la final să rămână un singur nemuritor.

Considerăm un număr întreg N şi un şir de M cifre zecimale nenule. Să se determine dacă numărul N poate fi rezultatul unei expresii aritmetice simple (fără paranteze), formată exclusiv din cifrele şirului citit şi din operatorii aritmetici desemnaţi pentru operaţiile de adunare şi scădere (+, -).

Scrieţi un program care citeşte numerele N şi M de pe prima linie a fişierului de intrare şi şirul de M cifre de pe linia următoare şi determină şi afişează expresia găsită sau valoarea 0 în cazul în care nu există soluţie.

Se consideră un şir de cifre zecimale (de la 0 la 9). În acest şir trebuie să inserăm virgule, separând astfel cifrele în scopul de a forma numere.

Scrieţi un program care să insereze virgule în şirul de cifre astfel încât să se obţină o secvenţă de numere strict crescătoare, iar ultimul număr din secvenţă să fie minim.

Gigel vrea să confecţioneze un ornament pentru pomul de iarnă format din pătrăţele frumos colorate. Pătrăţelele pot arăta ca în desenul alăturat. Se observă faptul că ele pot avea 4 culori diferite pe cele 4 laturi, 3, 2 sau chiar o singură culoare pe toate cele 4 laturi ale pătrăţelului.

Gigel are la dispoziţie n (n pătrat perfect) pătrăţele egale de acest tip cu laturile colorate doar în patru culori (alb, roşu, galben, albastru). Le vom numerota simplu de la 1 la 4.

Să se scrie un program care primeşte o listă de n pătrăţele colorate şi determină o aranjare a lor sub forma de pătrat de forma k•k (k•k = n) astfel încât două laturi adiacente să aibă aceeaşi culoare, precum şi numărul de astfel de aranjări.

În orașul Imios se află n galerii ce au locații interesante de vizitat (muzee, expoziții, castele), notate de la 1 la n. O galerie conține m locații, notate de la 1 la m. Fiecare locație are atribuit un număr de puncte, unic ca valoare. Orașul are multe birouri de informare turistică, de unde turiștii pot cumpăra un card de o zi pentru vizitarea locațiilor. Pe fiecare card se înregistrează punctul de plecare, notat prin 2 numere: numărul galeriei și cel al locației, din care se pot vizita cel mult k locații din oraș, diferite de punctul de plecare. Cardul are înregistrat un număr de puncte, ce vor fi utilizate în locațiile vizitate. Alegând o locație ce are x puncte, turistul poate selecta 4 categorii de vizitare, ce modifică punctele de pe card astfel:

• categoria rapidă: numărul de puncte de pe card se reduce cu dublul lui x
• categoria extinsă: numărul de puncte de pe card se reduce cu x/2 puncte
• categoria medie: la numărul de puncte de pe card se adaugă x puncte
• categoria clasică: din numărul de puncte de pe card se scad x puncte.

Alexandru a cumpărat un card și dorește să viziteze cât mai puține locații și să utilizeze toate punctele de pe card. Împreună cu cardul, a primit o hartă electronică a locațiilor din oraș, codificată printr-o matrice h, având n linii și m coloane, pe care este înregistrat numărul de puncte al fiecărei locații. Pe hartă, punctul de plecare, înregistrat pe card, conține numărul de puncte disponibile pe card pentru vizitare. A fost informat că după vizitarea unei locații, se poate deplasa numai într-o locație vecină cu aceasta în cele 8 direcții (N, NE, E, SE, S, SV, V, NV). Fiecare locație poate fi vizitată o singură dată, pe baza cardului. Alexandru a decis că dacă are mai multe variante posibile de vizitare, din care să aleagă, va opta pentru acea variantă în care ultima locație are cel mai mic număr de puncte. Dacă există mai multe variante de vizitare care au același număr minim de puncte pentru ultima locație, va opta pentru varianta în care prima locație are cel mai mic număr de puncte. Două variante de vizitare diferă prin: locațiile lor, ordinea locațiilor vizitate și categorii de vizitare alese pentru locații.

Să se scrie un program care obține numărul de variante posibile de vizitare a unor locații din oraș, care conțin cât mai puține locații vizitate din punctul de plecare, ce asigură utilizarea tuturor punctelor de pe card și lista punctelor din locațiile vizitate, în ordinea vizitării lor, pentru varianta pe care Alexandru o alege.

Într-o țară în curs de dezvoltare, într-un oraș oarecare, parcarea pe care primăria dorește să o construiască are formă dreptunghiulară și o putem codifica folosind o matrice cu L linii (numerotate de la 1 la L) și C coloane (numerotate de la 1 la C). Practic, pentru a o pava pe toată ar fi necesari L x C metri pătrați de dale. Firma care produce dalele și care este agreată de primar construiește dale cu lățimea de un metru și lungime care poate fi mai mare de un metru (dar o valoare întreagă). Firma asamblează dalele în pachete și toate pachetele au exact același conținut (dalele unui pachet pot avea lungimi diferite). Pentru că risipa banului public este în perioada sa de apogeu, primarul hotărăște să cumpere pentru fiecare coloană a parcării câte un pachet de dale și nu va putea folosi la pavarea acelei coloane decât dale din acel pachet. Se mai cunoaște și că în fiecare coloană este plantat exact un copac iar acesta nu va putea fi tăiat. Considerăm că un copac ocupă exact zona corespunzătoare unei dale 1 x 1.
După ce un consilier atrage atenția că e posibil ca structura pachetului achiziționat să nu permită pavarea oricărei coloane, primarul nefiind de acord cu această ipoteză hotărăște să te angajeze ca programator și să îi spui care este numărul de variante distincte de pavare a parcării. La numărarea variantelor trebuie ținut cont că toate dalele dintr-un pachet sunt de culori diferite. Considerăm distincte două modalități de pavare dacă există cel puțin o coloană unde același loc este acoperit de dale de culori diferite.

Majoritatea copiilor sunt sociabili și relaționează ușor cu cei de vârsta lor dar sunt și copii mai timizi sau mai puțin atrași de activitățile de grup. În urma studierii comportamentului unui eșantion de n copii, s-a stabilit, pentru fiecare doi copii dacă relaționează sau nu. Pentru serbarea de sfârșit de an, s-a propus realizarea unei scenete și este necesară selectarea unei grupe cât mai numeroase de micuți dar fără a depăși k, numărul maxim de personaje. Rolurile presupun interacțiunea fiecărui copil selectat cu toți ceilalți mici actori care joacă în scenetă. Să se determine cel mai mare număr de copii care pot fi implicați în serbare, știind ca fiecare dintre aceștia trebuie să relaționeze cu toți ceilalți copii din scenetă.

Adrian al III-lea este un prinț vrăjitor. De 4 noiembrie, ziua vrăjitoriei, acesta a vrut să o impresioneze pe Norela, fata visurilor lui. El are n cărți de joc, care inițial se află înșirate pe o masă cu fața în jos. Adrian are la dispoziție m magii, o magie fiind de forma: q a1 a2 …, aq. În timpul unei magii, se vor întoarce pe rând şi în ordine cărțile cu indicii a1 a2 …, aq. (numerele sunt distincte două câte două). Cartea va fi întoarsă indiferent dacă aceasta se află cu fața în sus sau cu fața în jos (dacă este cu fața în sus, se va întoarce cu fața în jos, iar dacă este cu fața în jos se va întoarce cu fața în sus), iar fiecare magie poate fi utilizată maxim o dată. Ajutați-l pe Adrian să o impresioneze pe Norela înaintea dușmanului său, Manea cel Sprâncenat! Aflați numărul minim de magii ce trebuie folosite, astfel încât la final toate cărțile să fie cu fața în sus. De asemenea, spuneți și care magii au fost folosite. În cazul în care există mai multe soluții, se va afișa cea minim lexicografică.

Scrie un program care pentru un număr natural nenul n, găsește numărul de secvențe de numere naturale nenule a1, a2, a3,..., an, astfel încât a1 * a2 * a3 *...* an = a1 + a2 + a3 +...+ an și a1 ≥ a2 ≥ a3 ≥...≥ an.

Două veverițe gemene au descoperit un depozit de alune care are o formă foarte ciudată. Mai precis, depozitul are forma unei matrice N x N cu N impar. Fiecare poziție din matrice este o cameră și în fiecare cameră se află câte o alună. Camerele sunt numerotate cu numărul de linie și numărul de coloană. Cunoscând N, să se răspundă la Q întrebări de forma: “Ce traseu a notat Chip pe poziția P?”