poj3982,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3612 Accepted: 1571
Description

Input

Output

Sample Input
`1 1 1`
Sample Output
`69087442470169316923566147`
Source

## Solution:

Use string instead of the long long. The system won't allocate that much memory for it.

## Source Code:

//Tue Nov 23 14:30:01 CST 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 sz = max(A.size(), B.size());
int flag = 0;
if(sz > (int)A.size()) A += string(sz-A.size(), '0');
if(sz > (int)B.size()) B += string(sz-B.size(), '0');
string ret = "";
for(int i=0; i<sz; i++)
{
int temp = A[i]-'0' + B[i] - '0' + flag;
flag = temp > 9 ? 1 : 0;
temp %= 10;
ret += ('0' + temp);
}
if(flag == 1)
ret += ('0' + flag);
//  cout << A << ", " << B << ", " << ret << endl;
return ret;
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
string a0, a1, a2;
while (cin >> a0 >> a1 >> a2)
{
vector<string> ret(100, "");
reverse(a0.begin(), a0.end());
reverse(a1.begin(), a1.end());
reverse(a2.begin(), a2.end());
ret[0] = a0;
ret[1] = a1;
ret[2] = a2;
for (int i = 3; i < 100; i++)
{
}
reverse(ret[99].begin(), ret[99].end());
cout << ret[99] << endl;
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}

poj3981,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3931 Accepted: 1933
Description

Input

Output

Sample Input
`you are what you do`
Sample Output
`we are what we do`
Source

## Solution:

Straight forward.

## Source Code:

//Tue Nov 23 14:10:28 CST 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))
{
int sz = str.size();
string ret = "";
for (int i = 0; i < sz;)
{
if (str[i] != 'y')
{
ret += str[i];
i++;
}
else
{
if (i + 2 < sz && str[i + 1] == 'o' && str[i + 2] == 'u')
{
ret += "we";
i += 3;
}
else
{
ret += str[i];
i++;
}
}
}
cout << ret << endl;
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}

poj3980,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4360 Accepted: 2732
Description

Input

Output

Sample Input
```5 3
100 2```
Sample Output
```2
0```
Source

## Solution:

Straight forward.

Take care of: 1st, use scanf instead of cin.

## Source Code:

//Tue Nov 23 13:57:52 CST 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 mod(int m, int n)
{
return m%n;
}

int main( int argc, const char* argv[] )
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
int a, b;
while(scanf("%d%d", &a, &b) != EOF)
{
printf("%d\n", mod(a, b));
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}

poj3979,

## Problem:

 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5903 Accepted: 1884
Description

Input

Output

Sample Input
```1/8+3/8
1/4-1/2
1/3-1/3```
Sample Output
```1/2
-1/4
0```
Source

## Solution:

PS: Take care of each situation that could happen.

1st, if the numerator is 0;

2nd, if they have gcd greater than 1 after the operation.

## Source Code:

//Mon Nov 22 23:32:14 CST 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 gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
int a, b, c, d;
char ch1, ch2;
while (cin >> a >> ch1 >> b >> ch2 >> c >> ch1 >> d)
{
//cout << a << b << c << d << endl;

int temp = b / gcd(b, d) * d;
int flag = 1;
switch (ch2)
{
case '+':
a = a * (temp / b) + c * (temp / d);
break;
case '-':
a = a * (temp / b) - c * (temp / d);
flag = a < 0 ? -1 : 1;
a = a < 0 ? -a : a;
}
int temp2 = gcd(a, temp);
//cout << temp2 << endl;
a /= temp2;
temp /= temp2;
if(a == 0)  //One WA here w/o considering if a is 0;
{
cout << "0" << endl;
continue;
}
if(temp == 1)
{
cout << a*flag << endl; //One WA here w/o *flag;
continue;
}
cout << a * flag << "/" << temp << endl;
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}

poj3507,

## Problem:

Judging Olympia
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5058 Accepted: 2430
Description
For years, a group of Regional Contest Directors (RCDs) of the ACM International Collegiate Programming Contest (ICPC) have been unsatisfied with the way contest submissions get ranked. The group sees it is academically wrong to emphasize the importance of program correctness, disregarding the “quality” of the program itself. After all, programming as a profession promotes design, style, maintainability, etc. and not just correctness. The group’s suggestion is to have a panel of six judges. Each judge is assigned the task of grading the submissions based on a particular aspect: 1) Correctness; 2) Robustness; 3) Overall design; 4) Clarity; 5) Coding style; and finally 6) Maintainability. The final grade of a submission would be the average of the six grades it gets.
The old guards of the current ICPC judging style have always responded that it is not possible to impartially judge a program on anything but correctness. How can the ICPC be certain that judging is fair? In other words, how can the ICPC be sure that non of the judges is favoring certain teams and disadvantaging others? Any hint of accusation to the judging process and ICPC loses the prestigious status it worked on for years. (Alright! So they do have a point.) Still, this hasn’t stopped other domains from judging candidates based on subjective metrics. Take for example Gymnastics, or The Nobel Prizes, or even the ACM’s very own Doctoral Dissertation Award. These are all highly respected awards where the winner is selected by judges using subjective metrics. ICPC could use a new judging system based on what is used in gymnastics. Rather than having each judge grade a certain aspect of the program, each of the six judges would assign an overall grade (out of ten) based on all of the six metrics mentioned above. To enforce impartiality, the final grade of a submission would be calculated as the average of all the grades after deleting two grades: The highest and the lowest. Any judge that favors a certain team (and assigns them an undeserved high grade,) risks the possibility of that grade being dismissed. Similarly, any judge that attempts to disadvantage a team by assigning them a low grade faces a similar risk.
Write a program to print the final grade of a submission.
Input
Your program will be tested on one or more test cases. Each test case is described on a single input line listing the grades of the judges. The end of the test cases is identified with a dummy test case with all the grades being zero.
Output
For each test case, print the grade on a separate line (without unnecessary decimal points and/or zeros.)
Sample Input
```8 8 8 4 4 4
8 8 6 4 4 3
0 0 0 0 0 0```
Sample Output
```6
5.5```
Source

