読者です 読者をやめる 読者になる 読者になる

夢追い人

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

頭動かないなら実装力鍛えようぜ((((

・・・あ、うん。

AOJ 0183

やらないだけ

#include <iostream>
#include <cstdio>
using namespace std;
string f[3];
int main() {
    while (cin>>f[0]) {
        if (f[0]=="0") break;
        for (int i=1; i<3; i++) cin>>f[i];
        char res='+';
        for (int i=0; i<3; i++) {
            if (f[0][i]==f[1][i]&&f[1][i]==f[2][i]) {
                if (f[0][i]!='+') res=f[0][i];
            }
            if (f[i][0]==f[i][1]&&f[i][1]==f[i][2]) {
                if (f[i][0]!='+') res=f[i][0];
            }
        }
        if (f[0][0]==f[1][1]&&f[1][1]==f[2][2]) {
            if (f[0][0]!='+') res=f[0][0];
        }
        if (f[0][2]==f[1][1]&&f[1][1]==f[2][0]) {
            if (f[0][2]!='+') res=f[0][2];
        }
        if (res=='+') puts("NA");
        else cout<<res<<endl;
    }
}

AOJ 0232

  1. あーDPのやり方違うのかー
  2. よし解いてみよう
  3. あれ?通らない…
  4. あれ?他の人のコードとあんまり考え方変わらないのに通らない…
  5. なぜ?なぜ????
  6. ・・・%.0fって四捨五入だったのかーーーーーーーー!!!!!!!!!!!!
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
int x, y, z, n, a, e;
int v[4];
P event[55];
 double dp[55][5050][2];
//double dp[55][5050];
int main() {
    while (scanf("%d%d%d",&x,&y,&z)) {
        if (!x&&!y&&!z) break;
        fill(event, event+55, P(0,0));
        memset(dp, 0, sizeof(dp));
        for (int i=0; i<x; i++) scanf("%d",&v[i]);
        for (int i=0; i<z; i++) {
            scanf("%d%d%d",&n,&a,&e);
            event[n]=P(a,e);
//            event[n]=P((a==1),a==3?-e:e);
        }
        dp[0][0][0]=1.0;
//        dp[0][0]=1.0;
        for (int i=0; i<y; i++) {
            if (event[i].first==1) {
                int next=min(y,i+event[i].second);
                for (int j=0; j<5050; j++) {
                    dp[next][j][1]+=dp[i][j][0];
                    for (int k=0; k<x; k++) {
                        int next2=min(y,i+v[k]);
                        dp[next2][j][0]+=dp[i][j][1]/x;
                    }
                }
            } else {
                for (int j=0; j<5050; j++) {
                    if (dp[i][j][0]==0.0&&dp[i][j][1]==0.0) continue;
                    for (int k=0; k<x; k++) {
                        int next=min(y,i+v[k]);
                        if (event[i].first==2) {
                            dp[next][j+event[i].second][0]+=dp[i][j][0]/x;
                            dp[next][j][0]+=dp[i][j][1]/x;
                        } else if (event[i].first==3) {
                            dp[next][max(0,j-event[i].second)][0]+=dp[i][j][0]/x;
                            dp[next][j][0]+=dp[i][j][1]/x;
                        } else {
                            dp[next][j][0]+=(dp[i][j][0]+dp[i][j][1])/x;
                        }
                    }
                }
            }
/*            for (int j=0; j<5050; j++) {
                if (dp[i][j]==0.0) continue;
                for (int k=0; k<x; k++) {
                    int nv=min(y,i+v[k]);
                    int np=j;
                    if (nv<y) {
                        if (event[nv].first) nv+=event[nv].second;
                        else np+=event[nv].second;
                    }
                    dp[min(y,nv)][max(0,np)]+=dp[i][j]/x;
                }
            }
*/        }
        double res=0.0;
        for (int k=0; k<5050; k++) res+=(dp[y][k][0]+dp[y][k][1])*k;
//        for (int k=0; k<5050; k++) res+=dp[y][k]*k;
//        printf("%.0f\n",res);
        printf("%d\n",(int)res);
    }
}

AOJ 0503

  1. ふーん…単純で通るのかー
  2. あれ?あ、最大ケースで深すぎて終わる…

2.5 闇解法発動

  1. うーん…あ、この高々1通りってことは、はー。なるへそ。
  2. 普通のAC
#include <cstdio>
#include <cmath>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, in;
ll m;
stack<int> s[3], temp[3];
void input(stack<int>& s) {
    int num; scanf("%d",&num);
    for (int i=0; i<num; i++) {
        int x; scanf("%d",&x);
        s.push(x);
    }
}
void clear(stack<int>& s) {
    while (!s.empty()) s.pop();
}
// 0-a 1-b 2-c
ll dfs(int from, int to) {
    ll res=1;
    bool con=true;
    while (s[0].size()!=n&&s[2].size()!=n&&res<=m) {
        con=true;
        for (int i=0; i<3&&con; i++) {
            for (int j=0; j<3&&con; j++) {
                if (i==to&&j==from) continue;
                if (s[i].empty()) continue;
                if (abs(i-j)!=1) continue;
                if (!s[j].empty()&&s[i].top()<s[j].top()) continue;
                s[j].push(s[i].top()); s[i].pop();
                from=i; to=j;
                con=false;
            }
        }
        res++;
    }
    return res;
}
int main() {
    while (scanf("%d%lld",&n,&m)) {
        if (!n&&!m) break;
        clear(s[0]); clear(s[1]); clear(s[2]);
        input(s[0]); input(s[1]); input(s[2]);
        ll res=m+1;
        if (s[0].size()==n||s[2].size()==n) {
            puts("0");
            continue;
        }
        for (int i=0; i<3; i++) temp[i]=s[i];
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {                               // iからj
                if (s[i].empty()) continue;                         // とりたいところが空
                if (abs(i-j)!=1) continue;                          // 隣接してない
                if (!s[j].empty()&&s[i].top()<s[j].top()) continue; // 置きたいところに置けない
                s[j].push(s[i].top()); s[i].pop();
                res=min(res, dfs(i,j));
                for (int k=0; k<3; k++) s[k]=temp[k];
            }
        }
        printf("%lld\n",res==m+1?-1:res);
    }
    return 0;
}
広告を非表示にする