OLI 2024, Brașov, clasa a XI-a · Clasa a XI-aProgramare dinamicăProbleme de numărare folosind programarea dinamică

Problema Avalansa

Organizația Internațională de Meteorologie monitorizează constant avalanșele ce se formează la nivel internațional. Pentru a fi mai ușor de urmărit, aceștia au reprezentat harta lumii sub forma unei matrice de N linii și M coloane, fiecare element reprezentând numărul de avalanșe pornite din acel punct în ultima perioadă de timp. De asemenea, ei au identificat trasee uzuale pe care avalanșele le urmează și, așadar, drumuri periculoase pentru turiști. Definesc astfel trasee sigure, formate din porțiuni definite de capetele lor a căror lungime este determinata de distanța euclidiană dintre coordonatele capetelor.

Cerință

Știind harta reprezentată și traseele uzuale ale avalanșelor, aceștia au nevoie de ajutor pentru a răspunde la două întrebări esențiale pentru oprirea formării avalanșelor:

1. Câte avalanșe s-au format în ultima perioadă de timp într-o zonă anume
2. Distanța minimă pe care un turist o are de parcurs, având în vedere că el va urmări cu strictețe drumurile sigure.

Date de intrare

Fișierul de intrare avalansa.in conține pe prima linie un singur număr natural C, care reprezintă cerința de rezolvat. A doua linie a fișierului conține două numere naturale separate printr-un spațiu N și M, care reprezintă dimensiunile matricei în care a fost împărțită harta. Următoarele N linii conțin câte M numere naturale separate prin câte un spațiu ce reprezintă elementele matricei formate de organizație. Următoarea linie conține un singur număr natural T, ce reprezintă numărul de porțiuni de trasee definite de cercetători între două puncte de pe hartă. Următoarele T linii conțin câte patru numere naturale, primele două reprezentând coordonatele unui capăt al unui traseu identificat, iar celelalte două reprezentând coordonatele celuilalt capăt al traseului (în format linie-coloană). Următoarea linie conține un singur număr natural Q, ce reprezintă numărul de interogări care se realizează. Următoarele Q linii conțin câte o interogare, fiecare fiind formată din două perechi de coordonate x y din matrice.

Date de ieșire

Fișierul de ieșire avalansa.out va conține Q linii astfel:

1. Dacă C = 1, atunci se va rezolva doar punctul 1 din cerință: Pentru fiecare interogare se va afișa pe o linie separată numărul total de avalanșe care s-au format în ultima perioadă în zona dreptunghiulară determinată de cele două perechi de coordonate din fișierul de intrare.
2. Dacă C = 2, atunci se va rezolva doar punctul 2 din cerință: Pentru fiecare interogare se va afișa pe o linie separată distanța minimă pe care o poate parcurge un turist între cele două puncte date în fișierul de intrare, folosind doar traseele determinate de cercetători. Lungimea unui traseu este formată din suma lungimilor porțiunilor de traseu pe care le conține.

Restricții și precizări

• C = 1 sau C = 2
• 1 ≤ N, M ≤ 1000
• 1 ≤ T, Q ≤ 1.000.000
• Coordonatele date sunt numere naturale între 1 și N, respectiv M
• Traseele definite sunt bidirecționale
• Pot exista două trasee uzuale identice. Considerăm că există un drum de la un punct la el însuși, cu lungimea 0
• Dacă nu există un drum între punctele cerute de la cerința 2, drept lungime minimă se va afișa -1
• Răspunsurile cu zecimale se afișează cu exact 4 zecimale, fără rotunjire

Exemple

1
4 6
2 0 1 0 2 4
2 5 6 2 0 0
1 2 3 0 0 3
0 0 1 8 9 0
0
2
1 1 4 4 
4 5 2 4

33
19

2
4 6
2 0 1 0 2 4
2 5 6 2 0 0
1 2 3 0 0 3
0 0 1 8 9 0
5
1 1 1 2
1 2 2 2
2 2 4 4
1 2 4 4
4 1 2 2
4
1 1 4 4
1 1 1 2
2 2 4 4
4 1 1 2

4.6055
1.0000
2.8284
3.2360

Explicația exemplelor

Pentru primul exemplu. Se cere numărul de avalanșe pornite din zonele încercuite mai jos:



Prin urmare, pentru prima zonă avem 2 + 1 + 2 + 5 + 6 + … + 1 + 8 = 33, iar pentru a doua 2 + 8 + 9 = 19.

Pentru al doilea exemplu. Traseele definite sunt următoare:



Unde traseele cele mai scurte sunt următoarele: traseu(1, 1, 4, 4) = traseu(1, 1, 1, 2) + traseu(1, 2, 4, 4) = sqrt(02 + 12) + sqrt(32 + 22) = 1 + 3.6055 = 4.6055; traseu(1, 1, 1, 2) = 1; traseu(4, 1, 1, 2) = traseu(4, 1, 2, 2) + traseu(2, 2, 1, 2) = sqrt(22 + 12) + sqrt(12 + 02) = 2.236 + 1 = 3.2360.

Problemă adăugată pe InfoAs de  Olimpiade și concursuri