Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbore2.in, arbore2.out | Sursă | Stelele Informaticii 2003, clasele 11-12 |
| Autor | Mihai Stroe | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbore2
Am doi copaci, reprezentati prin doi arbori binari cu M, respectiv N noduri. In fiecare nod al unui astfel de arbore cresc flori (cel putin 0, cel mult 10). Ordinea fiilor conteaza (se face distinctie intre fiul stang si fiul drept).
Doi arbori binari cu flori in noduri sunt similari daca (definitie recursiva):
- au ambii 0 noduri
sau - au ambii cel putin un nod, acelasi numar de flori in radacina, subarborii stangi sunt similari si subarborii drepti sunt similari.
Vreau sa transform cei doi arbori dati in 2 arbori similari (conform definitiei de mai sus) cu exact K flori fiecare, avand aceleasi radacini cu arborii initiali. Pentru a-mi atinge scopul pot sa fac 2 tipuri de operatii:
- tai o craca (elimin un subarbore dintr-unul din cei doi arbori)
- rup o floare (scad cu 1 numarul de flori din unul din nodurile unuia din arbori)
Deoarece vreau sa muncesc cat mai putin pentru a-mi atinge scopul, doresc sa tai cat mai putine craci si, daca am mai multe variante de a taia cat mai putine craci,, sa aleg una in care sa rup cat mai putine flori.
Date de intrare
...
Date de iesire
...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| arbore2.in | arbore2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
