/// 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 main() { ios_base::sync_with_stdio(0);cin.tie(0); int kk=1, tc, n, m, k, x; string s; cin>>tc; while(tc--) { vector<int>nowID, nextID, nowData, nextData, initial; cin>>n>>k; m=(1<<n); vector<int> child[m+2]; initial.push_back(0); for(int i=1;i<=m;i++) { cin>>x; initial.push_back(x); nowData.push_back(x); nowID.push_back(i); } while(nowData.size()>1) { for(int i=0;i<nowData.size();i+=2) { if(nowData[i]>=nowData[i+1]) { nextData.push_back(min(initial[nowID[i]], nowData[i]-nowData[i+1]+k)); nextID.push_back(nowID[i]); child[nowID[i]].push_back(nowID[i+1]); } else { nextData.push_back(min(initial[nowID[i+1]], nowData[i+1]-nowData[i]+k)); nextID.push_back(nowID[i+1]); child[nowID[i+1]].push_back(nowID[i]); } } nowData=nextData; nowID=nextID; nextData.clear(); nextID.clear(); } cout<<nowID[0]<<"\n"; cout<<child[nowID[0]][0]; for(int i=1;i<child[nowID[0]].size();i++) cout<<" "<<child[nowID[0]][i]; cout<<"\n"; } return 0; }
Tuesday, 31 May 2016
Arm Wrestling Tournament (UVALive 5060, Regionals 2010 >> Asia - Jakarta)
Saturday, 28 May 2016
Tariff Plan (UVA 12157, UVALive 4405, Regionals 2008 >> Asia - Kuala Lumpur)
/// 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 main() { ios_base::sync_with_stdio(0);cin.tie(0); int kk=1, tc, n, m, duration; string s; cin>>tc; while(tc--) { int mile=0, juice=0; cin>>n; while(n--) { cin>>duration; mile+=(duration/30+1)*10; juice+=(duration/60+1)*15; } if(mile<juice) cout<<"Case "<<kk++<<": Mile "<< mile <<"\n"; else if(juice<mile) cout<<"Case "<<kk++<<": Juice "<< juice <<"\n"; else cout<<"Case "<<kk++<<": Mile Juice "<< mile <<"\n"; } return 0; }
Friday, 27 May 2016
Prime Path (UVA 12101, SPOJ PPATH, POJ 3126, HDU 1973, UVALive 3639, Regionals 2006 >> Europe - Northwestern)
/// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 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 10000 vector<int>prime; bool status[MX+2]; int pl; void PrimeGenerate(int n) { int sq=sqrt(n); for(int i=3; i<=sq; i+=2) { if(!status[i]) for(int j=i*i; j<=n; j+=(i<<1)) status[j]=true; } status[0]=status[1]=true; for(int i=4;i<=n;i+=2) status[i]=true; prime.push_back(2); for(int i=3; i<=n; i+=2) if(!status[i]) prime.push_back(i); return; } int dp[MX], st, ed, taken[MX], dist[10010]; vector<int>v[10010]; int bfs(int num) { if(num==ed) return 1; dist[num]=1; queue<int>Q; Q.push(num); while(!Q.empty()) { int qq=Q.front(); Q.pop(); for(int i=0;i<v[qq].size();i++) if(!dist[v[qq][i]]) { dist[v[qq][i]]=dist[qq]+1; if(v[qq][i]==ed) return dist[v[qq][i]]; Q.push(v[qq][i]); } } return 100000; } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc, kk=1, n; PrimeGenerate(MX); int loopst; pl=prime.size(); for(int i=0;i<pl;i++) if(prime[i]>999) { loopst=i; break; } for(int i=loopst;i<pl;i++) { for(int j=loopst;j<pl;j++) { int tmp=prime[i]; int tmp2=prime[j], cnt=0; while(tmp && tmp2) { if(tmp%10 != tmp2%10) cnt++; tmp/=10; tmp2/=10; } if(cnt==1) { v[prime[i]].push_back(prime[j]); } } } cin>>tc; while(tc--) { cin>>st>>ed; if(ed>st) swap(st, ed); CLR(dist); int ans=bfs(st); if(ans<100000) cout<<ans-1<<"\n"; else cout<<"Impossible\n"; } return 0; }
Hours and Minutes (UVA 12531, UVALive 6138, Regionals 2012 >> Latin America)
/// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 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 100000 int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc, kk=1, n; while(cin>>n) { if(n%6) cout<<"N\n"; else cout<<"Y\n"; } return 0; }
Subscribe to:
Posts (Atom)