DCP-37: Walky Walk Back to All Problems

Medium Divide and Conquer > Dynamic Programming


Bob is developing a new game. In the game, there will be N blocks, numbered from 1 to N. Initially a player will be standing at block numbered 1 and can jump to other blocks. The player’s first jump should be from block 1 to block 2. Then the next jumps can be: 1. If the jump is in forward direction, the length must be one block longer than the previous jump. 2. If the jump is in backward direction, the length must be same as the previous jump. For example, after the first jump (when the player is at block 2), s/he can jump back to block 1 or block 4. Now each block contains a surcharge, if you jump on a certain block you have to pay that block’s surcharge (it doesn’t matter whether s/he visited the block before). Now the player’s target will be to go from block 1 to block N by paying minimum surcharge possible. Can you find that minimum surcharge? As the player is initially at block 1 and didn’t jump into the block 1 so s/he will not pay the surcharge for block 1. But if in any subsequent jump one player jumps to block 1, s/he must pay. Input: ------ Input starts with an integer **T (≤ 10)**, denoting the number of test cases. The first line of each case contains the integer **N, 2 ≤ N ≤ 1000**, the number of blocks. Then the next line contains N integers separated by space, where I’th integer **( 1 <= I <= N)** denotes the surcharge of I’th block. These integers will be between **1 and 500** Output: ------- For each case, print the case number and the minimum surcharge a players needs to give to go from block 1 to block N. See the samples for exact formatting. Sample Input ------------ 2 6 1 2 3 4 5 6 8 2 3 4 3 1 6 1 4 Sample Output ------------- Case 1: 12 Case 2: 14


Problem Setter:

Ahmad Faiyaz

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

14/30

Solve/Submission

Ranking

# User Language Timing
01 tariqiitju Cpp14 0.04s
02 sakib_muhit Cpp14 0.04s
03 jalal Cpp14 0.04s
04 rajdipsaha Cpp 0.04s
05 a_rahman Cpp14 0.05s
06 njrafi Cpp14 0.06s
07 ahqmrf Cpp14 0.43s
08 clcrr Cpp14 0.43s
09 alhelal_cse Cpp14 0.52s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support