Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

233

Posted by meaningful at 2017-09-14 19:33:22 on Problem 1733
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator