Все задачи

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

Гномы ложатся спать одновременно, вешая свои гамаки в случайном порядке. Но у каждого гнома есть свои предпочтения, один любит спать поближе к выходу, другому нравится забраться поглубже в штрек. Если гном спит на своем любимом месте, то он просыпается ровно через 8 часов. Если гном спит не на своем любимом месте, то он просыпается раньше на `C_i`*`|P_i\ -\ Q_i|` минут, где `C_i` – некоторый коэффициент, `P_i` – номер места, где спит гном, считая от выхода, `Q_i` – номер любимого места гнома. Проснувшийся гном сразу же направляется к выходу, будя по пути остальных гномов. Чем больше гном не досыпает до положенной нормы в 8 часов, тем в более дурном настроении он находится весь день.

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

В первой строке ввода содержатся семь целых чисел, разделенных пробелами – номера любимых мест для сна у гномов `Q_i` (`1\ ≤\ Q_i\ ≤\ 7`). Во второй сроке содержатся семь целых чисел – коэффициенты `C_i` (`1\ ≤\ C_i\ ≤\ 30`).

Вывести в первой строке перестановку целых чисел от 1 до 7 – номера мест `P_i` размещения гномов, при котором их суммарный недосып минимален. Если существует несколько вариантов с одинаковым минимумом, то вывести любой (один) из них.

1 4 1 7 7 1 7
7 5 4 10 12 3 6

1 4 2 6 7 3 5

Вагонетки с породой гномы привозят к подъемнику, а от подъемника забирают пустые. Гном Простак поднимает вагонетки наверх и сбрасывает породу в отвал. Когда гном привозит вагонетку к подъемнику, он отмечает на специальной доске это событие знаком '+'. Когда Простак поднимает вагонетку наверх, он ставит на доске знак '-'.

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

Ввод содержит одну строку длиной от 1 до 1000 символов, состоящую только из '+' и '-' – последовательность знаков на доске. Символ '-' может появиться в строке, только если очередь на разгрузку не пустая.

Вывести одно целое число – максимальную длину очереди.

++-++--+--

3

Гном Ворчун родился 29 февраля, поэтому свой день рождения он отмечает только в високосном году. Год является високосным, если он кратен 4 и при этом не кратен 100, либо кратен 400. Год не является високосным, если он не кратен 4 либо кратен 4, но при этом кратен 100 и не кратен 400.

Напишите программу, которая поможет Ворчуну определить, получит ли он подарки в заданном году.

Ввод содержит одно целое число `N` (`1\ ≤\ N\ <\ 10^9`) – номер года.

Вывести сообщение "Yes", если в год `N` подарки будут, или сообщение "No", в противном случае.

2007

No

Хотя в основе системы нумерации у гномов лежит число 10, гномы для представления больших чисел используют не десятки, сотни, тысячи, а представляют числа в виде суммы слагаемых, состоящих из одинаковых цифр. Гномы используют 54 слагаемых, а именно 1, 2, …, 9, 11, 22, …, 99, 111, …, 999, 1111, …, 9999, 11111, …, 99999, 111111, …, 999999. Для каждого слагаемого в языке гномов существует особое название и обозначение в виде одной из букв алфавита. Числа в этой системе нумерации можно записать несколькими способами, и гном Док решил найти наиболее компактное представление для записи всех чисел от 1 до 1000000.

Напишите программу, которая для заданного числа найдет его представление в виде суммы минимального числа слагаемых из одинаковых цифр.

Ввод содержит целое число `N` (`1\ ≤\ N\ ≤\ 10^6`).

Вывести число `N`, затем символ '=', затем представление числа `N` в виде суммы гномьих слагаемых. Количество слагаемых в сумме должно быть минимально. Слагаемые могут повторяться, порядок слагаемых в сумме не важен.

150

150=111+6+33

