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.

e-olymp 1077. Java против C++

Задача. Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

Но сейчас нас интересует лишь небольшие отличия, а именно соглашения, которыми пользуются программисты при описании имен переменных в Java и C++. Известно, что для понимания значений переменных часто используют английские слова или даже целые предложения, описывающие суть переменных, содержащих те или иные значения. Приведем ниже правила описания переменных, которыми руководствуются программисты, реализующие программы на Java и C++.

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name,nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

Вам требуется написать программу, которая преобразует переменную, записанную на одном языке в формат другого языка.

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

Во входном файле задано наименование переменной длиной не более [latex]100[/latex] символов.

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

В выходной файл требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!«.

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

Тесты

Test Input Output
1 java_word javaWord
2 cppWorD cpp_wor_d
3 simpleword simpleword
4 two__underscores Error!
5 _underscore_in_the_beginning Error!
6 underscore_in_the_end_ Error!
7 UppercaseInTheBeginning Error!
8 mixed_Style Error!

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

 

Алгоритм

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

Для удобства я изобразила этот алгоритм в виде схемы:

MMMMEWWWWWW

*круговая стрелочка означает, что мы остаемся в этом же состоянии.

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

Когда мы считываем очередной символ, мы переходим в другое состояние либо остаемся в предыдущем. В состояние Error(отмечено красным) мы переходим, если считаем какую-любо последовательность символов, не подходящую ни под один из стандартов.

Отдельно следует поговорить о состоянии CPP delimeter. Оно используется для контроля количества подчеркиваний. Если в нашей предполагаемой С++ переменной встречается подчеркивание, ей сразу же присваивается данное состояние, чтобы, при наличии второго подчеркивания сразу же перевести ее в состояние Error in CPP.

Финальные состояния отмечены зеленым цветом. В них мы переходим только после окончания строки непосредственно из предыдущего состояния.  Переход в состояние Universal означает, что исходная строка состоит исключительно из маленьких букв и подходит как для языка Java, так и для C++.

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

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

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

e-olymp 2165. Лишние пробелы

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

  • он находится в самом начале строки, до самого первого слова;
  • он находится в конце строки, после самого последнего слова;
  • несколько пробелов расположены между двумя словами (проще говоря, если слова разделены более чем одним пробелом, тогда все пробелы кроме одного — лишние).

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

Дана строка [latex]s[/latex] (0 ≤ |S| ≤ 255). Строка содержит только латинские буквы и пробелы.

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

Требуется вывести строку без лишних пробелов.

Код

Код

Тесты

Ivanov     Maxim
Scott      Fitzgerald
Gertruda      Stal
John      Green

Решение

Первый код написан на string. Вводим строку [latex]s[/latex], которая содержит латинские буквы и пробелы. В цикле рассматриваем все символы строки от начала до конца. В условии после каждого следующего символа ставим пробелы, используем функцию erase, которая удаляет из строки лишние пробелы. Выводим строку.

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

Ideone.com

Ideone.com

 

А808а

Задача.
Дан текст. Группы символов, разделенные пробелами(одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как и прежде, словами.

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

Тесты

Input Output Комментарий
123 321 1441 123 456 831 1441

123 — 2

1441 -2

321 — 1

456 — 1

831 — 1

 Пройдено
iW@910 b10r l4e iW@910 10o b11 a mU611211a9

10o — 1

a — 1

b10r — 1

b11 — 1

iW@910 — 2

l4e — 1

mU611211a9 — 1

 Пройдено
№!4%» ^&*() +|\/., №!4%» _-=~`;? +|\/., — 1

^&*() — 1

_-=~`;? — 1

№!4%» — 2

Пройдено
Hey Jude, don’t make it bad.
Take a sad song and make it better.
Hey — 1

Jude, — 1

Take — 1

a — 1

and — 1

bad. — 1

better. — 1

don’t — 1

it — 2

make — 2

sad — 1

song — 1

Пройдено

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

 

Ход решения:

Применяя функцию [latex]map[/latex], запишем в индекс массива [latex]m[/latex] слово и увеличим элемент массива данного индекса на единицу. Используя цикл [latex]while[/latex] мы проделаем это для каждого слова введенного с клавиатуры. Если слово повторится , то элемент снова увеличится на единицу. Таким образом получаем количество слов в данном тексте.

С помощью цикла [latex]for[/latex] выводим индекс массива (т.е. слово) и значение (его количество в тексте).

Ссылка на код

e-olymp 1080. Анаграмматическое расстояние

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

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.

Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно [latex]6[/latex], так как нужно удалить все буквы (любое слово, в том числе и пустая строка, являются анаграммой само к себе).

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

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

В первой строке задано положительное целое число [latex]N[/latex] (не превышающее [latex]60000[/latex]), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего [latex]2N[/latex]последующих строк).

Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.

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

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

Ссылка на задачу находится здесь.

Тесты

Входные данные Выходные данные
1 4
crocus
succor
dares
seared
empty

smell
lemon

Case #1:  0
Case #2:  1
Case #3:  5
Case #4:  4
2 1

 

Case #1:  0
3 5
lol
lolipop
primate
mathematics
kangaroo
kilimanjaro
sister
sisters
android
andromeda
Case #1:  4
Case #2:  8
Case #3:  7
Case #4:  1
Case #5:  4

Код (cstring)