## Wednesday, February 23, 2011

### poj_2656_Unhappy_Jinjin.cpp

poj2656,

Problem:
Unhappy Jinjin
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8014 Accepted: 5933
Description
Jinjin is a junior school student. Besides the classes in school, Jinjin's mother also arranges some supplementary classes for her. However, if Jinjin studies for more than eight hours a day, she will be unhappy on that day. On any day she gets unhappy, the more time she studies, the unhappier she will be. Now we got Jinjin's class schedule for the next several days and your task is to find out whether she will be unhappy on these days; if she will be unhappy, on which day she will be the unhappiest.

poj2719,

## Problem:

Faulty Odometer
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7609 Accepted: 4711
Description
You are given a car odometer which displays the miles traveled as an integer. The odometer has a defect, however: it proceeds from the digit 3 to the digit 5, always skipping over the digit 4. This defect shows up in all positions (the one's, the ten's, the hundred's, etc.). For example, if the odometer displays 15339 and the car travels one mile, odometer reading changes to 15350 (instead of 15340).
Input
Each line of input contains a positive integer in the range 1..999999999 which represents an odometer reading. (Leading zeros will not appear in the input.) The end of input is indicated by a line containing a single 0. You may assume that no odometer reading will contain the digit 4.
Output
Each line of input will produce exactly one line of output, which will contain: the odometer reading from the input, a colon, one blank space, and the actual number of miles traveled by the car.
Sample Input
```13
15
2003
2005
239
250
1399
1500
999999
0```
Sample Output
```13: 12
15: 13
2003: 1461
2005: 1462
239: 197
250: 198
1399: 1052
1500: 1053
999999: 531440```
Source
Rocky Mountain 2005

## Source Code:

```
//Thu Feb 24 00:20:44 CST 2011
#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 number;
while (cin >> number && (number != "0")) {
long long result = 0;
for (int i = 0; i < (int) number.size(); i++) {
int temp = number[i] - '0';
if (temp > 4)
temp--;
result = result * 9 + temp;
}
cout << number << ": " << result << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}

```

Spoj00400,

## Problem:

### Problem code: TOANDFRO

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down
```t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
```
Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as
`toioynnkpheleaigshareconhtomesnlewx`
Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.

### Input

There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2...20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.

### Output

Each input set should generate one line of output, giving the original plaintext message, with no spaces.

### Example

```Input:

5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0

Output:

theresnoplacelikehomeonasnowynightx
thisistheeasyoneab
```

## Solution:

Hint: The length of the string is always the multiplication of the number of input number.

## Source Code:

```
1 //Mon Feb 21 20:13:38 CST 2011
2 #include <vector>
3 #include <list>
4 #include <map>
5 #include <set>
6 #include <deque>
7 #include <queue>
8 #include <stack>
9 #include <bitset>
10 #include <algorithm>
11 #include <functional>
12 #include <numeric>
13 #include <utility>
14 #include <sstream>
15 #include <iostream>
16 #include <iomanip>
17 #include <cstdio>
18 #include <cmath>
19 #include <cstdlib>
20 #include <cctype>
21 #include <string>
22 #include <cstring>
23 #include <cstdio>
24 #include <cmath>
25 #include <cstdlib>
26 #include <ctime>
27
28 using namespace std;
29
30 int main(int argc, char* argv[]) {
31     //freopen("input.in", "r", stdin);
32     //freopen("output.out", "w", stdout);
33     int t;
34     while (cin >> t && t) {
35         string s1;
36         cin >> s1;
37         string s2(s1);
38         int rows = s1.size() / t;
39         for (int i = 0; i < (int) s1.size(); i++) {
40             int m = i / t;
41             //check which line it's at, odd line or even line.
42            int n = (m % 2 == 0 ? i % t : t - 1 - i % t);
43            s2[n * rows + m] = s1[i];
44         }
45         cout << s2 << endl;
46     }
47     //fclose(stdin);
48     //fclose(stdout);
49     return 0;
50 }

```

Spoj00004,

## Problem:

### Problem code: ONP

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

### Input

```t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]```
Text grouped in [ ] does not appear in the input file.

### Output

`The expressions in RPN form, one per line.`

### Example

```Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*```

## Solution:

Use the infix to postfix algorithms. Take the advantage of stack.

## Source Code:

```
//Mon Feb 21 19:09:43 CST 2011
#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, char* argv[]) {
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
int t;
cin >> t;
while (t--) {
string s1;
cin >> s1;
string stack = "";
string s2 = "";
for (int i = 0; i < s1.size(); i++) {
if (s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/'
|| s1[i] == '(' || s1[i] == '^')
stack = s1[i] + stack;
else if (s1[i] == ')') {
while (stack.size() != 0 && stack != '(') {
s2 += stack;
stack = stack.substr(1);
}
stack = stack.substr(1);
} else
s2 += s1[i];
}
cout << s2 << endl;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}

```

poj3852,

## Problem:

String LD
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 287 Accepted: 172
Description
Stringld (left delete) is a function that gets a string and deletes its leftmost character (for instance Stringld(“acm”) returns “cm”).

You are given a list of distinct words, and at each step, we apply stringld on every word in the list. Write a program that determines the number of steps that can be applied until at least one of the conditions become true:

1) A word becomes empty string, or
2) a duplicate word is generated.

For example, having the list of words aab, abac, and caac, applying the function on the input for the first time results in ab, bac, and aac. For the second time, we get b, ac, and ac. Since in the second step, we have two ac strings, the condition 2 is true, and the output of your program should be 1. Note that we do not count the last step that has resulted in duplicate string. More examples are found in the sample input and output section.
Input
There are multiple test cases in the input. The first line of each test case is n (1 <= n <= 100), the number of words.
Each of the next n lines contains a string of at most 100 lower case characters.
The input terminates with a line containing 0.
Output
For each test case, write a single line containing the maximum number of stringld we can call.
Sample Input
```4
aaba
aaca
baabcd
dcba
3
aaa
bbbb
ccccc
0```
Sample Output
```1
2```
Source
Tehran 2009

Just simulation.

## Source Code:

//Sun Feb 13 16:16:52 CST 2011
#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;

/** Perform the function. */
int checkString(vector<string> v, int number) {
int sz = number;
int count = 0;
while (true) {
for (int i = 0; i < sz; i++) {
if(v[i].size() == 1) return count;
v[i] = v[i].substr(1);
}
set<string> v1(v.begin(), v.end());
if (v1.size() < v.size())
return count;
count++;
}
}

int main(int argc, const char* argv[]) {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int number;
while (cin >> number && number) {
vector<string> v(number, "");
for (int i = 0; i < number; i++)
cin >> v[i];
int count = checkString(v, number);
cout << count << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}