e-olymp 1078. The line degree

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

Условие

Обозначим через $a*b$ конкатенацию строк $a$ и $b$.

Например, если $a = «abc»$ и $b = «def»$, то $a*b = «abcdef»$.

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

$a^0 = «»$ (пустая строка)
$a^{n+1} = a*a^n$

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

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

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

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

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

Тесты:

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

Код на Haxe:

Ход решения:

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

Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения $size/i$ будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, следовательно, её степень равна $1$.

Ссылки:

Оригинальное решение: cpp.mazurok.com.
Рабочий код для тестирования на try.haxe.org: Try Haxe !

e-olymp 2162. Палиндром

Ссылка на оригинальную статью

Ссылка на рабочий код

Ссылка на e-olymp

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

Входные данные
Дана строка [latex]S[/latex], [latex]|S| \leq 255[/latex], состоящая из строчных латинских букв и пробелов. Под [latex]|S|[/latex] подразумевается длина строки

Выходные данные
Вывести «Yes», если текст является палиндромом, и «No», если не является.

Тесты

Входные данные Выходные данные
a roza upala na lapu azora Yes
my gym Yes
palindrom No
character No

Код

Решение
Со входного потока считываем строку. Так как пробелы не должны учитываться, то легче будет работать со строкой без пробелов. Поэтому, пользуясь пространством имен StringTools, заменим все вхождения пробелов на пустые строки (инчае говоря, удалим все пробелы). Флаг ok в конце будет использован для вывода соответствующего сообщения. В цикле поочередно проверяем на равенство противоположные элементы строки. В случае единого несовпадения устанавливаем флаг в false и останавливаем цикл. Выводим сообщение в выходной поток.

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

Ссылка на оригинальную статью

Ссылка на Try Haxe!

Ссылка на e-olymp

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

Входные данные
Одно натуральное число $n$, количество знаков которого не превышает 255.

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

Тесты

Входные данные Выходные данные
33 Yes
0 Yes
1 No
1234567890987654321 Yes
12345678901 No

Код

Решение

Для начала вводим строку, где будет хранится наше число. Будем считать сумму цифр числа, т.к. число делится на 3, если сумма его цифр делится на 3. Для этого создаем переменную $sum$, в которой будет хранится сумма цифр. Запускаем цикл от 0 до размера  строки (количество цифр в числе). В цикле суммируем цифры числа, преобразуя каждый символ в Int с помощью функции parseInt. Далее проверяем — если сумма цифр делится по модулю на 3, то выводим «Yes», если нет — то «No».

AA1

Ссылка на оригинальную статью.

Ссылка на решение задачи на сайте Try Haxe!

Условие:

В заданной строке заменить подряд идущие пробелы на один пробел.

Тесты

Ввод Вывод Комментарий
as  fg   t as fg t Пройден
   rty g  uio  rty g uio Пройден

Решение:

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

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