Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Maxtri

Adăugată de :
sorynsoo
Sursă :
XOR2012
Autor :
-
Grupă :
Medie
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
500 ms
Limită memorie :
10240 kbytes

Fie o matrice cu N linii şi N coloane de numere naturale. Liniile şi coloanele sunt numerotate de la 1 la N. Se doreşte traversarea matricei pe un drum pornind din poziţia (1, 1) în (N, N), mergând pas cu pas. La un pas, de la o poziţie (i, j) se poate trece într-una din poziţiile (i+1, j), (i+1, j+1), (i, j+1). Costul drumului este dat de suma valorilor componentelor care fac parte din drum.

 

Cerinţa

Scrieţi un program care determină un drum de cost maxim de la poziţia (1, 1) la (N, N) şi cu proprietatea că acest cost maxim este multiplu de 3.

 

Date de intrare

Fişierul de intrare conţine pe prima linie un număr natural N, iar pe următoarele N linii se află câte N numere naturale separate prin câte un spaţiu reprezentând valorile de pe o linie din matrice.

 

Date de iesire

Fişierul de iesire va conţine un singur număr natural reprezentând costul maxim divizibil cu 3 al unui drum de la poziţia (1, 1) la (N, N). Dacă nu există niciun drum de cost divizibil cu 3, se va afişa valoarea 0.

 

Restricţii şi precizări:

  • 3 <= N <= 500
  • Elementele matricei sunt numere naturale cuprinse între 1 şi 10 000

 

Exemplu

Date de intrare 

Date de iesire

Explicaţii

3

2 3 1

5 6 7

9 8 4

24

Drumul de cost maxim trece prin componentele de coordonate (1,1) (2,1) (2,2) (2,3) (3,3). Costul său este 2+5+6+7+4 = 24, iar 24 este divizibil cu 3.

De remarcat că există drumuri de cost mai mare, dar care nu sunt divizibile cu 3.

Date de intrare

Date de iesire

Explicaţii

3

1 3 3

3 3 3

3 3 3

0

Nu există niciun drum de la (1,1) la (3,3) de cost divizibil cu 3.


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Lee


Comentarii

Adauga un comentariu: Click !