第一章_1.6 状态空间搜索

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.

 

poj_3753_根据关键字进行字符串拷贝.cpp

Problem Links:

poj3753,

Problem:

根据关键字进行字符串拷贝

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

Description

把源字符串拷贝到目的字符串，如果指定关键字，则以该关键字结束(不包括关键字本身)，如果拷贝失败，则得到空串。
具体要求：实现如下函数原型SafeStrcpy2KeyWord()，并在代码中调用该函数实现上述功能。该函数的实现要考虑各种可能的参数取值，以确保程序不出现崩溃。

int SafeStrcpy2KeyWord(char* pDestBuffer,	//拷贝的目的地地址

		       char* pSourceString,	//拷贝的源地址

		       int nDestBufferSize,	//拷贝的目的地缓冲区长度

		       char* szKeyWord);	//指定关键字符串

返回值：所拷贝的字符串长度。如果拷贝失败，则返回0。

Input

输入包含多组数据，以EOF结束
每组数据第一行为不含空格的源字符串，长度小于256；接下来的一行或多行都是关键字串（长度小于16），一直到END结束。“NULL”表示关键字串为空，此时输出的拷贝后的长度应为0，拷贝后的字符串为空串（也用”NULL”表示，见下文）。

Output

对于每组数据输出拷贝的长度和拷贝后的目的字符串，以空格分隔。如果该目的字符串为空，则用”NULL”表示。

Sample Input

/home/tony/work_server/1/rtest/relayer.out
/
/t
/1/r
.
NULL
END

Sample Output

0 NULL
5 /home
22 /home/tony/work_server
38 /home/tony/work_server/1/rtest/relayer
0 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:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3752_字母旋转游.cpp

Problem Links:

poj3752,

Problem:

字母旋转游戏

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

Description

给定两个整数M，N，生成一个M*N的矩阵，矩阵中元素取值为A至Z的26个字母中的一个，A在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过26时又从A开始填充。例如，当M=5，N=8时，矩阵中的内容如下：

   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:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3751_时间日期格式转换.cpp

Problem Links:

poj3751,

Problem:

时间日期格式转换

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

Description

世 界各地有多种格式来表示日期和时间。对于日期的常用格式，在中国常采用格式的是“年年年年/月月/日日”或写为英语缩略表示的”yyyy/mm/dd”， 此次编程大赛的启动日期“2009/11/07”就是符合这种格式的一个日期，而北美所用的日期格式则为“月月/日日/年年年年”或”mm/dd /yyyy”，如将“2009/11/07”改成这种格式，对应的则是”11/07/2009”。对于时间的格式，则常有12小时制和24小时制的表示方 法，24小时制用0-24来表示一天中的24小时，而12小时制只采用1-12表示小时，再加上am/pm来表示上午或下午，比如”17:30:00”是 采用24小时制来表示时间，而对应的12小时制的表示方法是”05:30:00pm”。注意12:00:00pm表示中午12点，而12:00:00am 表示凌晨12点。

对于给定的采用”yyyy/mm/dd”加24小时制（用短横线”-”连接）来表示日期和时间的字符串，请编程实现将其转换成”mm/dd/yyyy”加12小时制格式的字符串。

Input

第一行为一个整数T（T<=10），代表总共需要转换的时间日期字符串的数目。
接下来的总共T行，每行都是一个需要转换的时间日期字符串。

Output

分行输出转换之后的结果

Sample Input

2
2009/11/07-12:12:12
1970/01/01-00:01:01

Sample Output

11/07/2009-12:12:12pm
01/01/1970-12:01:01am

Hint

注意中午和凌晨时间的特殊表示

