Lista de probleme 1991

Să se calculeze suma S=12 + 22 + 32 + ... + n2, modulo 10.234.573.

Iepurașul Coconaș vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăți speciale. Zona este formată din N căsuțe numerotate de la 1 la N, dispuse una după cealaltă, iar fiecare căsuță conține un număr natural ce reprezintă cantitatea de energie necesară iepurașului pentru a sări într-o altă căsuță.

Iepurașul pleacă dintr-o anumită căsuță și se deplasează, de la stânga la dreapta, spre grădina cu morcovi după următoarele reguli:

• numărul înscris în căsuța în care se află iepurașul reprezintă numărul de căsuțe peste care el va sări;
• dacă numărul înscris în căsuța în care se află iepurașul este număr prim, atunci energia lui se dublează şi va sări peste un număr dublu de căsuţe;
• numărarea căsuțelor peste care va sări se face de la stânga la dreapta și începe cu căsuța imediat următoare. Astfel, dacă iepurașul se află în căsuța a treia și numărul înscris în această căsuță este 5, iepurașul va ajunge în căsuța cu numărul de ordine 13 (13=3+2*5).
• dacă iepurașul ajunge într-o căsuță care conține numărul 0, el rămâne acolo pentru că nu mai are energie să sară mai departe, altfel el continuă să sară după regulile descrise mai sus;
• iepurașul ajunge la grădina cu morcovi dacă ultimul salt pe care îl face depășește căsuța N.

Scrieți un program care citește trei numere naturale P, N și K iar apoi N numere naturale și determină:

1) dacă iepurașul poate ajunge sau nu, la grădina cu morcovi pornind din căsuța K și numărul de salturi pe care le face iepurașul pornind din căsuța K;
2) căsuța de pornire a iepurașului, astfel încât drumul parcurs de el să traverseze un număr maxim de căsuțe. Pentru a determina numărul de căsuțe se vor lua în calcul: căsuța de pornire, toate căsuțele peste care iepurașul a sărit și toate căsuțele în care a ajuns în urma salturilor. Iepurașul poate porni din oricare căsuță. În cazul în care există două sau mai multe căsuțe de pornire care conduc la același număr maxim de căsuțe traversate se va lua în considerare căsuța cu numărul de ordine cel mai mic.

Lui Mihai îi place matematica distractivă, sau poate mai mult distracția decât matematica. Pentru a scăpa de teme, el a inventat operația ”smile” notată cu semnul ☺, operație care se aplică numerelor naturale nenule conform exemplelor de mai jos:

• 6☺4=210
• 9☺2=711
• 8☺5=313
• 7☺6=113
• 6☺6=12
• 6☺10=416
• 43☺1500=14571543
• 23☺23=46

Profesorul de matematică i-a promis nota 10 pentru invenție, numai dacă știe să determine corect numărul divizorilor pari pentru rezultatul obținut prin operația ”smile”. Astfel, Mihai a primit N perechi de numere (a,b) pentru care trebuie să calculeze a☺b și să determine dacă rezultatul obținut are divizori pari.

Scrieți un program care citește un număr natural N și N perechi de numere naturale (a,b) și afișează:

a) pentru fiecare pereche de numere (a,b), rezultatul a☺b;
b) cel mai mic și cel mai mare rezultat a☺b care nu are divizori pari.

În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii Mi și Gi se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul Mi scrie și trimite un mesaj piticului Gi respectând următoarele reguli:

• un mesaj conține una sau mai multe secvențe;
• orice literă care apare în mesaj, de cel puțin două ori, pe poziții alăturate, este numită terminator;
• o secvență se încheie când s-a întâlnit o succesiune de litere terminator;
• cuvântul este format din prima majusculă și ultima minusculă din secvență, fără a lua în seamă litera terminator a secvenței;
• o secvență ascunde un cuvânt dacă terminatorul său se repetă de exact două ori și dacă conține cel puțin o literă mare și o literă mică, ignorând terminatorul de secvență;
• costul unui cuvânt este egal cu numărul total de apariții al celor două litere din care este format, în cadrul secvenței în care a fost ascuns, luând în considerare inclusiv literele terminator.

De exemplu secvența s f u E e t R u E E ascunde un cuvânt deoarece conține și majuscule și minuscule, iar litera terminator de secvență, E, se repetă de exact două ori. Secvența ascunde cuvântul Eu, iar costul cuvântului este 5 (3 litere E + 2 două litere u).

La primirea mesajului, piticul Gi determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.

Scrieţi un program care determină:

1) numărul de secvențe trimise care nu ascund cuvinte;
2) cuvintele din mesaj, în ordinea în care au fost trimise de piticul Mi;
3) pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de Gi.

Oli are un echer de forma unui triunghi dreptunghic, cu catetele de lungimi L1 și L2 unități, și o foaie de caiet de matematică cu M rânduri și N coloane de pătrățele având latura de o unitate.

Oli a poziționat echerul în colțul din stânga sus al foii de hârtie, ca în imaginea alăturată și vrea să îl mute astfel încât să atingă colțul din dreapta jos al foii de hârtie cu oricare din colțurile echerului, utilizând doar mutări de forma:

Scrieţi un program care citeşte lungimile catetelor echerului, numărul de rânduri, respectiv numărul de coloane ale foii de hârtie și determină:

