ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > CEN303_2016Questions > задача:


HW102. 51067 - Jumping frog

CEN303_2016Questions

Старт: 28.окт.2016 в 17:00:00
Финиш: 01.ноя.2016 в 05:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (3)

Задачи турнира

• HW062. 51021 - Number of Nodes
• HW071. 51042 - The most frequent ...
• HW072. 51043 - Genome Sequencing
• HW081. 51044 - Number of Trees
• HW082. 50699 - Fighting Vampires
• HW083. 50671 - Phalanx
• HW091. 51061 - The Longest Path
• HW101. 50682 - Hotel Durres
• HW102. 51067 - Jumping frog
• HW111. 50506 - The Biggest Island
• HW112. 50698 - Ayran Delivery
• PE11. 51023 - Preparing Keyword I...
• PE12. 50835 - Club Presidency
• PE13. 51024 - Total Stock Price
• PE14. 50998 - CEN112 Homework, ...
• PE21. 51071 - Phalanx-2
• PE22. 51072 - Castle on chessboard

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Ibrahim Mesecan.

Jumping frog

Question: A frog is trying to jump out of stone well. It has some energy cells or obstacles (positive or negative energy) on the wall. While passing through the steps (cells), it takes the energy in that step. It starts from the beginning and it can either jump over the obstacles or walk forward. Negative numbers mean jump backward, and positive numbers mean jump forward. The number in the cell is the number of cells to jump. For example, if a cell has 1, it means, the from either walk forward or jump over the next cell. Find out the maximum energy collected (sum of the energy in the cells visited) when walking through the cells.

Input specification: First, you will be given an integer, the height of the well (n). Then, in the following line you will be given n numbers (integers from -50 to 50) where 1 ≤ n ≤ 50.

Output specification: Show one integer: the maximum energy collected.

Sample Input I
8
-2 1 -3 3 -1 -3 3 2
Sample Output I
4
Sample Input II
8
2 2 -3 -1 5 2 0 -2
Sample Output II
11
Sample Input III
8
3 -3 2 -3 -1 2 1 -3
Sample Output III
7
Sample Input IV
3
1 -2 2
Sample Output IV
3

Explanation: You can visit every cell only once. The target is to start from the beginning and to reach to the right end with the maximum possible value.

When passing from any cell, you can directly go to the right or you can jump the cell according to the value of the cell. If the cell value is 2 you jump the following 2 cells. If the cell value is -2 then you jump 2 cells towards left.

Sample Input 1: If it walks over the cells, (-2) + 1 + (-3)...3+2 =0. If it goes -2, 1, -3 and jumps from 3 to 2 it can have 1. If it goes over -2 and jumps from 1 and 3, it can have 4. So the max is 4. Sample Input 2: It can walk through 2, and then jumps from the second 2 to 5. Then it jumps again from 2 to out of the path (2+2+5+2=11).



Для отправки решений необходимо выполнить вход.

www.contester.ru