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

re

Posted by xfxyjwf at 2005-09-08 12:43:16 on Problem 1032
In Reply To:狂赞楼主~~,我再补充一些证明步骤 Posted by:ray58750034 at 2005-09-08 12:39:19
> ----------------------------------------------------------------------------------------
> 1.1<a1
> 
> if a1=1, then a1(=1), a[t] together could be replaced by a[t]+1.
> reason:  a[t]+1>a[t]*1 
> 
> ----------------------------------------------------------------------------------------
> 2.to all i, 1<=a[i+1]-a[i]<=2;
> 
> if some i make a[i+1]-a[i]>2,
> then a[i],a[i+1] together could be replaced by a[i]+1,a[i+1]-1 together.
> 
> reason: a[i]*a[i+1] < (a[i]+1)*(a[i+1]-1)
> (a[i]+1)*(a[i+1]-1)=a[i]*a[i+1]+a[i+1]-a[i]-1 
> so a[i+1]-a[i]-1>0   (* a[i+1]-a[i]>2)
> 
> ----------------------------------------------------------------------------------------
> 3. at MOST one i, fits a[i+1]-a[i]=2
> 
> if i<j and a[i+1]-a[i]=2 and a[j+1]-a[j]=2 then
> a[i],a[j+1] could be replaced by a[i]+1, a[j+1]-1
> 
> reason: a[i]*a[j+1]< (a[i]+1)*(a[j+1]-1)
> so a[j+1]-a[i]-1>0   (* a[j]-a[i]>=1 a[j+1]-a[j]>=1 so a[j+1]-a[i]>=2 )
> 
> ----------------------------------------------------------------------------------------
> 4. a1<=3
> 
> if a1>=4, then a1,a2 together could be replaced by 2, a1-1, a2-1 together 
> 
> reason: a1*a2< 2*(a1-1)(a2-1)
> (a1-1)(a2-1)=a1*a2-a1-a2+1 
> so a1*a2>2*(a1+a2-1) (* a1>=4 and a2>=5)
> 
> ----------------------------------------------------------------------------------------
> 5. if a1=3 and one i fits a[i+1]-a[i]=2 then i must be t-1
> 
> if i<t-1 then a[i+2] could be replaced by 2, a[i+2]-2 together
> reason: a[i+2]<2*(a[i+2])-4
> so a[i+2]>4  (* a[1]=3 a[3]>=5 so a[i+2]>=5)

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