Lista de probleme 1991

Ionuţ pleacă la sfârşit de săptămână să se relaxeze într-un parc de distracţii. La intrarea în parc se află o piaţă mare, pavată cu plăci de marmură de aceeaşi dimensiune. Fiecare placă are scris pe ea un singur număr dintre f(1), f(2), f(3), …, f(n), unde f(k) este suma cifrelor lui k, pentru k din mulţimea {1, 2, . . ., n}. Piaţa are forma unui tablou bidimensional cu n linii şi n coloane. Plăcile care alcătuiesc piaţa sunt aşezate astfel:

• pe prima linie sunt plăci cu numerele f(1), f(2), …, f(n-2), f(n-1), f(n) (în această ordine de la stânga la dreapta);
• pe linia a doua sunt plăci cu numerele f(n), f(1), f(2), f(3), …, f(n-1), (în această ordine de la stânga la dreapta);
• pe linia a treia sunt plăci cu numerele f(n-1), f(n), f(1), f(2), f(3), …, f(n-2) (în această ordine de la stânga la dreapta);

…

• pe ultima linie sunt plăci cu numerele f(2), …, f(n-2), f(n-1), f(n), f(1) (în această ordine de la stânga la dreapta).

Părinţii lui Ionuţ vor ca şi în această zi, fiul lor să rezolve măcar o problemă cu sume. Astfel aceştia îi propun lui Ionuţ să determine suma numerelor aflate pe porţiunea dreptunghiulară din piaţă având colţurile în poziţiile în care se găsesc aşezaţi ei. Tatăl se află pe linia iT şi coloana jT (colţul stânga-sus), iar mama pe linia iM şi coloana jM (colţul dreapta-jos). Porţiunea din piaţă pentru care se doreşte suma este în formă dreptunghiulară, cu laturile paralele cu marginile pieţei (vezi zona plină din exemplu). Dacă Ionuţ va calcula suma cerută, atunci el va fi recompensat în parcul de distracţii, de către părinţii lui.

Determinaţi suma cerută de părinţii lui Ionuţ.

• toate cele patru vârfuri se regăsesc printre cele n puncte date;
• are laturile paralele cu axele OX, OY;
• are vârfurile colorate în aceeași culoare.

Să se determine numărul maxim de dreptunghiuri corecte care se pot forma cu cele n puncte din plan.

Se consideră un vector cu n elemente numere naturale. Calculați suma sumelor tuturor subsecvențelor ce se pot forma cu elementele vectorului. Pentru că suma poate fi foarte mare, afișați suma modulo 1.000.000.007.

Se consideră n intervale de numere întregi [Ai, Bi], 1≤i≤n. Să se determine numărul maxim de intervale care se suprapun (au cel puțin o valoare comună).

În oraşul Olimpidia, toate băncile au hotărât să adopte o convenţie în ceea ce priveşte identificarea clienţilor săi, astfel încât fiecare cont deschis de un client să aibă asociat un cod format din exact 6 cifre:

• prima cifră (cea mai din stânga cifră a codului) va reprezenta numărul băncii (acest lucru fiind posibil deoarece în oraş nu sunt mai mult de 9 bănci, acestea fiind numerotate începând de la 1);
• a doua cifră va reprezenta genul persoanei (1 pentru genul masculin şi 2 pentru genul feminin);
• ultimele 4 cifre vor reprezenta suma aflată în contul persoanei în momentul în care se aplică stabilita convenţie.

Cunoscând numărul total de conturi deschise şi codurile corespunzătoare acestora să se determine suma maximă pe care o are o persoană de gen masculin într-un cont aflat la banca X.

Am câștigat un concurs și primim la școală foarte foarte multe echipamente pentru un nou laborator. Pentru amenajarea laboratorului am primit și o sală de clasă. Din păcate în sala de clasă există doar o singură priză, în care ar putea fi conectat doar un singur echipament. Cum nu putem reface imediat instalația electrică, am hotărât să utilizăm prelungitoare.

Un prelungitor poate avea una sau mai multe prize în care pot fi conectate echipamente și eventual alte prelungitoare. Evident, pentru ca prelungitorul să poată fi utilizat el trebuie să fie alimentat la curentul electric.

Cunoscând configurația prelungitoarelor să se determine numărul maxim de echipamente ce pot fi alimentate la curentul electric.

În tărâmul Jupânului există N + 1 orașe. Acestea au fost construite în linie dreaptă, începând cu cel în care este casa Jupânului. Între oricare 2 orașe consecutive s-a construit câte un drum. Pentru fiecare drum, se cunoaște lungimea lui, exprimată în metri și viteza cu care se poate parcurge, exprimată în metri pe secundă.

Jupânul trebuie să ajungă din orașul 0 în orașul N. Acesta știe că poate îmbunătăți un drum, mărindu-i viteza de la V metri pe secundă la V + 1 metri pe secundă, cu costul de 1 dolar. Acesta poate îmbunătăți un drum de mai multe ori.

Jupânul are un buget de X dolari și ar vrea să-i folosească pentru a micșora timpul în care ajunge din orașul 0 în orașul N.

Zeno are n cutii cu bomboane, iar în fiecare cutie se găsește un număr natural nenul de bomboane. Zeno poate împărți bomboanele din toate cutiile colegilor în două moduri: frățește sau diferențiat. Cunoscând n numărul de cutii și numărul de bomboane din fiecare cutie să se scrie un program care determină:
a) Numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
b) O modalitate de împărțire a bomboanelor din fiecare cutie, dacă se face împărțirea diferențiată.

Pentru următorul an școlar admiterea celor N elevi în liceu se va face pe baza unor evaluări complexe. Fiecare dintre viitorii elevi ai clasei a IX-a va primi, în urma testelor și probelor pe care le va susține, un punctaj (număr natural nenul) cu care va participa la admiterea electronică.

Repartizarea fiecărui elev în clase se face în ordinea înscrierii respectând criteriile:

• Primul elev se repartizează în clasa cu numărul de ordine 1.
• În clasa în care este repartizat un elev nu există, până la momentul repartizării sale, nici un punctaj mai mare decât al său.
• Numărul claselor să fie cât mai mic posibil.

Determinaţi:

1. Punctajul primului elev care nu ar mai putea fi repartizat în prima clasă în condițiile în care toți elevii își doresc să fie repartizați în prima clasă(se aplică doar la cerința 1).
2. Numărul claselor ce se vor forma respectând criteriile.

Despre numărul natural N spunem că are proprietatea okcpp dacă oricum alegem K cifre ale sale vom găsi printre ele cel puţin P cifre distincte (oricare k cel puțin p).

Cerințe

(1) Fiind date numerele naturale K, P, A și B să se calculeze și să se afișeze numărul de numere okcpp din intervalul [A,B].
(2) Fiind date numerele naturale K, P și N să se calculeze și să se afișeze cel mai mic număr okcpp care este mai mare sau egal cu N.