1. Алиса изучает списки в языке Python. По заданию из учебника она написала такую программу n = int(input()) x = [i%10 for i in range(n)] print(sum(x)) Эта программа читает с консоли натуральное число nn и делает список этой длины, состоящий из чисел от нуля до девяти, которые идут по кругу. Например, для n=25n=25 список будет иметь вид [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4] В последней строчке на экран выводится сумма элементов этого списка. Для указанного списка, в частности, будет выведено число 100. Боб очень недоволен учебником. Он считает, что учебник упускает главное — списки нужны для хранения информации, значимой для работы программы, а это задание можно выполнить как минимум без списков, а в идеале — без циклов и условий. Напишите программу для этого задания, которую Боб сочтет удовлетворительной. Для этого она должна быстро и корректно работать для чисел до 10151015. Формат входных данных На вход подается одно натуральное число nn, которое не превосходит 10151015. Формат выходных данных Программа должна вывести одно число — ответ, который напечатала бы приведенная выше программа, если бы она была способна работать со столь большими числами. Методика проверки Программа проверяется на 30 тестах. Прохождение каждого теста оценивается в 0.5 балла. Тесты из условия задачи при проверке не используются. Sample Input 1: 25 Sample Output 1: 100 Sample Input 2: 1000000000000000 Sample Output 2: 4500000000000000 2. Автокорреляционная функция часто применяется при анализе сигналов, например, энцефалограммы человека или в радиолокации. Мы будем рассматривать некоторый цифровой сигнал a0,a1,a2,…,an−1a0,a1,a2,…,an−1, где каждое значение aiai равно 11 или −1−1. Определим автокорреляционную функцию u(t)u(t) по следующей формуле u(t)=∑0≤i<n−taiai+tu(t)=0≤i<n−t∑aiai+t Другими словами, если сигнал задан в виде списка из nn значений, то чтобы вычислить автокорреляционную функцию в точке tt, требуется взять одну копию списка без первых tt элементов, другую копию списка без последних tt элементов, поэлементно перемножить эти списки и найти сумму произведений. Рассмотрим пример. Пусть сигнал содержит шесть элементов 1,1,−1,1,−1,11,1,−1,1,−1,1. Найдем u(2)u(2). Исходная последовательность без первых двух элементов имеет вид −1,1,−1,1−1,1,−1,1. Исходная последовательность без последних двух элементов имеет вид 1,1,−1,11,1,−1,1. Тогда u(2)=(−1⋅1)+(1⋅1)+(−1⋅−1)+(1⋅1)=2u(2)=(−1⋅1)+(1⋅1)+(−1⋅−1)+(1⋅1)=2 По такому же принципу можно посчитать и остальные значения для tt от нуля до пяти. u(0)=(1⋅1)+(1⋅1)+(−1⋅−1)+(1⋅1)+(−1⋅−1)+(1⋅1)=6u(0)=(1⋅1)+(1⋅1)+(−1⋅−1)+(1⋅1)+(−1⋅−1)+(1⋅1)=6 u(1)=(1⋅1)+(−1⋅1)+(1⋅−1)+(−1⋅1)+(1⋅−1)=−3u(1)=(1⋅1)+(−1⋅1)+(1⋅−1)+(−1⋅1)+(1⋅−1)=−3 u(3)=(1⋅1)+(−1⋅1)+(1⋅−1)=−1u(3)=(1⋅1)+(−1⋅1)+(1⋅−1)=−1 u(4)=(−1⋅1)+(1⋅1)=0u(4)=(−1⋅1)+(1⋅1)=0 u(5)=1⋅1=1u(5)=1⋅1=1 Напишите программу, которая по заданному дискретному сигналу найдет значения автокорреляционной функции для всех tt от 00 до n−1n−1. Формат входных данных На вход в первой строке подается одно натуральное число nn — длина сигнала, 1≤n≤1001≤n≤100. Во второй строке через пробел записаны числа a0,a1,…,an−1a0,a1,…,an−1, задающие дискретный сигнал. Каждое значение aiai равно 11 или −1−1. Формат выходных данных Программа должна вывести через пробел nn целых чисел — значения автокорреляционной функции u(0),u(1),…u(n−1)u(0),u(1),…u(n−1). Если вы программируете на Python, то убрать перенос строки в функции print можно при помощи именованного параметра end, например, print(a,end=' '). Методика проверки Программа проверяется на 21 тесте. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется. Sample Input: 6 1 1 -1 1 -1 1 Sample Output: 6 -3 2 -1 0 1 3. Алиса и Боб играют в следующую игру. Имеется игровое поле в виде последовательности клеток, расположенных друг за другом. На поле расположены три фишки, каждая фишка в своей клетке. За один ход каждый игрок должен переместить одну фишку вправо на произвольное ненулевое число клеток. При этом фишка, которой делается ход, не может встать в клетку, где расположена другая фишка или перепрыгнуть через нее. Выигрывает тот игрок, который смог сделать последний ход. Рассмотрим пример. Ссылка на изображение Здесь возможны следующие ходы: сместить правую фишку на одну клетку; сместить среднюю фишку на одну клетку; сместить левую фишку на одну, две, три или четыре клетки. Алиса всегда делает первый ход, а фишки расставляет Боб. Но Боб не хочет побеждать, он хочет, чтобы Алиса нашла выигрышную стратегию. Поэтому он расставляет фишки так, чтобы Алиса могла гарантированно выиграть. Например, в приведенной выше позиции Алиса должна сместить самую левую фишку на три клетки. Ссылка на изображение Далее игра зависит от хода Боба. Предположим, он сместит правую фишку на одну клетку. Тогда Алиса в свой ход сместит левую фишку на одну клетку. Ссылка на изображение Теперь Боб может ходить только средней фишкой. Если он сдвинет ее на одну клетку, то Алиса сдвинет левую фишку на одну клетку. Ссылка на изображение Бобу остается вновь ходить средней фишкой. Он сдвинет ее на одну клетку, Алиса сдвинет левую фишку на одну клетку и победит. Ссылка на изображение Для всех других ходов Боба у Алисы также всегда найдется ход, ведущий к победе. Вы должны написать программу, которая по заданной позиции найдет ход, после которого Алиса сможет победить независимо от дальнейшей игры Боба. Если выигрышных ходов будет несколько, то Алиса может сделать любой из них. Напомним, что исходная позиция будет такой, что найдется как минимум один ход, гарантированно ведущий к победе. Формат входных данных На вход подается строка представляющая игровое поле. Пустая клетка в строке обозначена нулем, клетка с фишкой обозначена единицей. Длина строки не превосходит 1000 символов. В строке ровно три единицы. Формат выходных данных Программа должна вывести строку, представляющую игровое поле после хода Алисы, в том же формате, в котором она поступает на вход. Методика проверки Программа проверяется на 32 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется. Sample Input: 0100001010 Sample Output: 0000101010 4. В денежной системе Бурляндии выпускаются банкноты всех номиналов от aa до 2a2a включительно. У Алисы в бумажнике есть ровно одна банкнота каждого номинала. Алиса хочет сделать покупку ценой bb и расплатиться без сдачи. Кроме того, Алиса хочет, чтобы количество потраченных банкнот было как можно меньшим. Напишите программу, которая поможет Алисе выбрать банкноты так, чтобы сумма их номиналов была равна bb, а их количество было наименьшим среди возможных. Если указанным условиям удовлетворяет несколько наборов банкнот, то ваша программа может вывести любой из них. Формат входных данных На вход в одной строке подается два натуральных числа aa и bb — минимальный из номиналов купюр и требуемая сумма, 1≤a≤1000001≤a≤100000. Гарантируется, что для заданной суммы bb существует способ получить ее из имеющихся купюр. Формат выходных данных Программа должна вывести в одной строке через пробел номиналы всех банкнот, которые потребуются для оплаты. Все номиналы должны быть упорядочены по возрастанию. Методика проверки Программа проверяется на 32 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется. Sample Input: 10 99 Sample Output: 10 15 17 18 19 20 Пояснение к примеру Сумма чисел, указанных в ответе равна 99, и все числа лежат в диапазоне от 10 до 20 включительно. При этом сумма номиналов пяти самых ценных банкнот меньше чем 99, поэтому оплатить указанную сумму пятью или меньшим числом банкнот невозможно. Однако другие варианты получения требуемой суммы шестью банкнотами возможны, например, 13 14 15 18 19 20. Такой ответ тоже будет засчитан.