頭動かないなら実装力鍛えようぜ((((
・・・あ、うん。
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
- あーDPのやり方違うのかー
- よし解いてみよう
- あれ?通らない…
- あれ?他の人のコードとあんまり考え方変わらないのに通らない…
- なぜ?なぜ????
- ・・・%.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
- ふーん…単純で通るのかー
- あれ?あ、最大ケースで深すぎて終わる…
2.5 闇解法発動
- うーん…あ、この高々1通りってことは、はー。なるへそ。
- 普通の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; }