1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | /// Raihan Ruhin (username : raihanruhin) /// Online resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0), cin.tie(0); int tc, n, x, cnt; //cin>>tc; while(cin>>n) { cnt=0; for(int i=0;i<5;i++) { cin>>x; if(x==n) cnt++; } cout<< cnt <<endl; } return 0; } |
Saturday, 9 September 2017
Identifying tea (UVa 13012, UVaLive 7211, Regionals 2015 >> Latin America)
Thursday, 24 August 2017
Maximum sum increasing subsequence
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /// Raihan Ruhin (username: raihanruhin) /// Resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int dp[102][102], arr[102], n; int func(int now, int last) { if(now>n) return 0; int &ret = dp[now][last]; if(ret!=-1) return ret; ret=0; ret = func(now+1, last); if(arr[last]<arr[now]) ret = max(ret, func(now+1, now)+arr[now]); return ret; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); int tc, kk=1, x; cin>>tc; while(tc--) { cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; SET(dp); cout<<func(0, 0)<<endl; //cout<<"Case "<<kk++<<": "<< <<"\n"; } return 0; } |
Equilibrium point
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | /// Raihan Ruhin (username: raihanruhin) /// Resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0), cin.tie(0); int tc, kk=1, n, x, consecutive_sum[102]; bool found; consecutive_sum[0]=0; cin>>tc; while(tc--) { found =false; cin>>n; for(int i=1;i<=n;i++) { cin>>x; consecutive_sum[i] = consecutive_sum[i-1] + x; } for(int i=1;i<=n;i++) { if(consecutive_sum[n]-consecutive_sum[i] == consecutive_sum[i-1]) { found =true; cout<<i<<endl; break; } } if(!found) cout<<-1<<endl; //cout<<"Case "<<kk++<<": "<< <<"\n"; } return 0; } |
Sort an array of 0s, 1s and 2s
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | /// Raihan Ruhin (username: raihanruhin) /// Resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0), cin.tie(0); int tc, kk=1, n, x; cin>>tc; while(tc--) { cin>>n; int zero=0, one=0, two=0; for(int i=0;i<n;i++) { cin>>x; if(!x) zero++; else if(x==1) one++; else two++; } for(int i=0;i<n;i++) { if(i) cout<<" "; if(zero) { cout<<0; zero--; } else if(one) { cout<<1; one--; } else { cout<<2; two--; } } cout<<endl; //cout<<"Case "<<kk++<<": "<< <<"\n"; } return 0; } |
Subarray with given sum
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | /// Raihan Ruhin (username: raihanruhin) /// Resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0), cin.tie(0); int tc, kk=1, n, x, arr[102], s; cin>>tc; while(tc--) { cin>>n>>s; int i; for(i=1;i<=n;i++) cin>>arr[i]; arr[0]=0; int st = 1, x=0; bool found = false; i=1; while(i<=n || x>s) { if(x>s) { x -= arr[st]; st++; i--; } else if(x<s) { x += arr[i]; } if(x==s) { found=true; break; } i++; } if(found) cout<<st<<" "<<i<<endl; else cout<<-1<<endl; //cout<<"Case "<<kk++<<": "<< <<"\n"; } return 0; } |
Saturday, 19 August 2017
Missing number in array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | /// Raihan Ruhin (username : raihanruhin) /// Online resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0), cin.tie(0); int tc, n, x; map<int, bool>mp; cin>>tc; while(tc--) { cin>>n; for(int i=1; i<n; i++) { cin>>x; mp[x]=true; } for(int i=1; i<=n; i++) if(!mp[i]) { cout<< i <<endl; break; } mp.clear(); } return 0; } |
Friday, 18 August 2017
Kadane's Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | /// Raihan Ruhin (username : raihanruhin) /// Online resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc, n, arr[1002], tmp, mx, ans; cin>>tc; while(tc--) { cin>>n; tmp = 0; ans = 0; mx = -1e9; //single max element of the array for(int i=0; i<n; i++) { cin>>arr[i]; mx = max(mx, arr[i]); tmp += arr[i]; tmp = max(tmp, 0); ans = max(ans, tmp); } if(ans==0) cout<<mx<<endl; else cout<<ans<<endl; } return 0; } |
Monday, 10 July 2017
Army Buddies (UVa 12356, UVaLive 5789, Regionals 2011 >> Latin America)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int l[MX], r[MX]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc,kk=1, n, q, lf, rg; while(cin>>n>>q) { if(!n && !q) return 0; for(int i=1;i<=n;i++) l[i]=i-1, r[i]=i+1; r[n]=0; while(q--) { cin>>lf>>rg; l[r[rg]] = l[lf]; r[l[lf]] = r[rg]; if(l[lf]) cout<<l[lf]<<" "; else cout<<"* "; if(r[rg]) cout<<r[rg]<<"\n"; else cout<<"*\n"; } cout<<"-\n"; } return 0; } |
Sunday, 18 June 2017
Almost Shortest Path (UVa 12144, UVaLive 4210, Regionals 2008 >> Latin America - South America)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 502 struct Z { int v, cost; bool operator < (const Z &p) const { return p.cost<cost; } }; Z z, z2; int shortest[MX], forbidden[MX][MX]; vector<Z> adj[MX]; vector<int> parent[MX]; priority_queue<Z>pq; int dijkstra(int src, int dst, int node) { for(int i=0; i<node; i++) shortest[i]=1e9; z.v = src; z.cost = 0; pq.push(z); shortest[src]=0; while(!pq.empty()) { z = pq.top(); pq.pop(); int l = adj[z.v].size(); for(int i=0; i<l; i++) { z2 = adj[z.v][i]; if(forbidden[z.v][z2.v]==1) continue; if(shortest[z2.v]>shortest[z.v]+z2.cost) { parent[z2.v].clear(); parent[z2.v].push_back(z.v); z2.cost = shortest[z2.v]= shortest[z.v]+z2.cost; pq.push(z2); } else if(shortest[z2.v]==shortest[z.v]+z2.cost) parent[z2.v].push_back(z.v); } } return shortest[dst]; } void removeEdge(int src, int dst) { if(dst==src) return; for(int i=0;i<parent[dst].size();i++) { forbidden[ parent[dst][i] ][dst] = 1; removeEdge(src, parent[dst][i]); } return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc,kk=1, node, edge, u, v, cost, src, dst; while(cin>>node>>edge && node) { cin>>src>>dst; for(int i=0; i<edge; i++) { cin>>u>>v>>cost; z.v = v; z.cost = cost; adj[u].push_back(z); } int tmp = 1e9; int mn = dijkstra(src, dst, node); //initial if(mn<1e9) { removeEdge(src, dst); //remove edges of shortest tmp = dijkstra(src, dst, node); //second time } if(tmp==1e9) tmp = -1; cout<<tmp<<endl; CLR(forbidden); for(int i=0;i<node;i++) { adj[i].clear(); parent[i].clear(); } } return 0; } |
Thursday, 8 June 2017
Reverse Integer (LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public: int reverse(int x) { bool flag = false; if(x<0) { flag = true; x*=-1; } int rev = 0; while(x) { if((rev*10)/10 != rev) return 0; // checking overflow rev = rev*10 + x%10; x/=10; } if(flag) rev*=-1; return rev; } }; |
Median of Two Sorted Arrays (LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int l1 = nums1.size(); int l2 = nums2.size(); if(l1>l2) return findMedianSortedArrays(nums2, nums1); int k = (l1+l2-1)>>1; int lft = 0, rgt = l1; while(lft<rgt) { int md = (lft+rgt)>>1; if(nums1[md]<nums2[k-md]) lft = md+1; else rgt = md; } double x, y; if(lft>0 && (k-lft)>=0) x = max(nums1[lft-1], nums2[k-lft]); else if(lft>0) x = nums1[lft-1]; else if(k-lft>=0) x = nums2[k-lft]; if((l1+l2) & 1) return x; //total odd size, single median if(lft<l1 && (k-lft+1)<l2) y = min(nums1[lft], nums2[k-lft+1]); else if(lft<l1) y = nums1[lft]; else if((k-lft+1)<l2) y = nums2[k-lft+1]; return (x+y)/2.0; } }; |
Sunday, 4 June 2017
Football (UVa 12673, UVaLive 6530, Regionals 2013 >> Latin America)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 struct match{ int score, receive; bool operator < (const match &m) const{ return m.score-m.receive < score-receive ; } }; match mth[MX]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc,kk=1, n, g; //cin>>tc; while(cin>>n>>g) { for(int i=0;i<n;i++) cin>>mth[i].score>>mth[i].receive; sort(mth, mth+n); int point = 0; for(int i=0;i<n;i++) { //cout<<mth[i].score<<" "<<mth[i].receive<<endl; if(mth[i].score>mth[i].receive) point += 3; else if(mth[i].score==mth[i].receive) { if(g>0) { point += 3; g--; } else point += 1; } else if(mth[i].score<mth[i].receive) { if(g>(mth[i].receive-mth[i].score)) { point += 3; g= g-(mth[i].receive-mth[i].score)-1; } else if(g==(mth[i].receive-mth[i].score)) { point += 1; g= g-(mth[i].receive-mth[i].score); } } } cout<<point<<endl; } return 0; } |
Saturday, 3 June 2017
Proving Equivalences (UVa 12167, UVaLive 4287, Regionals 2008 >> Europe - Northwestern)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 vector<int>adj[20002]; stack<int>stk; int t, lo[20002], tim[20002], vis[20002], sccrm[20002], scc, done; void tarjan_scc(int u) { t++; vis[u]=1; lo[u]=tim[u]=t; stk.push(u); for(int i=0;i<adj[u].size();i++) { int v = adj[u][i]; if(!vis[v]) { tarjan_scc(v); lo[u]=min(lo[u], lo[v]); } else if(vis[v]==1) lo[u]=min(lo[u], tim[v]); } if(lo[u]==tim[u]) { scc++; do{ done = stk.top(); stk.pop(); sccrm[done]=scc; vis[done]=2; }while(done!=u); } return; } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int kk=1, tc, n, m, u, v; string s; cin>>tc; while(tc--) { cin>>n>>m; t=scc=0; while(!stk.empty()) stk.pop(); for(int i=1;i<=n;i++) { adj[i].clear(); vis[i]=0; } while(m--) { cin>>u>>v; adj[u].push_back(v); } for(int i=1;i<=n;i++) if(!vis[i]) tarjan_scc(i); // checking zero indegree and outdegree of scc bool hasIndegree[scc+2], hasOutdegree[scc+2]; CLR(hasIndegree); CLR(hasOutdegree); for(int i=1;i<=n;i++) for(int j=0;j<adj[i].size();j++) if(sccrm[i]!=sccrm[adj[i][j]]) //not in same scc { hasIndegree[sccrm[i]]=true; hasOutdegree[sccrm[adj[i][j]]]=true; } int zeroIndgree=0, zeroOutdegree=0; for(int i=1;i<=scc;i++) { if(!hasIndegree[i]) zeroIndgree++; if(!hasOutdegree[i]) zeroOutdegree++; } if(scc==1) cout<<0<<endl; else cout<<max(zeroIndgree, zeroOutdegree)<<endl; //cout<<"Case "<<kk++<<": "<< <<"\n"; } return 0; } |
Thursday, 1 June 2017
Interval Product (UVa 12532, UVaLive 6139, Regionals 2012 >> Latin America)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int z1, z2, node[MX*4]; void insert(int idx, int st, int ed, int s, int e, int val) { if(st==s && ed==e) { if(val>0) node[idx]=1; else if(val<0) node[idx]=-1; else node[idx]=0; return; } int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1; if(e<=mid) insert(lft, st, mid, s, e, val); else if(s>mid) insert(rgt, mid+1, ed, s, e, val); else { insert(lft, st, mid, s, mid, val); insert(rgt, mid+1, ed, mid+1, e, val); } node[idx] = node[lft] * node[rgt]; return; } int query(int idx, int st, int ed, int s, int e) { if(st==s && ed==e) { return node[idx]; } int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1; if(e<=mid) return query(lft, st, mid, s, e); else if(s>mid) return query(rgt, mid+1, ed, s, e); else return query(lft, st, mid, s, mid)*query(rgt, mid+1, ed, mid+1, e); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc,kk=1, n, q, x, y; char c; string s; while(cin>>n>>q) { for(int i=1;i<=n*4;i++) node[i]=1; for(int i=1; i<=n; i++) { cin>>x; insert(1, 1, n, i, i, x); } while(q--) { cin>>c>>x>>y; if(c=='C') insert(1, 1, n, x, x, y); else { z1 = query(1, 1, n, x, y); //cout<<z1.pos<<" "<<z1.neg<<" "<<z1.zero<<endl; if(z1==0) cout<<"0"; else if(z1<0) cout<<"-"; else cout<<"+"; } } cout<<endl; } return 0; } |
Monday, 24 April 2017
Tidy Numbers (Codejam Qualification Round 2017, Problem B)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 #define READ freopen("B-large-practice.in", "r", stdin) #define WRITE freopen("output.txt", "w", stdout) vector<long long>tidy; void precal(int sz, long long number) { if(sz==18) { tidy.push_back(number); return; } int lastDigit = number%10; for(int i=lastDigit;i<=9;i++) precal(sz+1, number*10+i); return; } int main() { READ; WRITE; ios_base::sync_with_stdio(0);cin.tie(0); int tc,kk=1; long long n; string s; cin>>tc; precal(0, 0); while(tc--) { cin>>n; auto it = upper_bound(tidy.begin(), tidy.end(), n); it--; cout<<"Case #"<<kk++<<": "<< *it <<"\n"; } return 0; } |
Oversized Pancake Flipper ( Codejam Qualification Round 2017, Problem A)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 #define READ freopen("A-large-practice.in", "r", stdin) #define WRITE freopen("output.txt", "w", stdout) int minFlip(string s, int k) { int n = s.length(); int cnt = 0; for(int i=0;i<=n-k;i++) { if(s[i]=='-') { cnt++; for(int j=i;j<i+k;j++) s[j] = s[j]=='-' ? s[j]='+' : s[j]='-'; } } for(int i=n-1;i>n-k;i--) if(s[i]!='+') return -1; return cnt; } int main() { READ; WRITE; ios_base::sync_with_stdio(0);cin.tie(0); int tc,kk=1, n, k; string s; cin>>tc; while(tc--) { cin>>s; cin>>k; n = minFlip(s, k); if(n==-1) cout<<"Case #"<<kk++<<": IMPOSSIBLE\n"; else cout<<"Case #"<<kk++<<": "<< n <<"\n"; } return 0; } |
Subscribe to:
Posts (Atom)