#3291

Распродажа (10-11)

Темы: [Жадный алгоритм] [Условный оператор (if)]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2011, Задача A ]

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи \(N\) одинаковых товаров и получи еще один товар бесплатно"и "купи \(K\) товаров по цене \(K-1\) товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит \(B\) рублей. Какое максимальное количество пачек бумаги можно приобрести на \(A\) рублей, правильно используя рекламные предложения?

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

Во входном файле записаны целые числа \(N\), \(K\), \(A\) и \(B\) (\(1\leq N\leq 100\), \(2\leq K\leq 100\), \(1\leq A \leq 10^9\), \(1\leq B \leq 10^9\)), разделенные пробелами.

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

Выведите одно целое число - максимальное количество пачек бумаги, которое смогут купить организаторы олимпиады.

Примечание

В первом примере, дважды используя второе рекламное предложение, можно купить 8 пачек бумаги, заплатив за 6.

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

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

4 4 13 2

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

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

3 4 8 3

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

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

3 4 7 1

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

#3292

Дипломы в папках (6-9)

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2011, Задача B ]

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

Иван хочет принести в приемную комиссию выбранного вуза папку, в которой находится диплом Московской олимпиады по программированию (такой диплом у Ивана ровно один). Для того чтобы понять, что в данной папке нужного диплома нет, Ивану нужно просмотреть все дипломы из этой папки. Просмотр одного диплома занимает у него ровно одну секунду и он может мгновенно переходить к просмотру следующей папки после окончания просмотра предыдущей. Порядок просмотра папок Иван может выбирать.

По заданному количеству дипломов в каждой из папок требуется определить, за какое наименьшее время в худшем случае Иван поймет, в какой папке содержится нужный ему диплом.

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

В первой строке входного файла записано целое число \(N\) (\(1\leq N\leq 100\)) - количество папок. Во второй строке записаны \(N\) целых чисел \(a_1\), \(a_2\), ..., \(a_N\) (\(1 \leq a_i \leq 100\)) - количество дипломов в каждой из папок.

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

Выведите одно число - минимальное количество секунд, необходимое Ивану в худшем случае для определения того, в какой папке содержится диплом.

Примечание

В примере Иван может просмотреть папку 2 за 1 секунду и, не найдя там диплома, понять, что диплом находится в папке 1.

Если же он найдет диплом в папке 2, то на поиск уйдет также 1 секунда.

Примеры

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

2
2 1

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

#3293

Дипломы в папках (10-11)

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2011, Задача B ]

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

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

По заданному количеству дипломов в каждой из папок требуется определить, за какое наименьшее время в худшем случае Иван поймет, в какой папке содержится нужный ему диплом.

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

В первой строке входного файла записано целое число \(N\) (\(1\leq N\leq 10^5\)) - количество папок. Во второй строке записаны \(N\) целых чисел \(a_1\), \(a_2\), ..., \(a_N\) (\(0 \leq a_i \leq 10^5\)) - количество дипломов в каждой из папок.

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

Выведите одно число - минимальное количество секунд, необходимое Ивану в худшем случае для определения того, в какой папке содержится диплом.

Примечание

В первом примере Иван может открыть и просмотреть папку 2 за 2 секунды и, не найдя там диплома, понять, что диплом находится в папке 1.

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

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

2
2 1

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

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

4
1 0 2 1

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

#3294

Параллелограмм (6-9)

Темы: [Элементарная геометрия]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2011, Задача C ]

На уроке геометрии семиклассники Вася и Петя узнали, что такое параллелограмм. На перемене после урока они стали играть в игру: Петя называл координаты четырех точек в произвольном порядке, а Вася должен был ответить, являются ли эти точки вершинами параллелограмма.

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

Напомним, что параллелограммом называется четырехугольник, противоположные стороны которого равны и параллельны.

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

В первой строке входного файла записано целое число \(N\) (\(1 \leq N \leq 10\)) - количество заданных Петей вопросов. Каждая из \(N\) последующих строк содержит описание четырех точек - четыре пары целых чисел \(X\) и \(Y\) (\(-100 \leq X\leq 100\), \(-100\leq Y \leq 100\)), обозначающих координаты точки. Гарантируется, что четыре точки, о которых идет речь в одном вопросе, не лежат на одной прямой.

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

Для каждого из вопросов выведите "YES", если четыре заданные точки могут образовать параллелограмм, и "NO" в противном случае. Ответ на каждый из запросов должен быть в отдельной строке без кавычек.

Примеры

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

3
1 1 4 2 3 0 2 3
1 1 5 2 2 3 3 0
0 0 5 1 6 3 1 2

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

YES
NO
YES

#3295

Параллелограмм (10-11)

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2011, Задача C ]

На уроке геометрии семиклассники Вася и Петя узнали, что такое параллелограмм. На перемене после урока они стали играть в игру: Петя называл координаты четырех точек в произвольном порядке, а Вася должен был ответить, являются ли эти точки вершинами параллелограмма.

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

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

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

В первой строке входного файла записано целое число \(N\) (\(1 \leq N \leq 10\)) - количество заданных Петей вопросов. Каждая из \(N\) последующих строк содержит описание четырех точек - четыре пары целых чисел \(X\) и \(Y\) (\(-100 \leq X\leq 100\), \(-100\leq Y \leq 100\)), обозначающих координаты точки.

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

Для каждого из вопросов определите, образуют ли данные точки параллелограмм. Если они образуют параллелограмм, то выведите номера этих точек в одной строке через пробел в порядке обхода параллелограмма. Начинать обход можно с любой из вершин. Если они не образуют параллелограмм, выведите в этой строке одно число 0. Ответ на каждый из запросов должен быть в отдельной строке.

Примеры

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

3
1 1 4 2 3 0 2 3
1 1 5 2 2 3 3 0
0 0 5 1 6 3 1 2

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

1 3 2 4
0
1 2 3 4