Codeforces Beta Round #61 (Div 2)

Mar 7, 2011.
Accepted: 3.        WA: 1.        NotTried: 1.

Tutorial

Problem 1: Petya and Java.
AC: This problem is mainly to determine which data type should be used based on the given integer. The redirect of operation is very useful here.
Time: O(1).
Source Code:
//Monday, March  07, 2011 09:15 CST
#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;

bool operator < (const string &a, const string &b)
{
    if (a.size() < b.size()) return true;
    if (b.size() < a.size()) return false;

    //They have the same number of digits.
    for (int i = 0;i < a.size();i++)
    {
        if (a[i] < b[i]) return true;
        if (b[i] < a[i]) return false;
    }
    return true;  //a could be less or equal to b.
}

string solve(string n)
{
    string b = "127";
    string s = "32767";
    string i = "2147483647";
    string l = "9223372036854775807";

    if(n < b) return "byte";
    if(n < s) return "short";
    if(n < i) return "int";
    if(n < l) return "long";
    return "BigInteger";
}

int main(int argc, char* argv[])
{
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}



***********************************************************************************************
Problem 2: Petya and Countryside.
AC: Little tech about dynamic programing in one dimension.
sum1[i] = sum1[i-1]+1, if the ith section is no lower than the (i-1)th one.
On the other side, check reversely.
Then, we'll get which gets the maximum.
Time: O(n).
Source Code:
//Monday, March  07, 2011 09:15 CST
#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.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    while (cin >> n)
    {
        vector<int> v(n);
        vector<int> sum1(n, 1);
        vector<int> sum2(n, 1);
        int max1 = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }
        for (int i = 1; i < n; i++)
        {
            if (v[i] >= v[i - 1])
                sum1[i] = sum1[i - 1] + 1;
        }
        for (int i = n - 1; i > 0; i--)
        {
            if (v[i - 1] >= v[i])
                sum2[i - 1] = sum2[i] + 1;
        }
        for (int i = 0; i < n; i++)
        {
            if (max1 < sum1[i] + sum2[i])
                max1 = sum1[i] + sum2[i];
        }
        cout << max1-1 << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

***********************************************************************************************

Problem 3: Petya and File System.
WA: Tried to build a structure for this problem, but didn't get it AC..
Source Code:
None.


***********************************************************************************************

Problem 4: Petya and His Friends.
AC: Think simply, and implement any algorithms that works for this problem. Don't stick on the algorithm theory. Remember, that's all for solving it, but not every problem's case has been put in theory.
Source Code:
//Monday, March  07, 2011 09:15 CST
#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[])
{
    int n;
    cin >> n;
    if(n==2)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << 6 << endl;
    cout << 10 << endl;
    cout << 15 << endl;
    for(int i=3; i<n; i++)
    {
        cout << 6*i << endl;
    }
    return 0;
}

***********************************************************************************************

Problem 5: Petya and Post.
NT: .
Source Code:
None.