Задачи по информатике

Задачи по информатике

Задача 1. Арбуз

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

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

В первой и единственной строке входных данных записано целое число w (1 ≤ w ≤ 100) — вес купленного ребятами арбуза.

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

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

Примеры

входные данные

8

выходные данные

YES

Примечание

Например, ребята могут поделить арбуз на две части размерами 2 и 6 килограммов соответственно (другой вариант — две части 4 и 4 килограмма).

Задача 2. Близнецы

Представьте себе, что у Вас есть брат или сестра-близнец. Обычное утро в Вашей семье. Пока вы еще спите, мама уже собирается на работу. Она так торопилась, что чуть не забыла оставить вам, ее любимым детям, немного денег, чтобы покушать в школе в столовой. В кошельке она нашла некоторое количество монет, а именно n монет произвольных достоинств a1, a2, ..., an. Времени у нее было мало, поэтому поделить монеты она не успела. Тогда она написала записку, в которой попросила вас разделить деньги поровну.

Проснувшись, Вы нашли оставленные мамой монеты и прочитали записку. «Но зачем делить монеты поровну?» — подумали Вы, ведь Ваш близнец еще спит и ничего не узнает. Поэтому Вы решили поступить следующим образом: выбрать себе некоторое подмножество монет, так чтобы сумма достоинств взятых Вами монет оказалась строго больше, чем сумма достоинств оставшейся части монет, которая достанется Вашему близнецу. Однако, Вы справедливо решили, что если взять слишком много монет, то Ваш близнец подумает, что Вы его обманули. Поэтому, чтобы не вызывать подозрений, Вы решили взять наименьшее количество монет, сумма достоинств которых окажется строго больше суммы достоинств оставшихся. Исходя из этого, выясните, какое минимальное количество монет Вам понадобится взять, чтобы разделить их описанным образом.

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

В первой строке задано целое число n (1 ≤ n ≤ 100) — количество монет. Во второй строке задана последовательность из nцелых чисел a1, a2, ..., an (1 ≤ ai ≤ 100) — достоинства монет. Все числа разделены пробелами.

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

В единственной строке выведите одно число — минимальное необходимое количество монет.

Примеры

входные данные

2
3 3

выходные данные

2

входные данные

3
2 1 2

выходные данные

2

Задача 3. Олимпиада в Хогвартсе.

В Хогвартсе проходит традиционная ежегодная олимпиада по теории магии среди младшекурсников. Завхозу школы Аргусу Филчу поручили заняться распределением студентов по аудиториям.

Каждый факультет выставил своих лучших учеников на олимпиаду. От Гриффиндора участвуетGстудентов, от СлизеринаSстудентов, Пуффендуй представляетH студентов и Когтевран—Rстудентов. В распоряжении Филча находитсяMаудиторий. На аудитории наложено особое заклятие расширения, поэтому при необходимости они могут вместить любое количество студентов. При рассадке необходимо учесть, что ученики одного факультета, находящиеся в одной аудитории, могут, воспользовавшись случаем, начать жульничать, обмениваясь идеями по решению задач. Поэтому в любой аудитории количество студентов с одного факультета, попавших в нее, следует свести к минимуму. Назовем рассадку, удовлетворяющую такому требованию, оптимальной.

Помогите посчитать, какое минимальное количество студентов с одного факультета все же придется посадить в одной аудитории даже при оптимальной рассадке.

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

В первой строке идут четыре целых числа G, S, H и R (1 ≤ G, S, H, R ≤ 1000) — количество учеников, представляющих каждый из факультетов школы.

Во второй строке идет целое число M (1 ≤ M ≤ 1000) — количество классов в распоряжении у Филча.

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

Выведите минимальное количество студентов с одного факультета, которое Филчу придётся посадить в одну аудиторию даже при оптимальной рассадке.

Примеры тестов

входные данные

4 3 4 4
2

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

2

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

15 14 13 14
5

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

3

 

Задача 2. Порядочные числа

У Миши развитое эстетическое чувство. Он считает, что не все числа одинаково порядочные. Когда ему грустно, он начинает придумывать числа и приводить их в порядок.

Миша очень любит рассматривать сумму цифр числа. Для того чтобы привести в порядок число A, он сначала записывает само число. Потом он пишет сумму цифр этого числа. Затем — сумму цифр суммы цифр и так далее, до тех пор, пока очередное число не станет однозначным. Он считает, что результатом приведения в порядок числа A является сумма всех выписанных чисел, включая само число A.

Миша настолько любит этот процесс, что он даже заменяет ему счёт овец, когда долго не получается заснуть. Он помнит, что вчера ночью, когда он в уме привёл в порядок число A, у него получилось число B. Но вот беда — он не помнит, какое именно он взял число A! Помогите ему в отыскании этого числа.

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

На ввод подаётся единственное целое число B (1 ≤ B ≤ 1, 000, 000, 000)

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

Если существует такое число A, что после приведения его в порядок, получается B, то выведите любое такое число. Если же Миша где-то ошибся в расчётах и такого числа не существует, то выведите -1.

Примеры тестов

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

42

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

29

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

20

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

-1

Примечание

Пояснение к первому примеру. Последовательность сумм цифр для 29 состоит из чисел 29, 11, 2. Соответственно, после приведения в порядок число 29 превращается в число 42 = 29 + 11 + 2.

 

Задача 3. Шляпа.

Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых.

Изначально в шляпу помещают некоторое количество бумажек с написанными на них словами. После этого команды из двух человек по очереди и вслучайном порядке начинают отгадывать слова - один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то записка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы.

Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M, и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд.

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

В первой строке дано количество команд N и количество попыток отгадать слова M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000). В следующих M строках сначала указывается номер ni команды, пытавшейся отгадать слово, а через пробел дано слово wi, написанное на бумажке. Номера команд лежат в диапазоне от 1 до N. Все слова wi состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв.

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

Выведите в одну строку N чисел, i-ое число должно равняться количеству слов, отгаданному i-ой командой.

Примеры тестов

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

2 3
1 hat
1 shirt
2 hat

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

1 1

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

3 2
1 mom
3 dad

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

1 0 1

Примечание

В первом примере первая команда отгадала слово shirt, а вторая слово hat.