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

Решение

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

Код через std::<string>

Код через std::<cstring>

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 1488. Шахматная головоломка

Задача

prb1488

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

В этот раз Борис задал Вове следующую головоломку: на шахматном поле размером $8 × 8$ клеток стоит одна шахматная фигура — конь. Необходимо расположить на поле еще две шахматные фигуры — ладью и слона, таким образом, чтобы они били коня, но не били друг друга, и конь не бил их. Так как Вова еще не очень силен в программировании, он попросил вас помочь ему с решением данной головоломки.

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

Ладья бьет те клетки, которые находятся на той же горизонтали или вертикали, что и она. Слон бьет те клетки, которые находятся на той же диагонали, что и он.

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

Первая строка входного файла содержит положение коня в следующем формате. Сначала буква от $a$ до $h$, обозначающая номер столбца в котором находится конь, потом цифра от $1$ до $8$, обозначающая номер строки.

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

В первую строку выведите положение ладьи в аналогичном формате, во вторую строку выведите положение слона.

Гарантируется, что требуемая расстановка всегда существует.

Тесты

Ввод Вывод
1 a1 a4
b2
2 h8 h5
g7
3 e5 d5
f6
4 c8 b8
d9
5 h6 e6
g7

Код

Решение

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

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

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

Остается только аккуратно прописать все  случаи.

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

Код для общего случая

Решение для общего случая

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

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

Ссылки

Задача 1488 на e-olymp

Код задачи на Ideone

Код для общего случая на Ideone

e-olymp 1119. Пирамида из символов

Задача

Вася хочет напечатать на принтере пирамиду из какого-то символа высоты $h$. Напишите программу, которая поможет ему в этом, не забывая, что программа должна быть «экономически выгодной», т.е печатать наименьшее количество символов.

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

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

В одной строке задан сначала символ, при помощи которого должна быть напечатана пирамида, а затем через пробел натуральное число, задающее высоту пирамиды $h (h ≤ 50)$.

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

В первой сроке выведите общее количество напечатанных «печатных» символов а ниже саму пирамиду.

Тесты

Входные данные Выходные данные
A 3 12
A
AAA
AAAAA
M 9 117
M
MMM
MMMMM
MMMMMMM
MMMMMMMMM
MMMMMMMMMMM
MMMMMMMMMMMMM
MMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMM

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

Решение

Для решения данной задачи потребуется выводить пробелы для отступов в каждой строке и заданный символ в виде пирамиды. Для этого напишем цикл, который будет перебирать строки. Для нахождения количества символов в пирамиде используем формулу: по арифметической прогрессии, где первый элемент это $1$, а каждый следующий больше предыдущего на $2$. В вывод пишется столько пробелов, сколько нужно для правильного расположения (с каждой следующей строчкой пробелов на $1$ меньше, в первой строке $b$ пробелов).

Ссылки

e-olymp
Ideone

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 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 7340. Поле-чудес

Задача

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

Вхідні дані

Слово записане великими англійськими буквами (не більше [latex]100[/latex] символів).

Вихідні дані

Відповідь до задачі.

Тести

Вхідні дані Вихідні дані
[latex]GOOGLE[/latex] [latex]4[/latex]
[latex]ALBUS[/latex] [latex]5[/latex]
[latex]OOO[/latex] [latex]1[/latex]

Код програми

Рішення завдання

Створимо місце для слова і прочитаємо його, далі використаємо функцію sort ( з бібліотеки algorithm
) для того, щоб однакові букви йшли поряд і заведемо змінну, спочатку рівну [latex]1[/latex], так як слово складається мінімум з однієї букви, і будемо збільшувати її на [latex]1[/latex], якщо зустрінеться нова буква.

Код програми з классом string

Рішення завдання

Створимо місце для слова і прочитаємо його, далі будемо перевіряти для кожної букви чи повторюється вона і якщо повторюється, то всі букви, окрім тої від якої перевіряємо, будемо видаляти. У кінці виведемо кількість елементів строки.

Код програми з множиною

Рішення завдання

Створимо місце і прочитаємо слово. Подалі кожну букву слова запишемо, як елемент множини [latex]і.[/latex] Так як множина автоматично видаляє всі однакові елементи, то відповіддю до завдання буде кількість елементів множини.

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

Код рішення з множиною на ideone.com.

Код рішення з классом string ideone.com.

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 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.

Ссылки

Chuck Norris

A task from codingame.com

Task

Binary with 0 and 1 is good, but binary with only 0, or almost, is even better! Originally, this is a concept designed by Chuck Norris to send so called unary messages.

Write a program that takes an incoming message as input and displays as output the message encoded using Chuck Norris’ method.

