Soluții trimise

Rezumat problemă

#2540 optiuni

Michael își petrece vacanța de vară la bunici, în Delta Dunării. În prima zi, se duce la pescuit cu tatăl său în locul în care acesta se ducea în copilărie. Michael își dă seama că traseul ales nu este singura opțiune de a parcurge distanța de la casa bunicilor până la locul unde pescuiesc, așa că, odată ce vizitează întreaga regiune împreună cu bunicul său, se întreabă în câte moduri distincte poate parcurge distanța de la casa bunicilor la locul unde pescuiesc. Regiunea pe care Michael o cunoaște are formă dreptunghiulară, cu rânduri numerotate de la 1 la L și coloane numerotate de la 1 la C. Valorile de 1 reprezintă zone de uscat și valorile de 0 reprezintă zone acoperite de apă. Michael poate merge doar pe uscat, cu următoarea restricție: din zona de coordonate (i, j) se poate duce doar în una din zonele (i – 1, j + 1), (i, j + 1), (i + 1, j + 1) – bineînțeles, doar dacă acestea reprezintă zone de uscat și Michael nu părăsește regiunea. Fiind un băiat inteligent, când Michael vizitează împrejurimile cu bunicul său, își dă seama de următorul lucru: coloanele din matricea care codifică regiunea se repetă identic din K în K. Coloanele 2, K + 2, 2 * K + 2, … sunt identice, coloanele K – 1, K + (K - 1), 2 * K + (K - 1), … sunt identice. Două coloane c1 și c2 sunt identice dacă elementul de pe poziția (i, c1) este egal cu elementul de pe poziția (i, c2), oricare ar fi i de la 1 la L. Știind coordonatele locului unde se află casa bunicilor și coordonatele locului de pescuit pe care tatăl lui Michael i l-a arătat acestuia, să se determine numărul de moduri de a parcurge distanța dintre ele. Două drumuri sunt considerate distincte dacă, scriind secvența rândurilor vizitate (în ordine crescătoare a coloanelor), ele diferă prin cel puțin o poziție.

Olimpiada internațională pe Echipe, 2018

