USACO 1.1

USACO 1.2は主にフォーマットを説明します.ヘッダは必ず/*ID:beihai 2013 PROG:(タイトル名、タイトルに説明がある)LANG:C+*/を打ってファイルストリームで入出力を開きます.
1.1.1 a+b

/* ID: beihai2013 PROG: test LANG: C++ */
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main() {
    ofstream fout ("test.out");
    ifstream fin ("test.in");
    int a, b;
    fin >> a >> b;
    fout << a+b << endl;
    return 0;
}

1.1.2簡単計算/*ID:beihai 2013 PROG:ride LANG:C+*/
include
include
include
include
include
include
include
using namespace std; const int MAXN = 1000; char s1[MAXN], s2[MAXN]; int main() { //scanf(“%s %s”, s1, s2); freopen(“ride.in”, “r”, stdin); freopen(“ride.out”, “w”, stdout); cin >> s1 >> s2; int ans1 = 1, ans2 = 1; for(int i = 0 ; i < (int)strlen(s1) ; i++) ans1 = (ans1 * (s1[i] - ‘A’ + 1)) % 47; for(int i = 0 ; i < (int)strlen(s2) ; i++) ans2 = (ans2 * (s2[i] - ‘A’ + 1)) % 47; if(ans1 == ans2) cout << “GO” << endl; else cout << “STAY” << endl;

//scanf("%s", s1);
return 0;

} 1.1.5簡単なシミュレーション.すべての人のお金の合計は0で、最初はすべての人のお金の数も0です.毎回一人が他の何人かにお金を分けて、均等に分けられないお金は自分で残しています.

/* ID: beihai2013 PROG: gift1 LANG: C++ */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 20;
char name[MAXN];
char p[MAXN][MAXN];
int val[MAXN];
map<string,int>mm;
int main()
{
    freopen("gift1.in", "r", stdin);
    freopen("gift1.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 1 ; i <= n ; i++){
        scanf("%s", p[i]);
        mm[p[i]] = i;
        val[i] = 0;
    }
    while(scanf("%s", name) != EOF){
        int sum, m;
        int u = mm[name];
        scanf("%d%d", &sum, &m);
        if(m == 0){
            continue;
        }
        for(int i = 0 ; i < m ; i++){
            scanf("%s", name);
            int v = mm[name];
            val[v] += sum / m;
        }
        val[u] -= sum - sum % m;
    }
    for(int i = 1 ; i <= n ; i++){
        printf("%s %d
", p[i], val[i]);
    }
    return 0;
}

1.1.6はますます難しくなってきた……アナログ時間、出力は1900年から、N年目の毎月13日はそれぞれ曜日6712345の数量のテーマで見間違えやすい、注意の与える条件は1900.1である.1は月曜日なので、転化しなければなりません.それから12月の日数を前にします.一年を巡るのはこの年の1-12月で、1月は前年の12月から変わったからです.

/* ID: beihai2013 TASK: friday LANG: C++ */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 400 + 5;
int ans[MAXN][10];
int mon[20] = {0, 31, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
int day(int year, int month)
{
    if(month == 3){
        if(year % 400 == 0) return 29;
        else if(year % 100 != 0 && year % 4 == 0)   return 29;
    }
    return mon[month];
}
void init()
{
    memset(ans, 0, sizeof(ans));
    int now = 5;
    for(int i = 1 ; i < MAXN ; i++){
        int year = 1900 + i - 1;
        for(int j = 1 ; j <= 7 ; j++)   ans[i][j] = ans[i - 1][j];
        for(int j = 1 ; j <= 12 ; j++){
            now = (now + day(year, j)) % 7;
            if(now == 0)    now = 7;
            ans[i][now]++;
// printf("year = %d, month = %d, now = %d, day(year,j) = %d
", year, j, now, day(year, j));
// system("pause");
        }
    }
}
int main()
{
    freopen("friday.in", "r", stdin);
    freopen("friday.out", "w", stdout);
    init();
    int n;
    scanf("%d", &n);
    for(int i = 1 ; i <= 7 ; i++){
        printf("%d", ans[n][i]);
        if(i == 7)  printf("
");
        else    printf(" ");
    }
    return 0;
}

1.1.7神坑シミュレーション.最初はO(N)でやろうと思っていたが、いろいろできなかった.O(N^2)でやろうとしたのは、ポイントごとに達成できる最左端と最右端を探していた.しかし、wと非wの状況を分けて議論しなければならない.

/* ID: beihai2013 TASK: beads LANG: C++ */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 1e3;
char str[MAXN];
int l[MAXN], r[MAXN];
int main()
{
    freopen("beads.in", "r", stdin);
    freopen("beads.out", "w", stdout);
    int n;
    scanf("%d", &n);
    scanf("%s", str);
    for(int i = n ; i < 2 * n ; i++)    str[i] = str[i - n];
    str[n * 2] = '\0';
    for(int i = 0 ; i < 2 * n ; i++){
        if(str[i] != 'w'){
            int now = i;
            while(now >= 0 && (str[now] == 'w' || str[now] == str[i]))  now--;
            l[i] = i - now;
            now = i;
            while(now < 2 * n && (str[now] == 'w' || str[now] == str[i]))   now++;
            r[i] = now - i;
        }
        else{
            int now = i;
            while(now >= 0 && str[now] == 'w')  now--;
            if(now >= 0){
                char temp = str[now];
                while(now >= 0 && (str[now] == 'w' || str[now] == temp))    now--;
                l[i] = i - now;
            }
            else    l[i] = i - now;
            now = i;
            while(now < 2 * n && str[now] == 'w')  now++;
            if(now < 2 * n){
                char temp = str[now];
                while(now < 2 * n && (str[now] == 'w' || str[now] == temp))    now++;
                r[i] = now - i;
            }
            else    r[i] = -i + now;
        }
    }
    int ans = 0;
    for(int i = 0 ; i < 2 * n ; i++)    ans = max(ans, l[i] + r[i + 1]);
    ans = min(ans, n);
    printf("%d
", ans);
    return 0;
}