MS9. Шифрование символов

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

Входные данные
Последовательность символов.

Выходные данные
Зашифрованная последовательность символов, напечатанная через пробел.

Тесты

входные данные выходные данные
the five boxing wizards jump quickly.

t 292 306 165 236 312 341 320 165 228 320 351 330 325 316 167 270 329 349 316 325 314 330 179 244 340 335 333 176 258 347 327 303 313 323 350 213
pack my box with five dozen liquor jugs

p 274 295 313 171 250 351 185 228 320 351 184 270 329 337 324 168 236 312 341 320 165 232 322 355 324 321 174 248 318 331 347 339 339 178 244 340 323 333
.!+= ;::—_//»‘ @#%

. 112 119 165 125 150 175 174 148 135 235 189 141 115 112 103 96 160 134 109

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

Решение задачи
Объявляем 2 символьные переменные. Считываем первый символ и выводим его. Остальные символы будут считываться в цикле, пока не произойдет переход на следующую строку.По мере ввода запоминаем старый символ во 2 переменной и выводим посредством простого уравнения [latex] \left |2\cdot a + b\right | [/latex].

Ссылки

A 325. Простые делители числа

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные выходные данные
2 2
7 7
50 2 5 5
169 13 13
583 11 53
2368 2 2 2 2 2 2 37
73890 2 3 3 5 821
885066 2 3 7 13 1621
6943960340 2 2 5 97 1787 2003

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

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

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.

Ссылки

MS2. Сумма чисел во входном потоке

Условие

Сосчитайте сумму чисел во входном потоке.

Тесты

Ввод
Вывод
1 2 3 4 5 6 21
12 13 14 39
1-100

5050

Решение

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

Код на ideone

MS17. Самосинхронизирующийся скремблер

Задача

Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера. Начальное значение и обратные связи скремблера должны быть заданы в программе значениями двух переменных типа unsigned char. Как расшифровать полученный код.

Примечание: разобьём данную нам задачу на две подзадачи. В первой будет рассмотрено скремблирование входных данных, а во второй будет проведено дескремблирование исходных данных первой подзадачи.

Подзадача 1

Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера.

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

Некая символьная последовательность.

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

Зашифрованная символьная последовательность.

Тесты

Входные данные Выходные данные
Dogs eat meat. ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa
Scramble it! fc 5a 80 ef 75 43 1e 92 9b 46 57 6
Base, base, it’s cheeseburger 1. Can you hear me? ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed 1b d5 af 3f ad 19 e2 ba 78 93 db 18 f0 9c 2c c0 fe 33 21 75 40 2c c0 b2 f2 ad 58 bb 68 81 ed 1c ba 78 cb

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

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

Для зашифровки будем использовать стандартный алгоритм скремблирования. Скремблером будет переменная key, которая изначально равна [latex]5[/latex]. Выбирать из скремблера будем нулевой и четвёртый биты. Входные данные будут поступать в переменную input, после чего на них и на скремблере будет применяться функция scram.
Так как входные данные имеют формат unsigned char, считывание не прекратится никогда вплоть до принудительной остановки программы, ведь любые входные данные могут быть восприняты как символы. Для предотвращения этого, необходим символ, который будет служить «сигналом» для остановки программы. В нашем случае, это будет символ перехода на следующую строку.
Основная проблема задачи заключается в выводе зашифрованных данных, так как в результате скремблирования некоторые символы могут оказаться не отображаемыми. Дабы избежать подобной ситуации, зашифрованные данные будем выводить в шестнадцатеричном числовом формате.

Подзадача 2

Расшифровать входные данные из предыдущей подзадачи.

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

Некие зашифрованные данные, записанные в виде последовательности чисел шестнадцатеричного формата.

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

Расшифрованные данные.

Тесты

Входные данные Выходные данные
ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa Dogs eat meat.
fc 5a 80 ef 75 43 1e 92 9b 46 57 6 Scramble it!
ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed 1b d5 af 3f ad 19 e2 ba 78 93 db 18 f0 9c 2c c0 fe 33 21 75 40 2c c0 b2 f2 ad 58 bb 68 81 ed 1c ba 78 cb Base, base, it’s cheeseburger 1. Can you hear me?

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

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

Для расшифровки будем применять обратный алгоритм к использованному в предыдущей задаче. Значение необходимого для расшифровки дескремблера нам известно из предыдущей задачи (а именно — [latex]5[/latex]), поэтому его мы и используем.
Входные данные будут считываться методом cin, где параметр hex будет указывать на то, что данные поданы в шестнадцатеричном формате. После считывания на входных данных будет применяться алгоритм дескремблирования, и итоговые данные будут выведены на экран.

Ссылки

D2631. Сумма ряда с заданной точностью

Задача

Найти количество членов ряда, требуемых для получения значения  [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] с точностью до [latex]\varepsilon [/latex], а также найти само значение суммы с заданной точностью.

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

Точность [latex]\varepsilon [/latex].

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

Количество членов ряда [latex]n[/latex].
Значение суммы [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex].

Тесты

 №  Входные данные  Выходные данные
 [latex]\varepsilon[/latex]  [latex]n[/latex]  [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex]
 1  0.01  98  4.74785
 2  1e-7  4188  5.71199
 3  1e-9  8900  5.71208
 4  1  1  0.367879

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

Решение

Докажем, что ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] сходится. Обозначим общий член данного ряда [latex]x_n[/latex]. Поскольку все члены ряда положительны, воспользуемся предельным признаком сравнения рядов. Для сравнения возьмём сходящийся ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ \frac { 1 }{ { n }^{ 2 } } } [/latex], общий член которого обозначим [latex]b_n[/latex]: [latex]\lim\limits_{ n\rightarrow \infty }{ \frac { x_n }{ b_n } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ n }^{ 2 } }=K[/latex], тогда данный ряд сходится, если [latex]0<K<\infty [/latex], либо [latex]K=0[/latex].
[latex]\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ n }^{ 2 } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ e }^{ {2}{\ln { \left( n \right)} } } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n }+{ {2}{\ln { \left( n \right)} } } }}={ e }^{ -\infty }=0 [/latex].
[latex]K=0[/latex], а значит ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] сходится и значение суммы является конечным числом. Тогда для сколь угодно малого [latex]\varepsilon >0[/latex] найдётся номер, начиная с которого каждый последующий член ряда меньше [latex]\varepsilon[/latex]

Ссылки