1.6.1 状态空间:
1.6.2 盲目搜索算法:
1.6.3 启发式搜索算法:
1.6.4 博弈问题算法:
1.6.5 剪枝:
1.6.6 路径寻找问题:
1.6.7 约束满足问题:
Saturday, October 30, 2010
第一章_1.4 数据结构(2) ---- 拓宽和应用举例:
1.4.1 并查集:
1.4.2 堆及其变种:
1.4.3 字典的两种实现方式: 哈西表, 二叉搜索树:
1.4.4 两个特殊树结构: 线段树和 Trie:
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 栈和队列:
1.3.2 串:
1.3.3 树和二叉数:
1.3.4 图及其基本算法:
1.3.5 排序与检索基本算法:
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 枚举:
1.2.2 贪心法:
1.2.3 递归与分治法:
1.2.4 递归:
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(),并在代码中调用该函数实现上述功能。该函数的实现要考虑各种可能的参数取值,以确保程序不出现崩溃。
返回值:所拷贝的字符串长度。如果拷贝失败,则返回0。
具体要求:实现如下函数原型SafeStrcpy2KeyWord(),并在代码中调用该函数实现上述功能。该函数的实现要考虑各种可能的参数取值,以确保程序不出现崩溃。
int SafeStrcpy2KeyWord(char* pDestBuffer, //拷贝的目的地地址
char* pSourceString, //拷贝的源地址
int nDestBufferSize, //拷贝的目的地缓冲区长度
char* szKeyWord); //指定关键字符串
返回值:所拷贝的字符串长度。如果拷贝失败,则返回0。
Input
输入包含多组数据,以EOF结束
每组数据第一行为不含空格的源字符串,长度小于256;接下来的一行或多行都是关键字串(长度小于16),一直到END结束。“NULL”表示关键字串为空,此时输出的拷贝后的长度应为0,拷贝后的字符串为空串(也用”NULL”表示,见下文)。
每组数据第一行为不含空格的源字符串,长度小于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小时制格式的字符串。
对于给定的采用”yyyy/mm/dd”加24小时制(用短横线”-”连接)来表示日期和时间的字符串,请编程实现将其转换成”mm/dd/yyyy”加12小时制格式的字符串。
Input
第一行为一个整数T(T<=10),代表总共需要转换的时间日期字符串的数目。
接下来的总共T行,每行都是一个需要转换的时间日期字符串。
接下来的总共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),用逗号","间隔
接下来每行输入一个小孩的名字(人名不超过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 ≤ 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
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 ≤ xi ≤ 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 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 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 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 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 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
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.
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:
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.
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;
-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][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:
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.
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.
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:
The highest score is achievable by traversing the cows as shown above.
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:
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).
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 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 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.
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 p1 and p2 such that
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.
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[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;
}
Location:
6746 Schneider Ave, Hammond, IN 46323, USA
Labels:
poj
Subscribe to:
Posts
(
Atom
)