ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1445. Christmas gifts

Набор тестов не полон для 1445, надо добавить...
Posted by xMagGTU Дмитрий Тишкин GPRS 26 Mar 2006 23:17
Переведите на англ пжл.

Принято решение(AC) которое для входа
4
2 2 3 5
выдаёт 2 5
 хотя правильный ответ 1 5
Ps. Я шокирован что тесты чемпионата Урала не полны ;)
Re: Ps. Я шокирован что тесты чемпионата Урала не полны ;)
Posted by Burunduk1 27 Mar 2006 00:41
Не стоит шокироваться.
Вот на прошлом контесте такое было... ;)
Re: Ps. Я шокирован что тесты чемпионата Урала не полны ;)
Posted by xMagGTU Дмитрий Тишкин GPRS 27 Mar 2006 02:26
>>Вот на прошлом контесте такое было... ;)
и чё было если не секрет?
Use English, please (-)
Posted by Dmitry 'Diman_YES' Kovalioff 27 Mar 2006 09:29
Re: Набор тестов не полон для 1445, надо добавить...
Posted by Stanislav Vasilyev 27 Mar 2006 13:25
это, случайно, не единственный тест на котором ваше решение дает неверный ответ?
Я автор задачи и тестов, мне крайне трудно поверить, что есть алгоритм, правильно обрабатывающий все остальные тесты, но не работающий в этом случае - подобных тестов полно. Пришлите, пожалуйста, программу на мыло snv2(at)mail(dot)ru
Re: Набор тестов не полон для 1445, надо добавить...
Posted by xMagGTU Дмитрий Тишкин GPRS 28 Mar 2006 04:11
>это, случайно, не единственный тест на котором ваше решение дает неверный ответ?
нет существует класс подобных тестов например ещё такой
n=4, 2 2 5 7 правильный ответ 1 7 мой бажный алго(ас на контесте) выдаст 2 7
>Я автор задачи и тестов, мне крайне трудно поверить, что >есть алгоритм, правильно обрабатывающий все остальные >тесты,
все 14
> но не работающий в этом случае - подобных тестов полно.
????
>Пришлите, пожалуйста, программу на мыло snv2(at)mail(dot)ru
 не буду(чем докажите что вы это вы)
однако мой сырец что получил ас на контесте я  думаю можно вытащить из базы timus.ru

суть бажного алгоритма нахождения мин неоходимого числа подарков:
создаём и заполняем
вектор a[1..500] счетчиков сколько каких компаний паралельно считаем общее число людей(s) и наикрупнейшую компанию(x)
затем перебираем(алго из задачи о числе конфигураций голосующих за  партий при присоединении(за) даной партии становящихся большинством )
t где 2t>=s, и среди них ищем 2t-s минемальный(p)
step x:затем if p<1 then p:=1
step y:(epmty)
step z:затем writeln(p,' ',x)
Самое прикольное что в таком виде задача валилась на 14 тесте
одноко если прекруть вот эту эвристику
step y: if a[x]>1 then p:=1;
То задача принимается.
однако такой алгоритм заведомо валится на таких тестах:
n=4
2 2 (x-2) x
где x>1,x нечётно

PS.после контеста я понял как правильно(я так думаю) решается и пересдал( в правильном решении 1 цикл
в цикле чтение, накомление нахождение максимума
а после цикла тоже всего одно присвоение и одно условное присвоение)

PPS пока печатал предыдущей PS внимательно посмотрел свой текущий ас -код и обнаружил что ВООБЩЕ все ваши тесты кривые а иммено ....

ok thank's that add test

Edited by author 31.03.2006 01:03
If that's the case... I doubt it was done advisedly, but new tests should be certainly added to the testset (-)
Posted by Dmitry 'Diman_YES' Kovalioff 28 Mar 2006 10:39
Re: Набор тестов не полон для 1445, надо добавить...
Posted by Stanislav Vasilyev 28 Mar 2006 12:29
thanks for testing our tests. This problem was supposed to be very easy, that's why I did not pay much attention to tests. Although, you have been very lucky to find bad solutions that can pass all the tests (including random).
Problem will be fixed soon
Re: Набор тестов не полон для 1445, надо добавить...
Posted by xMagGTU Дмитрий Тишкин GPRS 31 Mar 2006 01:02
Re: Набор тестов не полон для 1445, надо добавить...
Posted by IGOR _Lviv NU 23 Nov 2006 00:07
You are real cool programmer!:)
The algorithm is like that:
t:=max-(s-max)
if t<=0 then write(1)
 else write(t);
writeln(max);

max is the maximum number of people in group
s is summ of all people

P.S. Sorry for my poor english:)