Областной конкурс программирования 10-11 апреля 2012
| Вид материала | Конкурс |
- Vi международный конкурс им. С. С. Прокофьева Санкт-Петербург, 20 апреля – 3 мая 2012, 165.95kb.
- С. Н. Щелкунов 23 марта 2012 г. Положение о Нижегородском областном конкурс, 37.52kb.
- Программа «студенческого электронного конкурса сочинения на иностранном языке-2012», 337.21kb.
- На открытый областной конкурс,,Александр Невский,, 2012 год мкоу «приреченская основная, 132.46kb.
- Конкурс проводится в два этапа: муниципальный (с 1 октября 2011 г. 1 ноября 2011 г.), 64.71kb.
- Конкурс проводится при поддержке Министерства культуры Российской Федерации в рамках, 65.29kb.
- Фестиваль-конкурс проходит в три этапа: областной (заочный), 50.94kb.
- Общее положение, 56.59kb.
- К. В. Шевченко 2012 г положение об областном конкурс, 66.94kb.
- А. А. Чертова 2011 г положение об областном конкурс, 123.21kb.
Областной конкурс программирования 10-11 апреля 2012
Задача A Последовательность
Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000... Все что надо – определить, какая цифра находится в такой последовательности на определённом месте.
Входной файл: В первой строке входного файла находится одно натуральное число N (N < 65536). В i-той из N последующих строк записано натуральное число Ki (Ki < 105) – номер позиции в последовательности.
Выходной файл: В выходной файл следует через пробел вывести N цифр 0 или 1. А именно, i-тая цифра вывода должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.
Пример:
Input.txt Output.txt
4 0 0 1 0
3
14
7
6
Задача B Профессор
Жил-был рассеянный профессор. Рассеянный профессор одевается по утрам, причём какие-то вещи обязательно надо надевать до каких-то других (например, носки – до башмаков); в других случаях это всё равно (носки и штаны, например).
У рассеянного профессора есть несколько элементов одежды, которые обозначены буквами латинского алфавита. Для каждого из этих вещей есть список элементов одежды, которые должны быть надеты до него. Ваша задача – выстроить элементы одежды в том порядке, в котором их можно надеть.
Выходной файл: В первой строке входного файла находятся два натуральных числа N (N < 25) и K (K<100) – количество различных вещей профессора и количество закономерностей одевания одежды. Во второй строке перечислены начальными буквами все вещи профессора. В i-той из K последующих строк записаны парами предметы одежды, причем первый предмет одежды предшествует второму.
Выходной файл: в единственной строке файла выведите последовательность букв, определяющий правильный порядок одевания одежды. Если таких порядков несколько, то выведите тот, который является наименьшим в лексикографическом отношении.
Пример:
Input.txt Output.txt
6 3 a b d c e f
a b c d e f
a b
d c
b d
Задача C Цифры
Задано натуральные числа N и s. Составить алгоритм, определяющий, какие s цифр удалить из числа N, чтобы оставшиеся цифры составили наименьшее число.
Например: N=2435, s=1. Если удалить вторую цифру (4), получим число 235. Это и есть наименьшее число (остальные: 435,245,243).
Входной файл: в единственной строке входного файла записаны через пробел два числа N (0
Выходной файл: в единственной строке выходного файла выведите наименьшее число.
Пример:
Input.txt Output.txt
2435 1 235
Задача D Дырокол
Дырокол пробивает на длинной полосе бумаги по два одинаковых отверстия за одно нажатие его рычага и после нескольких нажатий получается следующее состояние бумаги.
0 0 0 00 0 00 00 0 0
Л П Л ПЛ П ЛЛ ПП Л П
Буквы «Л» и «П» под лентой обозначают, соответственно, левое и правое отверстия дырокола.
По известным координатам отверстий на полосе определить возможную ширину между отверстиями дырокола.
Входной файл: В первой строке входного файла находится одно натуральное число N (N < 101) – число отверстий на бумаге.
В следующей строке находятся N чисел ai (1
Выходной файл: В единственную строку выходного файла следует вывести одно число – ширину между отверстиями дырокола.
Пример:
Input.txt Output.txt
12 5
3 8 10 15 16 21 25 26 30 31 40 45
Задача E Калькулятор
Мальчику Пете задали в школе задание: он должен выполнить арифметические операции в различных системах счисления. Петя много тренировался в вычислениях, однако не может проверить, правильно ли он выполнял операции. Помогите Пете написать программу, которая по известному основанию системы счисления K выполняет с двумя числами a и b одно из арифметических действий (+, –, * и / (целочисленное деление)).
Входной файл: В первой строке входного файла находится одно натуральное число K (N ≤ 16) – система счисления.
Во второй строке находятся выражение, которое необходимо вычислить (гарантируется, что все числа и результат не превосходят 50000 в десятичной системе счисления).
Выходной файл: В единственную строку выходного файла следует вывести результат выражения в системе счисления K.
Пример:
Input.txt Output.txt
2 1101
101+1000
Задача F Литры
Имеется N банок с целочисленными объемами V1, ..., Vn литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок налить в сосуд ровно V литров воды.
Входной файл: В первой строке входного файла находится одно натуральное число N (N < 101) – число банок.
Во второй строке находятся N чисел Vi (1
В третьей строке находится V – объем, который необходимо налить.
Выходной файл: В единственную строку выходного файла следует вывести слово «YES», если можно налить объем V возможно или «NO» в противном случае.
Пример:
Input.txt Output.txt
5 NO
3 6 9 12 15
5
Задача G Гостиница
На Всероссийскую олимпиаду среди студентов колледжей по программированию приезжает множество делегаций из различных городов нашей страны. Расселить делегации по номерам в гостинице является непростой задачей.
Из одного крупного города приехала делегация, состоящая из N человек. В гостинице, куда решено было заселить делегацию, имеются лишь двухместные и трехместные номера. Для экономии средств делегация хочет занять как можно меньше номеров, при этом в занимаемых номерах не должно оставаться свободных мест.
Помогите определить, каким образом можно разместить делегацию из N в двухместных и трехместных номерах, чтобы использовать суммарно минимальное число номеров.
Входной файл: содержит единственное целое число N (2≤N≤100) – размер делегации.
Выходной файл: В единственной строке выходного файла выведите два целых числа a2 и a3, разделенных пробелом – число двухместных и трехместных номеров, которые необходимо выделить делегации, соответственно.
Пример:
Input.txt Output.txt
7 2 1
Задача H Акция
У Билла большая семья: трое сыновей, девять внуков. И всех надо кормить. Поэтому Билл раз в неделю ходит в магазин.
Однажды Билл пришел в магазин и увидел, что в магазине проводится акция под названием «каждый k-й товар бесплатно».
Изучив правила акции, Билл выяснил следующее.
Пробив на кассе товары, покупатель получает чек. Пусть в чеке N товаров, тогда (n div k) самых дешевых из этих товаров достаются бесплатно.
Например, если в чеке пять товаров за 200, 100, 1000, 400 и 100 рублей, соответственно, и k=2, тогда бесплатно достаются оба товара по 100 рублей, всего покупатель должен заплатить 1600 рублей.
Билл уже выбрал товары, и направился к кассе, когда сообразил, что товары, которые он хочет купить, можно разбить на несколько чеков, и благодаря этому потратить меньше денег.
Помогите Биллу выяснить, какую минимальную сумму он сможет заплатить за выбранные товары, возможно разбив их на несколько чеков.
Входной файл: Первая строка входного файла содержит два целых числа N, k (1≤N≤15000, 2≤k≤100) – количество товаров, которые хочет купит Билл и параметр акции «каждый k-й товар бесплатно».
Следующая строка содержит N целых чисел ai (1≤ ai≤10000) – цены товаров, которые покупает Билл.
Выходной файл: Выведите в единственную строку выходного файла одно число – минимальную сумму, которую должен заплатить Билл за товары.
Пример:
Input.txt Output.txt
5 2 1300
200 100 1000 400 100
Задача J НОД
Сегодня на уроке математики шестиклассник Петя изучил понятие наибольшего общего делителя. Петя тут же решил применить полученные знания на практике.
Петя выписал на листке бумаги N чисел a1, . . . , an — номера домов, в которых живут его друзья. Теперь он хочет выбрать такое подмножество этих чисел, чтобы их наибольший общий делитель был равен его любимому числу d.
Помогите Пете выбрать из выписанных чисел искомое подмножество.
Формат входного файла
Входной файл: Первая строка входного файла содержит два целых числа N и d (1 ≤ N ≤ 1000, 1 ≤ d ≤ 109).
Вторая строка содержит n целых чисел: a1, a2, . . . , an (1 ≤ ai ≤ 109).
Формат выходного файла
Выходной файл: Если существует искомое подмножество, выведите на первой строке выходного файла число k – количество чисел в нем. На второй строке выведите числа, входящие в это подмножество. Числа указывайте в том порядке, в котором они указаны во входном файле.
Если решения не существует, выведите на первой строке выходного файла число «−1». Если возможных ответов несколько, выведите один из них.
Пример 1:
Input.txt Output.txt
4 3 3
6 8 12 9 6 12 9
Пример 2:
Input.txt Output.txt
3 3 -1
2 4 8
Комментарии
Задача A Последовательность
Задача на тему «методы поиска. Бинарный поиск»
Можно конечно каждый раз формировать последовательность до элемента Ki< 105. Однако такие вычисления необходимо сделать N < 65536 раз, операции со строками очень медленные и по времени такое решение не пройдет.
Для решения задачи необходимо сначала сформировать массив, содержащий номера последовательности, содержащие единицу, а затем поиском, например бинарным поиском, определить находится ли в данном массиве необходимая позиция. Если да, то в этой позиции стоит «1», иначе «0».
Задача B Профессор
Задача на тему «Графы. Топологическая сортировка»
В данной задаче необходимо просто топологически отсортировать все вещи профессора.
Топологическая сортировка (Topological sort) — одна из основных алгоритмов на графах.
Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером.
Существует несколько способов топологической сортировки, но наиболее простым и распространенным является метод топологической сортировки с помощью обхода в глубину (англ. Depth-first search, сокращенно DFS).
Алгоритм описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
Основная трудность заключается в том, что вещи обозначены буквами латинского алфавита. Поэтому сначала необходимо дать соответствие этим буквам, например порядковому номеру одежды, затем работая с этими номерами топологически отсортировать, а потом по соответствию найти необходимую вещь профессора. Таким образом, в задаче необходимо осуществить несколько поисков, причем последовательный поиск вполне подходит.
Задача C Цифры
(По материалам Молдавской олимпиады, задача из книги Котова)
Пример. N=2435, s=1. Если удалить вторую цифру (4), получим число 235. Это и есть наименьшее число (остальные: 435,245,243).
Сформулируем общее правило удаления при s=1.
Просматривать число слева направо. Найти первую такую цифру, за которой идет строго меньшая цифра, и эту первую вычеркнуть. Если цифры идут монотонно, не убывая, вычеркнуть последнюю.
Если s>1, то s раз применяется приведенный выше алгоритм.
При этом может удаляться цифра или в середине введенной строки, или в конце.
Задача D Дырокол
Задача на тему «Полный перебор»
Задача решается полным перебором. Т.е. необходимо перебрать все возможные расстояния для дырокола, начиная с самого маленького.
Первое расстояние равно a[2]-a[1], следующее a[3]-a[1] и т.д.
Затем необходимо проверить подходит ли данное расстояние для всех отверстий, во время проверки запоминаем все отверстия, которые подошли.
Если все отверстия подошли, то выводим ответ.
Задача E Калькулятор
Задача на тему: «Перевод чисел из одной системы счисления в другую».
Для решения задачи необходимо заданные числа перевести в десятичную систему счисления, вычислить одно из арифметических действий, а затем перевести результат в заданную систему счисления.
Задача F Литры
Задача на тему «Целочисленная арифметика. Алгоритм Эвклида»
Обозначим S=НОД(V1,...,Vn). Если V делится нацело на S, то в сосуд с помощью банок можно налить V литров воды, иначе – нет.
Задача G Гостиница
Задача на целочисленную арифметику.
Понятно, что нам не имеет смысла иметь в сумме больше двух двоек, так как 3 двойки = 2 тройки
Если n mod 3=0, то ответ (n div 3, 0)
Если n mod 3 =1, то ответ ((n-4) div 3, 2)
Если n mod 3 =2, то ответ ((n-2) div 3, 1)
Задача H Акция
Задача на тему: сортировка.
Ход выполнения задачи:
Отсортируем все цены в порядке убывания
Разобьём их на группы по k, начиная с первого, и из каждой группы, может быть кроме последней, можно не платить за минимальный элемент (то есть не платить за элемент, номер которого делится на k)
Задача J НОД
Задача на целочисленную арифметику, нахождение НОД.
Для решения задачи нужно выполнить три этапа:
– Взять все числа, которые делятся на d
–Теперь взять у них у всех наибольший общий делитель
– Если он равен d, то выводим это множество, если нет, то вывести -1