Lista de probleme 972

Filtrare

Orice număr natural mai mare decât 2 poate fi scris ca sumă de numere naturale nenule aflate în ordine strict crescătoare, astfel încât orice termen al sumei, cu excepția primului termen, este un multiplu al termenului precedent din sumă. De exemplu, 27=3+6+18, unde 6 este multiplul lui 3, iar 18 este multiplul lui 6. Cum se dorește o descompunere formată dintr-un număr cât mai mare de termeni, vom obține și descompuneri cu 4 termeni: 27=1+2+8+16, 27=1+2+4+20, 27=1+2+6+18. Dintre cele trei descompuneri cu 4 termeni, descompunerea 27=1+2+4+20 este minimă din punct de vedere lexicografic (1 și 2 sunt la fel în cele trei descompuneri, dar 4 < 6 și 4 < 8). Numărul 30 poate fi descompus 30=2+4+8+16. El are o descompunere tot de lungime 4, dar este mai mare din punct de vedere lexicografic decât oricare dintre descompunerile cu patru termeni ale lui 27 (2 > 1).

Pentru mai multe seturi de date formate din câte două numere naturale A și B, A ≤ B, se cere să se determine, pentru fiecare set una dintre următoarele cerințe:
1. numărul maxim de termeni în care pot fi descompuse numerele din intervalul [A,B] după regula descrisă în enunț;
2. numărul de numere din intervalul [A,B] care pot fi descompuse cu un număr maxim de termeni;
3. numărul din intervalul [A,B] care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

ONI 2017, clasa a X-a

Mihai a construit o matrice pătratică A de dimensiune N cu valori în mulțimea {0,1}. El preferă acele matrice care au toate elementele identice și de aceea a calculat pentru matricea A, numărul K de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea A într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul D, și definește operația ZET care constă în alegerea unei submatrice pătratice de dimensiunea D din matricea precedentă în care schimbă toate elementele 0 în 1 și invers. El vrea să aplice operația ZET inițial pentru matricea A, apoi repetă operația pentru matricea obținută la momentul anterior, de un număr minim de ori, notat R, până când matricea obținută are toate elementele identice, sau dacă nu este posibil, R va avea valoarea -1.

Mihai vă roagă să calculați valorile K și R. Pentru a preciza tipul cerinței, Mihai folosește un cod T care dacă are valoarea 1, atunci solicită calcularea valorii K, iar dacă T are valoarea 2, atunci solicită calcularea valorii R.

ONI 2017, clasa a X-a

#2193 100m

Proba de 100 metri plat este una dintre cele mai populare și prestigioase probe din cadrul oricărui concurs de atletism. Recordul modial al acestei probe este deținut în prezent de sportivul jamaican Usain Bolt cu timpul de 9.58 secunde.
Uneori lupta dintre sportivi este atât de strânsă încât diferențierea dintre atleți se poate face doar cu ajutorul camerelor de luat vederi ce surprind finish-ul atleților. Au existat cazuri când doi sau mai multi atleți au fost declarați la egalitate.

Considerând N atleți, ce participă la o cursă de 100 metri plat, identificați prin numerele 1, 2, …, N, să se scrie un program care determină numărul P al clasamentelor distincte care pot fi obținute după finalizarea cursei. De exemplu, pentru N = 2, se pot obține 3 clasamente distincte: (1,2), (2,1), (1=2); unde (1=2) reprezintă situația când ambii atleți s-au clasat la egalitate.

ONI 2017, clasa a X-a

#2187 expand

Ana şi Bogdan au inventat un nou joc, pe care l-au numit Expand. Jocul are N cartonaşe, pe fiecare cartonaş fiind scrisă o literă şi o secvenţă formată din două sau trei litere. O mutare constă în utilizarea unui cartonaş prin care o singură apariţie a literei scrisă pe cartonaş va fi înlocuită în cuvântul curent cu secvenţa corespunzătoare de pe cartonaş. Apoi cartonaşul este repus în joc, astfel că acelaşi cartonaş poate fi utilizat de oricâte ori. Iniţial Ana alege o literă şi un cuvânt. Bogdan trebuie să obţină cuvântul spus de Ana, plecând de la litera respectivă, efectuând un număr minim de mutări. Scrieţi un program care determină numărul minim de mutări necesare pentru a obţine din litera aleasă de Ana cuvântul dat.