Source

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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[11]-'0') + (str[12]-'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]

poj_3750_小孩报数问题.cpp

Problem Links:

poj3750,

Problem:

小孩报数问题

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

Description

有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。

Input

第一行输入小孩的人数N（N<=64）
接下来每行输入一个小孩的名字(人名不超过15个字符)
最后一行输入W,S (W < N)，用逗号","间隔

Output

按人名输出小孩按顺序出列的顺序，每行输出一个人名

Sample Input

5
Xiaoming
Xiaohua
Xiaowang
Zhangsan
Lisi
2,3

Sample Output

Zhangsan
Xiaohua
Xiaoming
Xiaowang
Lisi

Source

Solution:

Simulation.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3748_位操作.cpp

Problem Links:

poj3748,

Problem:

位操作

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

Description

假设你工作在一个32位的机器上，你需要将某一个外设寄存器的第X位设置成0(最低位为第0位，最高位为第31位)，将第Y位开始的连续三位设置成110（从高位到低位的顺序），而其他位保持不变。对给定的寄存器值R，及X，Y，编程计算更改后的寄存器值R。

Input

仅一行，包括R,X,Y，以逗号","分隔，R为16进制表示的32位整数，X,Y在0-31之间且Y>=3，(Y-X)的绝对值>=3，保证两次置位不会重合

Output

更改后的寄存器值R（16进制输出）

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:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3650_The_Seven_Percent_Solution.cpp

Problem Links:

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%21
http://icpc.baylor.edu/icpc/
plain_vanilla
%28%2a%2a%29
?
the%207%25%20solution

Source

Mid-Central USA 2007

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3637_Shopaholic.cpp

Problem Links:

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 ≤ p_i ≤ 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

1
6
400 100 200 350 300 250

Sample Output

400

Source

Nordic 2007

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3632_Optimal_Parking.cpp

Problem Links:

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 ≤ x_i ≤ 99.

Output

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

Sample Input

2
4
24 13 89 37
6
7 30 41 14 39 42

Sample Output

152
70

Source

Nordic 2007

Solution:

Basic one.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3673_Cow_Multiplication.cpp

Problem Links:

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

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3630_Phone_List.cpp

Problem Links:

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

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

NO
YES

Source

Nordic 2007

Solution:

Trie Tree.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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[10];
};

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]

poj_3619_Speed_Reading.cpp

Problem Links:

poj3619,

Problem:

Speed Reading

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 S_i (1 ≤ S_i ≤ 100) pages per minute, a maximum consecutive reading time T_i (1 ≤ T_i ≤ 100) minutes, and a minimum rest time R_i (1 ≤ R_i ≤ 100) minutes. The cow can read at a rate of S_i pages per minute, but only for T_i minutes at a time. After she stops reading to rest, she must rest for R_i 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: S_i , T_i , and R_i

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 3
2 4 1
6 1 5
3 3 3

Sample Output

