Fișierul intrare/ieșire lumina.in, lumina.out Sursă ad-hoc
Autor Vlad Sănduleac Adăugată de avatar StelarCF Sanduleac Vlad StelarCF
Timp de execuție pe test 1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Lumina

Casian se strecoara intr-o baza extraterestra pentru a distruge controalele navei mama care ameninta planeta PACO. Baza este un dreptunghi de n*m patrate care au asociata o valoare li,j reprezintand nivelul de lumina. Datorita abilitatilor lui Casian, extraterestrii nu il pot vedea imediat decat daca el se afla intr-un patrat de lumina minim k sau daca suma ultimelor x casute este minim (x*k)/2. (Daca aceasta valoare este reala se ia numai partea intreaga)

Cerinta

Sa se afle lungimea minima L pe care trebuie sa o strabata Casian pentru a ajunge la controale si riscul minim r, unde riscul este suma tuturor nivelelor de lumina asociate patratelor prin care trece Casian

Date de intrare

Pe prima linie a fisierului de intrare lumina.in se afla n si m. Pe a doua linie se vor afla numerele x si k. Pe a treia linie se vor afla 4 numere reprezentand locul de unde porneste Casian si locul unde trebuie sa ajunga. Pe urmatoarele n linii se vor afla cate m numere reprezentand nivelele de lumina are patratelor.

Date de ieșire

In fisierul de iesire lumina.out se vor afisa numerele L si r, conform enuntului.

Restricții

  • 2 ≤ n, m ≤ 100
  • 3 ≤ x ≤ 10
  • 0 ≤ li,j ≤ 1000
  • 2 ≤ k ≤ 10000

Se garanteaza ca pentru orice test exista solutie

Exemplu

lumina.in lumina.out
4 4
3 7
1 1 4 4
1 1 4 4
0 4 4 4
7 3 2 3
14 9 8 3
6 16

Explicație

Casian porneste din casuta (1, 1) si poate trece prin casutele (1,2), (2,2), (3,2), (3,3), (3,4) si (4,4). Lungimea este 6. Pentru risc minim el poate trece prin (2,1) in loc de (1,2)

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii