Юный информатик стал исследовать, как изменяются суммы цифр натуральных чисел при умножении и делении на разные однозначные числа. Однажды он задался вопросом, можно ли восстановить число A, если нам известна сумма его цифр, а также сумма цифр числа D×A, где D — заданное однозначное число. Довольно быстро он установил, что для восстановления числа А этой информации недостаточно. Так, например, у чисел 9 и 45 одинаковые суммы цифр. Если же их умножить на 5, то получим числа 45 и 225, которые тоже имеют одинаковые суммы цифр.
Тогда юный информатик стал искать ответ на поставленный вопрос при условии, что нам известно K — количество десятичных знаков в числе A. К сожалению, и тут его ждало разочарование. У некоторых чисел, имеющих одинаковое количество цифр и одинаковые суммы цифр, после умножения на один и тот же множитель эти суммы опять оказываются одинаковыми. Такими числами, например, являются 42 и 51 при D = 3.
И тогда юный информатик поставил перед собой такую задачу: найти наименьшее K значное натуральное число A в десятичной системе счисления, которое имеет сумму цифр, равную S, а число D×A имеет сумму цифр, равную P.
Требуется написать программу, решающую поставленную задачу.
Вводятся четыре натуральных числа K, S, P, D (1 ≤ K ≤ 100, 1 ≤ S ≤ 9K, 1 ≤ P ≤ 9(K+1), 1 ≤ D ≤ 9).
Выведите число A, если оно существует, или –1, в противном случае. Число A не может начинаться с нуля.
Примечание
Решения, корректно работающие при K ≤ 40, будут оцениваться, исходя из 80 баллов.
3 15 15 1
159
|
В городе Шахматовске два интернет-провайдера выполняют план по всеобщей интернетизации страны. Город расположен на бесконечной целочисленной решетке, по всем линиям которой проходят прямые улицы, а единичные квадраты сетки определяют кварталы. Координатами квартала считаются координаты вершины левого нижнего угла соответствующего единичного квадрата. Кварталы города окрашены в черный и белый цвета в шахматном порядке, при этом квартал с координатами (0, 0) окрашен в черный цвет.Интернет-провайдер «Черный интернет» занимается подключением кварталов черного цвета. Недавно стало известно, что жителям квартала, подключенного K-м, будет предоставлена скидка в 10%. В соответствии с планом компании «Черный интернет» интернетизация будет проводиться в течение N дней. В i-й день бригада сотрудников компании движется по какой-то из улиц города, начиная из точки (xi, yi). Бригада проходит li кварталов в заданном направлении. При этом она подключает ранее не подключенные кварталы черного цвета, граничащие по стороне с путем движения бригады (см. рис.). Требуется написать программу, которая определит координаты квартала, подключенного во время реализации плана K-м по очереди. Гарантируется, что в процессе реализации плана будет подключено не менее K кварталов. |
|
В первой строке задаются два целых числа N и K (1 ≤ N ≤ 2 000, 1 ≤ K ≤ 1018).
Далее следуют N строк с описанием плана развития компании. В i-й строке описания плана записан путь бригады в i-й день: xi и yi (–1015 ≤ xi ≤ 1015, –1015 ≤ yi ≤ 1015) — координаты начальной точки пути, символ ci — направление движения, и li (1 ≤ li ≤ 1015) — расстояние, которое пройдет бригада. Направление движения задается одним из следующих символов: «N» — север (по увеличению y-координаты), «E» — восток (по увеличению x-координаты), «S» — юг (по уменьшению y-координаты), «W» — запад (по уменьшению x-координаты).
Выведите координаты x и y квартала, подключенного K-м.
5 19 20 6 S 5 9 7 S 7 9 18 W 1 13 18 N 2 12 13 E 5
15 13
На планете в звездной системе Альфа Кентавра неделя состоит из A дней, а год - из B дней. Годы нумеруются последовательными натуральными числами: 1, 2, 3, ... Кроме того, годы с номерами C1, C2, ..., CN являются високосными и состоят из (B+1) дней. В году дни с номерами D1, D2, ..., DM являются праздничными. Если праздник попадает на (B+1)-й день года, то он отмечается только в високосные годы. Первый день первого года является первым днем недели.
Один из жителей планеты решил устроиться на новую работу. В соответствии с заключенным трудовым договором он будет числиться на данной работе в течение E дней, начиная с первого дня 1-го года. По договору он имеет право выбрать один день недели (с 1 по A), который будет для него выходным. Праздничные дни также считаются нерабочими. Житель хочет выбрать себе выходной день таким образом, чтобы за период действия договора у него было максимальное количество нерабочих дней.
Требуется написать программу, которая определяет искомый день недели и вычисляет соответствующее количество нерабочих дней.
В первой строке входного файла через пробел записаны числа A и B - количество дней в неделе и в невисокосном году соответственно (1 ≤ A ≤ 2500, 1 ≤ B ≤ 10000). Во второй строке записано число N - количество високосных лет, и в третьей - номера C1, C2, ..., CN високосных лет в возрастающем порядке (0 ≤ N ≤ 5000, 1 ≤ C1 < C2 < ... < CN ≤ 107). В следующей строке число M - количество праздничных дней в году, и на новой строке - D1, D2, ..., DM в возрастающем порядке (1 ≤ D1 < D2 < ... < DM ≤ B+1). В последней строке записано число E (1 ≤ E ≤ 109). Известно, что житель заключил контракт не более чем на 107 лет.
В выходной файл выведите через пробел два числа - номер дня недели, который выгоднее всего сделать выходным, и соответствующее количество нерабочих дней за период действия договора. Если ответов несколько, то выведите любой из них.
7 13 1 2 2 1 14 29
1 8
При наборе текста довольно часто возникают опечатки из-за неправильного нажатия на клавиши. Например, некоторые буквы оказываются заменены на другие, появляются лишние буквы, некоторые буквы исчезают из слов. В большинстве случаев эти опечатки можно исправить автоматически. В частности, существует метод проверки орфографии, основанный на поиске в словаре слов, похожих на проверяемые.
Два слова называются похожими, если можно удалить из каждого слова не более одной буквы так, чтобы слова стали одинаковыми, возможно пустыми. Например, слова "spot" и "sport" похожи, так как одно и то же слово "spot" можно получить из первого слова без удаления букв, а из второго - удалением буквы "r".
Требуется написать программу, которая для каждого слова проверяемого текста определяет количество похожих на него слов в словаре.
В первой строке входного файла через пробел записаны натуральные числа N ≥ 1 - общее количество слов в словаре и M ≥ 1 - количество слов в проверяемом тексте (N+M ≤ 20000) В последующих N строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют M строк, в которых записаны слова проверяемого текста, по одному слову в строке.
Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.
Для каждого слова из текста выведите в выходной файл строку, содержащую это слово, далее через пробел количество слов из словаря, на которые оно похоже. Если в словаре имеется единственное похожее слово, то также выведите в этой строке это слово (через пробел).
5 8 father and or mother a Father and mather go o for e walk
Father 1 father and 1 and mather 2 go 1 or o 2 for 1 or e 1 a walk 0
Горнолыжник, готовясь к соревнованиям, нарисовал на бумаге схему горнолыжной трассы для выбора оптимального маршрута спуска. На схеме расположенные на трассе ворота представлены горизонтальными отрезками. Никакая пара ворот не имеет общих точек.
Маршрут должен представлять собой ломаную, начинающуюся в точке старта на вершине горы и заканчивающуюся в точке финиша у ее подножия. Маршрут выбирается таким образом, что y-координата каждой следующей вершины ломаной оказывается строго меньше y-координаты предыдущей вершины. Один из возможных маршрутов представлен на рисунке.
За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.
Требуется написать программу, которая определяет, какой минимальный общий штраф горнолыжник может получить при прохождении трассы.
В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.
В выходной файл выведите наименьший возможный общий штраф за прохождение трассы с точностью не менее 4 знаков после десятичной точки.
Потестовая.
4 3 6 3 1 5 7 4 1 4 5 5 10 1 2 4 5 2 5 2 0
7.8126