6
7
7

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:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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++)
{//The total Reading Time; Max Reading Time; Min Rest time;
cin >> v[i][0] >> v[i][1] >> v[i][2];
v[i][0] = (int) ((N + v[i][0] - 1) / v[i][0]);
// cout << v[i][0] << v[i][1] << v[i][2] << endl;
int times = (int) ((v[i][0] + v[i][1] - 1) / v[i][1]);
int total = v[i][0] + v[i][2]*(times-1);
cout << total << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj_3589_Number-guessing_Game.cpp

Problem Links:

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

2
5204 4902
0123 3210

Sample Output

1A2B
0A4B

Source

South Central China 2008 hosted by NUDT

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3517_AndThenThereWasOne.cpp

Problem Links:

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 ≤ m ≤ n

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 3
100 9999 98
10000 10000 10000
0 0 0

Sample Output

1
93
2019

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
更简单一些，就是先求出n-1的解，再进行一次类似旋转的操作（即：（f（n-1）+m+1+n）%n），即可得到解；

/*约瑟夫问题的数学方法
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：
这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
////////2008-04-08;
#include<stdio.h>
int main()
{
int a[10001];
int m,n,k;
while(scanf("%d%d%d",&n,&k,&m)==3&&(n+m+k)>0)
{
int i;
a[1]=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

Problem Links:

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

3
122344111
1111111111
12345

Sample Output

1122132431
101
1112131415

Source

Rocky Mountain 2007

Solution:

Straight forward.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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[0];
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]

poj_3427_Ecology_tax.cpp

Problem Links:

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 i₁ i₂ ... i_N — heights of each tree.

Constraints

1 ≤ N ≤ 30000, 1 ≤ L, i_k ≤ 30000

Output

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

Sample Input

Sample Input 1
3 1 
10 15 11
Sample Input 2
3 2
5 3 6

Sample Output

Sample Output 1
0
Sample Output 2
1

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

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3404_Bridge_over_a_rough_river.cpp

Problem Links:

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 t_i seconds to cross the river on the bridge; i=1, ... , N (t_i 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 t_i (separated by one or several spaces).

Output

The output contains one line with the result.

Sample Input

4
6 7 6 5

Sample Output

29

Source

Northeastern Europe 2001, Western Subregion

Solution:

Just like POJ 1700;

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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[0];
}
if (T == 2)
{
return v[1];
}
if (T == 3)
{
return v[0] + v[1] + v[2];
}
if (v[0] + 3 * v[1] + v[T - 1] > 2 * v[0] + v[1] + v[T - 2] + v[T - 1])
{
return 2 * v[0] + v[T - 2] + v[T - 1] + crossriver(v, T - 2);
}
else
{
return v[0] + 2 * v[1] + 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]

poj_3325_ICPC_Score_Totalizer_Software.cpp

Problem Links:

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

3
1000
342
0
5
2
2
9
11
932
5
300
1000
0
200
400
8
353
242
402
274
283
132
402
523
0

Sample Output

342
7
300
326

Source

Japan 2007 Domestic

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3299_Humidex.cpp

Problem Links:

poj3299,

Problem:

Humidex

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

Description

Adapted from Wikipedia, the free encyclopedia

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 + h
h = (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 15
T 30.0 D 25.0
E

Sample Output

T 30.0 D 15.0 H 34.0
T 30.0 D 25.0 H 42.3

Source

Waterloo Local Contest, 2007.7.14

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3230_Travel.cpp

Problem Links:

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 3
3 1 2
2 3 1
1 3 2

2 4 3
4 3 2
3 4 2

0 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

South Central China 2007 hosted by NUDT

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][1] = 0; Day 0, City 1;

dp[1][k] = dp[0][1] + income[1][k] - cost[1][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:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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[1][i] = dp[0][1] - cost[1][i] + income[1][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]

poj_3176_Cow_Bowling.cpp

Problem Links:

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

5
7
3 8
8 1 0
2 7 4 4
4 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:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3173_Parkside_s_Triangle.cpp

Problem Links:

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:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3117_World_Cup.cpp

Problem Links:

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 3
Brasil 3
Australia 3
Croacia 3
3 3
Brasil 5
Japao 1
Australia 1
0 0

Sample Output

0
2

Source

South America 2006, Brazil Subregion

Solution:

Easy straight forward.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3100_Root_of_the_Problem.cpp

Problem Links:

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 A^N is as close as possible to B. (The result A is an approximation to the Nth root of B.) Note that A^N 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 3
5 3
27 3
750 5
1000 5
2000 5
3000 5
1000000 5
0 0

Sample Output

1
2
3
4
4
4
5
16

Source

Mid-Central USA 2006

Solution:

Easy implementation. But take care.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_3062_Celebrity_jeopardy.cpp

Problem Links:

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 = 3
X=9

Sample Output

Y = 3
X=9

Source

Southeastern Europe 2006

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//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]

poj_2909_Goldbach_s_Conjecture.cpp

Problem Links:

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 p₁ and p₂ such that

n = p₁ + p₂

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 (p₁, p₂) and (p₂, p₁) 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 2¹⁵. 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[0] = v[1] = 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;
}