Wednesday, February 23, 2011

poj_2656_Unhappy_Jinjin.cpp

Problem Links:

poj2656,

Problem:
Unhappy Jinjin
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 8014Accepted: 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.

poj_2719_Faulty_Odometer.cpp

Problem Links:

poj2719,

Problem:

Faulty Odometer
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 7609Accepted: 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

Solution:

Translate the 10 based number to 9 based number.

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;
}

Monday, February 21, 2011

Spoj_00400_To_and_Fro.cpp

Problem Links:

Spoj00400,

Problem:

SPOJ Problem Set (classical)

400. To and Fro

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 }

Spoj_00004_Transform_the_Expression.cpp

Problem Links:



Spoj00004,

Problem:

SPOJ Problem Set (classical)

4. Transform the Expression

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[0] != '(') {
                    s2 += stack[0];
                    stack = stack.substr(1);
                }
                stack = stack.substr(1);
            } else
                s2 += s1[i];
        }
        cout << s2 << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Sunday, February 13, 2011

poj_3852_String_LD.cpp

Problem Links:

poj3852,

Problem:


String LD
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 287Accepted: 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

Solution:

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;
}