Здравейте,

Допреди малко си блъсках главата с тази задача докато в един момент ... взе че проработи! laugh Останах доволен от решението си и реших да го споделя smiley.

Решението е изцяло мое и е с рекурсия!

Решение: source - 56 реда, 45 SLOC; 100/100 точки

Прочитам входа и го запаметявам в назъбена матрица. Направил съм метод (рекурсивен), на който подавам текущата позиция на елемент (от 1-ви ред), намиращ съответната "специална стойност" . Получената стойност сравнявам с максималната (използвам Math.Max()). Накрая се принтира на конзолата максималната стойност.

П.П.: Първо пробвах да подкарам програмата да работи, а след това щях да имплементирам и булева матрица, която да проверява на коя позиция е минавано. Но явно в тестовете няма такива случаи и когато пробвах така решението си изкара 100/100. Гърми на zero test 4, но той не е фактор за точките. Ако се имплементира и булева матрица, трябва да се добави една проверка в началото на метода (за намиране на "специалната стойност"), която да връща 0.

Условие

Problem 2 – Special Value

You are given N number of rows. Each row contains a different number of columns. Each cell in a row contains a negative number or an index of a cell on the next row, i.e. rows[row][column] holds an index of cell in [row+1]. The row after the last row is the first row. If the number of columns on the next row is C, each of the cells on the current row are in the range [-C, C-1] inclusive.

A path in the rows is the max number of cells that can be passed, starting from any of the cells on the first row, and following the pattern above (i.e. each cell on row R, holds a negative number or an index on row R+1). The path ends when the path reaches an already visited cell in this path, or the number in the cell is negative.

A special value is the sum of the path + the absolute value of a negative number reached. If a path reaches a visited cell, this path cannot get a special value.

Your task is to find the biggest special value using the given rows.

Input

The input data should be read from the console.

On the first line you will be given the number N.

On the next N lines you will be given the numbers in each row, separated with ", " (comma and space).

Output

The output data should be printed on the console.

The output should contain only the maximal special number.

Constraints

  • The rows will be between 1 and 1000 inclusive.
  • The cells on each row will be between 1 and 1000 inclusive.

·         Allowed working time for your program: 0.5 seconds. Allowed memory: 16 MB.




в C# Advanced от tisho (1966 точки)