Crina și Rareș pornesc în călătoria imaginară spre Deva și pentru aceasta fiecare își construiește câte un autocar din piese de lego. Pentru a nu crea blocaje în trafic, intrarea autocarelor în oraș este gestionată de un semnal pe care este scris un număr natural S
. Astfel, fiecare autocar ce ajunge în dreptul semnalului, trebuie să aștepte, un număr de minute egal cu valoarea absolută a diferenței dintre S și numărul de identificare al autocarului său.
Cei doi copii își împart în mod egal piesele de lego pe care sunt scrise cifre (fiecare copil are același număr de piese ca și celălalt, pentru fiecare cifră în parte), cu care formează numerele de identificare ale celor două autocare. Crina aranjează una lângă alta toate piesele sale și formează cifră cu cifră, numărul N1
de identificare al autocarului ei iar Rareș procedează la fel și formează numărul N2
pentru autocarul său. Pentru ca cele două numere să nu fie identice, copiii stabilesc ca N1
să fie strict mai mic decât numărul S
al semnalului, iar numărul N2
strict mai mare decât S
. În cazul în care vreunul din cele două numere nu poate fi construit din piesele împărțite, atunci autocarul respectiv va avea identificatorul 0
și va aștepta la semnal până trece celălalt autocar.
Cerința
1. Determinați numerele N1
și N2
astfel încât, autocarul fiecărui copil să aștepte cât mai puține minute la semnal.
2. Știind că autocarele celor doi copii au ajuns în același timp în fața semnalului, determinați numărul minim de minute de așteptare ale autocarului care va trece primul de semnal.
Date de intrare
Fișierul de intrare lego.in
conține:
- pe prima linie numărul natural
C
ce poate avea valorile1
sau2
, reprezentând numărul cerinței; - pe cea de-a doua linie un singur număr natural
S
cu semnificația din enunț; - pe următoarele linii câte două numere naturale
n
i
șic
i
, despărțite prin câte un spațiu, cu următoarea semnificație:n
i
reprezintă numărul pieselor cu cifrac
i
, pe care le are fiecare copil.
Date de ieșire
Pentru C = 1
, fișierul de ieșire lego.out
va conține pe prima linie două numere naturale N1
și N2
, în această ordine, despărțite printr-un spațiu, determinate conform cerinței 1.
Pentru C = 2
, fișierul de ieșire lego.out
va conține pe prima linie, un singur număr natural determinat conform cerinței 2.
Restricții și precizări
1 ≤ S ≤ 10
18
;- fiecare copil are cel mult
19
piese; - cifrele
c
i
sunt distincte; - pentru rezolvarea corectă a cerinței 1 se acordă
60
de puncte iar pentru rezolvarea corectă a cerinței 2 se acordă40
de puncte.
Exemplul 1:
lego.in
1 153 1 7 3 4
lego.out
0 4447
Explicație
Se rezolvă doar cerința 1. Pe semnal este scris numărul 153
. Fiecare copil are 3
piese cu cifra 4
și o piesă cu cifra 7
. Crina nu poate construi cu aceste piese un număr mai mic decât 153
, de aceea autocarul său este identificat cu numărul 0
. Rareș construiește numărul N2 = 4447
.
Exemplul 2:
lego.in
2 42 1 3 1 5
lego.out
7
Explicație
Se rezolvă doar cerința 2. Pe semnal este scris numărul 42
. Fiecare copil are o cifră de 3
și o cifră de 5
. Crina construiește numărul N1 = 35
și așteaptă la semnal 42 - 35 = 7
minute. Rareș construiește numărul N2 = 53
și așteaptă la semnal 53 - 42 = 11
minute. Numărul minim al minutelor de așteptare este 7
.