e-olymp 1124. Алфавитное граффити

Задача

Граффити — один из видов современной варварской живописи. Вася, как и надлежит достойному потомку варваров, решил также заняться этим довольно перспективным с его точки зрения делом и увековечить свое пребывание в школе надписями в стиле граффити.
Так как по рисованию у Васи была твердая «двойка», а он начал еще и изучать английский, после изучения довольно тяжело давшейся ему в произношении третьей буквы английского алфавита он решил увековечивать свои муки в изучении этого опять трудного для него предмета отображением каждого этапа, связанного с изучением очередной буквы, соответствующей надписью на школьной стене.
Художественные изыскания Васи после изучения $3$-й и $7$-й букв приведены в примере выходных данных.
Так как с каждым этапом сделать правильную надпись Васе становилось всё трудней и трудней, напишите программу, которая поможет ему сделать шпаргалку для нанесения очередного узора.

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

Единственное число $N (3 ≤ N ≤ 26) -$ количество изученных букв английского алфавита.

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

Надпись на стене, сделанная Васей после изучения $N$ букв английского алфавита.

Объяснение:

Точками в примере обозначены пробелы для удобства подсчета, так как и с математикой, соответственно, у Васи тоже были проблемы… 🙂

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 3 a..a
a.ab
aabc
2 7 a……a
a…..ab
a….abc
a…abcd
a..abcde
a.abcdef
aabcdefg

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

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

Решение задачи

В каждой строке сначала выводим букву $a$. В первой строке выводим $n-1$ количество пробелов и строку $s$, которая содержит изначально
букву $a$. При переходе на новые строки к строке $s$ будем добавлять новую букву, которая идёт следующей в алфавите от последней буквы данной строки. В каждых последующих строках выводим на один пробел меньше и строку $s$. Выводим новые строки, чтобы в итоге вывести последнюю букву под номером $n$ в алфавите.

Ссылки

e-olymp 8569. Длина строки

Задача

Задана строка. Найдите ее длину.

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

Одна строка, содержащая не более 100 символов.

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

В первой строке выведите входную строку. Во второй строке выведите ее длину.

Тесты

Вход Выход
Deus Vult! Ave Nikita! Deus Vult! Ave Nikita!
22
Vive La France Vive La France
14
Benjamin Franklin could not read. Benjamin Franklin could not read.
33
Evolution Theory           False! Evolution Theory           False!
39
Programming Principles 1 Programming Principles 1
24

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

C-String

String

Решение

Формулировка задачи сама по себе диктует решение. Вводим строку, а после считаем длину.

Ссылки

e-olymp

ideone(cstring)

ideone(string)

 

e-olymp 1114. Символьные узоры на ткани

velaskes

Задача

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

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

В единой строке входного файла задано сначала символ узора S, затем через пробелы [latex]3[/latex] натуральных числа: ширина узора [latex]w[/latex] [latex](w < 80)[/latex], его высота [latex]h[/latex] [latex](h <= 40)[/latex] и повторяемость [latex]t[/latex] [latex](t <= 40)[/latex]. В примере выходных данных пробелы для наглядности заменены на точки.

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

Вывести требуемый узор.

Тесты

Ввод Вывод
1 W 7 9 1 WWWWWWW
.W.W.W.W
..WWWWWWW
…W.W.W.W
….WWWWWWW
…W.W.W.W
..WWWWWWW
.W.W.W.W
WWWWWWW
2 E 9 6 2 EEEEEEEEE
.E.E.E.E.E
..EEEEEEEEE
..E.E.E.E.E
.EEEEEEEEE
E.E.E.E.E
.EEEEEEEEE
..E.E.E.E.E
..EEEEEEEEE
.E.E.E.E.E
EEEEEEEEE
3 D 2 2 2 DD
D
DD
4 N 9 6 3 NNNNNNNNN
.N.N.N.N.N
..NNNNNNNNN
..N.N.N.N.N
.NNNNNNNNN
N.N.N.N.N
.NNNNNNNNN
.N.N.N.N.N
..NNNNNNNNN
.N.N.N.N.N
NNNNNNNNN
.N.N.N.N.N
..NNNNNNNNN
..N.N.N.N.N
.NNNNNNNNN
N.N.N.N.N
5 K 7 11 2 KKKKKKK
.K.K.K.K
..KKKKKKK
…K.K.K.K
….KKKKKKK
…..K.K.K.K
….KKKKKKK
…K.K.K.K
..KKKKKKK
.K.K.K.K
KKKKKKK
.K.K.K.K
..KKKKKKK
…K.K.K.K
….KKKKKKK
…..K.K.K.K
….KKKKKKK
…K.K.K.K
..KKKKKKK
.K.K.K.K
KKKKKKK

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

Решение

Считываем все входные данные. Создаём строку из [latex]w[/latex] символов, идущих подряд — из неё и пробелов будет состоять каждая нечётная строка. Далее заводим 3 переменные: times, num и flag. Предназначение каждой описано в комментариях в коде решения. После в цикле необходимо вывести узор, чередуя строки, в которых символы идут подряд и с пробелами. Перед каждой подстрокой с символами выводится подстрока с пробелами tmp. Число пробелов регулируется уже упомянутыми переменными num и flag. От нулевой строки до середины flag имеет значение true и num увеличивается с каждым проходом цикла на единицу, с середины до нуля — наоборот. При этом для того, чтобы узор с чётной высотой не шел полностью «ёлочкой» создаём условие, при котором по достижению середины количество дважды уменьшится.

Ссылки

e-olymp 8570. Длина слов

Задан текст — последовательность слов. Найдите длину каждого слова.

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

Текст содержит последовательность слов. Длина каждого слова не более $20$.

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

Для каждого слова в одной строке выведите его длину.

Тесты

Ввод Вывод
1 Programming Principles 1 11 10 1
2 I like C
very
much
1 4 1 4 4
3 12345678901234567890 20
4 ;-\ <cstring> 3 9
5 5^2-7*4/2 = 11 9 1 2
6 Veeeeeeery bIg LeTteR! 10 3 7
7 1,               25.
10!
2 3 3

Решение

Считываем в потоке и выводим длину каждого слова через пробел.

Код через строки string

Код через строки c-string

e-olymp 8571. Подсчитать буквы

Задача

Задана строка s и буква c. Сколько раз буква встречается в строке?

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

Первая строка содержит строку s с не более чем $100$ символами. Вторая строка содержит прописную букву латинского алфавита c.

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

Выведите сколько раз буква c встречается в строке s. Одна и та же заглавная и прописная буква считаются одинаковыми. То есть « и « считаются одинаковыми буквами.

Тесты

Programming Principles 1
p
3
This is a cat sitting on a tablet 5
Some english text 
e
3
sSstring
s
3
Another SoME eNGliSh tExT
e
4
abcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacac
b
18
abcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacac
a
36
aAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAab
a
70

Решение  через string

Решение  через Null-terminated String

 

Объяснение

Сначала считывается строка, затем, интересующая буква. Потом посматриваем каждый символ строки, и если он совпадает с нужной буквой (Код символа «A» в ASCII—  65, «a»—97. Соответственно, разница между символами прописной и заглавной латинской буквы— $32$ (в ASCII буквы английского алфавита идут по порядку), и символ отличающийся на $32$ от искомого— его заглавная версия, и нужно его учитывать), увеличиваем счётчик $k$. Затем, выводим результат.

e-olymp

ideone (string)

ideone (null-terminated string)

e-olymp 4844. Поиск общей подстроки

Задача взята с сайта e-olymp.

Задача

Дана строка [latex] A = [/latex] [latex] a_1a_2…a_n  [/latex] и строка [latex] B = [/latex] [latex] b_1b_2…b_m  [/latex]. Также дано число [latex] L [/latex].

Нужно узнать, есть ли у строк [latex] A [/latex] и [latex] B [/latex] общая подстрока длиной [latex] L [/latex].

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

В первых двух строках записаны строки [latex]A[/latex] и [latex]B[/latex], состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более [latex]100000[/latex] символов. В третьей строке записано целое число [latex]L   (0 \leq L \leq 100000) [/latex] — длина общей подстроки.

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

В выходной файл выведите [latex]YES[/latex], если существует общая подстрока такой длины. В противном случае выведите [latex]NO[/latex].

Тесты

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

1

saaa

baaa

3

YES

2

raabc

taaac

3

NO

3

aaaaaaaka

akaa

3

YES

4

abcdfeg

qwertycdfeg

10

NO

Код

Решение

Суффиксный автомат

