## Saturday, October 30, 2010

1.6.1 状态空间:
1.6.2 盲目搜索算法:
1.6.3 启发式搜索算法:
1.6.4 博弈问题算法:
1.6.5 剪枝:
1.6.6 路径寻找问题:
1.6.7 约束满足问题:

### 第一章_1.5 动态规划:

1.5.1 动态规划的两种动机:
1.5.2 常见模型的分析:
1.5.3 若干经典问题和常见优化方法:

### 第一章_1.4 数据结构(2) ---- 拓宽和应用举例:

1.4.1 并查集:

Example: (例题)
E.g.01 : 代码等式.
E.g.02 : 团伙.
E.g.03 : Galaxy.
E.x.01 : Ubiquitous Religions.
E.x.02 : The Suspects.
E.x.03 : 食物链.
E.x.04 : Find them, Catch them.
E.x.05 : A Bug's Life.
E.x.06 : Wireless Networks.
E.x.07 : Cube Stacking.
E.x.08 : War.

1.4.2 堆及其变种:

1.4.3 字典的两种实现方式: 哈西表, 二叉搜索树:
1.4.4 两个特殊树结构: 线段树和 Trie:

Example:(例题)
E.x.02: IMMEDIATE DECODABILITY.

### 第一章_1.3 数据结构(1) -----入门:

1.3.1 栈和队列:
Example: (例题)
E.g.01 : Rails.
E.g.02 : Tempus et mobilius Time and motion.
Excise : (练习)
1.3.7 Bitmap.
1.3.8 Partition.
1.3.9 算法复杂度.

1.3.2 串:
Example: (例题)
E.g.01 : .
Excise : (练习)
1.3.12 Necklaces.
1.3.13 .

1.3.3 树和二叉数:
Example: (例题)
E.g.00 : Ilya Murometz.
E.g.01 : .
E.g.02 : .
Excise : (练习)
1.3.18
1.3.19 .
1.3.20 .
Extra :
1.3.18 Tree Recovery.(POJ)

1.3.4 图及其基本算法:
Example: (例题)
E.g.01 : .
E.g.02 : .
Excise : (练习)
1.3.25 .
1.3.26 .
1.3.27 .

1.3.5 排序与检索基本算法:
Example: (例题)
E.g.01 : Cable Master.
E.g.02 : Stacks of Flapjacks.
E.x.01 : Gaby Ivanushka.
E.g.03 : SOLDIERS.
E.g.04 : Exchange.
Excise : (练习)
1.3.30 .
1.3.31 .

### 第一章_1.2 基本算法:

1.2.1 枚举:
Example: (例题)
E.g. 01 : Balloons in a box.
E.g. 02 : Library.
Excise : (练习)
1.2.4 Conductor.
1.2.5 Flip Coin.
1.2.6 Discrete Function.
1.2.7 Subnumber
Extra:

1.2.2 贪心法:
Example: (例题)
E.g. 01 : Gone Fishing.
E.g. 02 : Enlightened Landscape.
E.g. 03 : Mirror.
Excise: (练习)
1.2.12
1.2.13
1.2.14
Extra:
001 : Crossing River.

1.2.3 递归与分治法:
Example: (例题)
E.g. 01
E.g. 02
E.g. 03
E.g. 04
Excise: (练习)
1.2.18

1.2.4 递归:
Example: (例题)
E.g. 01 : Evil Eyes
E.g. 02 : Lost Lists
E.g. 03 : Chain
Excise: (练习)
1.2.23
1.2.24
1.2.25 : Chain.
1.2.26
1.2.27
1.2.28
Extra:
001 : Time Zones.

poj3753,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3494 Accepted: 707

Description

`int SafeStrcpy2KeyWord(char* pDestBuffer,	//拷贝的目的地地址		       char* pSourceString,	//拷贝的源地址		       int nDestBufferSize,	//拷贝的目的地缓冲区长度		       char* szKeyWord);	//指定关键字符串`

Input

Output

Sample Input
`/home/tony/work_server/1/rtest/relayer.out//t/1/r.NULLEND`

Sample Output
`0 NULL5 /home22 /home/tony/work_server38 /home/tony/work_server/1/rtest/relayer0 NULL`

Source

## Solution:

Do whatever the problem told you to do, but take care:
1st, if there is no match with the keyword, return the whole string.
2nd, take care of the for loop. It takes me 3 or 4 WAs.

## Source Code:

