Набор тестов не полон для 1445, надо добавить...
Переведите на англ пжл.
Принято решение(AC) которое для входа
4
2 2 3 5
выдаёт 2 5
хотя правильный ответ 1 5
Ps. Я шокирован что тесты чемпионата Урала не полны ;)
Re: Ps. Я шокирован что тесты чемпионата Урала не полны ;)
Не стоит шокироваться.
Вот на прошлом контесте такое было... ;)
Re: Ps. Я шокирован что тесты чемпионата Урала не полны ;)
>>Вот на прошлом контесте такое было... ;)
и чё было если не секрет?
Re: Набор тестов не полон для 1445, надо добавить...
это, случайно, не единственный тест на котором ваше решение дает неверный ответ?
Я автор задачи и тестов, мне крайне трудно поверить, что есть алгоритм, правильно обрабатывающий все остальные тесты, но не работающий в этом случае - подобных тестов полно. Пришлите, пожалуйста, программу на мыло snv2(at)mail(dot)ru
Re: Набор тестов не полон для 1445, надо добавить...
>это, случайно, не единственный тест на котором ваше решение дает неверный ответ?
нет существует класс подобных тестов например ещё такой
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 (-)
Re: Набор тестов не полон для 1445, надо добавить...
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, надо добавить...
Re: Набор тестов не полон для 1445, надо добавить...
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:)