Fişierul intrare/ieşire:echer.in, echer.outSursăONI 2015 clasa a 6-a
AutorFlorentina UngureanuAdăugată detgm000Tudor Mocioi tgm000
Timp execuţie pe test0.2 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Echer(clasa a 6-a)

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:

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, oricare ar fi 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.

Exemplu

echer.inecher.out
1
2 3 8 9
8
2
2 3 8 9
1 2 3 1 2 3 1 4

Explicaţie

Sunt necesare 8 mutări, ca în imaginea alăturată.

Trebuie sa te autentifici pentru a trimite solutii. Click aici