Cod sursa(job #254694)
| Utilizator |  Mihai-Alexandru Dusmanu dushmi |
Data | 7 februarie 2009 13:46:08 |
|---|---|---|---|
| Problema | Cuburi2 | Scor | 14 |
| Compilator | cpp | Status | done |
| Runda | Stelele Informaticii 2009, clasele 9-10, ziua 2 | Marime | 23.18 kb |
#include<stdio.h>
long max,pmax,x,y,i,n,m,j,n2,n3,n1,p,k,t,n4,pmaxx,l,init,smax[1001],a[1001],s[1001],st[1001],h[250001];
long comp()
{
if (n3<n4)
{
return -1;
}
else if (n3>n4)
{
return +1;
}
for(int ii=n3;ii>=0;ii--)
{
if (st[ii]<smax[ii])
{
return -1;
}
else if (st[ii]>smax[ii])
{
return +1;
}
}
return 0;
}
int main()
{
freopen("cuburi2.in","r",stdin);
freopen("cuburi2.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
scanf("%ld",&h[i]);
for(i=1;i<=m;i++)
{
scanf("%ld%ld",&x,&y);
for(j=1;j<=n3;j++) st[j]=0;
for(j=1;j<=n2;j++) s[j]=0;
n2=n3=0;
p=h[y];
do
{
st[++n3]=p%10;
s[++n2]=p%10;
p/=10;
}
while(p);
for(j=y-1;j>=x+1;j--)
{
p=h[j];
n1=0;
do
{
a[++n1]=p%10;
p/=10;
}
while(p);
t=0;
if(n2>n1)
{
for(k=n1+1;k<=n2;k++)
a[k]=0;
n1=n2;
}
else
{
for(k=n2+1;k<=n1;k++)
s[k]=0;
n2=n1;
}
for(k=1;k<=n1;k++)
{
s[k]+=a[k]+t;
t=s[k]/10;
s[k]=s[k]%10;
}
if(t>0) s[++n2]=t;
t=0;
if(n3>n2)
{
for(k=n2+1;k<=n3;k++)
s[k]=0;
n2=n3;
}
else
{
for(k=n3+1;k<=n2;k++)
st[k]=0;
n3=n2;
}
for(k=1;k<=n2;k++)
{
st[k]+=s[k]+t;
t=st[k]/10;
st[k]=st[k]%10;
}
if(t>0) st[++n3]=t;
}
n4=n3;
for(k=1;k<=n4;k++)
smax[k]=st[k];
pmaxx=x;
for(l=x+1;l<=y;l++)
{
for(init=1;init<=1000;init++)
st[init]=s[init]=0;
pmax=l;
if(pmax!=x && pmax!=y)
{
n2=n3=0;
p=h[x];
do
{
st[++n3]=p%10;
s[++n2]=p%10;
p/=10;
}
while(p);
for(j=x+1;j<=pmax-1;j++)
{
p=h[j];
n1=0;
do
{
a[++n1]=p%10;
p/=10;
}
while(p);
t=0;
if(n2>n1)
{
for(k=n1+1;k<=n2;k++)
a[k]=0;
n1=n2;
}
else
{
for(k=n2+1;k<=n1;k++)
s[k]=0;
n2=n1;
}
for(k=1;k<=n1;k++)
{
s[k]+=a[k]+t;
t=s[k]/10;
s[k]=s[k]%10;
}
if(t>0) s[++n2]=t;
t=0;
if(n3>n2)
{
for(k=n2+1;k<=n3;k++)
s[k]=0;
n2=n3;
}
else
{
for(k=n3+1;k<=n2;k++)
st[k]=0;
n3=n2;
}
for(k=1;k<=n2;k++)
{
st[k]+=s[k]+t;
t=st[k]/10;
st[k]=st[k]%10;
}
if(t>0) st[++n3]=t;
}
for(j=1;j<=n2;j++) s[j]=0;
for(j=y;j>=pmax+1;j--)
{
p=h[j];
n1=0;
do
{
a[++n1]=p%10;
p/=10;
}
while(p);
t=0;
if(n2>n1)
{
for(k=n1+1;k<=n2;k++)
a[k]=0;
n1=n2;
}
else
{
for(k=n2+1;k<=n1;k++)
s[k]=0;
n2=n1;
}
for(k=1;k<=n1;k++)
{
s[k]+=a[k]+t;
t=s[k]/10;
s[k]=s[k]%10;
}
if(t>0) s[++n2]=t;
t=0;
if(n3>n2)
{
for(k=n2+1;k<=n3;k++)
s[k]=0;
n2=n3;
}
else
{
for(k=n3+1;k<=n2;k++)
st[k]=0;
n3=n2;
}
for(k=1;k<=n2;k++)
{
st[k]+=s[k]+t;
t=st[k]/10;
st[k]=st[k]%10;
}
if(t>0) st[++n3]=t;
}
}
else if(pmax==x)
{
n2=n3=0;
p=h[y];
do
{
st[++n3]=p%10;
s[++n2]=p%10;
p/=10;
}
while(p);
for(j=y-1;j>=x+1;j--)
{
p=h[j];
n1=0;
do
{
a[++n1]=p%10;
p/=10;
}
while(p);
t=0;
if(n2>n1)
{
for(k=n1+1;k<=n2;k++)
a[k]=0;
n1=n2;
}
else
{
for(k=n2+1;k<=n1;k++)
s[k]=0;
n2=n1;
}
for(k=1;k<=n1;k++)
{
s[k]+=a[k]+t;
t=s[k]/10;
s[k]=s[k]%10;
}
if(t>0) s[++n2]=t;
t=0;
if(n3>n2)
{
for(k=n2+1;k<=n3;k++)
s[k]=0;
n2=n3;
}
else
{
for(k=n3+1;k<=n2;k++)
st[k]=0;
n3=n2;
}
for(k=1;k<=n2;k++)
{
st[k]+=s[k]+t;
t=st[k]/10;
st[k]=st[k]%10;
}
if(t>0) st[++n3]=t;
}
}
else if(pmax==y)
{
n2=n3=0;
p=h[x];
do
{
st[++n3]=p%10;
s[++n2]=p%10;
p/=10;
}
while(p);
for(j=x+1;j<y;j++)
{
p=h[j];
n1=0;
do
{
a[++n1]=p%10;
p/=10;
}
while(p);
t=0;
if(n2>n1)
{
for(k=n1+1;k<=n2;k++)
a[k]=0;
n1=n2;
}
else
{
for(k=n2+1;k<=n1;k++)
s[k]=0;
n2=n1;
}
for(k=1;k<=n1;k++)
{
s[k]+=a[k]+t;
t=s[k]/10;
s[k]=s[k]%10;
}
if(t>0) s[++n2]=t;
t=0;
if(n3>n2)
{
for(k=n2+1;k<=n3;k++)
s[k]=0;
n2=n3;
}
else
{
for(k=n3+1;k<=n2;k++)
st[k]=0;
n3=n2;
}
for(k=1;k<=n2;k++)
{
st[k]+=s[k]+t;
t=st[k]/10;
st[k]=st[k]%10;
}
if(t>0) st[++n3]=t;
}
}
if(comp()==-1)
{
n4=n3;
for(k=1;k<=n4;k++)
smax[k]=st[k];
pmaxx=l;
}
if(comp()==0)
pmaxx=l;
}
printf("%ld ",pmaxx);
for(j=n4;j>=1;j--)
printf("%ld",smax[j]);
n4=0;
printf("\n");
}
return 0;
}
