3087 - Lego

Enunt

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 valorile 1 sau 2, 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 ni și ci, despărțite prin câte un spațiu, cu următoarea semnificație: ni reprezintă numărul pieselor cu cifra ci, 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 ≤ 1018;
• fiecare copil are cel mult 19 piese;
• cifrele ci 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.

Rezolvare

<syntaxhighlight lang="python" line> def build_number(pieces):

   number = 0
   for i, piece in enumerate(pieces):
       number += piece * 10 ** i
   return number

def main():

   with open("lego.in", "r") as fin:
       c = int(fin.readline())
       s = int(fin.readline())
       pieces = [list(map(int, fin.readline().split())) for _ in range(2)]

   if c == 1:
       n1_pieces = [min(pieces[0][i], s) for i in range(10)]
       n2_pieces = [min(pieces[1][i], s) for i in range(10)]

       n1 = build_number(n1_pieces)
       n2 = build_number(n2_pieces)

       print(n1, n2)

   elif c == 2:
       min_wait = float('inf')
       for i in range(1, s):
           n1_pieces = [min(pieces[0][j], i) for j in range(10)]
           n2_pieces = [min(pieces[1][j], s - i) for j in range(10)]
           n1 = build_number(n1_pieces)
           n2 = build_number(n2_pieces)
           wait = abs(s - n1) + abs(s - n2)
           min_wait = min(min_wait, wait)

       print(min_wait)

if __name__ == "__main__":

   main()

</syntaxhighlight>