Форум Всеукраїнської інтернет-олімпіади NetOI

pro написав:

У продавца и покупателя по одной купюре указанных номиналов или сколько угодно?

Условие написав:

денег для покупки товара ДОСТАТОЧНО

по-моему "сколько угодно купюр указанных номиналов" и вопрос к задаче взаимоисключаются

кстати да)) цена может быть здесь или 2 или 1, если 1 то здача будет 1, если 2 то здачи не будет)
уязвимое местечко)

Да, желательно уточнить.

что выводить при таком тесте:
10000 1 1 1 1 1 1 1 .... 1 1 1 0(у покупателся 10000 купюр по 1, у продавца 0) - нет ответа
или пр таком?
10000 1 1 1 1 1 1 1 .... 1 1 1 10000 1 1 1 1 1 1 1 .... 1 1 1

Відредаговано Cris (2008-12-06 09:47:12)

partisan написав:

В условии явно не написано, что выводить если ответ бесконечность (например все номиналы четные) или такого не может быть?

почему бесконечно, у нас чказано что макс 10000 купюр по макс 50000, т.е макс цена 10000*50000=5*10^8

pro написав:

И все же меня настораживает тов факт, что количество купюр не превышает 10000. Это значит что оно может быть и меньше. Тогда сколько?

Ну вряд ли у покупателя или продавца может быть -3 купюры... Так что количество купюр будет не меньше нуля. Другое дело, может ли быть 0 купюр, но думаю особой роли это не играет.

Условие написав:

Програма Market  зчитує з клавіатури кількість купюр у покупця N, потім N  натуральних чисел – номінали купюр покупця, потім кількість купюр у продавця M, а потім  М натуральних чисел – номінали купюр у продавця. Всі числа розділено пропуском. Кількість купюр в початковий момент у кожного не перевищує 10000

Не понимаю, что непонятного? Числа N и М меньше или равны 10000. Логично предположить что они положительны, или по крайней мере неотрицательны. То есть лежат в промежутке [0,10000]

По поводу условия этой задачи:
1. В условие написано: "У покупателя есть купюры номиналом A(1)…,A(N), а у продавца - B(1)…,B(M). (В переводе на русский). Таким образом, заданы две последовательности, причем нумерация их элементов идет от 1 до N и от 1 до M, соответственно. На основании этого, мне кажется, логично предположить, что M и N не могут быть меньше, чем 1.
2. По поводу того могут ли номиналы купюр совпадать. В условии задачи это явно не оговоренно, заданы лишь неупорядоченные (судя по примеру) последовательности номиналов. Лично мне думается, что номиналы - уникальны, хотя, по моему мнению, окончательный ответ на этот вопрос надо бы дать жюри. Особого значения уникальность номиналов не имеет, но некоторое влияние на решение оказывает.
3. В примере 1 2 1 1, который предложил Uran, исходя из условия задачи логичным ответом был бы, по моему мнению, 0, т.к. в условии явно не оговорена такая ситуация. Там сказано: "найти максимальную стоимость товара, которую покупатель не может купить, т.к. не может точно рассчитаться за этот товар с продавцом, хотя денег на покупку хватает". В приведенном примере товар не может стоить 2 или 1, т.к. в первом случае сдача не нужна, а во втором ее можно дать. Хотя, по моему мнению, в данном случае жюри также надо бы дать ответ на этот вопрос.

Опять же, насколько я понимаю - 10000. Имеется в виду что есть 1 купюра номиналом А(1), 1 купюра номиналом А(2), и т.д. И нигде не сказано что все номиналы различны.

И все же, интересно было бы услышать ответ жюри по поводу примера Uranа. Плюс еще один спорный пример: 1 2 2 1 2 - тут вообще не существует неотрицательной цены, которую нельзя оплатить соответственно условию.

Відредаговано pro (2008-12-07 14:03:04)

Cris написав:

чет мне кажеться что или на эту задачу поставят жосткие ограничения на купюры, количество, повторяемость..., или ее вообше снимут с олимпиады)) или разкажит что от нас хотят авторы этой задачи))

по-моему единственный принципиальный вопрос по этой задаче - что выводить если покупатель может купить товары любой ценой от 1 до n

В умові сказано: "Покупець має купюри номіналом A(1)…,A(N), а продавець  B(1)…,B(M)", тобто є купюри номіналами N і M, хоча б по одній.
Далі сказано: "... кількість купюр у покупця N ... кількість купюр у продавця M ...", а тобто звідси логічно випливає, що купюр кожного номіналу рівно по одній. (окремий випадок коли A(i) = A(j), i != j, відносно цього хотілося б почути відповідь від журі)
Те саме і у тестах.

Відносно 0, -1 і т.д., напевно, мається на увазі: максимальну ціну, за яку не зможуть розрахуватись, тобто якщо ви якимось чином зможеет набрати суми -1, -2, -3, -4, але не можете набрати -5, то відповідь буде -5, але, що буде відповідю коли ми всі суми можемо купити? 0 не підійде, так як ми його можемо купити у будь-якому випадку.

Чекайте чату з журі...