В этом году 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

Комментарии (13)


  1. Rsa97
    22.12.2021 20:28
    +1

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


    1. vvmax Автор
      23.12.2021 10:19
      +1

      Добавили уточнение: радиус Земли принять равным 6371 км.


  1. am_I_Evil
    23.12.2021 10:20
    +1

    Я правильно понимаю что в файле in.txt будет для каждого прогона одно число или строка? В таком случае чтение из файла, да и даже вывод результата в поток занимают времени больше чем выполнение алгоритма. Во всяком случае для первой задачи. Что превращает задачи не в написание оптимального алгоритма, а в поиск самых быстрых способов чтения из файла и вывода на выбранном ЯП.


    1. MarrchCaat
      23.12.2021 10:32

      Количество способов прочесть строку или несколько из входного файла в указанных языках крайне ограничено. Да, если сделать ввод/вывод как-то очень неоптимально, то это будет большой минус. Ну что ж, значит - не надо его делать неоптимально, перебрать несколько вариантов - не сложно, если нет уверенности в том, какой оптимальнее. Ну и в конце концов, не корову же разыгрываем :) Будем считать это разминкой, а в новом году попробуем провести лучше и для взрослой аудитории!


  1. Rsa97
    23.12.2021 11:39
    +1

    В задаче с факториалами можно ли использовать GMP или BC Math? Величина факториала будет ограничена PHP_INT_MAX или может быть любое значение, например 1000!?


    1. MarrchCaat
      23.12.2021 17:20
      +1

      Насколько я вижу, приведенное в последней тестовой паре значение (8841761993739701954543616000000) уже существенно больше, чем PHP_INT_MAX во всех стандартных реализациях. А иначе это было бы слишком просто :)

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


      1. SerafimArts
        24.12.2021 18:05

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

        Если что, то FFI включён по умолчанию в консольном режиме… Получается, что можно написать обёртку над GMP руками и прокидывать их в пых, вместо использования расширения… Т.е. GMP использовать можно, но только дописав обёртку под него.


        П.С. С другой стороны, ещё ничего не сказано про функции запуска, т.е. можно через exec, например, поставить нужное расширение (или скачать из сырцов и скомпилить) и запустить код уже с ним)))


  1. AnnT123
    23.12.2021 17:21

    Уточните пожалуйста в задаче про вирусы для строки "ababa abababa" выводить значения с учетом перекрытий или без? Например, для "aba" - 3 или 5?


    1. MarrchCaat
      23.12.2021 17:24

      Если бы перекрытия "не считались", это приводило бы к неоднозначностям, и противоречило бы приведенным тестовым данным. В приведенной Вами строке aba - 5.


      1. AnnT123
        23.12.2021 18:29

        Чтобы не было неоднозначностей и надо уточнять ТЗ.

        Вот еще один момент противоречивости в том же задании:

        • В документе использовались первые три буквы от наименований производителей.

        • Чтобы как-то восстановить документ, необходимо написать функцию, которая возвращает повторяющиеся группы из трех знаков идущих подряд

        • Выходные данные: строки, где через запятую выведены группы повторяющихся букв

          Ведь пробел - это не буква, но это точно знак. Для такого входа "avava avavava as" согласно текущему ТЗ если смотреть по знакам, получаем на выходе "a a,2,ava,5,va ,2,vav,3". Или вса таки нет? :-)


        1. Rsa97
          23.12.2021 22:46
          +1

          Да, а ещё вопрос в том, какой алфавит использован (только латиница, латиница + кириллица, произвольный алфавит). Регистрозависимая строка или нет. Могут ли в ней быть спецсимволы и что с ними делать.
          По хорошему, в таких заданиях должны указываться ограничения на каждый входной параметр — тип значения, диапазон, предельный размер списка, алфавит и т.п.


          1. MarrchCaat
            24.12.2021 03:03
            +1

            Конечно, по-хорошему Вы правы. И я (участвуя много раз в жизни в проведении школьных олимпиад по математике) всегда тратил вместе с коллегами немало времени на то, чтобы максимально "вылизать" условия всех задач. По счастью, тут у нас все же не настолько ответственная задача :) Просто когда закончился "хакатон" для школьников - кому-то из нас вдруг пришла в голову мысль: "А зачем хорошим задачам пропадать?! Давайте их чуть-чуть усложним и поделимся с хабровцами!". Ну а в последний момент решили провести это в форме предновогоднего ненапряжного конкурса.

            Что касается алфавита - используется только латинский алфавит, только нижний регистр. Как в примерах.


  1. Alexandroppolus
    24.12.2021 10:24

    ЛИБО на PHP 8.0, ЛИБО на Python 3.6

    А почему нет JS?