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

Обсуждение задачи 1275. Knights of the Round Table

SPIRiT Help! Why do I get WA at test 23??? [4] // Задача 1275. Knights of the Round Table 12 авг 2005 12:58
I don't know,  what's wrong with my code. Who knows what's the trap?
Michael Rybak (accepted@ukr.net) Maybe use a larger type? (+) [3] // Задача 1275. Knights of the Round Table 4 фев 2006 06:46
My AC solution gets WA test 29 if I replace `long` with `short int` (short int is 2 bytes, long is 4)

P.S. You've got AC, so maybe you'd write what your problem was, to help anyone?

Edited by author 04.02.2006 06:51
SPIRiT Re: Maybe use a larger type? (+) [2] // Задача 1275. Knights of the Round Table 22 фев 2006 15:51
Okay, I got AC. But I still don't know, what was wrong with
test 23.
First I tried to solve this problem by solving Hauss equations very accurately. It works very fast, but it didn't pass the 23 test.
After that I rewrote the code. Now I solved 'the rings' directly. It's much slower, but it got AC.
The hints are: Start with the first knight and put the numbers 1, 1+K,1+2*K,etc. in a buffer, until you reach the first knight again. These knights form a ring, as I call it. They are served by servant in a form of a ring and don't intersect with other knights. So you can check them separately (the problem, therefore, can be separated in few parts).
Now, let us denote: X[i] - the number of goblets brought to the i-th and (i+K)-th knight (don't forget, that i+K maybe more that N and use modulus). Therefore we can say that: X[i]+X[i+K]=F-A[i+k], there A[i]- the initial number of goblets near the i-th knight. Also X[i-K]+X[i]=F-A[i], and etc. Therefore you have to solve a system of linear equations, where each equation has two variables (others are zero). This can be optimised very well. If number of knights in the ring is odd, the solving is one. If it's even, you have to minimise it. The result is Sum(|X[i]|). Good luck to you all
SPIRiT Re: Maybe use a larger type? (+) // Задача 1275. Knights of the Round Table 28 июл 2006 19:44
If you don't understand the solution you can mail me:
vdshevch2@mail.ru
Глащенко Никита Re: Maybe use a larger type? (+) // Задача 1275. Knights of the Round Table 11 июл 2009 00:40
Thank you :)