Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 191 192 193 194 195 196 197 >> Отображать по:
#1315
Шифр
  
Темы: [Строки]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дана символьная строка S длины N (0 N 100) и словарь, который содержит M слов (0 M 100), длина каждого из которых не превышает N. Строка и слова состоят из символов a, b, …, z.

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

Строка в примере после вычеркивания лишних букв f и t примет вид abachdsya (было сделано два вычеркивания: abafchtdsya), и может быть представлена как последвательность следующих слов: a, bach, dsy, a.

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

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

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

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

Примеры
Входные данные
11 5
abafchtdsya
aba
a
bach
dsy
zero
Выходные данные
2
#1316
Школы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Во взвешенном графе необходимо найти два минимальных остовных дерева.

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

Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником “Майбуття”, либо с одной из тех школ, которые имеют надежное электроснабжение.

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

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

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

В первой строке входного файла находятся два натуральных числа, разделенных пробелом:N (3 ≤ N ≤ 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci – стоимость прокладки линии электроснабжения (1 ≤ Ci ≤ 300) от школы Ai до школы Bi (i=1,2,…,N).

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

В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом – две наименьшие стоимости схем (S1 ≤ S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.

Гарантируется, что для входных данных существует две различные схемы надёжного электроснабжения.

Примеры
Входные данные
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Выходные данные
110 121
#1317
Квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes
X1,Y1), (X2,Y2), (X3,Y3). Найти длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник так, чтобы все вершины треугольника находились внутри квадрата либо на его сторонах.

Составьте программу, которая по координатам вершин треугольника находит длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник. L достаточно найти с точностью 10-4.

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

Файл содержит в одной строке действительные числа X1 Y1 X2 Y2 X3 Y3, разделенные пробелами, – координаты вершин треугольника (-10000 X1, Y1, X2, Y2, X3, Y3 10000).

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

Файл должен содержать одно число - длину L стороны искомого квадрата.

Примеры
Входные данные
0.0 0.0 1.1 0.0 0.0 1.1
Выходные данные
1.100000000
#1323
Префикс-функция
  

Дана непустая строка S, длина которой N не превышает 106. Будем считать, что элементы строки нумеруются от 1 до N.

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

Значением префикс-функции π[i] будем считать длину этой подстроки.

Префикс-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск образца в тексте»).

Требуется для всех i от 1 до N вычислить π[i].

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

Одна строка длины N, 0 < N ≤ 106, состоящая из маленьких латинских букв.

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

Выведите N чисел — значения префикс-функции для каждой позиции, разделенные пробелом.

Примеры
Входные данные
abracadabra
Выходные данные
0 0 0 1 0 1 0 1 2 3 4
#1324
Z-функция
  
ограничение по времени на тест
10.0 second;
ограничение по памяти на тест
64 megabytes

Дана непустая строка s, длина которой N не превышает 106. Будем считать, что элементы строки нумеруются от 1 до N.

Для каждой позиции i символа в строке определим Z-блок как наибольшую подстроку, которая начинается в этой позиции и совпадает с некоторым началом всей строки s. Значением Z-функции Z(i) будем считать длину этого Z-блока. (Заметим, что для первой позиции строки  Z-блок совпадает со всей строкой, поэтому Z(1)=N. С другой стороны, если s[i]≠s[1], то Z(i)=0).

Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск по образцу»).

Требуется для всех i от 1 до N вычислить Z(i).

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

Одна строка длины N, 0 < N ≤ 106, состоящая из маленьких латинских букв.

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

N чисел, разделенные пробелами: Z(1), Z(2), ... Z(N)

Примеры
Входные данные
abracadabra
Выходные данные
11 0 0 1 0 1 0 4 0 0 1
Страница: << 191 192 193 194 195 196 197 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест