e-olymp 2197. Антипалиндром

Антипалиндром

Условие задачи:

Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите её наибольшую по длине подстроку, не являющуюся палиндромом.

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

Выходные данные
В выходной файл выведите ответ на задачу, если ответов несколько — выберите лексикографически минимальный. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.

Тесты

Входные данные Выходные данные
1
abba abb
2
aaaaaaa NO SOLUTION
3
abcghgcba abcghgcb
4
abaaabbb abaaabbb

Код на языке C++:

 

Код на языке Java:

Решение задачи:
Сперва необходимо проверить, является ли строка множеством одинаковых символов. В этом случае найти подстроку, не являющуюся палиндромом, не представляется возможным. Затем проверим, является ли входная строка палиндромом. Если нет, выведем исходную строку. Иначе необходимо вывести подстроку без первого или последнего символа (в зависимости от лексикографического порядка строки).

Условие задачи на e-olymp
Засчитанная задача на e-olymp: на языке C++
Засчитанная задача на e-olymp: на языке Java
Код задачи на C++: Ideone
Код задачи на Java: Ideone

e-olymp 6128. Простой дек

Сабиров Ильдар
Сабиров Ильдар

Latest posts by Сабиров Ильдар (see all)

Задача. Простой дек

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back 

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front
  • pop_back
  • front
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

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

 push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

 ok

ok

2

ok

ok

1

ok

1

2

1

1

0

bye

 2  size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

0

ok

ok

2

4

8

ok

4

8

3

8

bye

Решение

Алгоритм решения

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

 

e-olymp 7447. Обрезка строки

Задача с сайта e-olymp.com.

Условие задачи

Имеется строка [latex]s[/latex]. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.

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

Содержит строку [latex]s[/latex] ([latex]1 ≤[/latex] длина[latex]\left( s \right) [/latex] [latex]≤ 100)[/latex].

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

Вывести наименьшее количество символов, которое следует удалить сначала.

Тесты

Входные данные Выходные данные
1 abbcddka 2
2 ABBA 0
3 abcde 5
4 abbac 1

Код на C++

Код на Java

Описание

Идея решения состоит в том, чтобы разбить строку на меньшие по длине подстроки и найти ответ на задачу для каждой из них. Для хранения строки используется переменная s, а ответы на подзадачи содержатся в двумерном массиве целых чисел answers. В answers[i][j] находится ответ для подстроки с i-ого по j-й символ включительно. В функции main сначала вводится строка s. Далее ширина и глубина массива answers устанавливаются равными длине s. После этого он заполняется начальными значениями. Значение [latex]-1[/latex] означает, что ответ для этой ячейки ещё не был найден. Однако очевидно, что если строка состоит ровно из одного символа, согласно условию задачи, его придётся удалить, значит, главную диагональ можно сразу заполнить единицами. Затем происходит вызов рекурсивной функции calculate, принимающей индексы левой и правой границ целевой подстроки. Первый раз она вызывается для всей строки от первого до последнего символа. Работает эта функция следующим образом: если индекс левой границы отрезка больше индекса правой, что, в случае данной задачи, не имеет смысла, она возвращает ноль. Иначе она возвращает ответ на задачу для данной подстроки, а если этого не делалось ранее, то предварительно находит его. Происходит это так: сначала значение ответа устанавливается равным длине подстроки, поскольку в худшем случае необходимо будет удалить её всю целиком. Если символы на концах подстроки одинаковые, они, как сказано в условии, будут удалены в дальнейшем, потому нужно рассматривать минимум из текущего значения ответа и ответа для подстроки без крайних символов. Однако может оказаться, что выгоднее удалить символы из каких-то двух меньших подстрок, потому далее в цикле рассматриваются все возможные комбинации двух подстрок, из которых можно составить конкатенацией текущую. В итоге получаем ответ на задачу для данной подстроки.

Код на ideone.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.

e-olymp 1078. Степень строки

Задача

Обозначим через [latex]a \cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a =[/latex]«abc» и [latex]b =[/latex]«def» то [latex]a \cdot b =[/latex]«abcdef».

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:
[latex]a^{0} =[/latex]«» (пустая строка)
[latex]a^{n+1} = a \cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s = a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s[/latex] = [latex]a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные Выходные данные
abcabc
gcdgcd
gcgcgc
gggggg
hhhh
2
2
3
6
4
BbbbBbbbBbbb
dogdogdog
aaaaaaaa
cstring
3
3
8
1

Код программы (c-string)

Решение задачи (c-string)

Из условия следует, что степень строки определяется максимальным числом одинаковых подстрок. В таком случае степень строки является одним из делителей длины этой строки, и очевидно, что максимальная степень строки будет обратно пропорциональна максимальной длине подстроки.

Для решения поставленной задачи используем функцию cstringpow, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной size (с использованием счётчика i в цикле), в которую было предварительно была сохранена длина строки, полученная функцией strlen. Числа, которые будут получатся из выражения size/i, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.
Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем, используя функцию strncmp, сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения size/i будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, а следовательно её степень равна [latex]1[/latex].

Код программы (string)

Решение задачи (string)

Решение задачи с использованием класса string аналогично. Единственное отличие — замена функций strlen и strncmp, предназначенных для работы с c-string, на эквивалентные им методы класса string size и compare.

Ссылки

e-olymp 131. Слова

Задача
Из слова «молоко» можно составить слово «коло». Сколько слов из заданного словаря можно составить, используя буквы заданного слова, причем каждую букву можно использовать не более одного раза.

Тесты

Входные данные Выходные данные
молоко
4
мило
коло
коліно
око
2
приветствие
8
ветер
треск
спирт
трепет
перерыв
север
текст
привести
5

Код программы

Решение
Создаем вектор [latex]D[/latex], в котором будем хранить количество каждого символа в слове, и обнуляем его. Тип [latex]char[/latex] вмещает максимум [latex]256[/latex] значений (в диапазоне от [latex]-127[/latex] до [latex]126[/latex]). Класс [latex]string[/latex] состоит из символов типа [latex]char[/latex], поэтому для того, чтобы «вернуть» значения этих символов к положительным (в чём возникает необходимость при обращении к элементам вектора), к ним прибавляется [latex]127[/latex].
Потом считаем число каждого символа в слове. Создаем переменную, в которой будем хранить число слов из словаря, которое можно составить, используя символ первого входного слова. Предполагаем, что слово [latex]words[/latex] составить можно ([latex]words=true[/latex]). Считаем использованные символы из первой входной строки и, если вдруг число стало отрицательным, то слово составить нельзя, обнуляем переменную [latex]words[/latex] и останавливаем цикл. К переменной [latex]rez[/latex] прибавляем переменную [latex]words[/latex] и выводим [latex]rez[/latex].

Ссылки
Код на ideone.com
Задача с сайта e-olymp.com.
Засчитанное решение.

e-olymp 6128. Простой дек

Задача

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

<strong>exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит [latex]100[/latex]. Все операции:

pop_front,
pop_back,
front,
back
всегда корректны.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример входных данных.

Тесты

Входные данные Выходные данные
push_back 3
push_front 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit
ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye

Код программы

Решение

Считываем строки из входного потока в случае с size, back, front, pop_front, pop_back и clear просто выводим и вызываем соответствующие функции. А в случае с push_front и push_back мы вызываем ввод для функции. В exit вызываем функцию [latex]return[/latex] [latex]0[/latex] для остановки программы.

Ссылки

Ideone;
e-olymp.