| Fişierul intrare/ieşire: | bibel.in, bibel.out | Sursă | Stelele Informaticii 2007, clasele 9-10 |
| Autor | Alexandru Mosoi | Adăugată de |  Andrei Grigorean •wefgef |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bibel
Se aproprie ziua Mirunei si Bibel, prietenul ei, vrea sa-i faca cadou un set de bile pentru ca Miruna sa nu mai imprumute bilutele fratelui ei. Fiindca Bibel are in buzunar o singura moneda de 50 bani, el sa gandeste sa o joace la cazinou.
Jocul preferat a lui Bibel e destul de simplu. El este compus din mai multe nivele de joc, iar la fiecare nivel Bibel trebuie sa colectioneze cateva bile aflate pe masa utilizand un carlig. La inceputul fiecarui nivel pe masa sunt puse noi bile. Un nivel se termina cand toate bilele de pe masa au fost colectate. Ceea ce poate Bibel sa faca este sa mute carligul in linie dreapta din pozitia lui curenta deasupra unei bile si sa ia bila de pe masa. Initial carligul se afla in origine, (0, 0).
Timpul necesar colectionarii unei bile este neglijabil. Timpul necesar miscarii carligului este egal cu patratul distantei intre punctul initial si final (modificand unitatea de masura corespunzator). Deoarece castigul final depinde de cat de repede reuseste Bibel sa termine jocul, Bibel vrea ca la sfarsitul fiecarui nivel sa stie care ar fi fost timpul total minim daca nivelul respectiv ar fi fost ultimul si el ar fi jucat optim (vezi exemplu).
Ajutati-o pe Miruna sa-si primeasca cadoul.
Date de intrare
Fisierul de intrare bibel.in contine o descriere a unui joc. Fiecare nivel este descris prin mai multe linii. Pe ultima linie din descrierea unui nivel se afla un singur numar, 1, iar celelate linii descriu coordonatele a cate o bila ce va fi pusa pe masa la inceputul nivelului. Formatul este 0 x y unde (x, y) reprezinta coordonatele in plan a unei bile. Ultima linie din fisier contine un singur numar 2 si marcheaza sfarsitul unui joc.
Date de iesire
In fisierul de iesire bibel.out pentru fiecare se va afisa un numar avand semnificatia din cerinta.
Restrictii
- Coordonatele bilelor sunt numere intregi
- 0 ≤ x, y ≤ 10000
- Numarul maxim de bile amplasate pe masa la inceputul unui nivel este ≤ 17
- Numarul total de linii din fisierul de intrare este ≤ 200
- Nu conteaza ordinea in care sunt ridicate bilele de pe masa, dar la sfarsitul fiecarui nivel masa trebuie sa fie goala.
Exemplu
| bibel.in | bibel.out |
|---|---|
| 0 0 2 0 2 0 0 2 2 1 0 4 4 0 6 6 0 8 8 1 2 | 12 40 |
Explicatie
Cea mai buna varianta ca sa termine primul nivel ar fi sa ridice de pe masa in ordine bilele de la pozitiile (0, 2), (2, 2), (2, 0).
Cea mai buna varianta ca sa termine al doilea nivel in timp minim ar fi sa ridice de pe masa in ordine bilele de la pozitiile (0, 2), (2, 0), (2, 2), (sfarsitul primului nivel) (4, 4), (6, 6), (8, 8) (sfarsitul celui de-al doilea nivel si al jocului).
