Темы
    Информатика(2560 задач)
---> 8 задач <---
Страница: 1 2 >> Отображать по:
#583
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача A ]
Дан список слов, разрешено за 0 операций повторять предыдущее слово и удалять последний символ. Набор символа в конце слова занимает 1 операцию. Требуется набрать все слова в произвольном порядке (первое фиксировано) за наименьшее количество операций.

Компания Macrohard выпустила новую версию своего редактора Nottoobad, который понимает некоторые голосовые команды. К сожалению, этих команд всего две - "повторить последнее слово" и "стереть последний символ". Причем при исполнении команды "повторить последнее слово" редактор автоматически вставляет пробел, который разделяет слова.

Однако компания утверждает, что с помощью этого редактора можно набирать текст, нажимая клавиши на клавиатуре гораздо реже. Например, чтобы набрать фразу "this thin thing" достаточно нажать на клавиши на клавиатуре всего 6 раз:

Чтобы повысить популярность своего продукта, компания решила провести конкурс, победителем которого станет тот, кто сможет набрать заданный набор слов в редакторе за наименьшее количество нажатий на клавиши. Причем первое слово зафиксировано, а остальные могут быть набраны в произвольном порядке. То есть, если надо набрать слова "apple", "plum" и "apricote", то первым надо набрать "apple", а слова "plum" и "apricote" можно поменять местами.

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

Входные данные

В первой строке входных данных задано число $N$ (1 <= $N$ <= 100) – количество слов, которые предстоит набрать. Следующие $N$ строк содержат слова – последовательности маленьких латинских букв, не длиннее 100 символов. Помните, что первое слово необходимо набрать первым!

Выходные данные

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

Примеры
Входные данные
1
lonelyword
Выходные данные
10
lonelyword
Входные данные
2
a
b
Выходные данные
2
a
b
Входные данные
2
abcdefg
abcdefg
Выходные данные
7
abcdefg
abcdefg
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Необходимо подсчитать количество нулей в конце числа N!, записанного в K-ичной системе счисления.

В 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
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
В прямоугольном зале с круглыми колоннами (координаты и радиусы колонн заданы) необходимо разместить круглый фонтан максимального радиуса.

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером $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
Для N человек известно 3 параметра: время надувания шарика, сколько шариков можно надуть до отдыха и время отдыха. Требуется определить, за какое минимальное время эти люди надуют N шариков.

Организаторы детского праздника планируют надуть для него $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 
Прямоугольное поле заполнено белыми и черными клетками, требуется определить количество вариантов замощения поля таким образом, чтобы на нем не встречалось ни одного белого или черного квадрата 2 на 2.

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1×1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника M×N метров.

Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2×2 метра, полностью покрытого плитками одного цвета. На рисунке 1 показаны примеры различных симпатичных узоров, а на рисунке 2 - несимпатичных.

Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Входные данные

В первой строке входных данных содержатся два положительных целых числа, разделенных пробелом: $M$ и $N$ (1 <= $M$·$N$ <= 30).

Выходные данные

Выведите единственное число - количество различных симпатичных узоров, которые можно выложить во дворе размера $M$×$N$ . Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.

Примеры
Входные данные
1 2
Выходные данные
4
Входные данные
4 1
Выходные данные
16

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест