| 
int main() { int T; cin>>T; REP(ttt, T) { ll N; cin>>N; VI A(N); REP(i, N) cin>>A[i]; ll lines=0; ll ans=1; REP(i, N) { ans += lines*(A[i]+1) + ((A[i]-1)*A[i]/2) +1; lines += A[i]+1; } cout<<"Case #"<<ttt+1<<": "<<ans<<endl; // break; } return 0; }
| 
ll N, K, P; int main() { int T; cin>>T; REP(ttt, T) { cin>>N>>K>>P; ll nz = 0; ll ans = 1; if(P==100) { ans = (N+K-1)/K; } else { for(ll all=N%K==0 ? K : N%K;all<=N;all+=K) { ll n = min(K, all); ll vote=n + nz; if(vote * 100 >= all * P) { nz=0; ans = 1; } else { if(n==K && (N-all)/K > 10) { ll lo=0,hi=(N-all)/K; int hiv; { ll n_vote = K + nz + K*hi; ll n_all = all + K*hi; hiv = (n_vote * 100 >= n_all * P); } if(hiv) { while(lo+1<hi) { ll mid = (lo+hi)/2; ll n_vote = K + nz + K*mid; ll n_all = all + K*mid; //cout<<"BS "<<mid<<" "<<(float)n_vote/n_all<<" "<<n_vote<<" "<<n_all<<endl; if(n_vote * 100 >= n_all * P) hi=mid; else lo=mid; } //cout<<"BSS hi="<<hi<<" init hi:"<<(N-all)/K<<" hiv:"<<hiv<<endl; ans += hi; nz += K*hi; all += K*hi - K; } else { ans++; nz += n; } } else { ans++; nz += n; } } //all += n; //cout<<" "<<n<<" "<<all<<" vote "<<vote<<" r "<<(float)vote/all<<" -> "<<(vote * 100 >= all * P)<<endl; } } cout<<"Case #"<<ttt+1<<": "<<ans<<endl; // break; } return 0; }
| 
int win(char col, vector<string>& w) { int dx[]={1,1,0,-1,-1,-1,0,1}; int dy[]={0,1,1,1,0,-1,-1,-1}; REP(y, 19) REP(x, 19) { REP(dir, 8) { int win=1; REP(st, 5) { int nx=x+dx[dir]*st; int ny=y+dy[dir]*st; if(!(0<=nx&&nx<19&&0<=ny&&ny<19)) {win=0;break;} if(w[ny][nx]!=col) {win=0;break;} } if(win) return 1; } } return 0; } int solve(vector<string>& w) { int Bs=0, Ws=0; REP(i, 19) REP(j, 19) Bs+=w[i][j]=='o'; REP(i, 19) REP(j, 19) Ws+=w[i][j]=='x'; //cout<<"count: "<<Bs<<" "<<Ws<<endl; if(!(Bs==Ws || Bs==Ws+1)) return 0; string col("ox"); int Bwin = win('o', w); int Wwin = win('x', w); //cout<<"win: "<<Bwin<<" "<<Wwin<<endl; if(Bwin && Wwin) return 0; if(!(!Bwin || (Bwin && Bs==Ws+1))) return 0; if(!(!Wwin || (Wwin && Bs==Ws))) return 0; if(Bwin) { int ok=0; REP(y, 19) REP(x, 19) { if(ok) break; if(w[y][x]=='o') { w[y][x]='.'; if(!win('o', w)) {ok=1;break;} w[y][x]='o'; } } if(!ok) return 0; } if(Wwin) { int ok=0; REP(y, 19) REP(x, 19) { if(ok) break; if(w[y][x]=='x') { w[y][x]='.'; if(!win('x', w)) {ok=1;break;} w[y][x]='x'; } } if(!ok) return 0; } return 1; } int main() { //ios::sync_with_stdio(false); string s; while(getline(cin, s)) { vector<string> w(19); w[0] = s; RANGE(i, 1, 19) getline(cin, w[i]); //cout<<w<<endl; int ok = solve(w); cout<<(ok?"YES":"NO")<<endl; //break; } return 0; }
| 
Failed Wake Up Test
(...のはずが 384 位で通過しました... が、だめだと思って事前に作ってあったので残しときます:)
| 
static const ll MODVAL = 1000000007; ll MODADD(ll x, ll y) { return (x+y)%MODVAL; } ll MODSUB(ll x, ll y) { return (x-y+MODVAL)%MODVAL; } ll MODMUL(ll x, ll y) { return (x*y)%MODVAL; } ll MODPOW(ll x, ll e) { ll v = 1; for(;e;x=MODMUL(x,x),e>>=1) if(e&1) v = MODMUL(v, x); return v; } ll MODINV(ll x) { return MODPOW(x, MODVAL-2); } #define MAXN 10010 ll facts[MAXN]; ll inv_facts[MAXN]; ll MODCOMB(ll n, ll r) { assert(0<=n && n<MAXN); assert(0<=r && r<=n); return MODMUL(facts[n], MODMUL(inv_facts[r], inv_facts[n-r])); } int main() { facts[0] = 1; inv_facts[0] = MODINV(facts[0]); RANGE(i, 1, MAXN) facts[i] = MODMUL(facts[i-1], i); RANGE(i, 1, MAXN) inv_facts[i] = MODMUL(inv_facts[i-1], MODINV(i)); REP(i, MAXN) assert(MODMUL(facts[i], inv_facts[i])==1); int T; cin>>T; REP(ttt, T) { ll N, K; cin>>N>>K; VI w(N); REP(i, N) cin>>w[i]; sort(ALL(w)); ll ans = 0; REP(i, N) { if(i-(K-1)>=0) { //ans += MODMUL(w[i], MODCOMB(i, i-(K-1))); // だめ ans = MODADD(ans, MODMUL(w[i], MODCOMB(i, i-(K-1)))); // OK } } cout<<"Case #"<<ttt+1<<": "<<ans<<endl; } return 0; }
| 
/////////////////////// [OPTION] maximumFlow #define INF 1000000 typedef int Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) { } }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; #define RESIDUE(s,t) (capacity[s][t]-flow[s][t]) Weight maximumFlow(const Graph &g, int s, int t) { int n = g.size(); Matrix flow(n, Array(n)), capacity(n, Array(n)); REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight; Weight total = 0; while (1) { queue<int> Q; Q.push(s); vector<int> prev(n, -1); prev[s] = s; while (!Q.empty() && prev[t] < 0) { int u = Q.front(); Q.pop(); FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) { prev[e->dst] = u; Q.push(e->dst); } } if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side Weight inc = INF; for (int j = t; prev[j] != j; j = prev[j]) inc = min(inc, RESIDUE(prev[j], j)); for (int j = t; prev[j] != j; j = prev[j]) flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc; VI path; for (int j = t; prev[j] != j; j = prev[j]) path.push_back(j); path.push_back(s); reverse(ALL(path)); total += inc; // cout<<"Update "<<path<<" -> total "<<total<<endl; } } void add_edge(Graph& g, int s, int e, int w) { g[s].push_back(Edge(s, e, w)); g[e].push_back(Edge(e, s, 0)); } /////////////////////// maximumFlow ll N, M, L; string K1, K2; int check() { Graph g(M*2+2, Edges()); int S=M*2, E=M*2+1; REP(i, M) { add_edge(g, S, i, 1); add_edge(g, M+i, E, 1); } // i in K1, j in K2 REP(i, M) REP(j, M) { int lok=1; REP(li, L) { char a=K1[i*L+li], b=K2[j*L+li]; if(!(a=='?' || b=='?') && a!=b) lok=0; } if(lok) add_edge(g, i, M+j, 1); } int flow = maximumFlow(g, S, E); return flow==M; } int main() { int T; cin>>T; REP(ttt, T) { cin>>M; cin>>K1>>K2; N=K1.size(); L=N/M; int gok=1; REP(ci, N) { if(K1[ci]=='?') { int ok=0; REP(cand, 6) { K1[ci]=cand+'a'; if(check()) {ok=1;break;} } if(!ok) {gok=0;break;} } } if(!check()) gok=0; if(gok) { cout<<"Case #"<<ttt+1<<": "<<K1<<endl; } else { cout<<"Case #"<<ttt+1<<": IMPOSSIBLE"<<endl; } } return 0; }
| 
// X in [x0, x1] // Y in [y0, y1] struct Rect { int x0, y0, x1, y1; bool operator<(const Rect& o) const { return x0<o.x0; } }; ostream& operator<<(ostream& os, const Rect& r) { os<<"[Rect "<<r.x0<<" "<<r.y0<<" "<<r.x1<<" "<<r.y1<<" ]"; return os; } int W, H, P, Q, N, X, Y, A, B, C, D; int foo() { vector<Rect> rects(N); int x=X, y=Y; REP(i, N) { Rect r = (Rect){x-(P-1), y-(Q-1), x, y}; r.x0 = max(r.x0, 0); r.y0 = max(r.y0, 0); r.x1 = min(r.x1, W-1); r.y1 = min(r.y1, H-1); rects[i] = r; int nx = (x * A + y * B + 1) % W; int ny = (x * C + y * D + 1) % H; x = nx; y = ny; } sort(ALL(rects)); // cout<<rects<<endl; ll ng = 0; VI line(H); int ri=0; REP(scanx, W-P+1) { REP(y, H-Q+1) line[y] = max(line[y]-1, 0); for(;ri<N && rects[ri].x0==scanx;ri++) { int wi = rects[ri].x1 - rects[ri].x0 + 1; RANGE(y, rects[ri].y0, rects[ri].y1+1) { line[y] = max(line[y], wi); } } REP(y, H-Q+1) ng += line[y] ? 1 : 0; } int ans = (W-P+1)*(H-Q+1) - ng; return ans; } int main() { int T; cin>>T; REP(ttt, T) { cin>>W>>H>>P>>Q>>N>>X>>Y>>A>>B>>C>>D; int r1 = foo(); cout<<"Case #"<<ttt+1<<": "<<r1<<endl; } return 0; }
| 
#define INF 1<<30 class BallsSeparating { public: int minOperations(vector <int> R, vector <int> G, vector <int> B) { int N=R.size(); VVI dp(N+1, VI(8, INF)); dp[0][0]=0; RANGE(i, 1, N+1) { REP(cur, 8) { REP(prev, 8) { int costs[3]; int all = R[i-1]+G[i-1]+B[i-1]; costs[0] = all - R[i-1]; costs[1] = all - G[i-1]; costs[2] = all - B[i-1]; REP(c, 3) { if((prev|(1<<c))==cur) { dp[i][cur] = min(dp[i][cur], dp[i-1][prev] + costs[c]); } } } } //cout<<i<<"::: "<<dp<<endl; } return dp[N][7]==INF ? -1 : dp[N][7]; } };
| 
BalancedParentheses ::=
Empty
| [a-z: ]
| :)
| :(
| ( BalancedParentheses )
| BalancedParentheses BalancedParentheses
int main() { int T; cin>>T; cin.ignore(); REP(ttt, T) { string s; getline(cin, s); int N=s.size(); VVI dp(N, VI(N+1)); REP(S, N) dp[S][0]=1; RANGE(L, 1, N+1) { REP(S, N) { int E=S+L-1; if(E>=N) continue; // cout<<s.substr(S, L)<<endl; // cout<<S<<" "<<L<<endl; if(L==0) dp[S][L]=1; if(L==1 && (s[S]==' ' || s[S]==':' || ('a'<=s[S] && s[S]<='z'))) dp[S][L]=1; if(L==2 && (s.substr(S, L)==":)" || s.substr(S, L)==":(")) dp[S][L]=1; if(L-2>=0 && s[S]=='(' && dp[S+1][L-2] && s[E]==')') dp[S][L]=1; if(L-2>=0) { RANGE(l, 1, L) if(dp[S][l] && dp[S+l][L-l]) dp[S][L]=1; // RANGE(l, 1, L) assert(0<=S && S<N && S+l<N && 0<L-l && L-l<=N); } } } cout<<"Case #"<<ttt+1<<": "<<(dp[0][N]?"YES":"NO")<<endl; // break; } return 0; }
| 
int main() { int T; cin>>T; REP(ttt, T) { ll N,K,A,B,C,R; cin>>N>>K>>A>>B>>C>>R; VI w(K); w[0] = A; RANGE(i, 1, K) { w[i] = (B * w[i - 1] + C) % R; } VI ww(K+2); // [0, K+2) REP(j, K) if(w[j]<ww.size()) ww[w[j]]++; ll ans = -1; RANGE(i, K, N) { ll nxt = -1; REP(j, ww.size()) { if(ww[j]==0) { nxt = j; break; } } assert(nxt!=-1); int rm = w[i%K]; if(rm<ww.size()) ww[rm]--; int add = nxt; if(add<ww.size()) ww[add]++; w[i%K] = nxt; // if((N-1-i)%(K+1)==0) { // cout<<i<<" "<<nxt<<endl; // } ans = nxt; if(5*K<N && (N-1-i)%(K+1)==0) break; } cout<<"Case #"<<ttt+1<<": "<<ans<<endl; // break; } return 0; }