Here is the encoding principle:

  • The input message consists of ASCII characters (7-bit)
  • The encoded output message consists of blocks of 0
  • A block is separated from another block by a space
  • Two consecutive blocks are used to produce a series of same value bits (only 1 or 0 values):
    — First block: it is always 0 or 00. If it is 0, then the series contains 1, if not, it contains 0
    — Second block: the number of 0 in this block is the number of bits in the series

Input

Line 1: the message consisting of N ASCII characters (without carriage return)

Output

The encoded message

Tests

[su_table]

Input
Output
C 0 0 00 0000 0 00
CC 0 0 00 0000 0 000 00 0000 0 00
%

00 0 0 0 00 00 0 0 00 0 0 0
Hello

0 0 00 00 0 0 00 000 0 00 00 00 0 0 00 0 0 000 00 0 0 00 00 00 0 00 00 0 0 00 00 00 0 00 00 0 0 0000

[/su_table]

Code

Solution

First, we create a so called mask, which takes the symbol, transform it to a binary 7-bit number and return string. Then we add this string to another one, while transforming every symbol in the cin.  Then we create a loop, where we check either symbol is 0 or 1 and add them to another string in the right order according to the encoding principle. In order to escape mistakes with ‘1’ in the first loop, we create another loop, where we change all ‘1’ to ‘0’.

 

e-olymp 1075. Умножение многочленов

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

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

Вводится в символьной форме два многочлена от [latex]x[/latex] с целыми коэффициентами. Вывести их произведение в порядке убывания степеней — также в символьной форме. Степень исходных многочленов не более [latex]10[/latex], коэффициенты исходных многочленов по модулю не более [latex]{ 10 }^{ 4 }[/latex].

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

В двух строках находятся многочлены.

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

В единственной строке выводится многочлен.

Тесты

Входные данные Выходные данные
1 0
0
0
2 x+1
x-1
x^2-1
3 -5
x^2+x+x-2x^3
10x^3-5x^2-10x
3 x^10+2x^9+3x^8
-1
-x^10-2x^9-3x^8
4 x^10+2x^9+3x^8
0
0
5 x^10+5x^2
x^3-4x
x^13-4x^11+5x^5-20x^3

Решение с использованием класса string

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

Нажмите, чтобы выполнить его на ideone.com.

Описание

Сначала в функции main объявляются две строки a и b. В них водятся исходные два многочлена. Но в форме строк, особенно учитывая, что подобные слагаемые не всегда приведены, умножать многочлены не удобно. Потому объявляются три вектора: a_decomposed, b_decomposed
и c_decomposed. Первые два имеют размер [latex]11[/latex], поскольку в условии сказано, что многочлены могут быть от нулевой до десятой степени включительно. В них элемент с индексом [latex]i[/latex] равняется коэффициенту при слагаемом многочлена, в котором [latex]x[/latex] имеет степень [latex]i[/latex]. Они заполняются при помощи функции decompose. В ней при помощи функции analyze отдельно анализируется каждое слагаемое многочлена, и результат заносится в вектор. c_decomposed хранит коэффициенты многочлена, полученного умножением двух исходных. Значения его элементов вычисляются при помощи функции multiplicate. После в ходе работы функции compose многочлен в требуемой форме записывается в строку c. Далее, если её первым символом является [latex]+[/latex], он удаляется из строки. Наконец, если c — непустая строка, она выводится. Иначе выводится [latex]0[/latex].

Решение с использованием c-string

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

Нажмите, чтобы выполнить его на ideone.com.

Описание

Алгоритм решения тот же. Следует отметить: поскольку объекты типа char* «не знают» свою длину, и в силу других причин, в некоторых местах программы используются «магические числа». Однако они не взяты случайно, а продиктованы условием задачи (к примеру, тем, что максимальная степень исходных многочленов — [latex]10[/latex] и т.п.). Только подходящее значение переменной max_number_of_symbols было найдено эмпирически.

Решение на Java

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

Нажмите, чтобы выполнить его на ideone.com.

e-olimp 1310. Наибольший блок

Задача

Блоком строки [latex]S[/latex] в позиции [latex]i[/latex] назовём наибольшую подстроку [latex]S[/latex], которая начинается в позиции [latex]i[/latex] и совпадает с префиксом [latex]S[/latex]. Длину блока в позиции 0 считать равной нулю. Вычислить длину наибольшего блока заданной строки [latex]S[/latex].

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

Единственная строка [latex]S[/latex] [latex]\left(\left|S\right|\leq{10}^{6}\right)[/latex].

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

Длина наибольшего блока строки [latex]S[/latex].

Тесты 

 Входные данные  Выходные данные
abaabaab  5
aaaaa 4
aaabaab 2

Реализация 

Код на ideone.com

Засчитанное решение на e-olimp.com

Решение

Для решения данной задачи необходимо рассмотреть алгоритм эффективного вычисления [latex]Z[/latex]-функции. Создадим массив [latex]z[/latex], где [latex]i[/latex]-ый элемент  равен наибольшему числу символов, начиная с [latex]i[/latex]-ой позиции,  совпадающих с первыми символами заданной строки [latex]s[/latex]. Эффективность алгоритма состоит в том, что при вычислении очередного элемента массива [latex]z[/latex] мы будем использовать уже вычисленные ранее значения. Назовем отрезком совпадения подстроку, совпадающую с префиксом заданной строки. Тогда искомое значение [latex]z\left [ i \right ][/latex] — это длина самого длинного отрезка совпадения, начинающегося в позиции [latex]i[/latex]. Из всех найденных отрезков совпадения будем хранить тот, который оканчивается правее всего. Положим, что [latex]l[/latex] и [latex]r[/latex] — индексы начала и конца данного отрезка соответственно. Тогда при вычислении [latex]z\left [ i \right ][/latex] возможны две ситуации: [latex]i>r[/latex] и [latex]i\leq r[/latex]. В первом случае позиция  [latex]i[/latex] лежит за пределами проанализированной части строки . Тогда ищем значение [latex]Z[/latex]-функции перебором до тех пор, пока не дойдем до несовпадения или конца заданной строки. Стоит отметить, что если [latex]z\left [ i \right ]>0[/latex], следует изменить индексы отрезка совпадений. Во втором случае текущая позиция [latex]i[/latex] лежит внутри отрезка совпадений [latex]\left [ l,r \right ][/latex]. Так как подстроки [latex]s\left [ l\ldots r \right ][/latex] и [latex]s\left [ 0\ldots r-l \right ][/latex] совпадают, то в качестве значения [latex]z\left [ i \right ][/latex] можно взять значение [latex]z\left [ i-l \right ][/latex]. Однако, значение [latex]z\left [ i-l \right ][/latex] может быть слишком большим для данного блока (суффикс строки будет меньше, чем данное значение, чего быть не может). Следовательно, [latex]z\left [ i \right ][/latex]-ому элементу будем присваивать значение минимума из длины суффикса [latex]\left ( r-i+1 \right )[/latex] и [latex]z\left [ i-l \right ][/latex]. Далее используем вышеописанный перебор. В конечном итоге максимальный элемент массива — длина наибольшего блока заданной строки.

e-olymp 2163. Сообразим на троих!

Задача

К Василию приехали два его друга с отличной новостью: они выиграли в лотерею [latex]n[/latex] рублей. Поскольку лотерейный билет был получен на сдачу во время общей закупки в магазине, то его принадлежность определить не удалось. Было решено разделить выигрыш поровну. Василий хотел бы узнать, можно ли честно разделить выигрыш.

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

Одно натуральное число [latex]n[/latex], количество знаков которого не превышает 255.

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

Вывести «YES», если входное число делится на 3, и «NO» если не делится.

Код string

Тесты

Входные данные Выходные данные
1 33 YES
2 0 YES
3 1 NO
4 1234567890987654321 YES
5 12345678901 NO

Решение

Для начала вводим строку, где будет хранится наше число. Будем считать сумму цифр числа, т.к. число делится на 3, если сумма его цифр делится на 3. Для этого создаем переменную [latex]a[/latex] в которой будет хранится сумма цифр. Запускаем цикл от 0 до размера  строки (количество цифр в числе). В цикле суммируем цифры числа, отнимая от него код символа 0, т.к. в [latex]string[/latex] записывается не число, а его код его символа. Далее проверяем — если сумма цифр делится по модулю на 3, то выводим «YES», если нет — то «NO».

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

Ссылка на решение e-olymp.

Код c-string

Решение

Алгоритм решения такой же как и для [latex]string[/latex], только вместо библиотеки [latex]string[/latex] подключаем библиотеку [latex]cstring[/latex], немного изменяем ввод и используем функцию [latex]strlen()[/latex] вместо [latex]size()[/latex].

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

Ссылка на решение e-olymp.

e-olymp 506. Новый компилятор

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

Постановка задачи

Вам необходимо преобразовать множество старых программ для новой версии компилятора. Для этого необходимо заменить «->» на «.» везде, кроме комментариев. Комментарии в данном языке программирования начинаются с символов «//» и продолжаются до конца строки. Напишите программу, выполняющую такое преобразование.

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

