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
best in buzau (BestInBuzau) optiuni 28 Septembrie 2024, 22:41 Evaluare finalizată 100
best in buzau (BestInBuzau) optiuni 27 Septembrie 2024, 12:33 Evaluare finalizată 100
Prof C.N. "Spiru Haret" (flaviusboian) optiuni 11 Septembrie 2024, 23:37 Evaluare finalizată 100
rares dumitrascu (zinca_5a_rares) optiuni 20 August 2024, 13:43 Evaluare finalizată 100
Burcă Luiza (louisyy) optiuni 08 Iunie 2024, 11:02 Evaluare finalizată 100
Stefan Dascalescu (stefdasca.ro) (stefdasca) optiuni 04 Iunie 2024, 17:45 Evaluare finalizată 100
Raileanu Alexandru (AlexandruR2008) optiuni 06 Aprilie 2024, 21:34 Evaluare finalizată 100
Macoveiciuc Sabrina Giulia (Sabrina10) optiuni 08 Februarie 2024, 21:11 Evaluare finalizată 100
Macoveiciuc Sabrina Giulia (Sabrina10) optiuni 08 Februarie 2024, 20:39 Evaluare finalizată 0
Anca Leuciuc (AncaLeuciuc) optiuni 10 Decembrie 2023, 19:47 Evaluare finalizată 100
Dracea Andora (Andora_fan) optiuni 08 August 2023, 16:33 Evaluare finalizată 100
Adrian Statescu (thinkphp) optiuni 03 Iulie 2023, 21:46 Evaluare finalizată 100
Panaete Adrian (proflaurian) optiuni 23 Mai 2023, 14:37 Evaluare finalizată 100
Panaete Adrian (proflaurian) optiuni 23 Mai 2023, 09:06 Evaluare finalizată 40
Panaete Adrian (proflaurian) optiuni 16 Mai 2023, 17:03 Evaluare finalizată 5
Panaete Adrian (proflaurian) optiuni 16 Mai 2023, 16:55 Evaluare finalizată 0
Tdr Tdr (Bossubosilorsefulbanilor) optiuni 06 Mai 2023, 22:30 Evaluare finalizată 100
Ungureanu Maia (maiaau) optiuni 01 Mai 2023, 17:26 Evaluare finalizată 20
Ungureanu Maia (maiaau) optiuni 01 Mai 2023, 17:25 Evaluare finalizată E.C
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:39 Evaluare finalizată 100
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:37 Evaluare finalizată 95
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:36 Evaluare finalizată 95
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:35 Evaluare finalizată 90
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:34 Evaluare finalizată 90
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:34 Evaluare finalizată 95
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:31 Evaluare finalizată 95
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:30 Evaluare finalizată 80
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:29 Evaluare finalizată 85
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:27 Evaluare finalizată 95
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:27 Evaluare finalizată 95
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:22 Evaluare finalizată 90
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:11 Evaluare finalizată 90
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:08 Evaluare finalizată 20
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 21 Aprilie 2023, 18:08 Evaluare finalizată 20
Sabo Alex (AlexSabo) optiuni 23 Martie 2023, 12:51 Evaluare finalizată 100
Sabo Alex (AlexSabo) optiuni 23 Martie 2023, 12:51 Evaluare finalizată 0
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 16 Martie 2023, 15:36 Evaluare finalizată 30
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 16 Martie 2023, 15:34 Evaluare finalizată 0
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 16 Martie 2023, 15:33 Evaluare finalizată 0
Moldovan Robert (use KN) (moldovan_robert_lol) optiuni 16 Martie 2023, 15:32 Evaluare finalizată 0
Benchea Matei (matei__b) optiuni 14 Martie 2023, 15:50 Evaluare finalizată 5
Gura Vlad (Vlad_G28) optiuni 01 Februarie 2023, 22:26 Evaluare finalizată 100
meditatii-informatica.com | Gabriel (arcker) optiuni 04 Ianuarie 2023, 23:10 Evaluare finalizată 100
Toncea Andrei (andrei170) optiuni 28 Decembrie 2022, 14:59 Evaluare finalizată 100
Ionescu Matei (matwu) optiuni 12 Noiembrie 2022, 10:32 Evaluare finalizată 0
Ionescu Matei (matwu) optiuni 12 Noiembrie 2022, 09:59 Evaluare finalizată 30
Ionescu Matei (matwu) optiuni 12 Noiembrie 2022, 09:59 Evaluare finalizată 15
Ionescu Matei (matwu) optiuni 12 Noiembrie 2022, 09:54 Evaluare finalizată 0
Frant Ioana (Frant_Ioana) optiuni 12 Noiembrie 2022, 09:42 Evaluare finalizată 20
Marcu Mihai (marcumihai) optiuni 09 Noiembrie 2022, 09:40 Evaluare finalizată 20