行きの電車とか、帰ってきてからとか
やったもの
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); }