Fișierul intrare/ieșire cladiri.in, cladiri.out Sursă OJI 2013, clasa a 6-a
Autor Cristina Iordaiche Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Cladiri (clasa a 6-a)

Având mai multe cuburi la dispoziție, Crina și Rareș au hotărât să construiască clădiri prin alipirea a două sau mai multor turnuri. Turnurile au fost obținute prin așezarea cuburilor unul peste celălalt. Înălțimea unui turn este dată de numărul de cuburi din care este format. Clădirile construite au fost așezate în linie, una lângă alta formând astfel o stradă, pe care cei doi copii se vor plimba.

Pentru numerotarea clădirilor Crina și Rareș au stabilit următoarele reguli:
  • Crina pornește dintr-un capăt al străzii iar Rareș din celălalt capăt al acesteia; fiecare dintre ei traversează strada complet, trecând prin dreptul fiecărei clădiri
  • Crina lipește pe fiecare clădire, câte un bilețel pe care scrie înălțimea turnurilor din care aceasta este construită, în ordinea în care ea le vede când trece prin dreptul lor (de exemplu, pentru imaginea de mai sus, Crina va lipi pe prima clădire un bilețel pe care va scrie numărul 3112 deoarece, primul turn e format din 3 cuburi, următoarele două turnuri ale acestei clădiri sunt formate din câte un cub iar cel de-al patrulea turn e format din 2 cuburi);
  • Rareș va proceda la fel, dar începe plimbarea din celalalt capăt al străzii. În exemplul din imagine, el va lipi pe prima clădire pe care o întâlnește un bilețel pe care scrie numărul 2121.
    La finalul plimbării, Crina și Rareș își dau seama că există clădiri pe care au lipit amândoi bilețele cu numere identice.

Cerință

a) Care este înălțimea celui mai înalt turn și care este numărul clădirilor care au în construcția lor un astfel de turn;
b) Care este numărul clădirilor pe care cei doi copii au lipit bilețele cu numere identice;
c) Care este cel mai mic număr de cuburi necesar pentru a completa clădirile astfel încât, pe fiecare clădire bilețelul pe care îl va lipi Crina să conțină același număr cu cel pe care îl va lipi Rareș. Cuburile din care a fost construită inițial clădirea nu se pot muta.

Date de intrare

Din fișierul de intrare cladiri.in se va citi de pe prima linie un număr natural N, reprezentând numărul clădirilor de pe stradă iar de pe următoarele N linii, câte un număr natural cu toate cifrele nenule, reprezentând numerele scrise de Crina pe bilețele, în ordinea în care au fost lipite de ea pe clădiri.

Date de ieșire

În fișierul de ieșire cladiri.out se va scrie pe prima linie două numere naturale despărțite printr-un singur spațiu ce reprezintă, în ordine, valorile cerute la cerința a). Pe cea de-a doua linie a fișierului se va scrie un număr natural, mai mare sau egal cu zero reprezentând răspunsul la cerința b) iar pe cea de-a treia linie a fișierului se va scrie un număr natural mai mare sau egal cu zero reprezentând răspunsul la cerința c).

Restricții

  • 1 ≤ N ≤ 10000
  • Fiecare clădire este alcătuită din cel mult 9 turnuri, iar înălțimea fiecărui turn este exprimată printr-o cifră nenulă.
  • Pentru rezolvarea corectă a cerinței a) se acordă 20% din punctajul fiecărui test, pentru rezolvarea corectă a cerinței b) se acordă 40% din punctajul fiecărui test iar pentru rezolvarea corectă a cerinței c) se acordă 40% din punctajul fiecărui test.
  • Respectați formatul fișierului de ieșire! Pentru a obține punctajul acordat unei cerințe, trebuie ca răspunsul din fișier să fie corect și scris exact pe linia precizată în enunț.

Exemplu

cladiri.in cladiri.out Explicații
6
3112
2772
42422
1741
27372
1212
7 3
2
8
Cel mai înalt turn este format din 7 cuburi. Sunt 3 clădiri care au în construcția lor
turnuri cu această înălțime, cele pe care Crina lipește numerele: 2772, 1741 și 27372.
Rareș lipește pe clădiri bilețele cu numerele: 2121, 27372, 1471, 22424, 2772 și 2113.
Două dintre aceste clădiri au primit aceleași numere și de la Crina: 2772 și 27372.
Valoarea determinată conform cerinței c) este 8. Se adaugă un cub la clădirea cu numărul
3112, 2 cuburi la cea cu numărul 42422, 3 cuburi la clădirea cu numărul 1741 și 2 cuburi
la cea cu numărul 1212.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii