Дан массив с числами, в десятичном представлении - из них можно удалить какие-то, а то что осталось конкатенировать. Для N чисел это даёт 2^N-1 возможных результатов (нельзя удалить все числа) - и нам интересно сколько из этих результатов делятся нацело на 13.
Для маленьких массивов можно написать простой перебор, но автор предлагает N=400000 - у одного из пользователей это сразу вызвало реакцию "2 в степени 400000 - это невозможно перебрать". Действительно, перебором тут не справиться :)
Задача тут - а под катом, поскольку о ней самой уже говорить нечего, я немножко расскажу про автора - это довольно любопытно (и может когда-то я смогу более подробный пост о нём сделать если получу от него самого больше информации).
Таинственный Незнакомец
Где-то осенью 2019 года на сайте CodeAbbey появился пользователь под ником CSFPython который довольно резво начал подниматься вверх по таблице рейтинга. Я даже сперва подумал "наверное, опять читер" - но код его решений выглядел как код человека мало знакомого с программированием. Кажется к декабрю он решил все задачи существовавшие на тот момент. Конечно я был заинтригован.
Прошло несколько недель - и вдруг я обнаружил в почте письмо сопровождающее донейшн через Paypal на $200 кажется - от какой-то незнакомой барышни. Я вежливо ответил что мол спасибо, таких пожертвований мой скромный сайт ещё не видел - но было бы интересно узнать кто же такой доброжелатель.
На это мне написал Клайв и пояснил что он как раз и есть CSFPython - а поскольку он не в ладах с PayPal-ом, то попросил свою дочь сделать перевод в размере примерно покрывающем годовое содержание двух небольших серверов которые используются сайтом.
Он пояснил вкратце что сам он не программист, но большой энтузиаст всякого рода головоломок - и в какой-то момент освоил Python чтобы решать те головоломки которые требуют какого-либо компьютерного расчета. А потом по случаю напал на мой сайт.
Тут надо напомнить что на CodeAbbey задачи не только (и не столько) головоломного типа - есть и на изучение алгоритмов (в т.ч. криптография, сжатие и пр), и на странные языки типа Брейнфака или Ассемблера для intel-4004 - и он со всем этим справился. Хотя "не программист".
В биографических замечаниях он был сдержан - пояснил что когда-то рассматривал для себя научную карьеру - в физике или математике - но позже преподавал в школе и "занимался административной деятельностью" там же.
Фейерверк Головоломок
Сайт мой на тот момент переживал достаточно застойный период - помимо прочих причин была ещё и специфическая. Я редко добавлял новые задачи из-за того что по тогдашним условиям получить "сертификат" на сайте можно было за 145 задач, любых. Соответственно добавлять простые задачи не хотелось - они обесценивали сертификаты - а более продвинутые придумать удавалось нечасто.
Здесь напомню - на сайте CodeAbbey доступны некие сертификаты - хотя мне неизвестно чтобы какие-то компании или институты их всерьез рассматривали - но они забавные и нравятся пользователям - в то же время получить их не так легко, так что для многих это мотивация. И ещё их можно прицепить в LinkedIn например.
Клайв как раз был человеком который предложил простой способ разрулить эту ситуацию - были добавлены сертификаты нового типа, выдаваемые за 120 задач, но отмеченных специальным тегом (то есть не слишком тривиальные). Старые сертификаты оставлены в действии для тех кто зарегистрировался и решал задачи до этого нововведения.
Оказалось, что эту идею Клайв предложил неспроста - начиная с этого момента он стал предлагать задачи на сайт - причем прямо скажем, его задачки обычно попадали в раздел "головоломки" и получали тот самый тег, который свидетельствует что задача подходит для "сертификации".
Поскольку задача состоит из текста условия - а также некоего кода который генерит входные данные и проверяет ответ - вскоре я сделал добавление на сайте, чтобы этот самый генерящий и верифицирующий код (setter / checker) можно было писать на Python (изначально как и сам сайт использовался только PHP). В отличие от большинства других пользователей предлагающих задачи Клайв обычно присылает материалы (текст и код) в духе "Plug and Play" - их достаточно просто добавить и всё наверняка работает.
Это кстати оказалось выгодно для меня самого еще и потому что теперь и мне есть что порешать :) Я не большой спец в головоломках - поэтому многие из задач Клайва явно ждут пока я сам выйду на пенсию и смогу думать над ними целыми днями.
Отмечу, многие из его задач более-менее связаны с идеей "динамического программирования" - но часто не прямо очевидно как его применить. Большинство из них привлекательны как раз потому, видимо, что сам он не будучи программистом (и тем более спортивным программистом) придумывает такие задачи которые позволяют постепенно "докопаться" до решения, "покрутив" задачу в голове какое-то время, поэкспериментировав с карандашом и бумагой.
Все задачи Клайва Фрэйзера доступны на его страничке на сайте - их количество давно уже перевалило за 50 (притом что всего задач на сайте чуть больше 450 накопилось с 2013 года). Иногда думаю что его задачи полезно будет когда-то выпустить отдельно, м.б. книжкой головоломок в духе Лойда и Дьюдени - сам он пока к этой затее относится скептически :)