Входной файл содержит от 1 до 500 строк длиной не более 50 символов с ASCII-кодами от 32 до 127 – текст программы, которую нужно преобразовать.

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

В выходной файл вывести преобразованный текст программы.

Тесты

Исходный текст программы Преобразованный текст программы

Реализация

Код на ideone.com

Засчитанное решение на e-olymp.com

Ход решения

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

 

e-olymp 1342. Периодические строки

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

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

Будем говорить, что символьная строка имеет период [latex]k[/latex], если она может быть образована путем объединения одной или нескольких одинаковых строк длиной [latex]k[/latex]. Например, строка «[latex]abcabcabcabc[/latex]» имеет период [latex]3[/latex], так как она может быть образована путём объединения [latex]4[/latex]-х строк «[latex]abc[/latex]». Она также имеет период [latex]6[/latex] (объединение двух строк «[latex]abcabc[/latex]») и [latex]12[/latex] (сама строка «[latex]abcabcabcabc[/latex]»).

Напишите программу определяющую наименьший период заданной строки.

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

В первой строке задано количество тестовых случаев [latex]N[/latex] во входных данных. Каждый тестовый случай размещен в отдельной строке и содержит не более [latex]80[/latex] символов без пробелов.

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

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

Тесты

Входные данные Выходные данные
2
HoHoHo
mama
2

2

2
abcdefg
abcabcabc
7

3

3
b
bbb
bbbbb
1

1

1

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

ideone.com

Засчитанное решение на e-olymp.com

Решение

Строка длины [latex]s[/latex] может быть образована подстрокой, длина которой не превышает половины длины строки. Следовательно, период лежит в промежутке [latex]\left [ 1;s/2 \right ][/latex], либо равен длине строки. Последовательно разбивая строку на подстроки длиной от [latex]1[/latex] до [latex]s/2[/latex], проверяем равны ли они между собой. Если такие подстроки не нашлись, то период равен длине строки.

e-olymp 185. Орки будущего

Условие

Задача взята с сайта e-olymp. Полное условие можно прочитать здесь.

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

В первой строке задано количество [latex]N[/latex] орков, участвующих в игрищах. Далее идет [latex]N[/latex] строк с речью соответствующего орка. Гарантируется, что речь каждого Орка находится в одной строке, и в игрищах принимает участие не менее одного и не более [latex]100[/latex] орков. Количество символов в каждой записанной речи орка не превышает [latex]1000[/latex] и не менее одного.

Из условия:

«…теперь в их алфавите в качестве гласных использовались только буквы «а», «o», «e», «u».»

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

«Самым «Годистым» орком считался тот из них, у кого это отношение было наименьшим, а в случае равенства этого показателя тот, у кого в произнесенной речи было больше сказано слов. Ваша задача – определить Орка года по заданному критерию.»

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

Единственное число – номер Орка, признанного Орком Года. В случае, если однозначно определить победителя невозможно, вывести   "O-o-o-rks...".

Решение

Напишем 2 функции: int countSyllables(char* speech), которая будет считать гласные (т.к. кол-во слогов всегда равно кол-ву гласных), и int countWords(char* speech), считающую кол-во слов. Для написания первой воспользуемся стандартной функцией strpbrk(), для второй — функцией strtok(). Для каждой считанной строки будем по очереди вызывать эти 2 функции и заносить полученные значения в соответствующие массивы syllables и words (вызывать будем именно в таком порядке, т.к. функция strtok() делает строку непригодной к дальнейшему использованию).

Далее, чтобы избежать работы с вещественными числами (что может привести к потере точности) будем сравнивать полученные результаты согласно требованиям, но вместо деления воспользуемся соотношением пропорции. Заведем переменную-флаг ambiguous, показывающую, однозначен ли победитель. В зависимости от ее значения, выведем номер победителя (переменная winner, по умолчанию победитель — первый орк) или строку "O-o-o-rks..."

Тесты

Входные данные Выходные данные
1 2
Hello, World!
Ok.
2
2  3
Ooh, hey there 😀
Hello, World of me!
Will be ambiguous???
 O-o-o-rks…
3  4
Some people like C!
Some say Java is better.
Heh, or maybe Python?
Who knows for sure?
 O-o-o-rks…
4  5
A Lannister always pays his debts.
Winter is coming…
Hear me roar!
King of the North!
Sherlock?
 1
5  8
O-o-o-rks…
Is not the same as…
O-o-o-rks!
or
O-o-orks…
…trust me,…
…when writing code, one must be extremely careful!
…beware!
 O-o-o-rks…

Код

Ссылки

Код на ideaone.

Засчитанное решение на e-olymp.