0 / 0 / 0
Регистрация: 26.03.2013
Сообщений: 12
|
|
1 | |
Фальшивомонетчики!26.03.2013, 19:49. Показов 761. Ответов 5
Метки нет (Все метки)
Фальшивомонетчики.
Один очень неграмотный и неопытный фальшивомонетчик напечатал купюры достоинством а1, а2,..аN и пошел в магазин. Однако владелец магазина тоже оказался фальшивомонетчиком, так что в кассе магазина были купюры достоинством b1,b1,..bN. Получиться ли у фальшивомонетчика-покупателя купить товар стоимостью Х рублей? Сделка считается состоявшейся, если покупатель и продавец смогли полностью рассчитаться. Формат входных данных. В первой строке записана сумма сделки Х, во второй - кол-во купюр N у покупателя, затем числа а1,а2..аN по одному в строке, затем - кол-во купюр M у продавца и числа b1,b2,..bN (достоинство каждой купюры не превышает 1000, N<50, M<50. Все числа в задаче предполагаются целыми. Формат выходных данных. Выводиться значение "1", если сделка возможна и "0" - в противном случае. Пример Входные данные 7 - сумма сделки 3 - кол-во купюр у покупателя 3, 5, 6 - достоинство купюр у покупателя 2 - кол-во купюр у продавца 4, 5 - достоинство купюр у продавца Выходные данные 1 - сделка совершена Пример Входные данные 10 - сумма сделки 4 - кол-во купюр у покупателя 2, 3, 3, 6 - достоинство купюр у покупателя 3 - кол-во купюр у продавца 5, 6, 7 - достоинство купюр у продавца Выходные данные 0 - сделка не совершена
0
|
26.03.2013, 19:49 | |
Ответы с готовыми решениями:
5
Фальшивомонетчики. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
50 / 50 / 41
Регистрация: 20.08.2012
Сообщений: 123
|
|
26.03.2013, 23:40 | 3 |
Первой мыслью было составить массив, значения в котором - это разница между ценой товара и банкнотами продавца (то есть возможные варианты сдачи), а затем перебирать варианты "цена минус банкноты покупателя", до первого совпадения полученного значения с любым значением из первого массива, но если все это дело хранить, то при 50 банкнотах количество возможных сумм ну ооочень велико (факториал 50, по-моему). Это и правда задача какая-то больше комбинаторная, а будет алгоритм - реализация на паскале не должна серьёзных трудностей вызвать
0
|
27.03.2013, 09:01 | 4 |
да, наверняка есть самый рациональный алгоритм уже составленный.
даже если у человека 5 банкнот то перебором всех вариантов будут: 12 13 14 15 23 24 25 34 35 45 123 124 125 134 135 145 234 235 245 345 1234 1235 2345 12345 Скорее всего это решается вложенными циклами
0
|
0 / 0 / 0
Регистрация: 26.03.2013
Сообщений: 12
|
||||||
02.04.2013, 21:11 [ТС] | 5 | |||||
Один очень неграмотный и неопытный фальшивомонетчик напечатал купюры достоинством а1, а2,..аN и пошел в магазин. Однако владелец магазина тоже оказался фальшивомонетчиком, так что в кассе магазина были купюры достоинством b1,b1,..bN. Получиться ли у фальшивомонетчика-покупателя купить товар стоимостью Х рублей? Сделка считается состоявшейся, если покупатель и продавец смогли полностью рассчитаться. Формат входных данных. В первой строке записана сумма сделки Х, во второй - кол-во купюр N у покупателя, затем числа а1,а2..аN по одному в строке, затем - кол-во купюр M у продавца и числа b1,b2,..bN (достоинство каждой купюры не превышает 1000, N<50, M<50. Все числа в задаче предполагаются целыми. Формат выходных данных. Выводиться значение "1", если сделка возможна и "0" - в противном случае. Пример Входные данные 7 - сумма сделки 3 - кол-во купюр у покупателя 3, 5, 6 - достоинство купюр у покупателя 2 - кол-во купюр у продавца 4, 5 - достоинство купюр у продавца Выходные данные 1 - сделка совершена Пример Входные данные 10 - сумма сделки 4 - кол-во купюр у покупателя 2, 3, 3, 6 - достоинство купюр у покупателя 3 - кол-во купюр у продавца 5, 6, 7 - достоинство купюр у продавца Выходные данные 0 - сделка не совершена
0
|
14.04.2013, 23:15 | 6 | |||||
0
|
14.04.2013, 23:15 | |