В этом году SuperJob вместе с CODDY и Codenrock организовали хакатон YOUNG CODERS PARTY, для юных кодеров от 14 до 18 лет, в итоге самые сильные участники получили свои крутые призы.

Предлагаем вам немного размяться и почувствовать себя на месте юных программистов.

Под катом серия предложенных участникам YOUNG CODERS PARTY задач (лишь слегка доработанных — чтобы вам было тоже интересно!). Присылайте свои решения до 28 декабря включительно; мы постараемся подвести итоги конкурса до Нового Года. Победители получат от нас призы — теплые толстовки, маски с принтами и стикерпаки! 

Правила отправки решений и определения победителей

Решения нужно присылать на наш адрес superjob.codersparty@gmail.com до 28 декабря включительно, каждую задачу в отдельном файле с именем, начинающимся с номера задачи. В теме письма укажите «Хакатон/PHP» или «Хакатон/Python» (см. ниже). В письме напишите свой ник на хабре. Каждый скрипт должен читать входные данные из расположенного в одной директории с ним файла in.txt и выводить результат в стандартный поток вывода. В случае, если выполнить задание с указанными входными данными невозможно, скрипт должен выводить слово ERROR.

Решения должны быть ЛИБО на PHP 8.0, ЛИБО на Python 3.6, победители будут определены для PHP и Python отдельно. Один участник может прислать решения на обоих языках, тогда они должны быть отправлены двумя отдельными письмами с соответствующими темами. В случае если от одного участника будет получено несколько решений на одном языке, то мы постараемся выбрать из них последнее по времени и будем игнорировать все остальные.

Среди правильных решений больше баллов получит то, которое работает оптимальнее. А именно, все решения будут проверены на одном для всех участников тестовом стенде, на одних тестовых данных (они могут и будут отличаться от приведенных в тексте задач), и будет определено суммарное время работы решения на всех входных данных для каждой задачи отдельно. Самое быстрое решение получит 100 баллов за эту задачу, второе место — 90, …, седьмое — 40, восьмое — 35, тринадцатое — 10 баллов, четырнадцатое — 8, …, семнадцатое — 2, остальные — 1 балл. В случае наличия после названия задачи мультипликатора в скобках — полученные баллы будут умножены на него. Призовые места будут распределяться по сумме баллов за все задания, набранные одним участником (отдельно для PHP и Python). В случае совпадения числа баллов приоритет отдается тому, кто решил большее число задач, при совпадении также и числа задач — тому, кто прислал свое решение раньше.

Задачи

№1. Монеты (х1.5)

У Васи есть N рублей купюрами. Он хочет разменять их на монеты по 1, 4, 5 и 7 рублей.

Автомат, который это делает, принимает на вход купюры, а выдает монеты, причем наименьшее их количество.

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

Входные данные: количество денег
Выходные данные: минимальное количество монет

Тестовые пары:

Входные данные: 14
Выходные данные: 2

Входные данные: 34
Выходные данные: 6

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

Входные данные: 7
Выходные данные: 1

Входные данные: 8
Выходные данные: 2

Входные данные: 123
Выходные данные: 18

Входные данные: 547
Выходные данные: 79

Входные данные: 999
Выходные данные: 143

№2. Страницы

Книга состоит из N страниц. Известно, что для записи всех номеров страниц этой книги было напечатано M символов.

Напишите программу, которая вычисляет N из M.

Входные данные: число символов для записи страниц книги
Выходные данные: количество страниц в книге

Тестовые пары:

Входные данные: 13
Выходные данные: 11

Входные данные: 25
Выходные данные: 17

Входные данные: 53
Выходные данные: 31

Входные данные: 1314
Выходные данные: 474

Входные данные: 10001
Выходные данные: 2777

Входные данные: 500505
Выходные данные: 101935

№3. Максимум

Дана строка, в которой через пробел написаны натуральные числа. Напишите программу, которая выводит наибольшее отношение произведения трех чисел из данного ряда к их сумме (с точностью до 2 знаков после десятичной точки). Числа могут быть равны между собой математически, но должны стоять на разных местах в исходной строке.

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

