Компания Macrohard выпустила новую версию своего редактора Nottoobad, который понимает некоторые голосовые команды. К сожалению, этих команд всего две - "повторить последнее слово" и "стереть последний символ". Причем при исполнении команды "повторить последнее слово" редактор автоматически вставляет пробел, который разделяет слова.
Однако компания утверждает, что с помощью этого редактора можно набирать текст, нажимая клавиши на клавиатуре гораздо реже. Например, чтобы набрать фразу "this thin thing" достаточно нажать на клавиши на клавиатуре всего 6 раз:
Поскольку Вы собираетесь участвовать в конкурсе, и у Вас есть знакомый в компании, который сообщил Вам по секрету набор слов, которые надо будет набрать, то неплохо бы написать программу, которая найдет порядок набора слов, при котором количество нажатий на клавиши будет минимальным.
В первой строке входных данных задано число \(N\) (1 <= \(N\) <= 100) – количество слов, которые предстоит набрать. Следующие \(N\) строк содержат слова – последовательности маленьких латинских букв, не длиннее 100 символов. Помните, что первое слово необходимо набрать первым!
Выведите в первой строке число – минимальное количество нажатий на клавиши, которое придется совершить, чтобы набрать все указанные слова в редакторе Nottoobad. На следующих строках выведите слова в том порядке, в котором их следует набирать для достижения этого количества нажатий. Если решений несколько, выведите любое из них.
1 lonelyword
10 lonelyword
2 a b
2 a b
2 abcdefg abcdefg
7 abcdefg abcdefg
В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно \(K\) различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.
Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием \(K\). А символы в конце - это конечно же нули - ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с 5!=1·2·3·4·5 . А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 - так что у предположения профессора есть разумные основания!
Теперь ученым срочно нужна программа, которая по заданным числам \(N\) и \(K\) найдет количество нулей в конце записи в системе счисления с основанием \(K\) числа \(N\)!=1·2·3·...·(\(N\)-1)·\(N\), чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!
В первой строке входных данных содержатся числа \(N\) и \(K\), разделенные пробелом, (1 <= \(N\) <= \(10^9\), 2 <= \(K\) <= 1000).
Выведите число \(X\) - количество нулей в конце записи числа \(N\)! в системе счисления с основанием \(K\).
5 10
1
1 2
0
100 10
24
1000 10
249
Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером \(X\)×\(Y\) метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось \(N\) круглых колонн, снести которые не представляется возможным.
Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.
В первой строке входных данных содержатся вещественные числа \(X\) и \(Y\), 1 <= \(X\), \(Y\) <= \(10^4\) . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), (\(X\), 0), (\(X\), \(Y\)) и (0, \(Y\)).
Во второй строке задается число \(N\) (0 <= \(N\) <= 10) - количество колонн. Следующие \(N\) строк содержат параметры колонн - \(i\)-я строка содержит три вещественных числа \(X_i\), \(Y_i\) и \(R_i\) - координаты центра и радиус \(i\)-й колонны (\(R_i\) <= \(X_i\) <= \(X\)-\(R_i\), \(R_i\) <= \(Y_i\) <= \(Y\)-\(R_i\), 0.1 <= \(R_i\) <= min(\(X\) / 2, \(Y\) / 2); для любых \(i\) ≠ \(j\) sqrt( (\(X_i\) - \(X_j\))2 + (\(Y_i\) - \(Y_j\))2 )>= \(R_i\) + \(R_j\)). Все вводимые числа разделены пробелами.
Выведите три вещественных числа: \(X_F\), \(Y_F\) и \(R_F\) - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.
10 10 0
5.000 5.000 5.000
1 1000 0
0.500 0.500 0.500
10 10 4 1 1 1 9 9 1 1 9 1 9 1 1
5.000 5.000 4.657
Организаторы детского праздника планируют надуть для него \(M\) воздушных шариков. С этой целью они пригласили \(N\) добровольных помощников, \(i\)-й среди которых надувает шарик за \(T_i\) минут, однако каждый раз после надувания \(Z_i\) шариков устает и отдыхает \(Y_i\) минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).
В первой строке входных данных задаются числа \(M\) и \(N\) (0 <= \(M\) <= 15000, 1 <= \(N\) <= 1000). Следующие \(N\) строк содержат по три целых числа - \(T_i\), \(Z_i\) и \(Y_i\) соответственно (1 <= \(T_i\), \(Y_i\) <= 100, 1 <= \(Z_i\) <= 1000).
Выведите в первой строке число \(T\) - время, за которое будут надуты все шарики. Во второй строке выведите \(N\) чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.
2 2 1 1 1 1 1 1
1 1 1
3 2 2 2 5 1 1 10
4 2 1
Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1×1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника
M×N метров.
Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных
клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным.
Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!
В первой строке входных данных содержатся два положительных целых числа, разделенных пробелом: \(M\) и \(N\) (1 <= \(M\)·\(N\) <= 30).
Выведите единственное число - количество различных симпатичных узоров, которые можно выложить во дворе размера \(M\)×\(N\) . Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.
1 2
4
4 1
16