Fişierul intrare/ieşire:tv.in, tv.outSursăAlgoritmiada 2016 - Runda 2, Seniori
AutorAdrian Budau, Eugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tembelizor

Bill are un tembelizor. Bill nu are nevoie sa se dea mare fata de prietenii lui. Asta pentru ca Bill este sarac si nu a avut bani sa cumpere unul mai bun. Fii ca Bill.

Fie C numarul de culori distincte din universul lui Bill. Consideram 1 ca fiind alb si C ca fiind negru. Un tembelizor este un televizor alb-negru (percepe initial doar culorile 1 si C). Pentru fiecare culoare i de la 2 la C - 1, se cunoaste costul costi necesar pentru a upgrada tembelizorul astfel incat acesta sa perceapa si culoarea i.
Bill tocmai a aflat ca o poza cu el o sa apara la stiri. O imagine poate fii interpretata ca o matrice de N * M, valoarea din casuta de pe linia i coloana j reprezentand culoarea pixelului aflat la aceea pozitie. In momentul in care o imagine apare la tembelizor, dispozitivul afiseaza fiecare pixel conform urmatoarelor reguli:

  • Daca avem un pixel de culoare V si tembelizorul percepe aceasta culoare, culoarea afisata pe ecran in acea pozitie este tot V
  • Daca avem un pixel de culoare V, dar tembelizorul nu percepe aceasta culoare, in locul culorii V va fi afisata cea mai apropiata culoare de V (altfel spus culoarea aflata la distanta minima) perceputa de tembelizor. Distanta intre doua culori X si Y este valoarea absoluta a diferentei dintre cele doua culori: |X - Y|. In cazul in care exista mai multe culori aflate la distanta minima, se va alege culoarea cu indice maxim. Observam ca deoarece tembelizorul este initial alb-negru, in cel mai rau caz fiecare culoare va fi reprezentata fie de 1 (alb) fie de C (negru).

Scopul lui Bill este sa plateasca o suma minima de bani pentru a isi upgrada tembelizorul, astfel incat imaginea lui la stiri sa fie "clara". O imagine se considera "clara" daca oricum ai selecta 2 pixeli adiacenti din imagine de culori diferite, acestia sa apara cu culori diferite si la tembelizor.

Date de intrare

Fişierul de intrare tv.in va contine pe prima linie 3 numere naturale N, M si C. Pe urmatoarele N linii se vor afla cate M valori reprezentand culoarea fiecarui pixel din matrice (imaginea cu Bill care o sa apara la stiri). Pe ultima linie se vor afla C - 2 valori reprezentand vectorul cost. A i-a valoare este costi+1, costul necesar pentru a upgrada tembelizorul cu culoarea i+1.

Date de ieşire

Fişierul de ieşire tv.out va contine un singur numar natural, costul minim pentru a face tembelizorul sa perceapa imaginea "clara".

Restricţii

  • 1 ≤ N,M ≤ 500
  • 3 ≤ C ≤ 150.000
  • Fiecare pixel o sa fie un numar natural din intervalul [1,C]
  • 1 ≤ costi ≤ 1.000.000.000
  • Pentru teste in valoare de 20 de puncte N, M, C ≤ 50
  • Pentru teste in valoare de 30 de puncte C ≤ 500
  • Pentru teste in valoare de 40 de puncte C ≤ 2.500

Exemplu

tv.intv.out
3 3 7
5 1 6
6 4 6
5 4 3
4 4 4 5 6
13
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?