夢追い人

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

はぁ・・・

はぁ・・・

Distribution

ちょっとカンニングしちゃったな・・・

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;
int n, m;
int c[10000];
vector<int> dist[10000];
int prev[10000];
int calc() {
    priority_queue<P> que;
    que.push(P(0,0));
    int r=0, g=0;
    while (!que.empty()) {
        P p=que.top(); que.pop();
        int v=p.second;
        if (dist[v].size()==0) {
            if (r<p.first) {
                r=p.first;
                g=p.second;
            }
            continue;
        }
        for (int i=0; i<dist[v].size(); i++) {
            int to=dist[v][i];
            que.push(P(p.first+c[to],to));
        }
    }
    for (int v=g; v!=0; v=prev[v]) {
        c[v]=0;
    }
    return r;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=0; i<n; i++) {
        int s, a; scanf("%d%d",&s,&a);
        if (s!=0) {
            dist[s-1].push_back(i);
            prev[i]=s-1;
        }
        c[i]=a;
    }
    int res=c[0];
    c[0]=0;
    for (int i=0; i<m; i++) {
        res+=calc();
    }
    printf("%d\n",res);
}

AOJ 0181

にぶたん

#include <cstdio>
int m, n;
int book[100];
bool C(int k) {
    int sum=0, cnt=1;
    for (int i=0; i<n; i++) {
        sum+=book[i];
        if (book[i]>k) return false;
        if (sum>k) {
            sum=book[i];
            cnt++;
        }
    }
    if (cnt>m) return false;
    return true;
}
int main() {
    while (scanf("%d%d",&m,&n)) {
        if (!m&&!n) break;
        for (int i=0; i<n; i++) scanf("%d",&book[i]);
        int l=1, u=1500001;
        while (u-l>1) {
            int mid=(u+l)/2;
            if (C(mid)) {
                u=mid;
            } else {
                l=mid;
            }
        }
        printf("%d\n",u);
    }
}

AOJ 0507

カンニング
再帰だったのか〜混乱する萎え

#include <cstdio>
#include <algorithm>
using namespace std;
int ans[1000];
int pos;
void func(int res, int ub) {
    if (res==0) {
        for (int i=0; ;i++) {
            printf("%d%c",ans[i],ans[i+1]==0?'\n':' ');
            if (ans[i+1]==0) break;
        }
    } else {
        for (int i=min(res,ub); i>=1; i--) {
            ans[pos]=i;
            pos++;
            func(res-i,i);
            pos--;
            ans[pos]=0;
        }
    }
}
int main() {
    int n;
    while (scanf("%d",&n)) {
        if (!n) break;
        func(n,n);
    }
}

AOJ 0524

カンニングした
どうやらO(n^2m)でやるところを実装下手なせいでO(n^2m^2)にしてしまってたらしい

#include <cstdio>
struct cood {int x, y;};
cood star[200], star2[1000];
int main() {
    int m,n;
    while (scanf("%d",&m)) {
        if (!m) break;
        for (int i=0; i<m; i++) {
            int x, y; scanf("%d%d",&x,&y);
            star[i]=(cood){x,y};
        }
        scanf("%d",&n);
        for (int i=0; i<n; i++) {
            int x, y; scanf("%d%d",&x,&y);
            star2[i]=(cood){x,y};
        }
        for (int i=0; i<n; i++) {
            int j;
            int dx=star2[i].x-star[0].x;
            int dy=star2[i].y-star[0].y;
            for (j=1; j<m; j++) {
                int x=star[j].x+dx;
                int y=star[j].y+dy;
                int k;
                for (k=0; k<n; k++) {
                    if (star2[k].x==x&&star2[k].y==y) break;
                }
                if (k==n) break;
            }
            if (j==m) {
                printf("%d %d\n",dx,dy);
                break;
            }
        }
    }
}

AOJ 0133

やるだけ

#include <iostream>
using namespace std;
string b[8];
int main() {
    for (int i=0; i<8; i++) cin>>b[i];
    cout<<90<<endl;
    for (int i=0; i<8; i++) {
        for (int j=7; j>=0; j--) {
            cout<<b[j][i];
        }
        cout<<endl;
    }
    cout<<180<<endl;
    for (int i=7; i>=0; i--) {
        for (int j=7; j>=0; j--) {
            cout<<b[i][j];
        }
        cout<<endl;
    }
    cout<<270<<endl;
    for (int i=7; i>=0; i--) {
        for (int j=0; j<8; j++) {
            cout<<b[j][i];
        }
        cout<<endl;
    }
}

AOJ 0134

やるだけ

#include <cstdio>
typedef long long ll;
int main() {
    int n; scanf("%d",&n);
    ll sum=0;
    for (int i=0; i<n; i++) {
        int x; scanf("%d",&x);
        sum+=x;
    }
    printf("%lld\n",sum/n);
}

AOJ 2000

やるだけだけどYesNoの大文字小文字問題にしてやられた

#include <cstdio>
#include <iostream>
using namespace std;
int field[21][21];
int main() {
    int n;
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<21; i++) for (int j=0; j<21; j++) field[i][j]=0;
        for (int i=0; i<n; i++) {
            int x, y; scanf("%d%d",&x,&y);
            field[y][x]=1;
        }
        int m; scanf("%d",&m);
        int rx=10, ry=10;
        int cnt=0;
        for (int i=0; i<m; i++) {
            char d; cin>>d;
            int dist; scanf("%d",&dist);
            if (d=='N') {
                for (int j=0; j<dist; j++) {
                    ry++;
                    if (field[ry][rx]) {
                        field[ry][rx]=0;
                        cnt++;
                    }
                }
            }
            if (d=='E') {
                for (int j=0; j<dist; j++) {
                    rx++;
                    if (field[ry][rx]) {
                        field[ry][rx]=0;
                        cnt++;
                    }
                }
            }
            if (d=='S') {
                for (int j=0; j<dist; j++) {
                    ry--;
                    if (field[ry][rx]) {
                        field[ry][rx]=0;
                        cnt++;
                    }
                }
            }
            if (d=='W') {
                for (int j=0; j<dist; j++) {
                    rx--;
                    if (field[ry][rx]) {
                        field[ry][rx]=0;
                        cnt++;
                    }
                }
            }
        }
        if (cnt!=n) puts("No");
        else puts("Yes");
    }
}

AOJ 2001

やるだけだけど添字にしてやられた

#include <cstdio>
int col[1001][101];
int main() {
    int n, m, a;
    while (scanf("%d%d%d",&n,&m,&a)) {
        if (!n&&!m&&!a) break;
        for (int i=0; i<=1000; i++) for (int j=0; j<=100; j++) col[i][j]=0;
        for (int i=0; i<m; i++) {
            int h, p, q; scanf("%d%d%d",&h,&p,&q);
            col[h][p]=q;
            col[h][q]=p;
        }
        int pos=a;
        for (int i=1000; i>0; i--) {
            if (col[i][pos]!=0) {
                pos=col[i][pos];
            }
        }
        printf("%d\n",pos);
    }
}

はぁ・・・・