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