1. numărul minim de mutări K, prin care poate muta echerul din colțul din stânga sus al foii de matematică, astfel încât echerul să atingă colțul din dreapta jos al foii;
2. cele K mutări efectuate pentru a deplasa echerul din colțul din stânga sus al foii, până când un colț al echerului atinge colțul din dreapta jos al foii; dacă există mai multe soluții, se va afișa soluția minimă în sens lexicografic.

În acest an evenimentul ”Hour of Code” a înregistrat un număr record de participanți din țara noastră. În cadrul acestui eveniment una dintre cele mai accesate aplicații a fost Lightbot, care a permis elevilor să-și testeze abilitățile de programare.

Aplicația Lightbot are N nivele, numerotate consecutiv de la 1 la N, în ordinea strict crescătoare a complexității lor. Lightbot a permis fiecărui participant să înceapă cu orice nivel strict mai mic decât N-1 și să sară peste un singur nivel, fără a finaliza codul, trecând la nivelul următor celui sărit. La finalizarea cu succes a codului corespunzător nivelului curent, participantul este promovat la nivelul imediat următor. Fiecare participant a început scrierea codurilor la un nivel P și a sărit peste un nivel L (P < L < P + K), finalizând K nivele memorate ca o succesiune de numere naturale de forma P, P+1,..., L-1, L+1,..., P+K. Succesiunile de nivele finalizate de participanți au fost memorate în fișierul lightbot.in. Succesiunile corespunzătoare participanților nu se intercalează în fișier.

Scrieţi un program care citeşte succesiunile corespunzătoare nivelelor finalizate de participanții care au jucat Lightbot și determină:

1. numărul total de participanți;
2. numărul celui mai dificil nivel care a fost rezolvat de un număr maxim de participanți;
3. pentru fiecare participant, numărul nivelului sărit de acesta.

În satul vecin există un teren agricol de formă dreptunghiulară împărțit în N*M pătrate elementare identice, dispuse alăturat câte M pe fiecare rând şi câte N pe fiecare coloană. Rândurile sunt numerotate de la 1 la N, iar coloanele de la 1 la M. Un pătrat elementar situat în teren pe rândul R și coloana C este identificat prin coordonatele (R,C).

Suprafețe dreptunghiulare din teren (formate fiecare din unul sau mai multe pătrate elementare alăturate) sunt revendicate de T fermieri din sat, în calitate de moștenitori, pe baza actelor primite de la strămoșii lor. Pentru că au apărut și acte false, s-a constat că pot exista mai mulți fermieri care revendică aceleași pătrate elementare.

În cele T acte ale fermierilor, suprafețele dreptunghiulare sunt precizate fiecare prin câte două perechi de numere (X,Y) și (Z,U), reprezentând coordonatele primului pătrat elementar din colțul stânga-sus al suprafeței (rândul X și coloana Y), respectiv coordonatele ultimului pătrat elementar situat în colțul dreapta-jos al suprafeței (rândul Z și coloana U).

Scrieţi un program care să citească numerele naturale N, M, T, R, C apoi cele T perechi de coordonate (X,Y) și (Z,U) precizate în acte (corespunzătoare suprafețelor dreptunghiulare revendicate) și care să determine:

1. numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C);
2. numărul maxim de fermieri care revendică același pătrat elementar;
3. numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier.

După descoperirea ruinelor unei cetăți medievale, arheologii au hotărât restaurarea acesteia, începând cu zidul principal. Acesta este format din N piloni, fiecare cu lățimea de 1 metru, așezați unul lângă altul (lipiți). Se cunoaște înălțimea, în metri, a fiecărui pilon dar, din păcate, nu toți mai sunt acum la același nivel.

Pentru restaurarea zidului, arheologii dispun de cărămizi care au lățimea de câte 1 metru și lungimi variabile, exprimate în metri. Sunt disponibile oricâte cărămizi, de oricare lungime. Considerăm că toate cărămizile disponibile și toți pilonii care alcătuiesc zidul au aceeași grosime, de 1 metru.

Restaurarea constă în două etape:

• în prima etapă, toți pilonii cu înălțimea mai mare sau egală cu H se retează, aducându-se astfel la înălțimea H, ceilalți, mai scunzi, păstrându-și înălțimea inițială;
• în a doua etapă se aduc toți pilonii la aceeași înălțime, umplându-se golurile dintre ei cu cărămizi, astfel încât zidul să devină compact; din motive neînțelese, arheologii vor așeza cărămizile “culcate”, fiecare dintre acestea ocupând, eventual, spațiul aflat deasupra mai multor piloni.

Arheologii au analizat situația, independent, pentru Q valori posibile ale lui H.

Pentru fiecare dintre cele Q valori alese pentru înălțimea H, se cere să se determine numărul minim de cărămizi necesare restaurării zidului, independent, pornind de la înălțimile inițiale ale pilonilor.

Jocul pe care îl joaca Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt N căsuțe de formă pătrată, cu latura egală cu 1. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la 1 la N. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.

Robo poate interschimba conținutul a două căsuțe, numai dacă distanța dintre centrele acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu i, respectiv cu j, este j-i (1≤i<j≤N).

El își poate fixa în orice moment distanța dintre brațe la 1 sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea N-1. Astfel, distanța dintre brațele sale poate fi 1, apoi, prin dublare, 2, apoi, prin dublare 4, apoi, prin dublare 8 etc. La începutul jocului, distanța dintre brațele lui Robo este 1. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.

Pe o tablă de şah cu N linii şi N coloane sunt plasaţi M nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.

O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.

Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.