Тестовые пары:

Входные данные: 1 2 3 4
Выходные данные: 2.66 или 2.67

Входные данные: 5 12 1 50 9 5 2 11
Выходные данные: 90.41

Входные данные: 3 3 3
Выходные данные: 3, 3.0 или 3.00

Входные данные: 10 20 30 40 50 60 50 40 30 20 10
Выходные данные: 937.5 или 937.50

Входные данные: 99 98 97 98 50 31 99 98 97
Выходные данные: 3244.92 или 3244.93

Входные данные: 1 1 1 1 1 1 1 1 1 1 1
Выходные данные: 0.33

№4. Обратный факториал (х2)

Факториалом натурального числа n называют последовательное произведение всех чисел от 1 до n и обозначают n!. Например, 5! = 1 * 2 * 3 * 4 * 5 = 120.

Напишите программу, которая из n! получает n.

Входные данные: n! - факториал числа n
Выходные данные: n - исходное число

Тестовые пары:

Входные данные: 120
Выходные данные: 5

Входные данные: 6
Выходные данные: 3

Входные данные: 5040
Выходные данные: 7

Входные данные: 2432902008176640000
Выходные данные: 20

Входные данные: 25852016738884976640000
Выходные данные: 23

Входные данные: 8841761993739701954543616000000
Выходные данные: 29

№5. Вирус

В корпоративный компьютер проник вирус, который удалил некоторые пробелы и добавил некоторые лишние символы в документе с данными по поставкам микроволновых печей. В документе использовались первые три буквы от наименований производителей. Чтобы как-то восстановить документ, необходимо написать функцию, которая возвращает повторяющиеся группы из трех знаков идущих подряд. Если нет повторов, то выводится 0

Пример: "anb" и "abn" разные группы, "ans" и "ans" одна группа. 

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

Тестовые пары:

Входные данные: ghjghjghjghjghj
Выходные данные: ghj,5,hjg,4,jgh,4

Входные данные: dfrbhtdrfdfr
Выходные данные: dfr,2

Входные данные: fghjk
Выходные данные: 0

№6. Про кратность (х1.5)

Напишите функцию, которая будет принимать массив из целых положительных чисел, и проверять, можно ли перемножить 3 из этих чисел и получить такое число, чтобы 2160 было кратно ему.

Входные данные: строка состоящая из целых положительных чисел, разделенных запятыми
Выходные данные: 0 или 1. Если да, то 1. Если нет, то 0.

Тестовые пары:

Входные данные: 3,1,6,3,7,7,8,2,3
Выходные данные: 1

Входные данные: 7,7,7,7
Выходные данные: 0

Входные данные: 9,9,9,9,9,9,99
Выходные данные: 0

Входные данные: 11,12,12,12,12,12
Выходные данные: 0

Входные данные: 9, 9, 8, 8, 20, 18
Выходные данные: 0

Входные данные: 4, 6, 8, 10, 12
Выходные данные: 1

№7. Рекламная рассылка (х2.5)

У компании есть некоторое количество офисов, положение каждого из которых задано вещественными координатами — широтой (-90.0…90.0) и долготой (-180.0…180.0). Можно для простоты считать, что значения на границах этих интервалов (ровно +90 и -90 для широты, ровно +180 и -180 для долготы) никогда не встречаются.

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

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

• в первой строке координаты офисов (пары чисел широта/долгота), разделенные запятыми;

• во второй строке координаты клиентов, заданные аналогично;

• в третьей строке вещественное число R.

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

Поверхность Земли считать идеальной сферой. Радиус Земли принять равным 6371 км.

Тестовые пары:

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

55.771839,37.605256,55.764811,37.607968,55.767919,37.598555,55.756817,37.632305
55.760849,37.618031,55.771515,37.608517,55.764600,37.603249,55.792799,37.424709
2.1

Выходные данные:1,2,2,1,3,2