FMI NO STRESS 13 | Ants in the Matrix

This was the problem page during the contest. Access the current page here.
Time limit: 2s Memory limit: 256MB Input: Output:

Cerință

Într-o zi frumoasă de vară, Vasile, elev de clasa a 12-a care urmează să dea bacul, se pregătea la informatică. El se află la bunicii săi unde nu are internet, și toată ziua a rezolvat exerciții cu matrici. A decis să ia o pauză, și-a luat foaia pe care era desenată o matrice de dimensiuni N×MN \times M care conține valori întregi, și a plecat în curte să își găsească o activitate nouă.

Afară a găsit un mușuroi de furnici și a decis să facă un mic joculeț cu FF dintre ele. El va lua pe rând, câte o furnică, și o va plasa în colțul stânga jos al matricii, fie el considerat de coordonate (0,0)( 0, 0 ). Acesta analizează traseul fiecărei furnici și notează unele puncte prin care trece aceasta. Dacă o furnică trece prin căsuța unui element din matrice, atunci valoarea din căsuța respectivă se va adăuga la scorul furnicii.

Furnicile găsite de Vasile sunt inteligente, prin urmare ele au următoarele proprietăți:

  • Fiecare furnică se va îndrepta către punctul de coordonate (M,N)( M, N );
  • Furnicile merg într-o linie dreaptă între două puncte consecutive observate de către Vasile;
  • Coordonatele punctelor au valori reale cu exact două zecimale;
  • Nu vor să piardă timp, așa că ele nu se vor îndepărta niciodată de ținta lor (sunt pe grind). Altfel spus, pentru două puncte consecutive PP și QQ, xQxP0x_Q - x_P \ge 0 și yQyP0y_Q - y_P \ge 0.

Atenție! Traseul furnicilor este descris în planul cartezian. Consultați desenul de la exemplu!

Vasile este intrigat de aceste comportamente și dorește să știe scorul pentru fiecare furnică.

Date de intrare

Pe prima linie se vor afla dimensiunile matricii, NN și MM. Pe următoarele NN linii se vor afla câte MM numere întregi viv_i, care reprezintă numerele care se află în matricea din joculețul lui Vasile. Pe următoarea linie se va afla FF, reprezentând numărul de furnici care participă în cursă. Următoarele FF linii vor conține perechi de coordonate (xi,yi)( x_i, y_i ), numere reale cu exact două zecimale, reprezentând punctele observate pentru furnica ii. Ultima coordonată pentru o furnică va fi (M,N)( M, N ).

Date de ieșire

Pe linia ii se va afișa scorul furnicii cu numărul ii.

Restricții și precizări

  • 1N,M5001 \leq N, M \leq 500;
  • 5000v5000-5000 \leq v \leq 5000;
  • 1F1051 \leq F \leq 10^5;
  • 0xiN0 \leq x_i \leq N;
  • 0yiM0 \leq y_i \leq M;
  • Vom nota cu LiL_{i} lungimea traseului furnicii ii
  • 1Li50001 \leq L_{i} \leq 5 000 pentru ii de la 11 la FF
  • Suma LiL_{i} pentru ii de la 11 la F106F \leq 10^6
  • Pentru teste în valoare de 1111 puncte, pentru două puncte consecutive PP și QQ, xQxP=0x_Q - x_P = 0 sau yQyP=0y_Q - y_P = 0 și toate punctele au coordonate întregi;
  • Pentru teste in valoare de alte 3030 de puncte, F100F \leq 100, 1N,M501 \leq N, M \leq 50;
  • Pentru teste în valoare de alte 2828 de puncte, toate punctele au coordonate întregi;
  • Pentru teste în valoare de alte 4242 de puncte, nu există restricții suplimentare;
  • Dacă o furnică merge pe marginea unei căsuțe și nu intră în interiorul ei, atunci ea nu va primi scorul respectivei căsuțe.
  • Atenție! Matricea valorilor specifice căsuțelor se citește în ordine de sus în jos (yy descrescător), de la stânga la dreapta (xx crescător). Punctele intermediare sunt date după coordonatele lor carteziene (xx, yy).

Exemplul 1

stdin

5 5
2 8 4 8 -1
9 5 3 1 4
10 0 10 6 7
11 -1 7 10 9
5 0 20 -15 8
4
3.80 1.20 4.60 3.66 5.00 5.00
1.20 1.70 2.10 3.75 5.00 5.00
0.00 4.00 3.00 4.00 3.00 5.00 5.00 5.00 
3.00 3.00 5.00 5.00

stdout

39
34
0
14

Explicație


Prima furnică va trece prin următoarele căsuțe:

  • 502015109741\red{5 \rightarrow 0 \rightarrow 20 \rightarrow -15 \rightarrow 10 \rightarrow 9 \rightarrow 7 \rightarrow 4 \rightarrow -1}
  • Scor total=39\red{\text{Scor total} = 39}

A doua furnică va trece prin următoarele căsuțe:

  • 5111053481\green{5 \rightarrow 11 \rightarrow -1 \rightarrow 0 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 8 \rightarrow -1}
  • Scor total=34\green{\text{Scor total} = 34}

A treia furnică nu intră în nici o căsuță, ci merge doar pe marginea lor. Deci, are scorul 0\purple{0}.
A patra furnică trece prin următoarele căsuțe:

  • 511011\blue{5 \rightarrow -1 \rightarrow 10 \rightarrow 1 \rightarrow -1}
  • Scor total=14\blue{\text{Scor total} = 14}

Furnica cu scorul cel mai mare este prima, cu un scor în valoare de 39\red{39}.

Exemplul 2

stdin

4 6
-7 -8 6 -3 1 10
10 -8 8 8 6 -1
-9 8 0 -10 0 -10
5 -9 -2 -7 -8 6
3
5.34 3.61 6.00 4.00
5.83 0.49 5.97 2.49 6.00 4.00
5.88 1.84 5.99 3.56 6.00 4.00

stdout

37
-16
-24

Log in or sign up to be able to send submissions!