#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>
using namespace std;
#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define LL long long
#define MX 12
#define MOD 1000000007
struct Z{
int row,col;
char c;
};
main()
{
int n,r,c;
Z z,z1,z2;
int pos1,pos2;
string s;
cin>>n;
vector<Z>mat;
stack<Z>mat2;
//stack<Z>mat;
while(n--)
{
cin>>z.c>>z.row>>z.col;
mat.PB(z);
mat2.push(z);
}
int matl=mat.size();
while(cin>>s)
{
bool chk=true;
int sl=s.length();
stack<Z>stk;
stk=mat2;
LL sum=0;
FOR(i,sl)
{
if(s[i]==')')
{
Z aa,bb;
aa=stk.top();
stk.pop();
bb=stk.top();
stk.pop();
if(bb.col==aa.row)
{
sum+=(bb.row*bb.col*aa.col);
z.c='x';
z.row=bb.row;
z.col=aa.col;
stk.push(z);
}
else
{
chk=false;
break;
}
}
else if(isalpha(s[i]))
{
FOR(j,matl)
if(mat[j].c==s[i])
{
z.c=mat[j].c;
z.row=mat[j].row;
//cout<<z.row<<endl;
z.col=mat[j].col;
//cout<<z.col<<endl;
stk.push(z);
break;
}
}
}
if(chk)
cout<<sum<<endl;
else
cout<<"error"<<endl;
}
return 0;
}
Sunday, 19 August 2012
Monday, 13 August 2012
Spoj 4301. Tables Solution
#include<iostream> #include<algorithm> using namespace std; int main() { long long n,k,s,cnt,a[2000],i,sum,ks; while(cin>>n>>k>>s) { ks=k*s; sum=0; for(i=0;i<n;i++) cin>>a[i]; sort(a,a+n); for(i=1;i<=n;i++) { sum+=a[n-i]; if(sum>=ks) break; } cout<<i<<endl; } }
URAL 1014. Product of Digits Solution
#include<iostream> using namespace std; int main() { long long i,q; string s; while(cin>>q) { if(q==0) {cout<<"10"<<endl; continue;} if(q==1) {cout<<"1"<<endl; continue;} s=""; for(i=9;i>1;i--) { if(q>=i && q%i==0) { q/=i; s+=i+'0'; i=10; } } if(q==1) { for(i=s.length()-1;i>=0;i--) cout<<s[i]; cout<<endl; } else cout<<"-1"<<endl; } }
URAL 1293. Eniya Solution
#include<iostream> using namespace std; int main() { long long n,a,b; while(cin>>n>>a>>b) cout<<n*a*b*2<<endl; }
URAL 1409. Two Gangsters Solution
#include<iostream> using namespace std; int main() { int a,b,c; while(cin>>a>>b) { c=a+b-1; cout<<c-a<<" "<<c-b<<endl; } }
Spoj 11. Factorial Solution
#include<iostream> #include<list> #include<string> #include<cstring> #include<sstream> #include<cctype> #include<string.h> #include<algorithm> #include<cmath> #include<stack> #include<fstream> #include<cstdlib> #include<vector> #include<map> #include<utility> #include<iomanip> #include<queue> using namespace std; #define INF (1<<29) #define SET(a) memset(a,-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define CLR(a) memset(a,0,sizeof(a)) #define FILL(a,v) memset(a,v,sizeof(a)) #define PB push_back #define FOR(i,n) for(int i = 0;i<n;i++) #define PI acos(-1.0) #define EPS 1e-9 #define MP(a,b) make_pair(a,b) #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define LL long long int main() { int point1,point2,n,x1,y1,x2,y2,ans; while(cin>>n>>x1>>y1>>x2>>y2) { if(y1==0) point1=1; else if(x1==n) point1=2; else if(y1==n) point1=3; else if(x1==0) point1=4; if(y2==0) point2=1; else if(x2==n) point2=2; else if(y2==n) point2=3; else if(x2==0) point2=4; if((point1==point2) && (point1==1 || point1==3)) { if(x1>x2) ans=x1-x2; else ans=x2-x1; } else if((point1==point2) && (point1==2 || point1==4)) { if(y1>y2) ans=y1-y2; else ans=y2-y1; } else if(point1==1 && point2==2) ans=y2+n-x1; else if(point1==2 && point2==1) ans=y1+n-x2; else if(point1==2 && point2==3) ans=n-x2+n-y1; else if(point1==3 && point2==2) ans=n-x1+n-y2; else if(point1==3 && point2==4) ans=x1+n-y2; else if(point1==4 && point2==3) ans=x2+n-y1; else if(point1==4 && point2==1) ans=x2+y1; else if(point1==1 && point2==4) ans=x1+y2; else if((point1==1 && point2==3) || (point1==3 && point2==1)) ans=min(3*n-x1-x2, n+x1+x2); else if((point1==2 && point2==4) || (point1==4 && point2==2)) ans=min(3*n-y1-y2, n+y1+y2); cout<<ans<<endl; } return 0; }
Spoj 4038. Counting The Way of Bracket Replacement Solution
#include<iostream> #include<list> #include<string> #include<cstring> #include<sstream> #include<cctype> #include<string.h> #include<algorithm> #include<cmath> #include<stack> #include<fstream> #include<cstdlib> #include<vector> #include<map> #include<utility> #include<iomanip> #include<queue> using namespace std; #define INF (1<<29) #define SET(a) memset(a,-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define CLR(a) memset(a,0,sizeof(a)) #define FILL(a,v) memset(a,v,sizeof(a)) #define PB push_back #define FOR(i,n) for(int i = 0;i<n;i++) #define PI acos(-1.0) #define EPS 1e-9 #define MP(a,b) make_pair(a,b) #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define LL long long #define MOD 100000 bool moduloUsed; LL memo[200+10][200+10]; string s; LL func(int left, int right) { int i, valid; if(left>right) return 1; if(memo[left][right]!=-1) return memo[left][right]; LL ret=0; for(i=left+1;i<=right;i+=2) { if(s[left]=='(' && s[i]==')') valid=1; else if(s[left]=='{' && s[i]=='}') valid=1; else if(s[left]=='[' && s[i]==']') valid=1; else if(s[left]=='?' && s[i]==')') valid=1; else if(s[left]=='?' && s[i]=='}') valid=1; else if(s[left]=='?' && s[i]==']') valid=1; else if(s[left]=='(' && s[i]=='?') valid=1; else if(s[left]=='{' && s[i]=='?') valid=1; else if(s[left]=='[' && s[i]=='?') valid=1; else if(s[left]=='?' && s[i]=='?') valid=3; else valid=0; ret+=valid*func(left+1,i-1)*func(i+1,right); if(ret>MOD) { moduloUsed=true; ret%=MOD; } } return memo[left][right]=ret; } int main() { LL ans,length; while(cin>>length>>s) { SET(memo); ans=func(0,length-1); if(!moduloUsed) cout<<ans<<endl; else printf("%05lld\n",ans); } return 0; }
URAL 1146. Maximum Sum Solution
#include<iostream> #include<list> #include<string> #include<cstring> #include<sstream> #include<cctype> #include<string.h> #include<algorithm> #include<cmath> #include<stack> #include<fstream> #include<cstdlib> #include<vector> #include<map> #include<utility> #include<iomanip> #include<queue> using namespace std; #define clr(a) memset(a,0,sizeof(a)) #define PB push_back #define pi acos(-1.0) #define eps 1e-9 long sum[120][120]; int main() { long n,a,b,c,d,arr[120][120]; long max,temp; cin>>n; { max=-100000000; for(a=1;a<=n;a++) for(b=1;b<=n;b++) cin>>arr[a][b]; for(a=1;a<=n;a++) for(b=1;b<=n;b++) for(c=1;c<=a;c++) for(d=1;d<=b;d++) sum[a][b]+=arr[c][d]; for(a=1;a<=n;a++) for(b=1;b<=n;b++) for(c=1;c<=a;c++) for(d=1;d<=b;d++) { temp=sum[a][b]-sum[a][d-1]-sum[c-1][b]+sum[c-1][d-1]; //cout<<sum[a][b]<<" "<<sum[a][d]<<" "<<sum[c][b]<<" "<<sum[c][d]<<endl; //cout<<temp<<endl; if(temp>max) max=temp; } cout<<max<<endl; } //clr(sum); return 0; }
URAL 1079. Maximum Solution
#include<iostream> #include<list> #include<string> #include<cstring> #include<sstream> #include<cctype> #include<string.h> #include<algorithm> #include<cmath> #include<stack> #include<fstream> #include<cstdlib> #include<vector> #include<map> #include<utility> #include<iomanip> #include<queue> using namespace std; #define INF (1<<29) #define SET(a) memset(a,-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define CLR(a) memset(a,0,sizeof(a)) #define FILL(a,v) memset(a,v,sizeof(a)) #define PB push_back #define FOR(i,n) for(int i = 0;i<n;i++) #define PI acos(-1.0) #define EPS 1e-9 #define MP(a,b) make_pair(a,b) #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define LL long long int main() { int tc,a[100000],mx,n,i; a[0]=0; a[1]=1; for(i=2;i<100000;i+=2) { a[i]=a[i/2]; a[i+1]=a[i/2]+a[i/2+1]; } //cin>>tc; while(cin>>n) { if(n==0) break; //cin>>n; mx=0; for(i=1;i<=n;i++) if(a[i]>mx) mx=a[i]; cout<<mx<<endl; } return 0; }
Spoj 3693. Maximum Sum Solution
#include<iostream> #include<list> #include<string> #include<cstring> #include<sstream> #include<cctype> #include<string.h> #include<algorithm> #include<cmath> #include<stack> #include<fstream> #include<cstdlib> #include<vector> #include<map> #include<utility> #include<iomanip> #include<queue> using namespace std; #define INF (1<<29) #define SET(a) memset(a,-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define CLR(a) memset(a,0,sizeof(a)) #define FILL(a,v) memset(a,v,sizeof(a)) #define PB push_back #define FOR(i,n) for(int i = 0;i<n;i++) #define PI acos(-1.0) #define EPS 1e-9 #define MP(a,b) make_pair(a,b) #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define LL long long #define MX 110000 struct Node{ LL mx,sum; }; Node nd[MX*4]; int lazy_value[4*MX]; bool lazy[4*MX]; void update_node(int idx, int st, int ed, LL val) { lazy[idx]=1; lazy_value[idx]=val; nd[idx].mx=val; nd[idx].sum=val; } void update_lazy(int idx, int st, int ed) { if(st==ed) return; int mid=(st+ed)/2; update_node(2*idx, st, mid, lazy_value[idx]); update_node(2*idx+1, mid+1, ed, lazy_value[idx]); lazy[idx]=lazy_value[idx]=0; } void insert(int idx, int st, int ed, int s, int e, LL val) { if(st==s && ed==e) { update_node(idx, st, ed, val); return; } //if(lazy[idx]) update_lazy(idx, st, ed); int mid=(st+ed)/2; if(e<=mid) insert(idx*2, st, mid, s, e, val); else insert(idx*2+1, mid+1, ed, s, e, val); /*else { insert(idx*2, st, mid, s, mid, val); insert(idx*2+1, mid+1, ed, mid+1, e, val); }*/ //mx[idx]=max(mx[idx*2], mx[idx*2+1]); nd[idx].mx = max(nd[idx*2].mx, nd[idx*2+1].mx); nd[idx].sum = max3(nd[idx*2].sum, nd[idx*2+1].sum, nd[idx*2].mx + nd[idx*2+1].mx); //n[idx].sum = max(n[idx.sum], ; return; } Node query(int idx, int st , int ed, int s, int e) { if(st==s && ed==e) return nd[idx]; //if(lazy[idx]) update_lazy(idx, st, ed); int mid=(st+ed)/2; if(mid>=e) return query(2*idx, st, mid, s, e); else if(s>mid) return query(2*idx+1, mid+1, ed, s, e); else //return max(query(idx*2, st, mid, s, mid), query(idx*2+1, mid+1, ed, mid+1, e)); { Node ret,a,b; a = query(idx*2, st, mid, s, mid); b = query(idx*2+1, mid+1, ed, mid+1, e); ret.mx = max(a.mx, b.mx); ret.sum = max3(a.sum, b.sum, a.mx + b.mx); return ret; } } int main() { int n, i, q, cnt, st, ed; LL val; char c; // string s_line; //cin>>n; scanf("%d",&n); for(i=1;i<=n;i++) { //cin>>val; scanf("%lld",&val); insert(1, 1, n, i, i, val); } //cin>>q; scanf("%d",&q); while(q--) { getchar(); //cin>>c; //cin>>st>>ed; scanf("%c%d%",&c,&st); if(c=='U') { scanf("%lld",&val); insert(1, 1, n, st, st, val); } else { scanf("%d",&ed); printf("%lld\n",query(1, 1, n, st, ed).sum); //cout<<<<endl; } } return 0; }
Period (Spoj 263, UVa 1328, UVaLive 3026, Regionals 2004 >> Europe - Southeastern)
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 | /// 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 1000010 string pattern; int failur[MX],length_b,cnt; void FailureFunction() { int i=1,j=0; failur[0]=0; while(i<length_b) { if(pattern[i]==pattern[j]) { j++; failur[i]=j; i++; } else if(j>0) j=failur[j-1]; else { failur[i]=0; i++; } } return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t,kk=1; while(cin>>length_b && length_b) { cin>>pattern; CLR(failur); FailureFunction(); cout<<"Test case #"<<kk++<<endl; for(int i=1; i<length_b; i++) { int miss_matched=i+1-failur[i]; if((i+1)%miss_matched==0) if((i+1)/miss_matched>1) cout<<i+1<<" "<<(i+1)/miss_matched<<endl; } cout<<endl; } return 0; } |
Spoj 3921. The Great Ball Solution
#include<iostream> #include<list> #include<string> #include<cstring> #include<sstream> #include<cctype> #include<string.h> #include<algorithm> #include<cmath> #include<stack> #include<fstream> #include<cstdlib> #include<vector> #include<map> #include<set> #include<utility> #include<iomanip> #include<queue> using namespace std; #define INF (1<<29) #define SET(a) memset(a,-1,sizeof(a)) #define ALL(a) a.begin(),a.end() #define CLR(a) memset(a,0,sizeof(a)) #define FILL(a,v) memset(a,v,sizeof(a)) #define PB push_back #define FOR(i,n) for(int i = 0;i<n;i++) #define PI acos(-1.0) #define EPS 1e-9 #define MP(a,b) make_pair(a,b) #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define LL long long #define MX 10000010 #define MOD 1000000007 struct Z{ int time; bool chk; bool operator < (const Z &p) const{ if(time==p.time) return chk<p.chk; return time>p.time; } }; main() { int t,n,tm,i; cin>>t; while(t--) { priority_queue<Z>pq; Z TM; int cnt=0, mx=0; cin>>n; for(i=0;i<n*2;i++) { cin>>tm; TM.time=tm; if(i%2==0) TM.chk=true; else TM.chk=false; pq.push(TM); } for(i=0;i<n*2;i++) { TM=pq.top(); if(TM.chk) { cnt++; mx=max(cnt,mx); } else cnt--; pq.pop(); } //cout<<pq.top().time<<endl; cout<<mx<<endl; } }
Subscribe to:
Posts (Atom)