"...И узрели они войско вражье хазарское. И было хазарам несметное число." —
Тут летописец задумался. Он знал, что число воинов было равно N.
Однако, это число могло делиться на три, а могло (что еще хуже)
содержать цифру три в десятичной записи!
Число три счастливое, а это никак не согласуется с образом врага!
Поэтому летописец решил написать вместо числа N другое число M,
которое не делится на три и не содержит в десятичной записи цифру три.
Разумеется, число M не может быть меньше N (летописец не преуменьшает
количество воинов). С другой стороны, число M должно как можно меньше
отличаться по величине от N,
иначе летописца могут обвинить в некомпетентности.
Помогите летописцу найти нужное M.
Формат входного файла
Во входном файле содержится натуральное число N, записанное без лидирующих нулей.
Формат выходного файла
Выходной файл должен содержать минимальное подходящее число M (M ≥ N),
записанное без лидирующих нулей.
Ограничения
Десятичная запись числа N содержит от 1 до 10000 цифр.
Несмотря на быстрый рост производительности компьютеров, некоторые вычислительные задачи
по прежнему требуют долгих расчётов.
Дешёвым и эффективным методом решения части таких задач являются вычислительные кластеры.
Кластер — это группа разнородных компьютеров, связанных локальной сетью,
между которыми распределяется работа.
Кластер обычно имеет центральный сервер, который занимается разделением исходной задачи
на подзадачи и сбором решения из частичных решений, полученных компьютерами, входящими в кластер.
Пусть кластер состоит из N компьютеров и сервера. Компьютеры имеют разную производительность,
так что i-й компьютер заканчивает расчёт одной подзадачи за ti секунд. По окончании расчёта
компьютер отправляет результаты на сервер, получает в ответ следующую подзадачу, тратит на неё ещё ti
секунд, и т.д.
Таким образом, в одну секунду на сервер могут прийти ответы от нескольких компьютеров.
Поскольку количество компьютеров в кластере можно легко наращивать,
центральный сервер часто становится узким местом, ограничивающим общую производительность.
Требуется написать программу, которая определит, через сколько секунд после начала работы кластера
нагрузка на сервер впервые достигнет максимума — все N компьютеров одновременно отправят ответы на сервер.
Формат входного файла
Во входном файле содержится число N, за которым следуют N чисел t1… tN.
Формат выходного файла
В выходном файле должно содержаться количество секунд до максимальной загрузки.
Так как это число может быть очень велико, оно должно быть выведено в виде разложения на простые множители.
При этом множители должны быть отсортированы по возрастанию и разделяться символом '*'
(ASCII 42).
Если степень вхождения простого числа больше единицы, следует указать её вслед за числом, разделив их
символом '^' (ASCII 94).
Например: число 25 будет иметь вид: 5^2, а число 3000 — 2^3*3*5^3.
Археологическая экспедиция обнаружила в долине реки
Амазонка следы доселе неизвестной цивилизации индейцев.
На стенах крупнейшего храмового комплекса исследователи
обнаружили надписи, которые при ближайшем рассмотрении оказались записями чисел.
Анализ следов письменности позволил археологам
определить, что индейцы использовали натуральные числа в диапазоне
от 1 до 2N.
Запись любого числа состояла из ровно N знаков двух видов.
За сходство с латинскими буквами ученые назвали один из знаков Q-символом,
другой — R-символом, а саму запись — QR-записью.
Выяснилось также, что индейцы сравнивали числа в QR-записи по следующему правилу:
числа равны, если имеют идентичную запись;
одно число меньше другого, если в записи первого количество
R-символов меньше, чем в записи второго;
при равном количестве R-символов числа сравниваются как строки
(при этом Q-символ считается меньше R-символа).
Для облегчения работы археологам необходима программа для перевода
натуральных чисел в QR-запись.
Формат входного файла
Во входном файле содержатся числа N и K.
Формат выходного файла
В единственной строке выходного файла должна содержаться QR-запись числа K.
Строка должна состоять ровно из N символов, каждый из
которых должен быть заглавной латинской буквой Q (ASCII 81) или R (ASCII 82).
Отличник Вася очень любит решать задачи по математике, однако большинство одноклассников
не разделяют его любовь и поэтому списывают решения у Васи.
При решении задач Вася пишет операнды и ответ в своей тетради,
но часто торопится и пропускает арифметические операции.
Васины одноклассники при списывании вынуждены подставлять в выражение знаки операций.
Самим им это делать не хочется, а так как задачи по программированию они тоже не любят,
то попросили вас написать программу, которая делала бы это за них.
Помимо вышеперечисленного известно, что:
Количество операндов равно N.
Операции в примере выполняются слева направо, т.е. 1+2/3*4 означает ((1+2)/3)*4.
При решении Вася использовал четыре операции: сложение ('+'),
вычитание ('-'), умножение ('*') и деление нацело — ('/').
На любом этапе вычислений промежуточный результат по модулю не превосходит 1000
Формат входного файла
Во входном файле содержится целые числа a1a2… aN — операнды.
За которыми следует ответ R.
Формат выходного файла
В выходном файле должна содержатся строка из N − 1 символа — знаки операций,
которые следует подставить в решение, чтобы получить ответ R.
Если решений несколько, выведите любое из них, если решений не существует,
выведите IMPOSSIBLE.
Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб решил заняться изучением математики.
Пройдя тему "Кривые второго порядка", он захотел воспользоваться новыми знаниями на практике,
а заодно вспомнить некоторые магические заклинания.
В результате действий старика появился бесконечный забор, с высоты птичьего полёта
имеющий вид параболы y=ax2+bx+c.
Пока Хоттабыч проводил свой эксперимент, его друг Волька сдавал экзамен по географии.
После появления забора Хоттабыч понял, что забор может отделять Волькину школу от его дома, и
Волька, возможно, больше никогда не сможет попасть домой.
Хоттабыч знает координаты дома Вольки (XH; YH) и координаты школы (XS; YS)
и просит вас подсказать, сможет ли Волька вернуться домой.
Также Хоттабыч знает, что забор не проходит ни через школу, ни через дом Вольки.
Формат входного файла
Во входном файле содержатся целые числа abcXHYHXSYS
Формат выходного файла
В выходном файле должно содержаться единственное слово: YES,
если Волька сможет добраться до дома, или NO — в противном случае.
Ограничения
Все числа по модулю не превосходят 103.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
1 0 0
0 1
0 -10
NO
2
1 0 0 0 1 0 10
YES
3
-2 -8 -16
-1 -11 -4 -17
YES
Задача F. Езда по тротуарам на велосипеде во Владивостоке
≡
Один владивостокский Программист очень любит ездить не велосипеде.
Его маршрут на карте имеет вид ломаной с N вершинами
в плоской прямоугольной системе координат.
Владивосток — большой город! Потеряться в нем легко, особенно на велосипеде.
К счастью, у Программиста с собой карта с маршрутом, а велосипед имеет
счётчик пройденного пути.
Исходя из этих данных, помогите найти текущие координаты программиста.
Формат входного файла
Во входном файле в содержится целое число N,
за которым идёт действительное L — текущий показатель счётчика.
Далее расположены N пар целочисленных координат xiyi — вершины маршрута.
Гарантируется, что L не превышает длины маршрута.
Некоторые вершины ломаной, в том числе идущие одна за другой, могут совпадать.
Формат выходного файла
Выведите два действительных числа — координаты искомой точки
с точностью до трех знаков после запятой.
Марсианская федерация автогонок ввела стандарт публикации результатов квалификационных заездов.
Согласно этому стандарту, стартовая решетка любого гран-при имеет вид таблицы, составленной по
определенным правилам. Правила оказались слишком сложными для хозяев автодромов, и они
попросили Вас написать программу для вывода этой таблицы.
В квалификационную сессию допускается N участников.
На марсианских гоночных трассах каждый стартовый ряд состоит из M позиций,
схема расположения которых на трассе такова:
Первая позиция находится в левой части трассы на уровне стартовой линии.
Внутри одного стартового ряда каждая последующая позиция находится правее и
дальше предыдущей на фиксированное расстояние.
Каждый следующий стартовый ряд формируется путем параллельного переноса предыдущего.
Из-за несоответствия некоторых гоночных болидов регламенту на старт выходят лишь
K ≤ N участников, при этом все они сохраняют свои стартовые позиции.
Правила публикации таблицы выглядят следующим образом:
Таблица разбита на блоки описания стартовых рядов.
Блоки разделены строкой из символов '=' (ASCII 61) во всю ширину таблицы.
Перед описанием ряда во всю ширину таблицы выводится заголовок — номер ряда и фраза 'starting line'.
После заголовка выводится строка из символов '-' (ASCII 45) и '+' (ASCII 43)
во всю ширину таблицы.
Далее следует информация о стартующих гонщиках данного ряда,
для ее вывода используются M строк и M столбцов.
Если гонщик занимает i-ое место в данном ряду, то его имя должно быть напечатано
на i-ой строке i-го столбца, если же гонщика не допустили к гонке, то эта ячейка пуста.
Если в ряду не оказывается ни одного гонщика, то блок с описанием этого ряда опускается.
Столбцы внутри ряда разделяются символами '|' (ASCII 124).
Граница всей таблицы состоит из символов '#' (ASCII 35).
Имена гонщиков и заголовки рядов выравниваются по центру с помощью пробелов.
Если строгого выравнивания достичь невозможно, то отступ слева должен быть на 1 меньше отступа справа.
Имена гонщиков и заголовки рядов отделяются от границ минимум одним пробелом слева и справа.
Все столбцы таблицы имеют равную, минимально возможную ширину.
Никакое имя гонщика не начинается с пробела и не заканчивается им.
Формат входного файла
Во первой строке входного файла содержатся числа K и M, в следующих 2*K строках
для каждого гонщика указано имя, а затем стартовая позиция.
Список отсортирован по возрастанию позиций.
Формат выходного файла
В выходном файле должна содержаться таблица с
описанием стартовой решетки по марсианским правилам.
Ограничения
1 ≤ N, M, K ≤ 100
Длина строки с именем гонщика не превосходит 100 символов.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
1 1
Michael Schumacher
1
######################
# 1 starting line #
#--------------------#
# Michael Schumacher #
######################
Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач.
Для этого на подстанциях были установлены N ретрансляторов.
Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору.
Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод,
назовем нагрузкой на данный провод для i-го ретранслятора.
Максимум из нагрузок на все провода для i-го ретранслятора
называется нагрузкой на данный ретранслятор.
Известно, что по проводам электросети сигнал может пройти
от одного ретранслятора к другому единственным образом.
Требуется написать программу, которая по заданной схеме электросети
подсчитает нагрузку на каждый ретранслятор.
Формат входного файла
Во входном файле содержится число N — количество ретрансляторов, за которыми
следуют N − 1 пар чисел uivi, означающих,
что i-ый провод соединяет ретрансляторы ui и vi.
Формат выходного файла
В выходном файле должно содержаться N чисел a1a2… aN,
где ai — нагрузка на i-ый ретранслятор.