//Fri May 28 12:55:30 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int SafeStrcpy2KeyWord(string &des, string src, string keyword)
{
if (keyword == "NULL")
{
des.clear();
return 0;
}
int N = keyword.size();
int M = src.size();
for (int i = 0; i + N <= M; i++)
{
string str = src.substr(i, N);
if (str == keyword)
{
return i;
}
des += src[i];
}
return 0;
}

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
string str;
while (cin >> str)
{
string s;
getchar();
while (getline(cin, s) && s != "END")
{
string des;
int len = SafeStrcpy2KeyWord(des, str, s);
if (len == 0 && des.size() == 0)
cout << "0 NULL" << endl;
else if (len == 0)
cout << str.size() << " " << str << endl;
else
cout << len << " " << str.substr(0, len) << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3752,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4838 Accepted: 1757

Description

`   A   B   C   D   E   F   G   H   V   W   X   Y   Z   A   B   I   U   J   K   L   M   N   C   J   T   I   H   G   F   E   D   K   S   R   Q   P   O   N   M   L`

Input
M为行数，N为列数，其中M，N都为大于0的整数。

Output

Sample Input
`4 9`

Sample Output
`   A   B   C   D   E   F   G   H   I   V   W   X   Y   Z   A   B   C   J   U   J   I   H   G   F   E   D   K   T   S   R   Q   P   O   N   M   L`

Source

## Solution:

Basically, it's just a straight forward  simulation.

In each state, select the next state.

## Source Code:

//Sat Apr 17 12:25:46 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int M, N;
while (cin >> M >> N)
{
vector<vector<char> > v(M, vector<char> (N, '#'));
int nextx = 0;
int nexty = 0;
int count = 0;
int position = 0;
int direction = 0; // right, down, left, up.
while (count < M * N)
{
count ++;
char letter = 'A' + position;
position = (position + 1) % 26;
v[nextx][nexty] = letter;
//Right;
if(direction == 0)
{
if(nexty + 1 == N || (nexty+1<N && v[nextx][nexty+1] != '#'))
{
direction = 1;
nextx++;
}
else
{
nexty++;
}
}
//Down;
else if(direction == 1)
{
if(nextx+1==M || (nextx+1<M && v[nextx+1][nexty] != '#'))
{
direction = 2;
nexty--;
}
else
{
nextx++;
}
}
//Left;
else if(direction == 2)
{
if(nexty-1<0 || (nexty-1>=0 && v[nextx][nexty-1] !='#'))
{
direction = 3;
nextx--;
}
else
{
nexty--;
}
}
//Up;
else
{
if(nextx-1 <0 || (nextx-1>=0 && v[nextx-1][nexty] != '#'))
{
direction = 0;
nexty++;
}
else
{
nextx--;
}
}
}
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
cout << " " << v[i][j];
}
cout << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3751,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4083 Accepted: 1918

Description

Input

Output

Sample Input
`22009/11/07-12:12:121970/01/01-00:01:01`

Sample Output
`11/07/2009-12:12:12pm01/01/1970-12:01:01am`

Hint

Source

## Source Code:

//Fri 29 Jan 2010 01:44:27 AM CST
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
string str;
int T;
cin >> T;
for(int i=0; i<T; i++)
{
string output;
cin >> str;
output += str.substr(5,5);
output += "/";
output += str.substr(0,4);
output += "-";
//output += str.substr(11);
int time = 10 * (str-'0') + (str-'0');
if(time == 0)
{
output += "12";
output += str.substr(13) + "am";
}
else if(time >0 && time <12)
{
output += str.substr(11) + "am";
}
else if(time == 12)
{
output += str.substr(11) + "pm";
}
else
{
time -= 12;
int d = time / 12;
int dd = time % 12;
output += ('0' + d);
output += ('0' + dd);
output += str.substr(13) + "pm";
}
cout << output << endl;
}
return 0;
}
[/sourcecode]

poj3750,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4457 Accepted: 2145

Description

Input

Output

Sample Input
`5XiaomingXiaohuaXiaowangZhangsanLisi2,3`

Sample Output
`ZhangsanXiaohuaXiaomingXiaowangLisi`

Source

Simulation.

## Source Code:

//Sat 30 Jan 2010 05:48:22 PM CST
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
vector<string> v;
v.clear();
int N;
string str;
cin >> N;
for(int i=0; i<N; i++)
{
cin >> str;
v.push_back(str);
str.clear();
}
int start;
int loop;
char c;
cin >> start >> c >> loop;
// cout << start << ", " <<loop << endl;
start--;
while(!v.empty())
{
int next = (start+loop-1) % v.size();
cout << v[next] << endl;
start = next==v.size()-1 ? 0 : next;
v.erase(v.begin() + next);
}
return 0;
}
[/sourcecode]

poj3748,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5792 Accepted: 2219

Description

Input

Output

Sample Input
`12345678,0,3`

Sample Output
`1234567c`

Source

## Solution:

Implement all the operations by using bit operation, that will be much easier than convert to any other format.

PS, take care of the cin and cout.

## Source Code:

