You CAN'T just assume x2 = x + 0.5 because x2 is some INTEGER / n. So max x2 can be x or x + 0.1 + x + 0.38 etc. Took me 15 minutes to ac after I understood it Any help? In WA5 X=Y and thus the answer should be "0" Arithmetic average is not exacltly x. Due to the rounding arithmetic average can be x + 0.01 or even x + 0.04999 Please tell me what could be the problem... WA14, Time limit exceeded, Time work 1.014 Visual C#: if (x!=10.0){ sum=ToInt32((x+0.05)*n); while (sum/n>=x+0.049999999999) sum--; } else { sum=x*n; } while (((ans+sum)/(ans+n))>=y+0.0499999999999 ) ans++; у меня та же ошибка, С# просто медленно работает. Это же решение на ++ заходит using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Globalization; namespace _1484Kino { class Program { static void Main(string[] args) { var userInput = Console.ReadLine().Split(); var x = double.Parse(userInput[0],CultureInfo.InvariantCulture); var y = double.Parse(userInput[1], CultureInfo.InvariantCulture); var n = int.Parse(userInput[2], CultureInfo.InvariantCulture); int count = 0; if (y > 0.9 && x<=10.0) { while (Math.Round(x, 1 )> 1) { x = ((x * n + 1) / (n + 1)); n += 1; count++; } Console.WriteLine(count); } else Console.WriteLine("Impossible"); } } } This enchanted test 8: I just can not get through it. Maybe there is just that unrepresentable case of "impossible", the emergence of which, under given conditions, I can not even imagine? I have a feeling that there is still some condition that the author forgot to mention. Most likely, this is the upper limit for the result. Edited by author 29.09.2018 22:19 I dont understand: when I had swaped 'Impossible' to '0' my program solved more tests than late. there is no test where the answer is impossible, you can can make every mark you want Even below 1.0 or above 10.0? I also do not see under what conditions it can be "impossible". Even if y = 1.0, then this is the result of rounding, but the ratio of the sum of estimates to their number, equal to 1.0499, really approaches. what's the trick? 3% of the ac rating..... what's the trick? 3% of the ac rating..... A lot of wrong tests - is all you need for low AC rating. I don't find mistakes in my program, but WA6 too my prog returns: 10.0 1.0 1000000 179000001 10.0 9.9 1 1 1.1 1.0 12345 123456 10.0 10.0 10 0 "Impossible" answer never returns
4.4 4.3 1000000 Maybe 14926? My AC program outputs 29851 How did you got that??? I use n*(y-x)/(1-y) (14926+4.4*1000)/(14926+1000000)=4.34999793088.. ((14926+4.4*1000)/(14926+1000000)):0:1=4.3 Edited by author 07.10.2006 21:08 You formula is incorrect. What if y == 1.0 ??? You are dividing by 0 ? y:=y+0.05-eps without rounding 1.0 will not be achieved Edited by author 07.10.2006 21:21 first: not (14926+4.4*1000)/(14926+1000000)=4.34999793088.. but (14926+4.4*1000000)/(14926+1000000)=4.34999793088.. second: not (14926+4.4*1000)/(14926+1000000)=4.34999793088.. but (14926+4449999)/(14926+1000000)=4.399261621 third: (29851+4449999)/(29851+1000000)=4.349998204 Yes you are right - i've made mistake while printing: 1000 -> 1000000, Thank you but i don't understand how we should compute not rounded X value I think that this task more harder than it seems after first reading:)
Edited by author 07.10.2006 22:45 x*n can be X=(x+.05)*n while (X/n>=x+0.05)X-- Edited by author 08.10.2006 00:45 mine is also 29851, but i still wa@6. I used y=y+0.05 in my program and get WA6. Why x should be increased x=x+0.05? 1.1 1.0 12345 My prog:24676 But Ihave Wa11 1.1 1.0 12345 My prog:24676 But Ihave Wa11 Can't understand Ans ((1.149999999) * 12345 + 24676) / (12345 + 24676) > 1.5 My Ans is 24692 for test 1.1 1.0 12345 rigth answer IMHO 24676, 24676 < 123456 my AC program works on this test cases 4.4 3.4 12478 5094 10 3.4 23577 63033 9.9 8.3 1000000 217687 4.6 1.2 12997 176760 6.6 2.2 44766 157576 10 1 2 359 2 1.9 1000000 105263 Edited by author 18.10.2006 02:45 Ivanidze, did you get AC? 9.9 8.3 1000000 217688 - 217687 makes into over 8.35 -> 8.4 6.6 2.2 44766 157577 - 157576 makes into over 2.25 -> 2.3 2.0 1.9 1000000 105264 - 105263 makes into over 1.95 -> 2.0 9.9 8.3 1000000 217688 - 217687 makes into over 8.35 -> 8.4 6.6 2.2 44766 157577 - 157576 makes into over 2.25 -> 2.3 2.0 1.9 1000000 105264 - 105263 makes into over 1.95 -> 2.0 Really? I think you are mistaken. For example: 6.6 2.2 44766 x<6.65=>x*n<6.65*n=297693.9 MAX(x*n)=297693, not 297694 because 297694/44766=6.6500..->6.7 (297693+157576)/(44766+157576)=2.24999752....->2.2 I suppose 9.9 8.3 1000000 217687 6.6 2.2 44766 157576 2.0 1.9 1000000 105263
Edited by author 10.10.2006 18:54 May be this test is useful. At least, it helped me :) 7.8 2.3 100 407 In this snare (x+0.05)*n is integer. In this case we should use (x+0.05)*n-1. Thank you. I had: "... SI:=(ceil((x+0.05)*n)-1)*100; ..." And now I have "... SI:=(ceil((x+0.05)*n-1e-10)-1)*100; ..." AC I think 7.8 2.3 100 must be 408. Am I right? AC rating became 2% try to submit your code 50 times and you'll get AC:))) How many times do I need to submit to get 1% rating??) Edited by author 22.02.2016 19:36 Is it guaranteed that input is always correct? For example, is this test possible 1.7 1.6 1 ? Edited by author 19.04.2011 03:28 Yes, input is correct. There are no such tests. What's wrong with this test? Answer is 1... Any one vote with "1" will put the rating below 1.6... (Task says "not greater than Y") Is there any tests where the answer is Impossible? I cant invent any where y=1 answer should be "Impossible" "where y=1 answer should be "Impossible"" sorry. it is not right because 1.0 ~ 1.04 9.1 10.0 1 you will never be able to get 10.0 (9.1+170)/18 = ? (9.95~10) ;) But actually 9.1 10.0 1 already fits to task - rating isn't greater Y! So seems answer should be 0 in this case... Edited by author 16.02.2016 15:27 Edited by author 16.02.2016 15:27 Edited by author 25.04.2012 19:42 {$N+} var x, y, temp:extended; n, l, r, m, sum, res:extended; function rnd(t:extended):extended; begin if frac(t)>=0.5 then rnd:=trunc(t)+1 else rnd:=trunc(t); end; begin readln(x, y, n); l:=10; r:=10*n; x:=x*10; sum:=-1; while l<=r do begin m:=trunc((l+r)/2); temp:=rnd(m/n*10); if abs(temp-x)<10e-12 then begin sum:=m; l:=m+1; continue; end; if temp<x then l:=m+1 else r:=m-1; end; {writeln(sum:0:0);} if sum=-1 then begin writeln('Impossible'); exit; end; l:=0; r:=2000000000; res:=-1; while l<=r do begin m:=trunc((l+r)/2); temp:=(sum+m)/(n+m); if rnd(temp*10)<=y*10 then begin res:=m; r:=m-1; end else l:=m+1; end; if res=-1 then writeln('Impossible') else writeln(res:0:0); end. If you count maximum value V such that V/N is equal to X (after rounding to one fractional digit) this note may be useful: V=floor(((X-1e-10)+0.049999999999999999999)*N); (if X<10.0) You should decrease X be 1e-10 because 9.9 may be equal to 9.90000000000004 or something like that. Next 9.9+0.0499999999999999 is rounded to 9.9 and you must find the maximal real X value (real = not rounded). The last note is that V is an integer value so you should use floor. When I found out there 3 facts I got AC. Sorry for my poor English, I hope this hint will help somebody Edited by author 22.10.2008 22:38 I use formula, i use binary search, i use linear search, and always got WA#8. search cin>>x>>y>>n; double X=(int)((x+0.05)*n); double Y=y+0.05; while (X/n>=x+0.05) X--; int ans=0; while (((double)(ans+X)/(ans+n))>=y+0.05 )ans++; cout<<ans; i'm going crazy: why it's not work?? Edited by author 08.10.2006 00:50 Ha-ha! I've solved it!!!! I think that you don't need to use binary search because of your formula is almost right, but it's ALMOST... I've had WA #8 too.. and I find out that's wrong in my solution in this test. I use only mathematic formulas. If you buy me beer in Rybinsk I told you what's wrong... But now... ;) i'm waitin' for some beer... I buy you beer in any case in Rybinsk. Give me test case where are i'm wrong. If x=10.0 then we shouldn't increase it right? Ivan, I think that Georgy Kerensky is right! when x is 10.0 then your double X must be equal to (int)(x*n) because of there is simple average 10.05 can't be! Also, I think that this inequality [ (ans+X)/(ans+n))>=y+0.05 ] you must solve in integer numbers... When I write in this way I'd got WA in different tests. But when this condition became to integer comparison I've got Accepted program... Here some test cases for testing your decision: 10 1 1000000 -> 179000001 10 1 1 -> 180 (not 179!) 10 7.7 123456 -> 41153 also try to testing your program in different tests from this forume... i've got AC!!! all problem in small bug whith precision. We cannot use : while (((ans+X)/(ans+n))>=y+0.05 )ans++; but we can use: while (((ans+X)/(ans+n))>=y+0.0499999999999 )ans++; and if (x!=10.0){ X=(int)((x+0.05)*n); while (X/n>=x+0.049999999999) X--; } else { X=x*n; } Thanks man! At last I got AC. I just rewrited the same idea by searching X in your terms, 'cause I am writing in pascal and this ancient tool doesn't know how to use Trunc or division:( unfortunately, for example while division instead of 179.00000 it gets 178.999898989 and so on with such things and in watch writes 179, and trunc gives 178 so it is very very interesting:) alright thanks friends again Maxim, thank you for you tests! :) To all: The problem can be solved without any search and without any floating-point arithmetics (but with int64 for safety). Just use these geneal rules for integer fractions: b>0: floor(a/b) = a>=0 ? a/b : -ceil(-a,b) ceil(a/b) = a>=0 ? (a+b-1)/b : -floor(-a, b) a>=0, b>0: round(a/b) = a/b + ((a%b)*2>=b ? 1 : 0) here / is integer division. % is remainder. X?A:B evaluates to 'A' if 'X' is true, evaluates to 'B' otherwise max x: x <= a/b ------> x = floor(a/b) max x: x < a/b ------> x = floor((a-1)/b) min x: x >= a/b ------> x = ceil(a/b) min x: x > a/b ------> x = ceil((a+1)/b) E.g. to find maximal initial nominator in general case we have to solve the inequality: A/N < (X*100+5)/100, A->MAX Edited by author 26.08.2008 16:48 max balls for 9.5 by 12 mans - 114, so (114 + p)/(12+p)>=2 => p >= 90 You the fool do not consider under the formula the blockhead It should not be <=2, it should be <2.05 Edited by author 26.08.2008 16:14 Can't understand where is my mistake :( Var t, s, x, y, n : extended; i : longint; begin readln(x, y, n); s := x*n; y := y + 0.05; for i := 1 to 10000000 do begin t := (s+i)/(n+i); if t < y then begin writeln(i); halt; end; end; writeln('Impossible'); end. I'm sorry for posting my code. But anybody who got AC, please help me! [code deleted by author] God damn it! Finally i solved it! Just linear search with few optimization. There is a lot of troubles with exactness of calculations. Thanx a lot for authors of previous topic. It helped me very much :) Edited by author 10.10.2006 01:55 You shouldn't worry this much :D Let S=maximal posible sum of points Then S=max{S:S/N<x+0.05},S=min(S,10*N); with multiplying by 100 we have the problem in integers If L is an answer then L=min(L:(S+L)/(N+L)<y+0.05); After multiplying by 100 we againg work in integers. But WA11 Edited by author 08.10.2006 14:56 That's the point? The same algo, but WA 12: var X, Y, s: extended; N, M: integer; SI: Integer; begin read(X, Y, N); if X <> 10.0 then X := X + 0.05; Y := Y + 0.05; if (X = Y) or (X < Y) then writeln('0') else begin s := n * X; SI := trunc(s); M := trunc((SI - N * Y) / (Y - 1)); while ((M + SI) / (M + N)) >= Y do inc(M); writeln(M); end; end. Thank for an answer! But now I have AC(0.015) with help of test 4.6 1.2 12997 Mistake were in convertion XX=X*100 from double to int and instead of 460 I had XX=359 because X=4.59999999. I inprove my algorithm by an operator XX=(X+0.000001)*100 but lost previously 1 day for debugging right program. About yor code my advice is convert all problem to int type first of all. Also it's important to know that we must use sign < but not<= then we roundind down after adding 0.05 4.6 1.2 12997 What is the right answer? I get AC (0.015) using dichotomy, and 0.0499999999999 instead of 0.05. (X+0.05) rounded to 1 digit after decimal point is equal to X+0.1, but (X+0.0499999999999) rounded to 1 digit after decimal point is equal to X. Edited by author 10.10.2006 18:20 Edited by author 10.10.2006 18:21 Edited by author 10.10.2006 18:21 |
|