Переиграй школьников в YOUNG CODERS PARTY
В этом году 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
Входные данные: 52
Выходные данные: 31
Входные данные: 1313
Выходные данные: 474
Входные данные: 10000
Выходные данные: 2777
Входные данные: 500500
Выходные данные: 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.
Выходные данные: последовательность номеров (по порядку, как они были перечислены во входных данных) клиентов, получающих рассылку, за каждым из которых следует номер офиса (аналогично, по порядку, в котором они были перечислены во входных данных), куда он приглашен. Все числа разделены запятыми.
Поверхность Земли считать идеальной сферой.
Тестовые пары:
Входные данные:
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
