Algorithm
problem Link : : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1943
Have you ever heard of this game? The player jumps in a special game board under certain rules, so that the numbers he jumps on, after being linked up by plus or minus signs, get closest to zero. The game board looks like the one shown in Figure 1.1. Its size is determined by the number of squares in the middle row N. (Figure 1.1 is an example where N = 4.) The player starts at the bottom-most square, then jumps in any of the directions shown in Figure 1.2. The game ends when the player reaches the topmost square. During the game, the player cannot jump out of the game board. Finally we write down the 2N − 1 numbers in order, then insert plus or minus signs between each pair of adjoining numbers such that the result is closest to zero. Let us look at the game board in Figure 1.1 as a example. We should get: 7+8+(-5)+(-2)-5-1-2=0, 7+10+(-7)-6+(-3)-3+2=0, 7+10+(-5)-10-5+1+2=0, or 7+10+(-5)+(-2)-5-3-2=0. Figure 1.1 Figure 1.2 Input The first line of input contains N (1 ≤ N ≤ 30). The following 2N − 1 lines give the numbers in the squares in the game board. The j-th number in the (i + 1)-th line corresponds to the j-th number in the i-th row of the game board. (The numbers are all ≥ −50 and ≤ 50.) Input contains multiple test cases, and it ends with a case where N = 0. Output For each case, your output should print the absolute value of the result you get for each game board.
Sample Input 4 2 3 1 -3 5 7 6 10 -2 20 -7 -5 -8 10 8 7 0
Sample Output 0
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int n, v;
vector < vector<int>> board;
int memo[61][31][3001];
int solve(int idx, int col, int val){
if(idx == 0) {
return abs(val);
}
int &dp = memo[idx][col][val];
if(dp != -1) return dp;
dp = INT_MAX;
bool top_half = idx < n;
if(top_half>{
if(col>0){
int add_left = abs(val + board[idx-1][col-1]);
int sub_left = abs(val - board[idx-1][col-1]);
dp = min(dp, solve(idx-1,col-1,add_left));
dp = min(dp, solve(idx-1,col-1,sub_left));
}
if(col<idx){
int add_right = abs(val + board[idx-1][col]);
int sub_right = abs(val - board[idx-1][col]);
dp = min(dp, solve(idx-1,col,add_right));
dp = min(dp, solve(idx-1,col,sub_right));
}
}else{
int add_left = abs(val + board[idx-1][col]);
int sub_left = abs(val - board[idx-1][col]);
int add_right = abs(val + board[idx-1][col+1]);
int sub_right = abs(val - board[idx-1][col+1]);
dp = min(dp, solve(idx-1,col,add_left));
if(idx != 2*n-1) dp = min(dp, solve(idx-1,col,sub_left));
dp = min(dp, solve(idx-1,col+1,add_right));
if(idx != 2*n-1) dp = min(dp, solve(idx-1,col+1,sub_right));
}
return dp;
}
int main() {
while(scanf("%d",&n),n){
board.clear();
for(int i=0;i < 2*n-1;i++){
vector<int> row;
for(int j=0;j < n-abs(n-i-1);j++){
scanf("%d",&v);
row.push_back(v);
}
board.push_back(row);
}
memset(memo, -1, sizeof memo);
printf("%d\n",solve(board.size()-1,0,board.back()[0])>;
}
}
Input
2
3 1
-3 5 7
6 10 -2 20
-7 -5 -8
10 8
7
0
Demonstration
UVA Online Judge solution -11002-Towards Zero - UVA Online Judge solution in C,C++,java