# NOIP 2010 Group 2: Tortoise Chess

## Initial Problem

描述

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
Copy

73
Copy



## My Translation

There is a 1-D grid of N cells, each with a whole number, or "point value" in them. There are also M cards, each consisting of either 1, 2, 3, or 4. In each "turn" you select one of the M cards to move a pointer the number indicated on the card steps forward. Then, that particular card is discarded. The process repeats until no cards are left. Then, the total points are calculated by summing the M+1 point values the pointer landed on. Calculate the maximum possible total points given all point values and all M cards.

## The Algorithm

The sentence "each turn ... select one of the M cards ..." proposes that this is a DP problem, because any other naive method wouldbe of O(N^2). We can try making advantage of the fact that there is only 4 card possibilities. It is possible to track the amount of cards saying 1, 2, 3, or 4, and build up solutions from that. Because of 4 DP parameters (# of ones, twos, threes, and fours) the DP array must be 4-D with each dimension of the maximum possible number of ones, twos, threes, or fours. My code illustrates this example. If there was only 2 parameters, this would be roughly a 0-1 Knapsack Problem.

## The Code

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[41][41][41][41];
int num[4], board[401];

int main()
{
int L, C; scanf("%d %d", &L, &C);
for(int i=0;i<L;i++) scanf("%d",&board[i]);
for(int i=0;i<C;i++)
{
int x; scanf("%d", &x);
num[x-1]++;
}
for(int a=0;a<=num[0];a++)
for(int b=0;b<=num[1];b++)
for(int c=0;c<=num[2];c++)
for(int d=0;d<=num[3];d++)
{
int t=0;
if(a) t=max(t,dp[a-1][b][c][d]);
if(b) t=max(t,dp[a][b-1][c][d]);
if(c) t=max(t,dp[a][b][c-1][d]);
if(d) t=max(t,dp[a][b][c][d-1]);
dp[a][b][c][d]=t+board[a+2*b+3*c+4*d];
}

printf("%d",dp[num[0]][num[1]][num[2]][num[3]]);
}


# Shortest Paths

In this article I will discuss the different algorithms for determining the shortest path from two points in a graph.

BFS can be used to search the shortest path because it searches layer by layer for the destination node.

SPFA.

# UVA 10364: Peter's Smokes

## Problem Statement

Peter has n cigarettes. He smokes them one by one keeping all the butts. Out of k > 1 butts he can roll a new cigarette. How many cigarettes can Peter have? Input Input is a sequence of lines. Each line contains two integer numbers giving the values of n and k. The input is terminated by end of file. Output For each line of input, output one integer number on a separate line giving the maximum number of cigarettes that Peter can have. Sample Input 4 3 10 3 100 5 Sample Output 5 14 124

## The Algorithm

This is a purely mathematical problem. It involves repeatedly dividing N and summing it to get the total amount. First, Peter has N cigars, plus N/k cigars (first butt->cigar transition, or "gluing"), then N/k^2 cigars, (2nd gluing), until N/k^i is 0 (at least when rounded.)

## The Code Itself

#include <iostream>
using namespace std;

int main()
{
int n,m;
while(cin>>n>>m)
{
int t=0;
while(n>=m)
{
t+=n;
n=n/m+n%m;
}
t+=n;
cout<<t<<endl;
}
return 0;
}


Darren Li

New York City