| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
233#include<iostream>
using namespace std;
int s[100010],q[100010];
int isd(int a,int b,int c,int d){return (s[a]-s[b])*(c-d)-(s[c]-s[d])*(a-b);}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int main()
{
int n=1,l,i,j,f,b,a1,a2,tp;char c=0;
while (1){c=getchar();if (c=='\n') break;s[n]=s[n-1]+c-'0';n++;}
scanf("%d",&l);s[0]=a1=f=b=0;a2=l;n--;
for (i=l,j=i-l;i<=n;i++,j++)
{
while (f<b-1 && isd(j,q[b-1],j,q[b-2])<0) b--;
q[b++]=j;
while (f<b-1 && isd(i,q[f+1],i,q[f])>=0) f++;
tp=isd(i,q[f],a2,a1);
if (tp>0 || (tp==0 && (i-q[f]<a2-a1))) a1=q[f],a2=i;
}
tp=a1;a1=s[a2]-s[a1];a2-=tp;tp=gcd(a1,a2);
printf("%d/%d",a1/tp,a2/tp);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator