Инструменты пользователя

Инструменты сайта


подготовка_к_олимпиаде._тур_5

1. Конфеты

В магазине Апу стоит большая стеклянная банка с конфетами N сортов. Гомер схватил горсть конфет из банки, но узкое горлышко банки помешало ему вытащить руку. Гомер хочет вытащить из банки как минимум K конфет одного сорта, неважно какого. Напишите программу, определяющую, какое минимальное количество конфет Гомер должен оставить в своей руке, чтобы добиться поставленной цели.

Первая строка ввода содержит два целых числа - количество сортов N и количество одинаковых конфет K (1 ≤ N, K ≤ 10).

Вывести одно число — минимальное количество конфет, среди которых будет не менее K конфет одного сорта.

Пример вводаПример вывода
3 24
2 35

Пояснение к примеру 1: если взять только 3 конфеты, они с некоторой вероятностью могут оказаться 3 различных сортов, а если добавить 4-ю конфету, то конфет одного из сортов станет 2. Аналогично в примере 2: если взять 4 конфеты, то может оказаться по 2 конфеты двух сортов, и чтобы получить 3 конфеты одного из сортов, нужно добавить к ним 5-ю.

2. Экстрасенс

В одной из палаток «Страны чудес Гудвина» артист, выдающий себя за экстрасенса, показывает следующее представление. «Экстрасенс» просит одного из зрителей задумать два целых числа A и B в диапазоне от 1 до 100. Затем зритель должен взять несколько чистых карточек и записать на первой карточке число A, на второй – число A+B, на третьей – число A+2·B, на i-ой – число A+(i−1)·B и т.д. После этого карточки перемешиваются, одна из карточек прячется, а остальные показываются «экстрасенсу». Увидев числа на карточках, артист, имеющий хорошую память, легко угадывает число на спрятанной карточке. В редких случаях для угадывания «экстрасенсу» требуется более одной попытки.

Напишите программу, которая выполняет подобный трюк и определяет число на спрятанной карточке. В первой строке ввода содержится одно целое число N (3 ≤ N ≤ 50) – количество заполненных карточек. Во второй строке ввода содержится (N−1) целых положительных чисел, разделенных пробелами – числа на показанных карточках. В первой строке вывести одно или более чисел в порядке возрастания, разделяя их пробелами – все варианты для числа на спрятанной карточке.

Пример вводаПример вывода
5
9 5 11 7
3 13

3. Шарики

В разных частях парка «Страна чудес Гудвина» стоят клоуны и раздают детям воздушные шары. У каждого клона шары своего цвета. Клоун дает ребенку только один шар и только один раз, но можно взять несколько шариков разного цвета у нескольких клоунов. Собирание шариков является своеобразным аттракционом, так как парк настолько большой, что не каждый ребенок может найти всех клоунов, чтобы получить воздушные шары всех возможных цветов. Известно, сколько пришло в парк детей и сколько шариков раздал каждый клоун. Нужно определить количество детей, собравших шарики всех цветов.

В первой строке ввода содержатся два целых числа – количество детей N (1≤N≤100), пришедших в парк, и количество клоунов K (1≤K≤100). Во второй строке K целых чисел в диапазоне от 0 до N – количество шариков, розданных клоунами.

Вывести два целых числа, разделенных пробелом – минимальное и максимальное возможное количество детей, собравших шарики всех цветов.

Пример вводаПример вывода
10 2
9 9
8 9

4. Сдача

«Я знаю больше двухсот способов сдать сдачу в один доллар и один пенни» – сказал Апу, отсчитывая сдачу Гомеру с пятерки за конфеты.

«Думаю, даже если использовать монеты всех шести номиналов, количество способов не может быть больше ста» – ответил Гомер.

Чтобы Гомер смог проверить утверждение Апу, напишите программу, которая определяет количество способов сдать сдачу монетами заданных номиналов.

Первая строка ввода содержит два целых числа – сумма сдачи S (1 ≤ S ≤ 500) и количество различных номиналов монет N (1 ≤ N ≤ 10). В следующей строке N различных целых чисел в диапазоне от 1 до 1000 в порядке возрастания – номиналы монет.

Вывести одно целое число – количество количество способов сдать сдачу монетами заданных номиналов.

Пример вводаПример вывода
101 6
1 5 10 25 50 100
293
/home/m/mvgoru/wiki.gumnasion.ru/public_html/data/pages/подготовка_к_олимпиаде._тур_5.txt · Последние изменения: 2013/10/28 23:15 — Пронин Роман