ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1484. Кинорейтинг

Why WA#8
Послано Ivanidze 8 окт 2006 00:49
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
Re: Why WA#8
Послано Alexander Sokolov [MAI] 8 окт 2006 01:02
what if n==1?
Re: Why WA#8
Послано Maxim Korchyomkin 8 окт 2006 05:38
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...
Re: Why WA#8
Послано Ivanidze 8 окт 2006 11:47
I buy you beer in any case in Rybinsk. Give me test case where are i'm wrong.
Re: Why WA#8
Послано Georgy Kerensky 8 окт 2006 18:11
If x=10.0 then we shouldn't increase it right?
Re: Why WA#8
Послано Maxim Korchyomkin 8 окт 2006 20:07
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...
Re: Why WA#8
Послано Ivanidze 9 окт 2006 00:31
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;
    }
Re: Why WA#8
Послано Georgy Kerensky 9 окт 2006 12:33
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
Re: Why WA#8
Послано Denis Koshman 26 авг 2008 16:34
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