Создадим структуру struct state, которая будет хранить информацию о переходах. len — это длина строки (далее будем использовать, как длину строки в каком-то состоянии), link — это суффиксальная ссылка, список переходов будем хранить в контейнере map <char, int> next, где ключом будет выступать символ, а значением — номер состояния.. Сам суффиксный автомат будем хранить в массиве этой структуры. Заведем переменные last и  sz, отвечающие за последнее состояние и номер нового состояния соответственно.

Нам потребуется функция инициализирующая суффиксный автомат sa_init(). Так как вначале состояние лишь одно, то его длина равна [latex]0[/latex], а суффиксную ссылку приравняем к [latex]-1[/latex].

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

Поиск наибольшей общей подстроки

Сначала для строки a  построим суффиксный автомат. Заведем две переменные, благодаря которым найдем совпадающую часть двух строк. Для этого нужна переменная, отвечающая за состояние v и переменная, отвечающая за длину совпадающей части l. Если есть переход, то переходим и увеличиваем длину на 1. Если нету, то уменьшаем длину совпадающей подстроки и переходим в новое состояние, меняя l. Цикл будет работать до тех пор, пока не найдем переход. Однако, если по суффиксным ссылкам мы дошли до состояния, в которое ведет ссылка изначальной вершины, то символ не встретился. Теперь длина наибольшей общей подстроки bestpos — это максимум из всех значений l.

Ссылки

ideone

e-olymp

E-Olymp 8377. Стойкое число


Задача

По числу $x$ определим $p(x)$ как произведение его цифр. Рассмотрим последовательность $x$, $p(x)$, $p(p(x))$… Стойкостью $x$ назовем индекс (начиная с $0$) первого однозначного числа в этой последовательности. Например, из $99$ получим последовательность $99$, $9 · 9 = 81$, $8 ·  1 = 8$. Стойкость числа $99$ равна $2$. По заданному числу $n$ определите его стойкость.

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

Каждая строка содержит одно целое число $n (0 \leqslant n \leqslant 2 · 10^9)$.

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

Для каждого значения $n$ выведите в отдельной строке его стойкость.

Решение

Опишем функцию $p(x)$, которая будет считать произведение цифр числа $x$. Для этого в функции заводим дополнительную переменную, например, $t$, равную единице, которую будем циклично домножать на остаток от деления $x$ на $10$, а $x$ уменьшать на разряд до тех пор, пока $x$ не попадёт в разряд единиц. Получившееся значение $t$ снова передаём в функцию $p(x)$ в качестве аргумента. Продолжим действия, описанные выше, до тех пор пока значение $t$ не будет находиться в разряде единиц. Индекс последней итерации функции и будет искомой стойкостью числа $x$.

Тесты

Ввод Вывод
1 99
268
6
2
4
0
2 796
1
100
5
0
1
3 2356951
53
9892
2
2
3

Код

Код для считывания строками

Код c-string

 

Ссылки

Continue reading

e-olymp 4843. Равные подстроки

Задача

Дана строка $S = s_1 s_2 s_3\cdots s_n$и множество запросов вида $(l_1, r_1, l_2, r_2)$.

Для каждого запроса требуется ответить, равны ли подстроки $s_{l1} … s_{r1}$ и $s_{l2} \cdots s_{r2}$.

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

В первой строке записана строка $S$, состоящая из строчных латинских букв. Эта строка непустая и имеет длину не более $100000$ символов. Во второй строке записано целое число $q (1 \leq q \leq 50000)$ — количество запросов. В каждой из следующих $q$ строк записаны числа $l_1, r_1, l_2, r_2 (1\leq l_1 \leq r_1 \leq |S|; 1\leq l_2 \leq r_2 \leq |S|)$.

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

Для каждого запроса выведите «$+$», если соответствующие подстроки равны, и «$-$», в противном случае.

Тесты

Входные данные Выходные данные
1 abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7
++-+
2 qa
3
1 1 1 1
2 2 2 2
1 1 2 2
++-
3 barcarbank
3
2 3 5 6
1 2 7 8
1 3 7 9
++-
4 abbabdad
4
1 3 4 6
2 3 5 6
1 2 4 5
3 5 6 8
—++

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

Решение

Для решения задачи используется метод  substr(), возвращающий подстроку строки по индексу её начала и количеству букв, за ней последующих.

Ссылки

e-olymp
ideone

