Lista de probleme 6

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. Împărțirea frățească se realizează astfel:

  • numărul de colegi care primesc bomboane din fiecare cutie este același (dacă din prima cutie primesc bomboane k colegi și din cutia 2 vor primi tot k colegi, și din cutia 3 tot k colegi etc).
  • bomboanele din fiecare cutie se împart în mod egal între cei k colegi, aceștia primind un număr nenul de bomboane;
  • în final în fiecare cutie trebuie să rămână un număr identic de bomboane (posibil zero) care îi revin lui Zeno. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, din prima cutie oferă câte 4 bomboane pentru 3 colegi, din a doua cutie câte 7 bomboane pentru 3 colegi, iar din ultima cutie câte 5 bomboane pentru 3 colegi, iar în fiecare cutie rămân 2 bomboane.

Împărțirea diferențiată se realizează în felul următor:

  • dintre colegii care primesc bomboane din aceeași cutie fiecare coleg primește un număr diferit de bomboane (număr nenul), neexistând doi colegi care primesc număr identic de bomboane din aceeași cutie;
  • din fiecare cutie Zeno oferă bomboane unui număr cât mai mare de colegi.
  • diferențele în modul dintre numărul de bomboane primite consecutiv de doi colegi sunt distincte două câte două. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, bomboanele din prima cutie se pot împărți astfel (3, 4, 6, 1), bomboanele din a doua cutie (6, 2, 7, 1, 3, 4), iar bomboanele din a treia cutie se pot împărți astfel (2, 1, 3, 7, 4).

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ă.

#2156 Adlic

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.

În regiunea Ionia a lumii grecești antice, regiune ce corespunde teritoriului actual al Mării Egee, există mai multe insule. Harta mării este reprezentată de o matrice de dimensiuni N•M, având valori de 1 și 0, iar fiecare element din matrice reprezintă o zonă de dimensiune 1•1 din mare. Liniile matricei sunt numerotate de la 1 la N, de sus în jos, iar coloanele de la 1 la M, de la stânga la dreapta. Astfel, colțul din stânga sus al matricei este asociat zonei (1,1), iar colțul din dreapta jos corespunde zonei (N,M).

Un element care conține valoarea 0 reprezintă faptul că în acea zonă se află apă. O insulă este determinată
de un dreptunghi format în totalitate din valori de 1. Se garantează faptul că toate zonele care conțin valoarea 1
formează dreptunghiuri valide și că oricare două insule sunt separate de apă.

Ionienii, fiind oameni practici, doresc construirea unui far-bibliotecă (așezat pe o platformă 1•1), într-o zonă acoperită de apă. Poziția platformei va fi aleasă într-o celulă C astfel încât suma distanțelor dintre toate insulele și C să fie minimă. Distanța dintre o celulă C și o insulă este definită ca fiind minimul dintre distanțele Manhattan dintre C și fiecare celulă care aparține insulei (distanța poate trece atât prin alte insule, cât și prin zone acoperite de apă). Distanța Manhattan dintre două celule aflate pe linia x1 și coloana y1, respectiv pe linia x2 și coloana y2, este definită ca |x1 – x2| + |y1 – y2|, unde |x| reprezintă valoarea absolută a lui x.

#2153 Mirror

Numim „oglinda” numărului natural nenul a, numărul b, obţinut prin modificarea fiecărei cifre din reprezentarea sa binară, de exemplu pentru a=22(10)=10110(2) se obţine 01001(2)= 9(10)=b.

Cunoscându-se numerele naturale N, K și cele N numere natural nenule, scrieți un program care:

  1. Transformă în baza doi termenii şirului dat obţinându-se un nou şir format din alipirea cifrelor binare. Din acest şir se vor determina și afișa, separate prin câte un spațiu, toate reprezentările în baza 10 corespunzătoare secvenţelor alăturate de exact K cifre binare, parcurse de la stânga la drepta. Dacă ultima secvenţă nu are exact K cifre binare, atunci aceasta nu se va mai lua în considerare.
  2. Să aplice K transformări asupra şirului iniţial, înlocuind la fiecare pas orice termen cu „oglinda” sa. Asupra termenilor care devin zero nu se vor mai efectua alte operații. După efectuarea celor K transformări, să se determine cea mai lungă secvență de numere care au cifra 1 pe aceeași poziție în reprezentarea lor în baza doi. Dacă sunt mai multe astfel de secvențe având lungimea maximă, se va afișa cea mai din stânga.

#2154 okcpp

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.

#2158 Orase2

Î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.

ONI 2017, Clasa a IX-a