## Solution:

Easy implementation;

## Source Code:

//Sun Nov 14 20:37:24 CST 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 a[6];
while(cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] && (a[0]||a[1]||a[2]||a[3]||a[4]||a[5]))
{
int mmax = a[0];
int mmin = a[0];
int sum = a[0];
for(int i=1; i<6; i++)
{
mmax = max(mmax, a[i]);
mmin = min(mmin, a[i]);
sum += a[i];
}
cout << 1.0*(sum - mmax - mmin)/4. << endl;
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}

## Saturday, October 30, 2010

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

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

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

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

1.4.1 并查集:

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

1.4.2 堆及其变种:

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

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

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

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

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

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

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

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

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

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

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

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

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

poj3753,

## Problem:

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

Description

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

Input

Output

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

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

Source

## Solution:

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

## Source Code:

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

using namespace std;

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

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

poj3752,

## Problem:

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

Description

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

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

Output

Sample Input
`4 9`

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

Source

## Solution:

Basically, it's just a straight forward  simulation.

In each state, select the next state.

## Source Code:

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

using namespace std;

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

poj3751,

## Problem:

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

Description

Input

Output

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

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

Hint

Source

## Source Code:

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

int main()
{
string str;
int T;
cin >> T;
for(int i=0; i<T; i++)
{
string output;
cin >> str;
output += str.substr(5,5);
output += "/";
output += str.substr(0,4);
output += "-";
//output += str.substr(11);
int time = 10 * (str[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]

poj3750,

## Problem:

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

Description

Input

Output

Sample Input
`5XiaomingXiaohuaXiaowangZhangsanLisi2,3`

Sample Output
`ZhangsanXiaohuaXiaomingXiaowangLisi`

Source

Simulation.

## Source Code:

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

using namespace std;

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

poj3748,

## Problem:

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

Description

Input

Output

Sample Input
`12345678,0,3`

Sample Output
`1234567c`

Source

## Solution:

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

PS, take care of the cin and cout.

## Source Code:

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

using namespace std;

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

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

poj3650,

## Problem:

The Seven Percent Solution

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

Description

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

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

Input

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

Output

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

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

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

Source
Mid-Central USA 2007

## Source Code:

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

using namespace std;

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

poj3637,

## Problem:

Shopaholic

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

Description

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

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

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

Input

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

Output

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

Sample Input
`16400 100 200 350 300 250`

Sample Output
`400`

Source
Nordic 2007

## Source Code:

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

using namespace std;

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

poj3632,

## Problem:

Optimal Parking

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

Description

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

Input

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

Output

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

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

Sample Output
`15270`

Source
Nordic 2007

Basic one.

## Source Code:

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

using namespace std;

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

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

poj3673,

## Problem:

Cow Multiplication

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

Description

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

Input

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

Output

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

Sample Input
`123 45`

Sample Output
`54`

Source
USACO 2008 February Bronze

## Source Code:

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

using namespace std;

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

poj3630,

## Problem:

Phone List

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

Description

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

• Emergency 911

• Alice 97 625 999

• Bob 91 12 54 26

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

Input

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

Output

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

Sample Input
`2391197625999911254265113123401234401234598346`

Sample Output
`NOYES`

Source
Nordic 2007

Trie Tree.

## Source Code:

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

int Count;

class TreeNode
{
public:
bool istring;
TreeNode *child[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]

poj3619,

## Problem:

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

Description

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

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

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

Input

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

Output

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

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

Sample Output
`677`

Source
USACO 2007 November Bronze

## Solution:

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

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

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

## Source Code:

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

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N, K;
while (cin >> N >> K)
{
vector<vector<int> > v(K, vector<int> (3));
for (int i = 0; i < K; i++)
cin >> v[i][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]

poj3589,

## Problem:

Number-guessing Game

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

Description

Larry likes playing the number-guessing game.

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

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

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

Input

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

Output

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

Sample Input
`25204 49020123 3210`

Sample Output
`1A2B0A4B`

Source
South Central China 2008 hosted by NUDT

## Source Code:

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

using namespace std;

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

poj3517,

## Problem:

And Then There Was One

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

Description

Let’s play a stone removing game.

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

 Initial state Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Final state

Figure 1: An example game

Initial state: Eight stones are arranged on a circle.

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

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

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

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

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

Input

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

n k m

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

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

The number of datasets is less than 100.

Output

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

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

Sample Output
`1932019`

Source
Japan 2007

## Solution:

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

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

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

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

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

## Source Code:

////////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

poj3438, spoj03081,

## Problem:

Look and Say

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

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

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

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

Sample Input
`3122344111111111111112345`

Sample Output
`11221324311011112131415`

Source
Rocky Mountain 2007

## Solution:

Straight forward.

## Source Code:

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

using namespace std;

int main()
{
int N;
cin >> N;
for(int i=0; i<N; i++)
{
string str;
cin >> str;
int len = str.size();
char ch = str[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]