Olimpiada Municipala de Informatica, Iasi, 2017

Camelia este pasionată de operații aritmetice. Într-o zi, s-a gândit să evalueze valoarea unei expresii ce este formată din litere mici şi operatorii: +, <, >. În expresie, fiecare literă va fi înlocuită cu numărul de ordine pe care îl are în alfabet (a=1, b=2 etc.). Prietena ei, Mădălina i-a pregătit Cameliei mai multe expresii de acest tip, pe care să le evalueze și apoi să determine care este numărul cel mai mare, obținut dintr-un șir de litere, din expresiile date.

Scrieţi un program care determină pentru un şir de n expresii, formate din litere mici şi operatorii: +, <, >, două cerinţe:
-cerinţa 1: să determine numărul cel mai mare, obținut dintr-un șir de litere, din expresiile date;
-cerinţa 2: să evalueze fiecare expresie și să afișeze valoarea ei.

Olimpiada Municipala de Informatica, Iasi, 2017

Se consideră un şir format din n numere naturale, având valori de la 1 la 4. Câte subşiruri formate din cel puţin un element există în şirul dat, astfel încât produsul elementelor din subşir să fie strict mai mic decât un număr dat p?

#2184 schior

Un schior profesionist se află pe un platou montan. Harta platoului este împărțită în n rânduri (numerotate de la 1 la n) a câte m parcele (numerotate de la 1 la m), fiecare parcelă reprezentând o zonă de teren de formă pătrată cu latura de 1 metru. Pe fiecare parcelă de pe hartă este scris un număr, ce reprezintă altitudinea parcelei respective. Schiorul se poate deplasa din parcela curentă în oricare din cele opt parcele învecinate (pe orizontală, verticală sau diagonală), cu condiția ca altitudinea noii parcele să fie mai mică sau egală cu altitudinea parcelei în care se afla anterior. Cunoscând coordonatele parcelei în care se află inițial schiorul, să se determine altitudinea minimă la care poate ajunge acesta.

Olimpiada Municipala de Informatica, Iasi, 2017

Fie o permutare P a mulțimii {1, 2, 3, ... N}. Se numește inversiune o pereche (i, j), i < j pentru care P[i] > P[j]. Fie funcția M(N) = suma numărului de inversiuni a fiecărei permutare a numerelor {1, 2, 3, ... N}. Pentru N dat, să se calculeze M(N) modulo 666013.

#2168 dir

Costel trebuie să realizeze, împreună cu echipa sa, o aplicaţie software pentru gestiunea fişierelor de pe hard-disc, sarcina sa fiind aceea de a scrie un modul pentru determinarea căilor tuturor fişierelor de date aflate în structura arborescentă a folderelor de pe disc. Membrii echipei au stabilit o codificare proprie pentru memorarea structurii fişierelor de pe disc, utilizând un şir de caractere. Scrieţi un program care, cunoscând şirul de caractere ce codifică o structură de fişiere de pe disc, determină calea pentru fiecare fişier de date din structură. Prin cale a unui fişier se înţelege o succesiune de foldere, fiecare folder fiind urmat de caracterul \(backslash), începând de la folderul aflat pe cel mai înalt nivel al structurii (primul specificat în şirul ce codifică structura de fişiere), până la subfolderul în care se află fişierul de date respectiv şi terminată cu numele fişierului. Căile determinate vor fi afişate în ordine lexicografică.

#2167 alee

Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări. Parcul are forma unui pătrat cu latura de n metri și este înconjurat de un gard care are exact două porți. Proiectanții de la Primărie au realizat o hartă a parcului și au trasat pe hartă un caroiaj care împarte parcul în nxn zone pătrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice pătratice cu n linii și n coloane. Liniile și respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei corespund zonelor pătrate de latură 1 metru. O astfel de zonă poate să conțină un copac sau este liberă. Edilii orașului doresc să paveze cu un număr minim de dale pătrate cu latura de 1 metru zonele libere (fără copaci) ale parcului, astfel încât să se obțină o alee continuă de la o poartă la alta. Scrieți un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.