Различия

Здесь показаны различия между выбранной ревизией и текущей версией данной страницы.

--- подготовка_к_олимпиаде._тур_5 [2013/10/28 22:53]
Пронин Роман
+++ подготовка_к_олимпиаде._тур_5 [2013/10/28 23:15] (текущий)
Пронин Роман
@@ Строка 1: / Строка 1: @@
-**1. Шарики**
+**1. Конфеты**
-В разных частях парка "Страна чудес Гудвина" стоят клоуны и раздают детям воздушные шары. У каждого клона шары своего цвета. Клоун дает ребенку только один шар и только один раз, но можно взять несколько шариков разного цвета у нескольких клоунов. Собирание шариков является своеобразным аттракционом, так как парк настолько большой, что не каждый ребенок может найти всех клоунов, чтобы получить воздушные шары всех возможных цветов.
+В магазине Апу стоит большая стеклянная банка с конфетами N сортов. Гомер схватил горсть конфет из банки, но узкое горлышко банки помешало ему вытащить руку. Гомер хочет вытащить из банки как минимум K конфет одного сорта, неважно какого. Напишите программу, определяющую, какое минимальное количество конфет Гомер должен оставить в своей руке, чтобы добиться поставленной цели.
-Известно, сколько пришло в парк детей и сколько шариков раздал каждый клоун. Нужно определить количество детей, собравших шарики всех цветов.
-В первой строке ввода содержатся два целых числа – количество детей N (1≤N≤100), пришедших в парк, и количество клоунов K (1≤K≤100). Во второй строке K целых чисел в диапазоне от 0 до N – количество шариков, розданных клоунами.
+Первая строка ввода содержит два целых числа - количество сортов N и количество одинаковых конфет K (1 ≤ N, K ≤ 10).
-Вывести два целых числа, разделенных пробелом – минимальное и максимальное возможное количество детей, собравших шарики всех цветов.
+Вывести одно число — минимальное количество конфет, среди которых будет не менее K конфет одного сорта.
 ^Пример ввода^Пример вывода^
-|10 2\\ 9 9|8 9|
+|3 2|4|
+|2 3|5|
+Пояснение к примеру 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 и т.д. После этого карточки перемешиваются, одна из карточек прячется, а остальные показываются "экстрасенсу". Увидев числа на карточках, артист, имеющий хорошую память, легко угадывает число на спрятанной карточке. В редких случаях для угадывания "экстрасенсу" требуется более одной попытки.
-**2. Список аттракционов**
+Напишите программу, которая выполняет подобный трюк и определяет число на спрятанной карточке.
+В первой строке ввода содержится одно целое число N (3 ≤ N ≤ 50) – количество заполненных карточек. Во второй строке ввода содержится (N−1) целых положительных чисел, разделенных пробелами – числа на показанных карточках.
-В парке развлечений "Страна чудес Гудвина" много замечательных аттракционов. Учительница, которая возила детей в парк, решила выяснить насколько их много, и опросила детей, в каких аттракционах они были. Результаты опроса она записала, обозначая каждый названный аттракцион одной из букв латинского алфавита. Некоторые аттракционы дети назвали несколько раз, а про какие-то они, возможно, забыли, но учительнице достаточно определить, сколько различных аттракционов среди названных.
+В первой строке вывести одно или более чисел в порядке возрастания, разделяя их пробелами – все варианты для числа на спрятанной карточке.
-Напишите программу, которая анализирует результаты опроса и определяет количество аттракционов в парке.
-В первой строке ввода содержится одна строка длиной от 1 до 250 символов, состоящая из прописных латинских букв.
-Вывести одно целое число – количество аттракционов в парке по результатам опроса.
 ^Пример ввода^Пример вывода^
