|
|
This problem has the same russian name as the problem #1366 - "Подарки". It is not good, could you fix it somehow? I have wrong answer #14, but I do not understand why. Please help me, give me some tests. Thenks. 10 1 2 3 4 5 6 7 8 9 10 1 10 1 3 3 3 2 3 1 2 3 My Answers such as yours! Can give still tests. What does your program deduce on such test? 4 2 2 3 5 My answer - 2 5 Look at my program, can will see a mistake! What wrong in my program? This is my code: [code deleted] Thanks in advance!!! Edited by moderator 28.07.2006 10:34 interesting problem.... This problem take a second place after A+B problem according their interest Переведите на англ пжл. Принято решение(AC) которое для входа 4 2 2 3 5 выдаёт 2 5 хотя правильный ответ 1 5 Ps. Я шокирован что тесты чемпионата Урала не полны ;) Не стоит шокироваться. Вот на прошлом контесте такое было... ;) >>Вот на прошлом контесте такое было... ;) и чё было если не секрет? это, случайно, не единственный тест на котором ваше решение дает неверный ответ? Я автор задачи и тестов, мне крайне трудно поверить, что есть алгоритм, правильно обрабатывающий все остальные тесты, но не работающий в этом случае - подобных тестов полно. Пришлите, пожалуйста, программу на мыло snv2(at)mail(dot)ru >это, случайно, не единственный тест на котором ваше решение дает неверный ответ? нет существует класс подобных тестов например ещё такой 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 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 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:) I`ve submited two distinct solutions and both AC, but on the test: 4 1 3 5 5 one of them prints "1 5" and other prints "2 5". Edited by author 28.03.2006 01:32 |
|
|