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

Обсуждение задачи 1793. Тарелки 2

Notes to authors of this problem.
Послано 198808xc 31 авг 2011 21:45
In fact, it cost me 4 submissions to get accepted. However, I still think that this is a problem with simple geometry. However, some confusion in the problem statement rather made a big trouble for me.

The problem statement said that the plates had the shape of truncated cones. However, it still remains a problem, that which bottom of the truncated cone is larger. By the common sense, the upper bottom of the cone should be larger, and it is indeed so in the testdata (I have submitted a checker for this), but the fact does not appear in the statements.
PS: even if the lower bottom is larger, my program could still give the correct results.

Secondly, the height of the tray need NOT be larger than (or equal with) the height of the cones. If the height of tray is smaller, the plates could still fit in the tray, and in this situation, some part of the plates could even be outside the tray. So important the condition is, it doesn't appear in the problem statements at all! I could not understand this.

And, at last, I want to give the last hint to all authors: try to solve this problem by 64-bit integers. Floating point numbers might bring in errors, which you don't want to see.
Re: Notes to authors of this problem.
Послано Sandro (USU) 31 авг 2011 22:12
Oops! Of course, the radius of plate's edge is greater than the radius of plate's bottom.
I have fixed the problem statement.
Re: Notes to authors of this problem.
Послано 198808xc 31 авг 2011 22:55
Well, I think that correcting the second confusion could be more important.

Or, is this an intentional trap of this problem?
Re: Notes to authors of this problem.
Послано IgorKoval(from Pskov) 1 сен 2011 03:03
It's good idea to use 64-bit fractional arithmetic.

#include <iostream>
#include <algorithm>
using namespace std;

__int64 gcd( __int64 a, __int64 b ) {
    return b? gcd( b, a%b ) : a ;
}

class drobT {
    public :
        __int64 u, d;
        drobT()
        {
            u = 0;
            d = 1;
        }
        friend drobT socr ( drobT a ) {
            __int64 div, x, y;
            x = (a.u>=0)? a.u : -1*a.u;
            y = (a.d>=0)? a.d : -1*a.d;
            div = gcd( max(x,y), min(x,y) );
            a.u /= div;
            a.d /= div;
            return a;
        }
        friend drobT operator  + ( const drobT& a, const drobT& b )
        {
            drobT c;
            c.u = a.u * b.d + b.u * a.d;
            c.d = a.d * b.d;
            return socr(c);
        }
        friend drobT operator  - ( const drobT& a, const drobT& b )
        {
            drobT c;
            c.u = a.u * b.d - b.u * a.d;
            c.d = a.d * b.d;
            return socr(c);
        }
        friend drobT operator * ( const drobT& a, const drobT& b )
        {
            drobT c;
            c.u = a.u * b.u;
            c.d = a.d * b.d;
            return socr(c);
        }
        friend drobT operator * ( const __int64& a, const drobT& b )
        {
            drobT c;
            c.u = a * b.u;
            c.d = b.d;
            return socr(c);
        }
        friend drobT operator  / ( const drobT& a, const drobT& b )
        {
            drobT c = b;
            if( c.u < 0 ) {
                c.u = -c.u;
                c.d = -c.d;
            }
            swap( c.d, c.u );
            return socr(c * a);
        }
        friend bool operator <= ( drobT a, drobT b ) { return a.u*b.d <= a.d*b.u;}
        friend bool operator <= ( const __int64 a, drobT b ) { return a*b.d <= b.u;}
        friend bool operator < ( drobT a, drobT b ) { return a.u*b.d < a.d*b.u; }
        friend bool operator < ( const __int64 num, drobT b ) { return num*b.d < b.u; }
        friend drobT pow2( const drobT& a ){ return a*a; }
};
//input
istream& operator >> ( istream& cin, drobT& dr  ) {
    cin >> dr.u;
    dr.d = 1;
    return cin;
}

/*
secret code)
*/
Re: Notes to authors of this problem.
Послано 198808xc 1 сен 2011 19:42
Wow, it's a good template for double-precision calculations.
However, this problem could be solved with single-precision __int64 numbers.