Proggy-Buggy 2018: Задача A. Шифр Цезаря

Задание

Багги мнит себя Гаем Юлием Цезарем и любит громогласно его цитировать при каждом удобном случае, выдавая мысли Цезаря за свои. Проги пошутил над Багги и зашифровал в стиле Цезаря список цитат, которыми пользуется Багги. Багги в панике. Если хотите, помогите ему расшифровать известную цитату :

UDMHUHCHUHBH

Напишите программу, которая для вышеприведенного шифртекста выводит соответствующий открытый текст.

Код

Решение

Шифр Цезаря так же известен как шифр сдвига. Каждая буква сдвигается в алфавите на константу влево или вправо по модулю длины алфавита . В нашем случае зашифрованное и расшифрованное сообщение будет состоять только из букв (в условии не сказано ничего про сам алфавит).

Ниже пример шифрования методом сдвига (в данном случае на 3 единицы вправо)

A заменяется на D
B заменяется на E
и так далее
Z заменяется на C

Нам остается только подобрать ключ. Простым перебором получаем что зашифрованное сообщение было получено сдвигом всех букв исходного сообщения на единицу влево.
Ну что еще сказать?
Пришёл, увидел, победил!
Veni, vidi, vici!

Анаграммы

Анаграммы

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

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

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

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

Тесты

Ввод Вывод
 

1

 

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

Код на ideone

e-olymp 662. Налог

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

«Курс валюты Зимбабве опустился накануне до рекордно низкого уровня — $1,2$ млрд. зимбабвийских долларов за один доллар США»
(Новости от $7.06.2009$)

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

Один из налогов на доходы составляет $1%.$ Напишите программу, которая по введенному числу $D$ (величине дохода гражданина) вычислит этот налог.

При этом применяются следующие правила округления:

  1. Если налог выражается целым числом, то он не округляется.
  2. Если налог выражается дробным числом, то он округляется в сторону большего целого (в пользу государства).

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

Вводится одно число $D$ (натуральное, $10^{5} \leqslant D < 10^{200}$) – величина дохода гражданина.

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

Выведите одно натуральное число – величину налога.

Continue reading

e-olymp 1611. Реверс подстроки

Задача

Дана строка $s$, в которой выделили подстроку, состоящую из символов с $i$-го по $j$-ый включительно (символы строки $s$ нумеруются с единицы) и поменяли местами $i$-ый символ с $j%-ым, %(i + 1)%-ый с %(j — 1)$-ым и так далее (конвертировали подстроку). Выведите строку $s$ после внесенных изменений.

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

В первой строке содержится строка $s$ длиной не более $1000$ символов, во второй — два числа $i$ и $j$ $\left (i \leqslant j \right).$

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

Выведите строку $s$ после внесенных изменений.

Тесты

Входные данные Выходные данные
$zbbg \\ 2 \; 3$ $zbbg$
$gaqipkajibk \\ 5 \; 6$ $gaqikpajibk$
$helloworld \\ 5 \; 7 $ $helloworld$
$rkdobnjfyy \\ 6 \; 3 $ $rkdobnjfyy$

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

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

Для решения задачи объявим массив, в котором будем хранить входную строку. Далее в цикле обращаем подстроку и выводим строку $s$ после внесенных изменений.

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

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

Для решения задачи вводим строку $s$. Далее в цикле конвертируем подстроку и выводим строку $s$ после внесенных изменений.

Ссылки

Условие задачи на e-olymp
Код решения на ideone(c-string)
Код решения на ideone(string)

e-olymp 1079. Удаление букв

Задача

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

Найдите максимально возможную длину полученного слова.

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

Каждый тест состоит из одной строки, содержащей два заданных слова, разделенных пробелом. Длина каждого слова от $1$ до $200$ символов. Всего имеется не более $10$ тестов.

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

Для каждого теста выведите максимально возможную длину полученных одинаковых слов (длину максимального слова, которое можно получить путем удаления некоторых букв). Если одинаковые слова получить невозможно, то выведите $0$.

Тесты

Входные данные Выходные данные
AAABBB ABABAB
AXYAAZ CCCXCCCYCCCZCC
4
3
AAAAA BBBBB 0
ABABA BCACB 3
STRING GNIRTS 1

String

C-String

Решение задачи

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

Ссылки

Условие задачи на сайте  E-Olymp
код задачи (string) на Ideone
код задачи (c-string) на Ideone
описание расстояния Левенштейна на Wikipedia

