Lista de probleme 2

Ira iubește să se joace pe telefon. Atât de mult, încât părinții au luat decizia să îi blocheze telefonul pentru a se concentra la școală. Fiind fată isteață, ea a descoperit cum poate debloca telefonul de una singură.

Pe ecranul telefonului îi apar mai multe informații:

• un număr natural N
• un șir A cu N numere naturale, numerotate de la 1 la N
• un număr natural K
• un număr natural Q, apoi Q numere x, reprezentând un indice din șirul dat.

Pentru a-și putea continua jocul ea trebuie sa răspundă corect la toate cele Q întrebări de tipul: Care este diferența între cel mai mare și cel mai mic element din secvență care începe la poziția x și are lungime k?

Scrieți un program care citește datele și răspunde corect la toate cele Q întrebări. Ira abia așteaptă să se joace din nou pe telefon!

Se dă o rețea de N * M calculatoare, dispuse sub forma unei matrici cu N linii și M coloane, numerotate începând cu 1, între care se pot transfera informații.

Fiecare calculator funcțional are asociat un cod, număr natural. Calculatoarele defecte sunt marcate cu -1 și nu pot participa la transferul de informație.

Transferul de informație între două calculatoare funcționale se face direct, dacă acestea sunt vecine, sau indirect, prin intermediul altor calculatoare funcționale. Două calculatoare sunt vecine dacă se află pe aceeași linie și coloane adiacente sau pe aceeași coloană și linii adiacente, adică calculatorul de la poziția (i, j) este vecin cu cel de la pozițiile: (i + 1, j), (i - 1, j), (i, j + 1) sau (i, j - 1).

Costul transferului de informație între două calculatoare vecine funcționale este 0, dacă cele două coduri diferă prin cel mult un bit în reprezentarea binară, respectiv 1, în caz contrar. Costul transferului de informație între două calculatoare care nu sunt vecine este suma costurilor transferurilor directe intermediare.

Scrieți un program care să determine costul minim necesar pentru transferul informației de la calculatorul de pe poziția (1, 1) la cel de pe poziția (N, M).