Гном Чихун получил свое прозвище из-за частого чиханья. Иногда он может чихнуть 2-3 раза посреди какого-нибудь длинного слова гномьего языка. Если чих получится в середине слога, то слово станет непонятным и его придется произносить заново. Поэтому для Чихуна важно знать, как слово делится на отдельные слоги. Основой слога в гномьем языке является непрерывная последовательность гласных букв, к которой слева и справа может примыкать 0 или более согласных. Если слог не является первым слогом слова, то к нему относится только согласная, стоящая непосредственно перед группой гласных. Остальные согласные перед слогом относятся к предыдущему слогу слова. Гласными буквами являются буквы 'a', 'e', 'i', 'o' и 'u', согласными – все остальные. Буква 'h' не является самостоятельной согласной, она указывает на приглушение согласной, стоящей перед ней, или на то, что гласные произносятся раздельно (относятся к разным слогам). Буква 'h' не может стоять перед 'h', но может быть первой буквой слова. (На самом деле в гномьем языке гораздо больше букв, чем в латинском алфавите, но их нет даже в кодировке Unicode, поэтому задачу придется решать для транскрипции гномьих слов латинскими буквами).

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

Ввод содержит одно слово длиной не более 50 букв, состоящее из строчных латинских букв. Слово содержит как минимум одну гласную букву.

Вывести слово из входного файла, указав места разбиения слова на слоги с помощью символа '-'.

bundshaatur

bund-shaa-tur

aha

a-ha

Гном Тихоня нашел карту, где указано расположение знаменитой сокровищницы Казад Дума. Чтобы попасть в сокровищницу, нужно переставить специальным образом валуны в комнате перед сокровищницей, тогда дверь в нее откроется. Квадратная комната разбита на клетки одинакового размера. В каждой клетке может находиться один валун, который можно перекатить в соседнюю по вертикали или горизонтали свободную клетку. Все валуны одинаковы и взаимозаменяемы. Тихоне известно текущее расположение валунов в комнате и расположение этих валунов для открытия двери. Он хочет переставить валуны как можно быстрее, чтобы успеть попасть в сокровищницу до появления Барлога. Напишите программу, определяющую минимальное число действий для открытия двери (одно действие  – это перекатывание валуна в соседнюю свободную клетку).

Первая строка содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 4`) – размер стороны комнаты. Далее следует 2*`N` строк, содержащих по `N` символов '.' и '@'. Первые `N` строк содержат текущее расположение валунов, остальные – расположение валунов, при котором дверь в сокровищницу открывается. Символ '.' обозначает пустую клетку, символ '@' – клетку с валуном.

Вывести одно целое число – минимальное число перекатываний.

2
.@
@.
@.
.@

2

Гном Весельчак любит решать головоломки. Одна из его любимых головоломок имеет форму квадратной коробки, в которой лежат монеты разного диаметра из драгоценных металлов. Цель головоломки – протащить одну из монет по дну коробки, не коснувшись стенок коробки и других монет, в заданное конечное положение. Нельзя двигать другие монеты, кроме заданной.

Напишите программу, которая определяет, сможет ли Весельчак решить головоломку.

В первой строке ввода содержатся четыре целых числа – размер коробки `R` (`10\ ≤\ R\ ≤\ 1000`), количество монет `N` (`1\ ≤\ N\ ≤\ 20`) и координаты точки `X` и `Y` (`0\ <\ X,\ Y\ <\ R`), в которую должен попасть центр двигаемой монеты. Далее следует `N` строк, в каждой строке содержатся три целых числа – координаты центра `i`-ой монеты `X_i` и `Y_i` (`0\ <\ X_i,\ Y_i\ <\ R`) и ее диаметр `D_i` (`1\ ≤\ D_i\ <\ 100`). В начальном положении ни одна из монет не касается стен коробки или других монет. Двигать нужно первую монету. Левый нижний угол коробки имеет координаты (0,0).

Вывести сообщение "Yes", если головоломку можно решить, или сообщение "No", в противном случае.

100 1 10 10
90 10 16

Yes

Шахту гномов окружает забор. Время от времени на одного из гномов находит вдохновение, тогда он берет краску и начинает красить забор в свой любимый цвет. Часто вдохновение быстро заканчивается, и забор остается недокрашенным.

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

Первая строка ввода содержит два целых числа `N` (`1\ ≤\ N\ ≤\ 10^5`) и `M` (`1\ ≤\ M\ ≤\ 10^5`) – количество досок в заборе и количество попыток покрасить забор. Далее следует `M` строк, каждая строка содержит сначала букву от 'A' до 'G' – цвет любимой краски гнома, затем два целых числа `i` и `j` (`1\ ≤\ i\ ≤\ j\ ≤\ N`) – номер доски, с которой гном начал красить забор, и номер доски, на которой он закончил.

Вывести строку из `N` символов – цвет каждой доски забора. Неокрашенные доски обозначить символом '.'.

5 2
A 2 4
E 3 5

.AEEE