e-olymp 2371. Черный квадрат

Условие

Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.

Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.

На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.

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

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

Первая строка содержит четыре целых числа: $m$, $n$, $s$ и $k$ $ \left( 1 \leqslant m, n \leqslant 5000, 1 \leqslant s \leqslant \min \left( m, n \right), 1 \leqslant k \leqslant m \right) $.

Вторая строка содержит $n$ символов и описывает $k$-ую строку картины, ‘.’ означает белую клетку, ‘*’ означает черную клетку.

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

Если изображение может быть однозначно восстановлено, то следует вывести «Unique». Если существует несколько вариантов восстановления картины, то вывести «Ambiguous». Если ни одной соответствующей картины не существует, вывести «Impossible».

Тесты

Ввод Вывод
$3$ $4$ $2$ $3$
..**
Unique
$4$ $4$ $2$ $3$
*.*.
Impossible
$3$ $5$ $2$ $2$
.**.
Ambiguous
$2$ $8$ $1$ $2$
……*.
Unique

Код

String

C-string

Решение

Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов ‘*’. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:

  1. Спасенная из огня полоска не содержит звездочек. Тогда мы проверяем, может ли поместиться квадрат из звездочек хотя бы в одну из двух частей, на которые эта полоска делит картину. Если да, проверяем, однозначно ли определяем этот квадрат, или же имеется несколько вариантов его возможного расположения в них.
  2. Спасенная из огня полоска содержит звездочки. Тогда, если количество звездочек не совпадает с длиной стороны квадрата, то построить его невозможно, а иначе проверяем, однозначно ли определяем этот квадрат. Здесь необходимо аккуратно рассмотреть все «особенные» случаи, такие как квадрат, состоящий из одной звездочки, а также первая и последняя полоски картины. Очевидно, что в этих случаях расположение квадрата определяется единственным образом.

Если сравнивать, что выгоднее использовать в данной задаче для задания спасённой из огня полоски — строку или массив символов, — то использование строки способствует немного более быстрому решению задачи, чем массив символов; объём используемой памяти при этом не изменяется.

Ссылки

Условие на e-olymp.com
Код с использованием string на ideone.com
Код с использованием c-string на ideone.com

e-olymp 670. Поиск палиндромов

Задача

Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «madam», «bob».
Определите, сколько палиндромов заданной длины $K$ содержит заданная строка $S$.

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

В первой строке содержится целое число $K$ ($2 \leqslant K \leqslant 200$), а во второй – заданная строка $S$, состоящая только из латинских букв, причем большие и малые буквы различаются (т.е. «Bob» — не палиндром). Длина $S$ от $1$ до $30000$ символов.

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

В единственной строке должно находиться количество различных палиндромов длины $K$, содержащихся в $S$ (т.е. являющихся последовательностями подряд идущих символов в $S$) (различными считаются палиндромы, начинающиеся с разных позиций в $S$).

Тесты

Входные данные Выходные данные
$3$ $3$
$babcbab$
$1$ $5$
$abcde$
$4$ $0$
$aarreeds$
$5$ $3$
$aaaaaaa$
$3$ $0$
$CaccaC$

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

String

C-String

Решение задачи

Мы рассматриваем все подстроки строки $s$ длины $k$ и проверяем, является ли каждая подстрока палиндромом. В случае положительного ответа, увеличиваем счетчик. Проверка, является ли каждая подстрока палиндромом, выполняется следующим образом: мы ставим указатели на противоположные концы подстроки, далее сравниваем элементы на которые указывают указатели и если они равны, одновременно сдвигаем указатели на один к центру этой подстроки. Продолжаем этот процесс до тех пор, пока указатели не «встретятся». Если на каком то этапе элементы не равны, прекращаем процесс с отрицательным ответом для этой подстроки. Если же указатели «встретились», то эта подстрока является палиндромом.

Ссылки

Условие задачи на e-olymp
Код решения. String
Код решения. C-String

e-olymp 1607. Число в обратном порядке

Задача

Запишите целое неотрицательное число $n$ в обратном порядке.

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

Одно целое неотрицательное $64$-х разрядное число.

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

Выведите число в обратном порядке.

Тесты

Входные данные Выходные данные
$1234$ $4321$
$100$ $001$
$34567$ $76543$
$10983743$ $34738901$
$98352374234$ $43247325389$

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

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