//Sat Apr 17 14:43:26 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main( int argc, const char* argv[] )
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int R, X, Y;
char c;
while(cin >> hex >> R >> dec >> c >> X >> c >> Y)
{
R &= ~(1<<(X));
R |= (1<<(Y));
R |= (1<<(Y-1));
R &= ~(1<<(Y-2));

cout << hex << R << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
[/sourcecode]

poj3650,

## Problem:

The Seven Percent Solution

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5293 Accepted: 3475

Description

Uniform Resource Identifiers (or URIs) are strings like http://icpc.baylor.edu/icpc/, mailto:foo@bar.org, ftp://127.0.0.1/pub/linux, or even just readme.txt that are used to identify a resource, usually on the Internet or a local computer. Certain characters are reserved within URIs, and if a reserved character is part of an identifier then it must be percent-encoded by replacing it with a percent sign followed by two hexadecimal digits representing the ASCII code of the character. A table of seven reserved characters and their encodings is shown below. Your job is to write a program that can percent-encode a string of characters.

 Character Encoding " " (space) %20 "!" (exclamation point) %21 "\$" (dollar sign) %24 "%" (percent sign) %25 "(" (left parenthesis) %28 ")" (right parenthesis) %29 "*" (asterisk) %2a

Input

The input consists of one or more strings, each 1–79 characters long and on a line by itself, followed by a line containing only "#" that signals the end of the input. The character "#" is used only as an end-of-input marker and will not appear anywhere else in the input. A string may contain spaces, but not at the beginning or end of the string, and there will never be two or more consecutive spaces.

Output

For each input string, replace every occurrence of a reserved character in the table above by its percent-encoding, exactly as shown, and output the resulting string on a line by itself. Note that the percent-encoding for an asterisk is %2a (with a lowercase "a") rather than %2A (with an uppercase "A").

Sample Input
`Happy Joy Joy!http://icpc.baylor.edu/icpc/plain_vanilla(**)?the 7% solution#`

Sample Output
`Happy%20Joy%20Joy%21http://icpc.baylor.edu/icpc/plain_vanilla%28%2a%2a%29?the%207%25%20solution`

Source
Mid-Central USA 2007

## Source Code:

//Tue Apr 20 11:49:19 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main( int argc, const char* argv[] )
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
string str;
while(getline(cin ,str) && str != "#")
{
for(int i=0; i<str.size(); i++)
{
if(str[i] == ' ') cout << "%20";
else if(str[i] == '!') cout << "%21";
else if(str[i] == '\$') cout << "%24";
else if(str[i] == '%') cout << "%25";
else if(str[i] == '(') cout << "%28";
else if(str[i] == ')') cout << "%29";
else if(str[i] == '*') cout << "%2a";
else cout << str[i];
}
cout << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3637,

## Problem:

Shopaholic

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3631 Accepted: 2119

Description

Lindsay is a shopaholic. Whenever there is a discount of the kind where you can buy three items and only pay for two, she goes completely mad and feels a need to buy all items in the store. You have given up on curing her for this disease, but try to limit its effect on her wallet.

You have realized that the stores coming with these offers are quite selective when it comes to which items you get for free; it is always the cheapest ones. As an example, when your friend comes to the counter with seven items, costing 400, 350, 300, 250, 200, 150, and 100 dollars, she will have to pay 1500 dollars. In this case she got a discount of 250 dollars. You realize that if she goes to the counter three times, she might get a bigger discount. E.g. if she goes with the items that costs 400, 300 and 250, she will get a discount of 250 the first round. The next round she brings the item that costs 150 giving no extra discount, but the third round she takes the last items that costs 350, 200 and 100 giving a discount of an additional 100 dollars, adding up to a total discount of 350.

Your job is to find the maximum discount Lindsay can get.

Input

The first line of input gives the number of test scenarios, 1 ≤ t ≤ 20. Each scenario consists of two lines of input. The first gives the number of items Lindsay is buying, 1 ≤ n ≤ 20000. The next line gives the prices of these items, 1 ≤ pi ≤ 20000.

Output

For each scenario, output one line giving the maximum discount Lindsay can get by selectively choosing which items she brings to the counter at the same time.

Sample Input
`16400 100 200 350 300 250`

Sample Output
`400`

Source
Nordic 2007

## Source Code:

//Sat Jun 19 16:00:59 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++)
cin >> v[i];
sort(v.begin(), v.end());
int sum = 0;
for (int i = N - 3; i >= 0; i -= 3)
sum += v[i];
cout << sum << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3632,

## Problem:

Optimal Parking

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5732 Accepted: 3113

Description

When shopping on Long Street, Michael usually parks his car at some random location, and then walks to the stores he needs. Can you help Michael choose a place to park which minimises the distance he needs to walk on his shopping round? Long Street is a straight line, where all positions are integer. You pay for parking in a specific slot, which is an integer position on Long Street. Michael does not want to pay for more than one parking though. He is very strong, and does not mind carrying all the bags around.

Input

The first line of input gives the number of test cases, 1 ≤ t ≤ 100. There are two lines for each test case. The first gives the number of stores Michael wants to visit, 1 ≤ n ≤ 20, and the second gives their n integer positions on Long Street, 0 ≤ xi ≤ 99.

Output

Output for each test case a line with the minimal distance Michael must walk given optimal parking.

Sample Input
`2424 13 89 3767 30 41 14 39 42`

Sample Output
`15270`

Source
Nordic 2007

Basic one.

## Source Code:

//Tue Apr 20 12:57:54 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N;
cin >> N;
while (N--)
{
int mmin = -1;
int mmax = -1;
int t;
cin >> t;
for(int i=0; i<t; i++)
{
int number;
cin >> number;
if(number < mmin || mmin == -1) mmin = number;
if(number > mmax || mmax == -1) mmax = number;
}
cout << 2 * (mmax - mmin) << endl;
}

// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3673,

## Problem:

Cow Multiplication

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7792 Accepted: 5135

Description

Bessie is tired of multiplying pairs of numbers the usual way, so she invented her own style of multiplication. In her style, A*B is equal to the sum of all possible pairwise products between the digits of A and B. For example, the product 123*45 is equal to 1*4 + 1*5 + 2*4 + 2*5 + 3*4 + 3*5 = 54. Given two integers A and B (1 ≤ A, B ≤ 1,000,000,000), determine A*B in Bessie's style of multiplication.

Input

* Line 1: Two space-separated integers: A and B.

Output

* Line 1: A single line that is the A*B in Bessie's style of multiplication.

Sample Input
`123 45`

Sample Output
`54`

Source
USACO 2008 February Bronze

## Source Code:

//Sun 31 Jan 2010 02:03:36 PM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
string s1;
string s2;
cin >> s1 >> s2;
int sum1 = 0;
int sum2 = 0;
int sz1 = s1.size();
int sz2 = s2.size();
for(int i=0; i<sz1; i++)
{
sum1 += s1[i]-'0';
}
for(int i=0; i<sz2; i++)
{
sum2 += s2[i]-'0';
}
cout << sum1*sum2 << endl;
return 0;
}
[/sourcecode]

poj3630,

## Problem:

Phone List

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9408 Accepted: 2992

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:

• Emergency 911

• Alice 97 625 999

• Bob 91 12 54 26

In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output "YES" if the list is consistent, or "NO" otherwise.

Sample Input
`2391197625999911254265113123401234401234598346`

Sample Output
`NOYES`

Source
Nordic 2007

Trie Tree.

## Source Code:

//Sun Jul 4 00:43:51 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MMAX 100000
using namespace std;

int Count;

class TreeNode
{
public:
bool istring;
TreeNode *child;
};

vector<TreeNode> v(MMAX);

class TrieTree
{
private:
TreeNode root;
public:
void init();
bool insert(string word);
};

void TrieTree::init()
{
Count = 0;
root = v[Count++];
memset(root.child, NULL, sizeof(root.child));
root.istring = false;
}

bool TrieTree::insert(string word)
{
TreeNode *start = &root;
int len = word.size();
for (int i = 0; i < len; i++)
{
if (start->child[word[i] - '0'] == NULL)
{
start->child[word[i] - '0'] = &v[Count];
v[Count].istring = false;
memset(v[Count].child, NULL, sizeof(v[Count].child));
Count++;
}
else if (start->child[word[i] - '0']->istring == true || i == len - 1)
{
start->child[word[i] - '0']->istring = true;
return false;
}
start = start->child[word[i] - '0'];
}
start->istring = true;
return true;
}

int main(int argc, const char* argv[])
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int ncase;
cin >> ncase;
while (ncase--)
{
int N;
cin >> N;
string str;
bool flag = true;
TrieTree x;
x.init();
for (int i = 0; i < N; i++)
{
cin >> str;
if (x.insert(str) == false)
{
flag = false;
}
}
if (flag == false)
{
cout << "NO" << endl;
}
else
{
cout << "YES" << endl;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
[/sourcecode]

poj3619,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6238 Accepted: 2697

Description

All K (1 ≤ K ≤ 1,000) of the cows are participating in Farmer John's annual reading contest. The competition consists of reading a single book with N (1 ≤ N ≤ 100,000) pages as fast as possible while understanding it.

Cow i has a reading speed Si (1 ≤ Si ≤ 100) pages per minute, a maximum consecutive reading time Ti (1 ≤ Ti ≤ 100) minutes, and a minimum rest time Ri (1 ≤ Ri ≤ 100) minutes. The cow can read at a rate of Si pages per minute, but only for Ti minutes at a time. After she stops reading to rest, she must rest for Ri minutes before commencing reading again.

Determine the number of minutes (rounded up to the nearest full minute) that it will take for each cow to read the book.

Input

* Line 1: Two space-separated integers: N and K
* Lines 2..K+1: Line i+1 contains three space-separated integers: Si , Ti , and Ri

Output

* Lines 1..K: Line i should indicate how many minutes (rounded up to the nearest full minute) are required for cow i to read the whole book.

Sample Input
`10 32 4 16 1 53 3 3`

Sample Output
`677`

Source
USACO 2007 November Bronze

## Solution:

1st, get the total reading time for each cow;

2nd, get the up limit of consecutive reading time; (PS: result - 1 = Times needed to rest).

3rd, total = total reading time + MinrestTime * (result from 2nd - 1);

## Source Code:

//Fri Apr 23 01:56:26 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N, K;
while (cin >> N >> K)
{
vector<vector<int> > v(K, vector<int> (3));
for (int i = 0; i < K; i++)
cin >> v[i] >> v[i] >> v[i];
v[i] = (int) ((N + v[i] - 1) / v[i]);
// cout << v[i] << v[i] << v[i] << endl;
int times = (int) ((v[i] + v[i] - 1) / v[i]);
int total = v[i] + v[i]*(times-1);
cout << total << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3589,

## Problem:

Number-guessing Game

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4276 Accepted: 3148

Description

Larry likes playing the number-guessing game.

Two players are needed in a game. Suppose they are X and Y, and X presents a number for Y to guess. Firstly, X chooses a number with four different digits, keeping it in mind, and tells Y to start guessing. Every time Y has guessed, X should give out *A*B to show Y how close to the number his answer is. Here the symbol * stands for a number, and the number before A is the number of digits in Y's answer with both correct value and position. The number before B is the number of digits in Y's answer with correct value but incorrect position.

For example, if X chooses the number 5204, and Y guesses 4902, then X should give out 1A2B, in which 1A corresponds for digit 0 with both correct value and position and 2B corresponds for digit 2 and 4 with correct value but incorrect position. Then Y will go on guessing according to 1A2B that X presents him until he gets the totally correct number 5204 (when X shows him 4A0B).

Now you are given two numbers, and what you need to do is just testing how close they are.

Input

The first line of the input is an integer T which indicates the number of test cases. For each test case, input two numbers. Each number contains four different digits.

Output

For each test case, output *A*B stands for how close the two numbers are.

Sample Input
`25204 49020123 3210`

Sample Output
`1A2B0A4B`

Source
South Central China 2008 hosted by NUDT

## Source Code:

//Sun 31 Jan 2010 02:14:54 PM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
int N;
cin >> N;
for(int i=0; i<N; i++)
{
string str1;
string str2;
cin >> str1 >> str2;
int A = 0;
int B = 0;
for(int j=0; j<4; j++)
{
if(str1[j] == str2[j])
A ++;
else
{
for(int k=0; k<4; k++)
{
if(str2[j] == str1[k])
{
B++;
break;
}
}
}
}
cout << A << "A" << B << "B" << endl;
}
return 0;
}
[/sourcecode]

poj3517,

## Problem:

And Then There Was One

 Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 3173 Accepted: 1587

Description

Let’s play a stone removing game.

Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from m and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make k hops clockwise on the remaining stones and remove the one you reach. In other words, skip (k − 1) remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown in Figure 1. Initial state Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Final state

Figure 1: An example game

Initial state: Eight stones are arranged on a circle.

Step 1: Stone 3 is removed since m = 3.

Step 2: You start from the slot that was occupied by stone 3. You skip four stones 4, 5, 6 and 7 (since k = 5), and remove the next one, which is 8.

Step 3: You skip stones 1, 2, 4 and 5, and thus remove 6. Note that you only count stones that are still on the circle and ignore those already removed. Stone 3 is ignored in this case.

Steps 4–7: You continue until only one stone is left. Notice that in later steps when only a few stones remain, the same stone may be skipped multiple times. For example, stones 1 and 4 are skipped twice in step 7.

Final State: Finally, only one stone, 1, is on the circle. This is the final state, so the answer is 1.

Input

The input consists of multiple datasets each of which is formatted as follows.

n k m

The last dataset is followed by a line containing three zeros. Numbers in a line are separated by a single space. A dataset satisfies the following conditions.

2 ≤ n ≤ 10000, 1 ≤ k ≤ 10000, 1 ≤ mn

The number of datasets is less than 100.

Output

For each dataset, output a line containing the stone number left in the final state. No extra characters such as spaces should appear in the output.

Sample Input
`8 5 3100 9999 9810000 10000 100000 0 0`

Sample Output
`1932019`

Source
Japan 2007

## Solution:

1 2 3 4 5 6 7 8
4 5 6 7 8 9 10 11
4 5 6 7 8 9 10
1 2 3 4 5 6 7

/*约瑟夫问题的数学方法

k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2

k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1

f=0;
f[i]=(f[i-1]+m)%i; (i>1)

## Source Code:

////////2008-04-08;
#include<stdio.h>
int main()
{
int a;
int m,n,k;
while(scanf("%d%d%d",&n,&k,&m)==3&&(n+m+k)>0)
{
int i;
a=0;
for(i=2;i<n;i++)
{
a[i]=(a[i-1]+k)%i;
}
printf("%d\n",(a[n-1]+n+m+1)%n);
}
return 0;
}
[/sourcecode]

### poj_3438_Look_and_Say.cpp

poj3438, spoj03081,

## Problem:

Look and Say

 Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 6516 Accepted: 3944

Description
The look and say sequence is defined as follows. Start with any string of digits as the first element in the sequence. Each subsequent element is defined from the previous one by "verbally" describing the previous element. For example, the string 122344111 can be described as "one 1, two 2's, one 3, two 4's, three 1's". Therefore, the element that comes after 122344111 in the sequence is 1122132431. Similarly, the string 101 comes after 1111111111. Notice that it is generally not possible to uniquely identify the previous element of a particular element. For example, a string of 112213243 1's also yields 1122132431 as the next element.

Input
The input consists of a number of cases. The first line gives the number of cases to follow. Each case consists of a line of up to 1000 digits.

Output
For each test case, print the string that follows the given string.

Sample Input
`3122344111111111111112345`

Sample Output
`11221324311011112131415`

Source
Rocky Mountain 2007

## Solution:

Straight forward.

## Source Code:

//Sun 31 Jan 2010 02:00:16 AM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
int N;
cin >> N;
for(int i=0; i<N; i++)
{
string str;
cin >> str;
int len = str.size();
char ch = str;
int count = 1;
for(int i=1; i<len; i++)
{
if(ch == str[i])
count++;
else
{
cout << count << (ch-'0');
ch = str[i];
count = 1;
}
}
cout << count << (ch - '0') << endl;
}
return 0;
}
[/sourcecode]

poj3427,

## Problem:

Ecology tax

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3267 Accepted: 1672

Description

In a big and rich on natural resources country, the government started a campaign to control deforestation. In fact the government is not too interested in how many trees get fallen, but rather how effectively the wood is utilized. So a law was passed which requires every logging company to pay amount of money in proportion to amount of wood that it wastes during operation.

A felling quota on some territory was allotted to a company in this country. Company lorries may only transport logs of exactly L meters long. So when a tree gets sawed into logs, the remainder is wasted.

Trees in this country grow exactly 1 meter per year, so the company may decrease the amount of tax to be paid by simply waiting for some years. Your task is to determine the number of years needed to achieve smallest possible tax. If there is more than one answer, find minimal (earliest) one.

Input

Input file contains number of trees N, length of log L, followed by integers i1 i2 ... iN — heights of each tree.

#### Constraints

1 ≤ N ≤ 30000, 1 ≤ L, ik ≤ 30000

Output

Output file must contain single integer — number of years to wait.

Sample Input
`Sample Input 13 1 10 15 11Sample Input 23 25 3 6`

Sample Output
`Sample Output 10Sample Output 21`

Hint

Bold texts appearing in the sample sections are informative and do not form part of the actual data.

Source
Northeastern Europe 2006, Far-Eastern Subregion

## Source Code:

//Wed May 5 02:12:32 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N, L;
while (cin >> N >> L)
{
int year = 0;
for (int i = 0; i < N; i++)
{
int number;
cin >> number;
number %= L;
if (number > 0 && year + number < L)
year = L - number;
}
cout << year << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3404,

## Problem:

Bridge over a rough river

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3063 Accepted: 1211

Description

A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs ti seconds to cross the river on the bridge; i=1, ... , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.

Input

The input consists of two lines: the first line contains the value of N and the second one contains the values of ti (separated by one or several spaces).

Output

The output contains one line with the result.

Sample Input
`46 7 6 5`

Sample Output
`29`

Source
Northeastern Europe 2001, Western Subregion

## Solution:

Just like POJ 1700;

## Source Code:

//Fri May 21 15:37:01 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

long long crossriver(vector<int> v, int T)
{
if (T == 1)
{
return v;
}
if (T == 2)
{
return v;
}
if (T == 3)
{
return v + v + v;
}
if (v + 3 * v + v[T - 1] > 2 * v + v + v[T - 2] + v[T - 1])
{
return 2 * v + v[T - 2] + v[T - 1] + crossriver(v, T - 2);
}
else
{
return v + 2 * v + v[T - 1] + crossriver(v, T - 2);
}
}

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int T;
while(cin >> T)
{
vector<int> v;
for(int i=0; i<T; i++)
{
int number;
cin >> number;
v.push_back(number);
}
sort(v.begin(), v.end());
cout << crossriver(v, T) << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3325,

## Problem:

ICPC Score Totalizer Software

 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 5326 Accepted: 3685

Description

The International Clown and Pierrot Competition (ICPC), is one of the most distinguished and also the most popular events on earth in the show business.One of the unique features of this contest is the great number of judges that sometimes counts up to one hundred. The number of judges may differ from one contestant to another, because judges with any relationship whatsoever with a specific contestant are temporarily excluded for scoring his/her performance.

Basically, scores given to a contestant's performance by the judges are averaged to decide his/her score. To avoid letting judges with eccentric viewpoints too much influence the score, the highest and the lowest scores are set aside in this calculation. If the same highest score is marked by two or more judges, only one of them is ignored. The same is with the lowest score. The average, which may contain fractions, are truncated down to obtain final score as an integer.

You are asked to write a program that computes the scores of performances, given the scores of all the judges, to speed up the event to be suited for a TV program.

Input

The input consists of a number of datasets, each corresponding to a contestant's performance. There are no more than 20 datasets in the input.

A dataset begins with a line with an integer n, the number of judges participated in scoring the performance (3 ≤ n ≤ 100). Each of the n lines following it has an integral score s (0 ≤ s ≤ 1000) marked by a judge. No other characters except for digits to express these numbers are in the input. Judges' names are kept secret.

The end of the input is indicated by a line with a single zero in it.

Output

For each dataset, a line containing a single decimal integer indicating the score for the corresponding performance should be output. No other characters should be on the output line.

Sample Input
`31000342052291193253001000020040083532424022742831324025230`

Sample Output
`3427300326`

Source
Japan 2007 Domestic

## Source Code:

//Sun 31 Jan 2010 02:27:56 PM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
int N;
while((cin >> N) && (N != 0))
{
int mmax = 0;
int mmin = 1000;
int sum = 0;
vector<int> v(N, 0);
for(int i=0; i<N; i++)
{
cin >> v[i];
sum += v[i];
mmax = max(mmax, v[i]);
mmin = min(mmin, v[i]);
}
int ret = (sum - mmax - mmin) / (N - 2);
cout << ret << endl;
}
return 0;
}
[/sourcecode]

poj3299,

## Problem:

Humidex

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7083 Accepted: 2800

Description

The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It differs from the heat index used in the United States in using dew point rather than relative humidity.

When the temperature is 30°C (86°F) and the dew point is 15°C (59°F), the humidex is 34 (note that humidex is a dimensionless number, but that the number indicates an approximate temperature in C). If the temperature remains 30°C and the dew point rises to 25°C (77°F), the humidex rises to 42.3.

The humidex tends to be higher than the U.S. heat index at equal temperature and relative humidity.

The current formula for determining the humidex was developed by J.M. Masterton and F.A. Richardson of Canada's Atmospheric Environment Service in 1979.

According to the Meteorological Service of Canada, a humidex of at least 40 causes "great discomfort" and above 45 is "dangerous." When the humidex hits 54, heat stroke is imminent.

The record humidex in Canada occurred on June 20, 1953, when Windsor, Ontario hit 52.1. (The residents of Windsor would not have known this at the time, since the humidex had yet to be invented.) More recently, the humidex reached 50 on July 14, 1995 in both Windsor and Toronto.

The humidex formula is as follows:
`humidex = temperature + hh = (0.5555)× (e - 10.0)e = 6.11 × exp [5417.7530 × ((1/273.16) - (1/(dewpoint+273.16)))]`

where exp(x) is 2.718281828 raised to the exponent x.While humidex is just a number, radio announcers often announce it as if it were the temperature, e.g. "It's 47 degrees out there ... [pause] .. with the humidex,". Sometimes weather reports give the temperature and dewpoint, or the temperature and humidex, but rarely do they report all three measurements. Write a program that, given any two of the measurements, will calculate the third.

You may assume that for all inputs, the temperature, dewpoint, and humidex are all between -100°C and 100°C.

Input

Input will consist of a number of lines. Each line except the last will consist of four items separated by spaces: a letter, a number, a second letter, and a second number. Each letter specifies the meaning of the number that follows it, and will be either T, indicating temperature, D, indicating dewpoint, or H, indicating humidex. The last line of input will consist of the single letter E.

Output
For each line of input except the last, produce one line of output. Each line of output should have the form:
`T number D number H number`

where the three numbers are replaced with the temperature, dewpoint, and humidex. Each value should be expressed rounded to the nearest tenth of a degree, with exactly one digit after the decimal point. All temperatures are in degrees celsius.

Sample Input
`T 30 D 15T 30.0 D 25.0E`

Sample Output
`T 30.0 D 15.0 H 34.0T 30.0 D 25.0 H 42.3`

Source
Waterloo Local Contest, 2007.7.14

## Source Code:

//Tue 02 Feb 2010 01:03:58 AM CST
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;

int main()
{
double temperature,dewpoint,humidex;
double h,e,f1,f2;
char c1,c2;
while(cin >> c1 && c1!='E')
{
// scanf("%lf %c %lf",&f1,&c2,&f2);
cin >> f1 >> c2 >> f2;
switch (c1+c2)
{
case 'T'+'D':
{
temperature = (c1=='T') ? f1:f2;
dewpoint = (c1=='D') ? f1:f2;
e = (double) (6.11 * exp (5417.7530 * ((1/273.16) - (1/(dewpoint+273.16)))));
h = (double) ((0.5555) * (e - 10.0));
humidex = temperature + h;
break;
}
case 'T'+'H':
{
temperature = c1=='T' ? f1:f2;
humidex = (c1=='H') ? f1:f2;
h = humidex - temperature;
e = (double) (h / 0.5555 + 10.0) ;
dewpoint = (double) (1/(-log(e/6.11)/5417.7530 + (1/273.16))-273.16);
break;
}

case 'H'+'D':
{
humidex = (c1=='H') ? f1:f2;
dewpoint = (c1=='D') ? f1:f2;
e = (double) (6.11 * exp (5417.7530 * ((1/273.16) - (1/(dewpoint+273.16)))));
h = (double) ((0.5555) * (e - 10.0));
temperature = humidex - h;
break;
}
}
printf("T %.1f D %.1f H %.1f\n",temperature,dewpoint,humidex);
// scanf("%c",&c1);
}
return 0;
}
[/sourcecode]

poj3230,

## Problem:

Travel

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2951 Accepted: 1240

Description

One traveler travels among cities. He has to pay for this while he can get some incomes.

Now there are n cities, and the traveler has m days for traveling. Everyday he may go to another city or stay there and pay some money. When he come to a city ,he can get some money. Even when he stays in the city, he can also get the next day's income. All the incomes may change everyday. The traveler always starts from city 1.

Now is your turn to find the best way for traveling to maximize the total income.

Input

There are multiple cases.

The first line of one case is two positive integers, n and m .n is the number of cities, and m is the number of traveling days. There follows n lines, one line n integers. The j integer in the i line is the expense of traveling from city i to city j. If i equals to j it means the expense of staying in the city.

After an empty line there are m lines, one line has n integers. The j integer in the i line means the income from city j in the i day.

The input is finished with two zeros.
n,m<100.

Output
You must print one line for each case. It is the max income.

Sample Input
`3 33 1 22 3 11 3 22 4 34 3 23 4 20 0`

Sample Output
`8`

Hint
In the Sample, the traveler can first go to city 2, then city 1, and finish his travel in city 1. The total income is:
-1+4-2+4-1+4=8;

Source

## Solution:

Initially, I use the dfs to implement every possible way, but it will get a TLE. (No doubt).

Then, DP is a good choice to implement it.

Basically, it's a straight forward dynamic programming problem.

Initialization:

dp = 0; Day 0, City 1;

dp[k] = dp + income[k] - cost[k]; 1<=k <=n;

The state formula is like:

ith day, city j:

dp[i][j]  =  max{ dp[i-1][j] + income[i][j] - cost[j][j],  (1<=k<=n) dp[i-1][k] + income[i][j] - cost[k][j]};

## Source Code:

//Fri Apr 9 00:58:12 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int maxincome = -1;
int n, m;

void Solve(vector<vector<int> > cost, vector<vector<int> > income, int city,
int currentDay, int day, int maximum)
{
maximum += income[city][currentDay - 1];
if (day == m)
{
maxincome = max(maxincome, maximum);
return;
}
for (int i = 0; i < n; i++)
{
if (i == city)
Solve(cost, income, city, currentDay + 1, day + 1, maximum
- cost[city][city]);
else
Solve(cost, income, i, 1, day + 1, maximum - cost[city][i]);
}
}

int main(int argc, char* argv[])
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
while (cin >> n >> m && (n || m))
{
vector<vector<int> > cost(100, vector<int> (100, 0));
vector<vector<int> > income(100, vector<int> (100, 0));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cin >> cost[i][j];
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
cin >> income[i][j];
}
// Solve(cost, income, 1, 1, 1, 0);

vector<vector<int> > dp(100, vector<int> (100, 0));

for (int i = 1; i <= n; i++)
{
dp[i] = dp - cost[i] + income[i];
}

for (int i = 2; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
dp[i][j] = dp[i - 1][j] + income[i][j] - cost[j][j];
for (int k = 1; k <= n; k++)
{
dp[i][j] = max(dp[i][j], dp[i - 1][k] + income[i][j]
- cost[k][j]);
}
maxincome = max(maxincome, dp[m][j]);
}
}
cout << maxincome << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
[/sourcecode]

poj3176,

## Problem:

Cow Bowling

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7685 Accepted: 5014

Description
The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:
`          7        3   8      8   1   0    2   7   4   4  4   5   2   6   5`

Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame.

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input
Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output
Line 1: The largest sum achievable using the traversal rules

Sample Input
`573 88 1 02 7 4 44 5 2 6 5`

Sample Output
`30`

Hint
Explanation of the sample:
`          7         *        3   8       *      8   1   0       *    2   7   4   4       *  4   5   2   6   5`

The highest score is achievable by traversing the cows as shown above.

Source
USACO 2005 December Bronze

## Solution:

Basic Dynamic Programming problem.

## Source Code:

//Sat 30 Jan 2010 09:57:32 PM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
int N;
cin >> N;
vector<vector<int> > v;
for(int i=0; i<N; i++)
{
vector<int> temp (i+1);
for(int j=0; j<=i; j++)
{
cin >> temp[j];
}
v.push_back(temp);
}
for(int i=1; i<N; i++)
{
for(int j=0; j<=i; j++)
{
if(j==0) v[i][j] += v[i-1][j];
else if(j==i) v[i][j] += v[i-1][j-1];
else v[i][j] += max(v[i-1][j-1], v[i-1][j]);
}
}
int mmax = 0;
for(int i=0; i<N; i++)
mmax = max(mmax, v[N-1][i]);
cout << mmax << endl;
return 0;
}
[/sourcecode]

poj3173,

## Problem:

Parkside's Triangle

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5634 Accepted: 3367

Description
Bessie taught the cows to make Parkside's Triangle. It is generated from two numbers: the size and the seed. The size N (1 <= N <= 20) determines how many rows are in the triangle and the seed S (1 <= S <= 9) determines the first number in the triangle. Here are two examples:
` N=5, S=3                  N=6, S=1  3 4 6 9 4                1 2 4 7 2 7      5 7 1 5                  3 5 8 3 8        8 2 6                    6 9 4 9          3 7                      1 5 1           8                        6 2                                     3`

The first line of any triangle has no blanks at its front.

Analyze the above examples, discover the rule, and write a program that will generate Parkside's Triangle given any size N (1 <= N <= 20) and any seed S (1 <= S <= 9).

Input
Line 1: Two space-separated integers: N and S

Output
Lines 1..N: Parkside's Triangle as above; no trailing blanks on any line.

Sample Input
`5 3`

Sample Output
`3 4 6 9 4  5 7 1 5    8 2 6      3 7        8`

Source
USACO 2006 December Bronze

## Solution:

Easy Math problem,
Take care of the space between numbers.

## Source Code:

//Sat Apr 24 01:39:44 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int N, S;
while (cin >> N >> S)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int a = ((j + 1) * j / 2 + i + S) % 9;
if (a == 0)
a = 9;
if (i > j)
cout << " ";
else if (j < N - 1)
cout << a << " ";
else
cout << a << endl;
}
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
[/sourcecode]

poj3117,

## Problem:

World Cup

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5806 Accepted: 3002

Description

A World Cup of association football is being held with teams from around the world. The standing is based on the number of points won by the teams, and the distribution of points is done the usual way. That is, when a teams wins a match, it receives 3 points; if the match ends in a draw, both teams receive 1 point; and the loser doesn’t receive any points.

Given the current standing of the teams and the number of teams participating in the World Cup, your task is to determine how many matches ended in a draw till the moment.

Input

The input contains several test cases. The first line of a test case contains two integers T and N, indicating respectively the number of participating teams (0 ≤ T ≤ 200) and the number of played matches (0 ≤ N ≤ 10000). Each one of the T lines below contains the name of the team (a string of at most 10 letter and digits), followed by a whitespace, then the number of points that the team obtained till the moment. The end of input is indicated by T = 0.

Output

For each one of the test cases, your program should print a single line containing an integer, representing the quantity of matches that ended in a draw till the moment.

Sample Input
`3 3Brasil 3Australia 3Croacia 33 3Brasil 5Japao 1Australia 10 0`

Sample Output
`02`

Source
South America 2006, Brazil Subregion

## Solution:

Easy straight forward.

## Source Code:

//Tue May 25 00:56:40 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int T, N;
while (cin >> T >> N && T)
{
long long sum = 0;
string s;
int score;
for (int i = 0; i < T; i++)
{
cin >> s >> score;
sum += score;
}
cout << 3 * N - sum << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj3100,

## Problem:

Root of the Problem

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8575 Accepted: 4589

Description

Given positive integers B and N, find an integer A such that AN is as close as possible to B. (The result A is an approximation to the Nth root of B.) Note that AN may be less than, equal to, or greater than B.

Input

The input consists of one or more pairs of values for B and N. Each pair appears on a single line, delimited by a single space. A line specifying the value zero for both B and N marks the end of the input. The value of B will be in the range 1 to 1,000,000 (inclusive), and the value of N will be in the range 1 to 9 (inclusive).

Output

For each pair B and N in the input, output A as defined above on a line by itself.

Sample Input
`4 35 327 3750 51000 52000 53000 51000000 50 0`

Sample Output
`123444516`

Source
Mid-Central USA 2006

## Solution:

Easy implementation. But take care.

## Source Code:

//Sun 31 Jan 2010 04:43:48 PM CST
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
int B, N;
cin >> B >> N;
while(B + N != 0)
{
int ret = (int) pow(B, 1.0/N);
int res1 = (int) pow(ret, 1.0*N);
int res2 = (int) pow(ret+1, 1.0*N);
if(res1+res2 > 2*B) cout << ret << endl;
else cout << ret+1 << endl;
cin >> B >> N;
}
return 0;
}
[/sourcecode]

poj3062,

## Problem:

Celebrity jeopardy

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9439 Accepted: 5285

Description
It's hard to construct a problem that's so easy that everyone will get it, yet still difficult enough to be worthy of some respect. Usually, we err on one side or the other. How simple can a problem really be?

Here, as in Celebrity Jepoardy, questions and answers are a bit confused, and, because the participants are elebrities, there’s a real need to make the challenges simple. Your program needs to prepare a question to be solved --- an equation to be solved --- given the answer. Specifically, you have to write a program which finds the simplest possible equation to be solved given the answer, considering all possible equations using the standard mathematical symbols in the usual manner. In this context, simplest can be defined unambiguously several different ways leading to the same path of resolution. For now, find the equation whose transformation into the desired answer requires the least effort.

For example, given the answer X = 2, you might create the equation 9 - X = 7. Alternately, you could build the system X > 0; X^2 = 4. These may not be the simplest possible equations. Solving these mind-scratchers might be hard for a celebrity.

Input
Each input line contains a solution in the form <symbol> = <value>

Output
For each input line, print the simplest system of equations which would to lead to the provided solution, respecting the use of space exactly as in the input.

Sample Input
`Y = 3X=9`

Sample Output
`Y = 3X=9`

Source
Southeastern Europe 2006

## Source Code:

//Tue May 25 14:20:09 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main( int argc, const char* argv[] )
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
string str;
while(getline(cin, str))
{
cout << str << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj2909,

## Problem:

Goldbach's Conjecture
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7566 Accepted: 4382
Description
For any even number n greater than or equal to 4, there exists at least one pair of prime numbers p1 and p2 such that
n = p1 + p2
This conjecture has not been proved nor refused yet. No one is sure whether this conjecture actually holds. However, one can find such a pair of prime numbers, if any, for a given even number. The problem here is to write a program that reports the number of all the pairs of prime numbers satisfying the condition in the conjecture for a given even number.
A sequence of even numbers is given as input. There can be many such numbers. Corresponding to each number, the program should output the number of pairs mentioned above. Notice that we are interested in the number of essentially different pairs and therefore you should not count (p1, p2) and (p2, p1) separately as two different pairs.
Input
An integer is given in each input line. You may assume that each integer is even, and is greater than or equal to 4 and less than 215. The end of the input is indicated by a number 0.
Output
Each output line should contain an integer number. No other characters should appear in the output.
Sample Input
```6
10
12
0```
Sample Output
```1
2
1```
Source
Svenskt Mästerskap i Programmering/Norgesmesterskapet 2002

## Solution:

Just like POJ 2262.

## Source Code:

//Fri May 21 17:33:08 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#define m 1000000
bool v[m];

using namespace std;

void Prime()
{
v = v = true;
for (int i = 2; i < m; i++)
if (v[i] == false)
for (int j = i + i; j < m; j += i)
v[j] = true;
return;
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
Prime();
int N;
while (cin >> N && N)
{
long count = 0;
if (N % 2 != 0 && v[N - 2] == false)
{
count++;
}
for (int i = 3; i <= N / 2; i += 2)
{
if (v[i] == false && v[N - i] == false)
{
count++;
}
}
cout << count << endl;
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}