Pouring water P16062
Tenim uns contenidors d’aigua, de certes capacitats. Tenim una disposició inicial i voldríem arribar a una altra. Per fer-ho, només podem abocar aigua d’un contenidor a un altre fins que el contenidor d’origen es buida o el contenidor de destí queda ple, és a dir, no podem decidir la quantitat d’aigua abocada. Podries trobar el mínim nombre de cops que hem d’agafar i abocar un contenidor per arribar a la disposició desitjada?
Escriviu un programa que calculi el mínim nombre possible de moviments per resoldre donada una configuració inicial dels contenidors.
Entrada
La primera línia conté un nombre n entre 3 i 5, el nombre de contenidors. La segona línia conté n nombres entre 1 i 50, les capacitats de cada contenidor. La tercera línia conté n nombres, la quantitat d’aigua inicialment a cada contenidor. La quarta línia conté n nombres, la quantitat d’aigua final desitjada a cada contenidor. Un -1 indica que no importa com quedi aquest contenidor.
Sortida
La sortida és el nombre mínim de moviments per obtenir la configuració desitjada.
Input
3 10 7 4 0 7 4 -1 -1 2
Output
6
Input
3 8 5 3 8 0 0 4 4 0
Output
7
Input
3 8 5 3 8 0 0 4 3 1
Output
-1
Input
5 50 50 12 8 2 50 50 0 0 0 -1 31 -1 -1 -1
Output
-1
Input
5 50 50 50 50 1 50 0 0 0 0 -1 25 -1 -1 -1
Output
50
- Author
- Izan Beltran
- Language
- Catalan
- Official solutions
- Python
- User solutions
- Python