Для решения задачи вводим строку. Узнаем ее длину с помощью функции s.length(), затем циклом выводим строку в обратном порядке. Задача решена.

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

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

Для решения задачи вводим входные данные в массив x[64]. При вводе считаем какое количество символов заполнилось в массив. Затем от этого числа( length) начинаем цикл, который выводит массив в обратном порядке. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(String)
Код решения на ideone.com(C-string)

e-olymp 3912. Реверс удавов

Задача

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

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

Первая строка содержит одно число $N (1 ≤ N ≤ 100000)$ – количество удавов. В следующих $N$ строках написаны имена удавов в том порядке, в котором они ползут. Имя удава – строчка, содержащая не более $10$ маленьких латинских букв.

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

Выведите единственную строку – название стаи после команды «Реверс».

Тесты

Входные данные Выходные  данные
3
abc
def
ghi
ghidefabc
3
zxcgh
i
db
dbizxcgh
4
mn
kjl
iu
ghj
ghjiukjlmn
8
kdh
jg
lqwoc
kfxvk
iduhx
nsh
s
kjwyv
kjwyvsnshiduhxkfxvklqwocjgkdh

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

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

Записываем каждого удава в одномерный массив  flock типа  string размера N, а затем выводим его, начиная с конца.

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

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

Записываем каждого удава в динамический массив  flock типа  char размера $N$ $\times$   boa_name_size, где  boa_name_size – это константа, размером в $11$ символов, которую определяем с помощью директивы #define в начале программы. Не $10$, а $11$ потому что в нуль-терминированных строках (c-string) последний символ – символ конца строки '\0'.
Далее выводим наш массив с последней строки до первой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com (string)
Решение задачи на ideone.com (c-string)

e-olymp 440. Подделка чека

Задача

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

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

Во входном файле в первой строке содержится одно целое положительное число не более чем из $100$ цифр.

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

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

Тесты

Входные данные Выходные данные
$123321$ $332121$
$7888778888878888788878878777887$ $8888878888788878887778878777887$
$1091$ $9100$
$26364$ $64263$
$98765$ $98765$

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

String

C-String

Решение задачи

Пусть заданы два числа: $a = \overline{a_1a_2 \ldots a_k},\ b = \overline{b_1b_2 \ldots b_k}$. Тогда $a > b \Leftrightarrow \exists i: \ \forall j < i \ a_j = b_j \ \wedge \ a_i = b_i$. Отсюда получаем необходимое условие получения максимального числа при перестановке в записи числа $a$ групп цифр $\overline{a_ia_{i+1} \ldots a_l}$ и $\overline{a_ja_{j+1} \ldots a_m} \ l<j$ местами: $i = \min_{1 < s < k} s: \ \exists t>s: \ a_t \gt a_s$. Если такое $i$ существует, то далее мы делаем перебор по всем возможным перестановкам, таким что первая группа чисел начинается с индекса $i$ и таким образом находим максимально возможное число. В противном случае данное число уже является максимальным.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp. String
Решение на e-olymp. C-String
Код решения на Ideone. String
Код решения на Ideone. C-String

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 333. Детская железная дорога-2

Задача

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

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

Сколько всего разных слов может быть в таком необычном «английском» словаре Витэка?

Тесты

Входные данные
Выходные данные
ALPHABET 35
AAAA 4
UNIVERSITY

54
ABABABABC

24

Код на C++

Код на Java

Решение

Казалось бы, задачу можно решить простым циклом. Ведь в 6-буквенном слове: 6 однобуквенных слов, 5 двубуквенных и т.д. Однако очевидной становится проблема повторения,причем не только повторений букв, но и повторений подстрок, что изрядно усложняет наше решение. Создадим вектор, состоящий из строк, куда мы будем добавлять все подстроки строки из входного потока. Отсортируем полученный вектор. Это нужно для того чтобы одинаковые элементы шли рядом с друг другом. Тогда мы можем использовать функцию unique(), которая удалит из вектора все повторяющиеся элементы, кроме одного. Для того, чтобы провести resize() вектора нам понадобится итератор, который мы приравняем к функции unique(). После resize() останется только вывести размер вектора и прибавить к нему единицу, так как само слово не является подстрокой.

Ссылки

1.Код на С++

2.Код на Java

3.Условие на e-olymp