1000000000 1000000001 100000000000000000 1000000000000000000 for such kind of tests my solution works more than 10 sec, here I got AC in 0.031. I agree with you. I don`t think so! Confirming this test has to be added. My solution that got AC on the contest gets TLE on it. Please,give me some hints or advices to solve this problem help fr5om mathemation. For me was interesting mathematical nature of the problem. I got Ac under next understanding. We must find volume of intersection [l.r] with dison union of [kx,ky] and [k0*x,infinity] Thank you for your answer. I'm sorry, but i did not understand your method. Can you describe your method more widely. Form disjoint segments:[kx,ky],k=1,2,3.. When [kx,ky] will intersect with [(k+1)x-1,(k+1)y] at k=k0:stop. From this moment we have [k0*x,infinity[ After standard programming task: find intersection of given segment[l,r] and disjoint system of closed segments. Edited by author 14.10.2009 17:30 Edited by author 15.10.2009 19:22 Congratulage! To implment that isue to be great! Very interesting problem, took me 2 days :). I started out wrong, but then saw the progression of [kx,ky] and the gaps between them. My solution subtracts the gaps from [l,r]. I had an initial misconception of the progression of the gaps, but corrected it and got AC. It's interesting that if y > x then the gaps will always shrink to size zero, eventually. Hi admin, I misunderstood the problem. More precisely, I replaced the sentence: the problem set of any contest must contain at least x and at most y problems with this one: the problem set of any contest must contain either x or y problems It turned out that the modified version of the problem is also solvable, and I have designed the program for submittion. Unsurprisingly, I got Wrong Answer. Now, I will try to solve the original problem. And, admin, would you please consider to add the modified version to the ProblemSet? I use solution with O(1). The idea was conected with arithmetical progression. it passes throw all tests but 22 and later. I don' know what to do. To do calculations while [kx,ky] and [(k+1)x,(k+1)y] not intersect is very slow solution There is an O(1) solution. Give pls some tests, for different errors 4 5 7 13 3 6 11 99 6 8 11 99 10 13 20 200 50 56 20 200 30 33 20 200 19 21 20 200 11 11 20 200 10 10 20 200 10 15 17 18 10 15 16 19 10 15 15 20 20 33 14 19 1 1 1 1 2222222222222221 2222222222222222 100000000000000000 200000000000000000 16 19 5 11 10 33 16 25 10 21 16 25 1 2 18 20 1 2 19 20 1 2 20 20 30 33 30 33 30 33 31 32 Answers: 5 89 87 178 40 69 109 17 19 0 0 2 0 1 3105 or so :) 0 10 10 3 2 1 4 2 Use these functions for debugging int f(int x,int y,int z) { int i; if (z==0) return 1; for (i=x;i<=y;i++) { if (i>z) break; if (f(x,y,z-i)==1) return 1; } return 0; } int ff(int x,int y,int l,int r) { int z=0; for (int k=l;k<=r;k++) z+=f(x,y,k); return z; } also: to verivy k*x>a for big numbers is better to use: k>=floor(a/x) if a%x!=0 k>a/x if a%x==0 because k*x can generate overflow I got Ac after using all attention to boundary values 10^18. Edited by author 11.10.2009 21:19 function calc(x, y, l ,r: int64): int64; var n, nx, ny: int64; n1,n2: int64; begin if l < x then l := x; if x > r then begin result := 0; exit; end; if ( x = 1 ) then begin result := (r - l + 1); exit; end; if x = y then begin result := ( r div x - ((l-1) div x) ); exit; end; if y + 1 >= x + x then begin result := (r - l + 1); exit; end; n := (y - 2) div ( y - x ) + 1; while (y * (n - 1) + 1 >= x * n) and (n > 0) do dec(n); if n * x <= l then begin result := (r - l + 1); exit; end; result := 0; if n*x <= r then begin result := r - n*x + 1; r:=n*x - 1; end; nx := (l + y - 1) div y; if nx*x > r then begin result := result + 0; exit; end; ny := r div x; if ny * y < l then begin result := result +0; exit; end; if ( ny * x <= l ) and (ny*y >= r)then begin result := result +r - l + 1; exit; end; if ( nx * x <= l ) and (nx*y >= r)then begin result := result +r - l + 1; exit; end; if (ny * y < l ) and ( ny * x + x > r) then begin result := result +(0); exit; end; if nx = ny then begin if l < nx * x then l := nx * x; if r > nx * y then r := ny * y; result := result +(r - l + 1); exit; end; if l < nx * x then l := nx * x; if r > nx * y then r := ny * y; n1 := nx + 1; n2 := ny - 1; if n1 <= n2 then result := result + (n2 - n1 + 1) + (y-x) * (( n1+n2) * (n2-n1+1) div 2); result := result + nx * y - l + 1 + (r - ny*x + 1);
end; |
|