poj_3982_ProblemD_序列.cpp

Problem Links:

poj3982,

Problem:

序列

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

Description

数列A满足An = An-1 + An-2 + An-3, n >= 3

编写程序，给定A0, A1 和 A2, 计算A99

Input

输入包含多行数据

每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)
数据以EOF结束

Output

对于输入的每一行输出A99的值

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;

string add(string A, string B)
{
    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++)
        {
            ret[i] = add(ret[i - 1], add(ret[i - 2], ret[i - 3]));
        }
        reverse(ret[99].begin(), ret[99].end());
        cout << ret[99] << endl;
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

poj_3981_ProblemC_字符串替换.cpp

Problem Links:

poj3981,

Problem:

字符串替换

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

Description

编写一个C程序实现将字符串中的所有"you"替换成"we"

Input

输入包含多行数据

每行数据是一个字符串，长度不超过1000
数据以EOF结束

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

poj_3980_ProblemB_取模运算.cpp

Problem Links:

poj3980,

Problem:

取模运算

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

Description

编写一个C函数mod(int n, int m),实现取模运算%

Input

输入包含多行数据

每行数据是两个整数a, b (1 <= a, b <= 32767)
数据以EOF结束

Output

于输入的每一行输出a%b

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

poj_3979_ProblemA_分数加减法.cpp

Problem Links:

poj3979,

Problem:

分数加减法

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

Description

编写一个C程序，实现两个分数的加减法

Input

输入包含多行数据
每行数据是一个字符串，格式是"a/boc/d"。

其中a, b, c, d是一个0-9的整数。o是运算符"+"或者"-"。

数据以EOF结束
输入数据保证合法

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

poj_3507_Judging_Olympia.cpp

Problem Links:

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

Arab and North Africa 2007

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