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




# User Language Timing
01 feodorv C 0.01s
02 jalal Cpp 0.04s
03 Ishrak Cpp 0.04s
04 Robbinb1993 Cpp 0.04s
05 tariqiitju Cpp14 0.04s
06 sakib_muhit Cpp14 0.04s
07 mh755628 Cpp 0.04s
08 rajdipsaha Cpp 0.04s
09 Morass Cpp14 0.04s
10 Sarwar05 Cpp 0.04s
11 SakibAlamin Cpp 0.05s
12 robin_aust Cpp 0.05s
13 killer_knight Cpp 0.05s
14 a_rahman Cpp14 0.05s
15 Pure_Protea Cpp14 0.05s
16 njrafi Cpp14 0.06s
17 ahqmrf Cpp14 0.43s
18 clcrr Cpp14 0.43s
19 alhelal_cse Cpp14 0.52s

Your feedback is our precious!

Or call +88 02 9853138 for support