Oli are un echer de forma unui triunghi dreptunghic, cu catetele de lungimi L1 şi L2 unităţi, şi o foaie de caiet de matematică cu M rânduri şi N coloane de pătrăţele având latura de o unitate.
Oli a poziţionat echerul în colţul din stânga sus al foii de hârtie, ca în imaginea precedentă şi vrea să îl mute astfel încât să atingă colţul din dreapta jos al foii de hârtie cu oricare din colţurile echerului, utilizând doar mutări de forma:
Cerinţă
Scrieţi un program care citeşte lungimile catetelor echerului, numărul de rânduri, respectiv numărul de coloane ale foii de hârtie şi determină:
1. numărul minim de mutări K, prin care poate muta echerul din colţul din stânga sus al foii de matematică, astfel încât echerul să atingă colţul din dreapta jos al foii;
2. cele K mutări efectuate pentru a deplasa echerul din colţul din stânga sus al foii, până când un colţ al echerului atinge colţul din dreapta jos al foii; dacă există mai multe soluţii, se va afişa soluţia minimă în sens lexicografic. Un şir de mutări X=(X1, X2, …, XK) este mai mic în sens lexicografic decât alt şir de mutări Y=(Y1, Y2, …, YK) dacă există P (1 ≤ P ≤ K) a.î. XI = YI, I din {1, 2, …, P-1} şi XP < YP.
De exemplu şirul de mutări 1 2 3 1 este mai mic în sens lexicografic decât şirul de mutări 1 2 4 1.
Date de intrare
Fişierul de intrare echer.in conţine pe prima linie una dintre valorile 1 sau 2, reprezentând cerinţa 1 dacă se cere determinarea numărului minim de mutări prin care poate muta echerul din colţul din stânga sus al foii de matematică astfel încât să atingă colţul din dreapta jos al foii, respectiv cerinţa 2, dacă se cere determinarea mutărilor efectuate pentru a deplasa echerul din colţul din stânga sus al foii până când un colţ al echerului atinge colţul din dreapta jos al foii.
A doua linie a fişierului conţine patru numere naturale, separate prin câte un spaţiu, reprezentând valorile L1, L2, M şi N, în această ordine.
Date de ieşire
Fişierul de ieşire echer.out va conţine pe prima linie un număr natural K reprezentând numărul minim de mutări dacă cerinţa a fost 1, respectiv K numere naturale separate prin câte un spaţiu reprezentând mutările efectuate pentru a deplasa echerul din colţul din stânga sus al foii de matematică până când un colţ al echerului atinge colţul din dreapta jos al foii, dacă cerinţa a fost 2.
Restricţii
• 1 ≤ L1, L2 ≤ 1000
• 1 ≤ M, N ≤ 1000000
• Se garantează că există soluţie pentru orice set de date de intrare.
• Pentru rezolvarea corectă a cerinţei 1 se obţine 30% din punctaj.
• Pentru rezolvarea corectă a cerinţei 2 se obţine 70% din punctaj.
Exemple
echer.in
echer.out
Explicaţii
1
2 3 8 9
8
Sunt necesare 8 mutări, ca în imaginea alăturată.
2
2 3 8 9
1 2 3 1 2 3 1 4
Mutările sunt cele ilustrate în imaginea de mai sus.
