Old Programmer
4147 subscribers

Олимпиадные задачи по программированию. Продолжаем

116 full reads
171 story viewUnique page visitors
116 read the story to the endThat's 68% of the total page views
1 minute — average reading time

Все материалы моего канала Old Programmer о программировании и программистах расположенные по темам тут. А здесь все мои ресурсы по рекурсивному и олимпиадному программированию

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

Задача "Цветы"

Фабула

Мальчик 8-ого марта решил сделать подарок своей маме и сестренке — подарить им по цветку. Для этого он пришел в цветочный магазин и начал выбирать цветы. Дело было уже к вечеру и в цветочном магазине осталось только два вида цветов. Поскольку он увлекался программированием то и выбирать решил следуя определенному алгоритму. Во-первых, он решил, что цветы в паре должны быть разные. Далее он решил, что будет брать пару цветов разного вида и если хотя бы один цветок в паре немного завял (плохой), то он откладывает в сторону оба цветка и берет следующую пару. Такую пару ему удалось найти и он вернулся домой с цветами. А поскольку он увлекался программированием, то тут же в голове у него родилась задача, которую он с успехом решил.

Входные данные

На входе даны четыре числа
a1, b1, a2, b2

в строке через пробел,

a1 — количество хороших цветов одного вида, b1 — количество плохих цветов того же вида. a2, b2 — аналогичные данные для второго вида цветов.

Выходные данные

yes — если использую алгоритм, который придумал мальчик, обязательно получишь пару хороших цветов разного вида. no - если нет гарантии получить пару хороших цветов.

Пример

Олимпиадные задачи по программированию. Продолжаем

Решение

Задача очень проста. Но в ней есть важный момент. Нужно только поставить вопрос: каково самое неблагоприятное развитие событий для мальчика? Конечно, самое благоприятное событие, это когда мальчик сразу берет два хороших цветка. Также не плохо, когда мальчик берет сразу два плохих цветка. Это ведь означает, что плохие цветки обеих типов цветов уменьшаются, а хорошие - нет. Значит самое неблагоприятное развитие событий, это когда мальчик каждый раз берет пару - <хороший, плохой>. Вот из этого и нужно исходить. Пара <хороший, плохой> уменьшает количество хороших цветков одного типа и плохих другого типа. Если все время будут идти такие пары, то все сведется к тому как соотносится количество хороших цветов одного типа с количеством плохих цветов другого типа. Вот собственно и все. А программа на Python просто элементарна (olimp4001.py).

До скорых встреч, друзья. Подписываемся на мой канал Old Programmer , здесь много материалов по разным вопросам программирования .

Программа  olimp4001.py
Программа olimp4001.py