夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

行きの電車とか、帰ってきてからとか

やったもの

AOJ 1019

#include <cstdio>
int n, k, s[100], b[100];
int main() {
    while (scanf("%d%d",&n,&k)) {
        if (!n&&!k) break;
        for (int i=0; i<k; i++) {
            scanf("%d",&s[i]);
            b[i]=0;
        }
        for (int i=0; i<n; i++) for (int j=0; j<k; j++) {
            int x; scanf("%d",&x);
            b[j]+=x;
        }
        bool flag=true;
        for (int i=0; i<k; i++) if (s[i]<b[i]) flag=false;
        if (flag) puts("Yes");
        else puts("No");
    }
}

AOJ 1020

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
double dp[16][3][3];
char s,t,b;
int main() {
    int n, sx, sy, tx, ty, bx, by;
    while (scanf("%d",&n)) {
        if (!n) break;
        memset(dp, 0, sizeof(dp));
        cin>>s>>t>>b;
        sx=(s-'A')/3; sy=(s-'A')%3;
        tx=(t-'A')/3; ty=(t-'A')%3;
        bx=(b-'A')/3; by=(b-'A')%3;
        dp[0][sx][sy]=1.0;
        for (int i=0; i<=n; i++) {
            for (int j=0; j<3; j++) {
                for (int k=0; k<3; k++) {
                    for (int l=0; l<4; l++) {
                        int x=j+dx[l], y=k+dy[l];
                        if (x>=0&&x<3&&y>=0&&y<3&&(x!=bx||y!=by)) {
                            dp[i+1][x][y]+=dp[i][j][k]/4.0;
                        } else {
                            dp[i+1][j][k]+=dp[i][j][k]/4.0;
                        }
                    }
                    // printf("%f%c",dp[i][j][k],k==2?'\n':' ');
                }
            }
        }
        printf("%.8f\n",dp[n][tx][ty]);
    }
}

PKU 2456

#include <cstdio>
#include <algorithm>
using namespace std;
int n, c;
int x[100000];
bool C(int d) {
    int last=x[0], j=1, cnt=1;
    for (int i=1; i<c; i++) {
        while (j<n&&x[j]<last+d) j++;
        if (j<n) {
            cnt++;
            last=x[j];
        }
    }
    return cnt==c;
}
int main() {
    scanf("%d%d",&n,&c);
    for (int i=0; i<n; i++) scanf("%d",&x[i]);
    sort(x, x+n);
    int lb=0, ub=1000000000;
    while (ub-lb>1) {
        int mid=(lb+ub)/2;
        if (C(mid)) {
            lb=mid;
        } else {
            ub=mid;
        }
    }
    printf("%d\n", lb);
}

PKU 3320

#include <cstdio>
#include <map>
#include <set>
using namespace std;
map<int, int> cnt;
set<int> list;
int p, a[1000000];
int main() {
    scanf("%d",&p);
    for (int i=0; i<p; i++) {
        scanf("%d",&a[i]);
        list.insert(a[i]);
    }
    int s=0, t=0, num=0, ans=p, n=list.size();
    for (;;) {
        while (t<p&&num<n) {
            if (cnt[a[t++]]++==0) num++;
        }
        if (num<n) break;
        ans=min(ans, t-s);
        if (--cnt[a[s++]]==0) num--;
    }
    printf("%d\n",ans);
}