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

Arithmetic average is not exacltly x. Due to the rounding arithmetic average can be x + 0.01 or even x + 0.04999

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?

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++;

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

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.

Any help?

Test
2.0 9.5 12
Ans
0

:)

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

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 dont understand: when I had swaped 'Impossible' to '0' my program solved more tests than late.

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

I increased x if x<10 so that x=trunc((x+0.05)*10*n))/(10*n)
and then used formula ans>n*(x-y)/(y-1);

I tried much to do but that WA makes me go mad, please help me if you can I will be very thanksful, I think I may study smt. from that

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

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

what's the trick?
3% of the ac rating.....

Can u give me some test and anwers plz!
10 1 1->202?