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

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

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

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

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