Другие языки программирования и технологии

Помогите составить алгоритм решения задачи

Нужен алгоритм для решения этой задачи. Заранее спасибо за помощь.

Инопланетяне с планеты Пандора уже много лет исследуют землян. Для этого на Землю внедрено множество агентов-пандорианцев. Так как среднестатический пандорианец примерно в 20 раз меньше среднестатичестического землянина, для перемещения по планете они используют специальных роботов, внешне неотличимых от жителей Земли. Внутри этих роботов с комфортом располагается команда агентов-исследователей.

Сегодня команда, управляющая роботом «Геннадий», получает свой гонорар. Команда состоит из двух пандорианцев, Джейка и Джейка, которые в данный момент исследуют жителей России. Гонорар исследователи получают один на двоих наличными в обыкновенном российском банке.

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

Напишите программу, которая поможет Джейку и Джейку ответить на этот вопрос.

Входные данные
На вход подается число K — сумма, которую получат Джейк и Джейк ( 1 ≤ K ≤ 100 000 ).

Выходные данные
Выведите «YES», если вне зависимости от того, какими именно монетами и купюрами будет выдана нужная сумма, их можно будет поделить поровну, и «NO» — в противном случае. Действие происходит в России, поэтому для выдачи нужной суммы могут быть использованы купюры и монеты следующих номиналов: 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей.
Дмитрий Бажин
Дмитрий Бажин
161
Независимо от используемых купюр можно поделить суммы:

4, 20, 40, 200, 400, 2000, 4000, 10000 * n

и комбинации этих сумм.

Т. е. разряд единиц рублей - только 0 или 4
Разряды десятков, сотен и тысяч рублей - только 0, 2 или 4
Разряды десятков тысяч и больше не имеют значения.

readln(k);
flg := (k mod 10) in [0, 4];
k := k div 10;
flg := flg and ((k mod 10) in [0, 2, 4]);
k := k div 10;
flg := flg and ((k mod 10) in [0, 2, 4]);
k := k div 10;
flg := flg and ((k mod 10) in [0, 2, 4]);
if flg then writeln('yes') else writeln('no')
Исраил Арсалиев
Исраил Арсалиев
77 008
Лучший ответ
Я бы решал от противного. То есть для любого К старался сделать такой размен, чтобы нельзя было поделить. Копай в этом направлении.
Потому что если делать прямой перебор разменов, как советует товарищ выше, то при больших суммах тебе никаких ресурсов не хватит.
Оптимизации: если К - нечетное, все ясно. Если К можно составить из нечетного количества одинаковых купюр - тоже. И наоборот: если К делится на четное количество любых номиналов.
11
11 11
65 986
Ну тупо в лоб:
1. Определить все варианты размена заданной суммы представленными номиналами.
2. Для каждого варианта определить, можно ли K/2 набрать монетами из этого варианта.

Сразу напрашивается оптимизация для нечетных К.
Если подумать, то, наверное, еще что-нибудь сократить можно, но думать лень на ночь глядя
Sergey Bratcev
Sergey Bratcev
25 516
Я бы решал от противного. То есть для любого К старался сделать такой размен, чтобы нельзя было поделить. Копай в этом направлении. Оптимизации: если К - нечетное, все ясно. Если К можно составить из нечетного количества одинаковых купюр - тоже. И наоборот: если К делится на четное количество любых номиналов.
Казбек Джазаев
Казбек Джазаев
369

Похожие вопросы