ID   Utilizator Problema Data încărcării Stare
this is (the_end) optiuni 10 Septembrie 2019, 17:53 Evaluare finalizată 100
Camilla Camilla (camilla) optiuni 21 August 2019, 23:16 Evaluare finalizată 100
Arama Alexandru (Alexandru_Arama) optiuni 26 Iulie 2019, 20:11 Evaluare finalizată 100
Arama Alexandru (Alexandru_Arama) optiuni 26 Iulie 2019, 20:07 Evaluare finalizată 75
Arama Alexandru (Alexandru_Arama) optiuni 26 Iulie 2019, 19:47 Evaluare finalizată 5
Mesota Ioan (MESOTRIST_2) optiuni 06 Iulie 2019, 13:58 Evaluare finalizată 100
Mesota Ioan (MESOTRIST_1) optiuni 04 Iulie 2019, 21:25 Evaluare finalizată 100
Marziali Mattia (masecla22) optiuni 14 Aprilie 2019, 19:55 Evaluare finalizată 100
Hutanu Horia (Hutanu_Horia) optiuni 08 Aprilie 2019, 13:22 Evaluare finalizată E.C
Popescu Adelin (adelin117) optiuni 12 Martie 2019, 14:05 Evaluare finalizată 0
Popescu Adelin (adelin117) optiuni 12 Martie 2019, 14:05 Evaluare finalizată 0
Baltoi Teodor (teodor_baltoi) optiuni 25 Februarie 2019, 10:59 Evaluare finalizată 0
Baltoi Teodor (teodor_baltoi) optiuni 25 Februarie 2019, 10:40 Evaluare finalizată 0
Baciu Dani (danibaciu78) optiuni 25 Februarie 2019, 10:31 Evaluare finalizată 0
Baciu Dani (danibaciu78) optiuni 25 Februarie 2019, 10:30 Evaluare finalizată 0
Baltoi Teodor (teodor_baltoi) optiuni 25 Februarie 2019, 10:27 Evaluare finalizată 0
Baciu Dani (danibaciu78) optiuni 25 Februarie 2019, 10:26 Evaluare finalizată 0
Dragan Andrei (dandre1) optiuni 18 Februarie 2019, 15:18 Evaluare finalizată 0
Negreanu-Maior Andrei Gabriel (lanteamgabi) optiuni 18 Februarie 2019, 09:40 Evaluare finalizată 100
Adrian Negreanu-Maior (lanteamadrian) optiuni 18 Februarie 2019, 09:39 Evaluare finalizată 100
Negreanu-Maior Lucia (lanteamlucia) optiuni 18 Februarie 2019, 09:39 Evaluare finalizată 100
illuminatty is looking at everyone (fer_haur_99) optiuni 29 Ianuarie 2019, 15:42 Evaluare finalizată E.C
Andrei Visalon (Prekzursil) optiuni 20 Decembrie 2018, 02:31 Evaluare finalizată 100
Andrei Visalon (Prekzursil) optiuni 20 Decembrie 2018, 02:31 Evaluare finalizată 100
Andrei Visalon (Prekzursil) optiuni 20 Decembrie 2018, 02:30 Evaluare finalizată 95
Andrei Visalon (Prekzursil) optiuni 20 Decembrie 2018, 02:29 Evaluare finalizată 95
Andrei Visalon (Prekzursil) optiuni 20 Decembrie 2018, 02:27 Evaluare finalizată 0
Andrei Visalon (Prekzursil) optiuni 20 Decembrie 2018, 01:21 Evaluare finalizată E.C
Ciobotaru Andrei (CiobotaruAndrei2005) optiuni 19 Decembrie 2018, 09:26 Evaluare finalizată 0
Ene Dumitru (ed) optiuni 06 Decembrie 2018, 19:45 Evaluare finalizată E.C
Jurcut Paul (Jurcut_Paul) optiuni 21 Noiembrie 2018, 11:59 Evaluare finalizată 30
Sabau Florin (FlorinSabau) optiuni 20 Noiembrie 2018, 17:10 Evaluare finalizată 30
Sabau Florin (FlorinSabau) optiuni 20 Noiembrie 2018, 16:58 Evaluare finalizată 30
Sabau Florin (FlorinSabau) optiuni 20 Noiembrie 2018, 16:08 Evaluare finalizată 0
Stefan Marc (Hunt3r) optiuni 24 Octombrie 2018, 09:16 Evaluare finalizată 0
jef jef2 (jef) optiuni 21 Octombrie 2018, 16:22 Evaluare finalizată E.C
Tonitza Nicolae (Nicolae_Tonitza) optiuni 22 Septembrie 2018, 10:40 Evaluare finalizată 0
Coman Andrei (andreicoman299) optiuni 18 Septembrie 2018, 18:15 Evaluare finalizată 100
Popovici Robert (PopoviciRobert) optiuni 14 Septembrie 2018, 12:11 Evaluare finalizată 100
Borcani Robert (borcanirobert) optiuni 23 August 2018, 11:37 Evaluare finalizată 100
Borcani Robert (borcanirobert) optiuni 23 August 2018, 11:36 Evaluare finalizată 0
Borcani Robert (borcanirobert) optiuni 22 August 2018, 12:48 Evaluare finalizată 20
Raluca Sylvie (ralucasylvie) optiuni 03 August 2018, 12:19 Evaluare finalizată 100
✔️ Popa Adrian (a53) optiuni 26 Iulie 2018, 06:07 Evaluare finalizată 100
Sabau Florin (FlorinSabau) optiuni 15 Iulie 2018, 10:22 Evaluare finalizată 25
Sabau Florin (FlorinSabau) optiuni 15 Iulie 2018, 10:08 Evaluare finalizată 0
Dobrin Bashev (dobito6) optiuni 08 Iulie 2018, 15:37 Evaluare finalizată 100
Dobrin Bashev (dobito6) optiuni 24 Iunie 2018, 23:11 Evaluare finalizată 100
Dobrin Bashev (dobito6) optiuni 24 Iunie 2018, 23:09 Evaluare finalizată 15
ANDRU-PAD ADRIANA ANDRADA (andrada_pad) optiuni 22 Iunie 2018, 13:30 Evaluare finalizată 100