-|ABRACADABRA|5|
+|5\\ 9 5 11 7|3 13|
-**3. Арена**
+**3. Шарики**
-В "Стране чудес Гудвина" есть цирк-шапито, где показывают представление с дрессированными животными. Перед номером с хищными животными на круглую арену устанавливают клетку в форме многоугольника. Для безопасности зрителей после установки клетки необходимо определить, насколько близко хищник в клетке может приблизиться к краю арены.
+В разных частях парка "Страна чудес Гудвина" стоят клоуны и раздают детям воздушные шары. У каждого клона шары своего цвета. Клоун дает ребенку только один шар и только один раз, но можно взять несколько шариков разного цвета у нескольких клоунов. Собирание шариков является своеобразным аттракционом, так как парк настолько большой, что не каждый ребенок может найти всех клоунов, чтобы получить воздушные шары всех возможных цветов.
+Известно, сколько пришло в парк детей и сколько шариков раздал каждый клоун. Нужно определить количество детей, собравших шарики всех цветов.
-Напишите программу, которая вычисляет минимальное расстояние от края арены до клетки.
+В первой строке ввода содержатся два целых числа – количество детей N (1≤N≤100), пришедших в парк, и количество клоунов K (1≤K≤100). Во второй строке K целых чисел в диапазоне от 0 до N – количество шариков, розданных клоунами.
-В первой строке ввода содержится два целых числа R (10 ≤ R ≤ 10000) и N (3 ≤ N ≤ 50) – радиус арены и количество вершин в многоугольнике, задающим клетку. Далее следует N строк, в каждой строке содержатся два целых числа, разделенных пробелом – координаты вершин многоугольника. Вершины перечисляются в порядке обхода по или против часовой стрелки. Центр координат соответствует центру арены. Многоугольник полностью находится внутри арены и может быть невыпуклым.
-Вывести одно вещественное число – минимальное расстояние от края арены до клетки с точностью 10<sup>−4</sup>.
+Вывести два целых числа, разделенных пробелом – минимальное и максимальное возможное количество детей, собравших шарики всех цветов.
 ^Пример ввода^Пример вывода^
-|21 4\\ 0 10\\ 10 0\\ 0 -10\\ -10 0|11.0000|
+|10 2\\ 9 9|8 9|
+**4. Сдача**
-**4. Поиск детей**
+"Я знаю больше двухсот способов сдать сдачу в один доллар и один пенни" – сказал Апу, отсчитывая сдачу Гомеру с пятерки за конфеты.
-Родители отправили детей в "Страну чудес Гудвина", а сами отправились в кафе у входа пить кофе. Дети посмотрели на указатели у входа в парк, выбрали один из аттракционов и отправились в него. Выйдя из аттракциона, они посмотрели на указатели рядом с выходом и снова выбрали один из аттракционов. И так далее. Дети делают выбор совершенно случайно и могут снова посещать те аттракционы, где уже бывали. На каждый аттракцион дети тратят 10 минут. Временем на перемещение между аттракционами можно пренебречь.
+"Думаю, даже если использовать монеты всех шести номиналов, количество способов не может быть больше ста" – ответил Гомер.
-Выпив несколько чашек кофе, родители решили найти детей. Известно, что родители выпивают чашку кофе за 10 минут. Известно, какие указатели размещены у входа в парк и у выхода каждого из аттракционов. Напишите программу, которая поможет родителям быстрее найти детей, определив список аттракционов, где дети могут находиться.
-В первой строке ввода содержатся два целых числа, разделенных пробелом – количество аттракционов в парке N (1 ≤ N ≤ 100) и количество выпитых чашек кофе K (1 ≤ K ≤ 100). Далее следует строка, содержащая сначала одно целое число m (1 ≤ m ≤ N) – количество указателей у входа в парк, затем m целых чисел в диапазоне от 1 до N – номера аттракционов на указателях. Далее следует N строк, содержащих аналогичную информацию об указателях у выхода каждого аттракциона.
+Чтобы Гомер смог проверить утверждение Апу, напишите программу, которая определяет количество способов сдать сдачу монетами заданных номиналов.
-В первой строке вывести в порядке возрастания номера аттракционов, где могут находиться дети.
+Первая строка ввода содержит два целых числа – сумма сдачи S (1 ≤ S ≤ 500) и количество различных номиналов монет N (1 ≤ N ≤ 10). В следующей строке N различных целых чисел в диапазоне от 1 до 1000 в порядке возрастания – номиналы монет.
+Вывести одно целое число – количество количество способов сдать сдачу монетами заданных номиналов.
 ^Пример ввода^Пример вывода^
-|5 2\\ 4 1 2 3 4\\ 1 2\\ 1 3\\ 1 4\\ 1 5\\ 1 1|1 3 4 5|
+|101 6\\ 1 5 10 25 50 100|293|

База знаний гимназии 1 им. Барсукова

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

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

Различия

Инструменты страницы