---> 121 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 7 8 9 10 11 12 13 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется перевернуть слова, состоящие из латинских букв, не трогая остальные.

Дан текст, состоящий из слов, знаков препинания и других символов. Словом в тексте считается последовательность символов из прописных и строчных букв латинского алфавита. Требуется перевернуть (записать в обратном порядке) все слова текста, оставив знаки препинания и другие символы, включая буквы русского алфавита, без изменений. В строке не более 255 символов, строк в файле не более 1000.

Примеры
Входные данные
Thisisveryveryverylongword
Выходные данные
drowgnolyrevyrevyrevsisihT
Входные данные
This test is very! easy and short.
But it's  ,. mo:re difficult than first.
Выходные данные
sihT tset si yrev! ysae dna trohs.
tuB ti's  ,. om:er tluciffid naht tsrif.
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
3 megabytes

Про строку известно, что некоторые её подстроки равны между собой. Восстановите исходную строку.

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

В первой строке содержатся два натуральных числа \(N\) и \(M\) (1 \(\le\) \(N\), \(M\) \(\le\) \(10^5\)) — длина строки и количество пар подстрок, равенство которых известно.

В следующих \(M\) строках содержатся три натуральных числа \(a_i\), \(b_i\) и \(l_i\) (1 \(\le\) \(a_i\) \(\le\) \(b_i\) \(\le\) \(N\), 1 \(\le\) \(l_i\) \(\le\) \(N\) − \(b_i\) + 1), означающие, что в исходной строке равны подстроки длины \(l_i\), начинающиеся в символах с номерами \(a_i\) и \(b_i\).

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

Выведите \(N\) строчных латинских букв — любую строку, удовлетворяющую указанным требованиям. Если решения не существует, выведите строку «No solution».

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

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

У Василисы в сундуке хранятся грамоты с древними заклинаниями. Она втайне была в учении у самой Бабы-Яги, поэтому знает, что, чтобы творить волшебство, нужно произнести заклинание, да такое, в котором скрыто содержится нужное волшебное слово. Но достаточно ли сильны заклинания, хранящиеся в сундуке?

Вот что Василиса Премудрая узнала от Бабы-Яги:

Вхождение слова в заклинание — это подпоследовательность букв заклинания, совпадающая со словом. Буквы слова могут идти не подряд, но должны быть расположены в том же порядке. К примеру, заклинания «cadabra» и «barabara» содержат слово «abra», а заклинание «raba» — не содержит.

Вхождение называют скрытым, если никакие две его буквы не идут подряд. Например, в заклинание «abuba» слово «aua» входит скрыто, так как буквы вхождения (первая, третья и пятая) идут не подряд, а через одну. В заклинание «bauab» слово «aua», напротив, входит не скрыто.

Силой заклинания относительно волшебного слова считается количество скрытых вхождений в него этого волшебного слова. Например, волшебное слово «az» в заклинание «abazaba» входит два раза, но только один раз — скрыто, поэтому сила его равна единице.

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

Зная заклинание и волшебное слово, посчитайте силу этого заклинания относительно данного волшебного слова.

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

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

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

В первой строке выходного файла выведите одно число — силу заклинания относительно данного волшебного слова.

Пояснения к примерам

В первом примере волшебное слово «az» входит в заклинание скрыто всего один раз: «a» соответствует первой букве заклинания, а «z» — четвёртой. Другое вхождение волшебного слова, в котором «a» соответствует третьей букве, а «z» — четвёртой, не является скрытым, так как соседние буквы волшебного слова расположены в заклинании рядом.

Во втором примере две буквы «i» могут поместиться, только если они соответствуют четвёртой и шестой буквам заклинания; буква «e», которая должна стоять перед ними, может соответствовать первой или второй букве заклинания.

Примеры
Входные данные
abazaba
az
Выходные данные
1
Входные данные
eeeiiieee
eii
Выходные данные
2
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Миша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив чёрно-белого изображения.

Бинарное чёрно-белое изображение — это прямоугольник, состоящий из пикселей, каждый из которых может быть либо чёрным, либо белым. Негатив такого изображения получается путём замены каждого чёрного пикселя на белый, а каждого белого пикселя — на чёрный.

Миша, как начинающий программист, написал свою программу с ошибкой, поэтому в результате её исполнения мог получаться некорректный негатив. Для того чтобы оценить уровень несоответствия получаемого негатива исходному изображению, Миша начал тестировать свою программу.

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

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

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

Первая строка входного файла содержит целые числа \(n\) и \(m\) (\(1\le n,m\le100\)) — высоту и ширину исходного изображения (в пикселях).

Последующие \(n\) строк содержат описание исходного изображения. Каждая строка состоит из \(m\) символов «B» и «W». Символ «B» соответствует чёрному пикселю, а символ «W» — белому.

Далее следует пустая строка, а после неё — описание выведенного Мишиной программой изображения в том же формате, что и исходное изображение.

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

В выходной файл необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.

Примеры
Входные данные
3 4
WBBW
BBBB
WBBW

BWWW
WWWB
BWWB
Выходные данные
2
Входные данные
2 2
BW
BB

WW
BW
Выходные данные
2
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

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

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером \(1\times1\times L\), на одной из сторон которого есть место для рекламы — пространство размера \(1\times L\), в которое можно вписать ровно \(L\) букв латинского алфавита.

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

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

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

После того, как некоторое число \(K\) блоков, каждый из которых имеет длину \(L\), поставили друг на друга, получилась прямоугольная таблица размером \(K\times L\), в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображённом на рисунке, в результате этого процесса получилась бы строка «TOEIIZENITKN». Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока «TOEIIZENITKN».

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

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

Первая строка входного файла содержит два натуральных числа \(N\) и \(L\) — число различных типов блоков на складе и длина каждого блока соответственно (\(1\le N\le100\), \(1\le L\le100\)). Последующие \(N\) строк содержат по одной записи длиной \(L\), состоящей из строчных латинских букв — надписи на блоках соответствующего типа. Надписи на блоках разных типов не совпадают.

Последняя строка входного файла содержит новую рекламную надпись \(s\) — строку, состоящую только из строчных латинских букв (\(1\le|s|\le200\)). Можно считать, что на складе находится неограниченное число блоков каждого типа.

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

В первой строке выходного файла необходимо вывести натуральное число \(K\) — минимальное количество блоков, которое нужно использовать для составления новой рекламы. Следующая строка должна содержать \(K\) чисел — номера типов блоков, которые нужно для этого использовать, перечисляя их сверху вниз. Типы блоков нумеруются с единицы в порядке их задания во входном файле.

Если ответов несколько, выведите любой из них. Если решения не существует, выведите в выходной файл число \(-1\).

Примеры
Входные данные
3 4
tiet
oink
ezin
zenit
Выходные данные
3
1 2 3
Входные данные
2 11
sillysample
happysample
sam
Выходные данные
1
2
Входные данные
2 3
baa
aab
bb
Выходные данные
2
2 2
Входные данные
2 3
aaa
bbb
cc
Выходные данные
-1

Страница: << 7 8 9 10 11 12 13 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест