нина. Задание по информатике вар 2 — решения. Формат входных данных
 Скачать 0.65 Mb.
|
|
Многопрофильная олимпиада РТУ МИРЭА 2021/2022 Отборочный этап Информатика Вариант 2 Задание 1. Ваня любит играть с новыми числами. Он пишет большое число из его цифр составляет множество других чисел такой же длины. Необходимо написать программу, которая подсчитывает количество новых чисел. Формат входных данных Строка длиной N 0 < N < 1010 Формат выходных данных Необходимо вывести количество новых чисел Решение from collections import Counter import math N = list(input()) N_set = set(N) c = Counter(N) f_fac =1 for i in N_set: f_fac = f_fac * math.factorial(c[i]) print(int(math.factorial(len(N))/f_fac)-1) Многопрофильная олимпиада РТУ МИРЭА 2021/2022 Отборочный этап Информатика Вариант 2 Задание 2. Ваня вдохновился машиной Тьюринга и создал ее аналог. Его машина умеет складывать два неотрицательных числа A и B. Число A написано на ленте машины, а число B хранится в буфере. В процессе сложения машина анализирует содержимое ленты и буфера и вместо числа A формирует на ленте сумму чисел A и B. У машины есть головка, которая считывает числа с ленты. В один момент времени, головка может считать только одну цифру с ленты. В начальный момент времени на ленте записано число A, а головка находится над некоторой заданной цифрой числа A. Цифры на ленте нумеруют справа налево, начиная с 1. У машины есть три команды: "move" - передвинуться на одну цифру вправо, если головка стоит над последней цифрой, то команда перенесет головку в начало числа; "+" - изменить цифру, над которой находится в данный момент на следующую (9 заменяется на 0); "0" - добавить дополнительный ноль слева от числа на ленте. Команду можно использовать только тогда, когда головка находится над крайней левой цифрой. Головка перемещается налево и устанавливает значение ноль. Необходимо написать программу, которая формирует минимально возможную последовательность команд для машины Вани, после выполнения которой на ленте окажется число A+B. Формат входных данных В первой строке содержится число, напечатанное на ленте (длиной не более 250 знаков). Вторая строка содержит число (длиной не более 250 знаков), которое нужно прибавить к числу, записанному на ленте. Третья строка – позиция головки. Формат выходных данных Вывести последовательность команд. Команды разделены пробелом. Если последовательность команд написать невозможно, нужно вывести единственное сообщение "No solution". Решение import sys a = input() b = input() position = int(input()) Многопрофильная олимпиада РТУ МИРЭА 2021/2022 Отборочный этап Информатика Вариант 2 if (len(a) > 250 or len(b) > 250 or position > len(a)): print("No solution") sys.exit(0) position *= -1 ab = list(map(int, list(str(int(a) + int(b))))) a = list(map(int, list(a))) b = int(b) answer = [] def check(): global ab, a if (len(ab) != len(a)): return False for i in range(len(a)): if (a[i] != ab[i]): return False return True while(not check()): if (a[position] != ab[position]): if (a[position] == 9): a[position] = 0 else: a[position] += 1 answer.append("+") continue if (position == (len(a) * -1) and len(ab) > len(a)): a.insert(0, 0) position -= 1 answer.append("0") continue if (position == -1): position = (len(a) * -1) else: position += 1 answer.append("move") Многопрофильная олимпиада РТУ МИРЭА 2021/2022 Отборочный этап Информатика Вариант 2 print(" ".join(answer)) Задание 3. Мальчики Ваня и Петя играют в игру. Есть набор символов задача каждого мальчика получить наибольшее количество способов превращения этого набора символов в палиндром. Выиграет тот, кто найдет наибольшее количество способов. Помогите мальчикам определить победителя. Необходимо написать программу, с помощью которой можно определить, сколько существует способов вычеркивания из заданного слова некоторого (возможно пустого) набора символов, чтобы образованная таким образом строка являлась палиндромом. Способы, отличающиеся порядком вычеркивания символов, считаются одинаковыми Формат входных данных В первой и единственной строке записано слово длиной N 0 < N < 60 Формат выходных данных Необходимо вывести число способов превращения строки в палиндром. Решение import math s = input() n = len(s) dp = [[-1 for i in range(n)] for i in range(n)] def f(i, j): global dp, s if (i > j): return 0 if (i == j): dp[i][j] = 1 return dp[i][j] if (dp[i][j] != -1): return dp[i][j] if (s[i] == s[j]): dp[i][j] = f(i+1, j) + f(i, j-1) + 1 else: dp[i][j] = f(i+1, j) + f(i, j-1) - f(i+1, j-1) Многопрофильная олимпиада РТУ МИРЭА 2021/2022 Отборочный этап Информатика Вариант 2 return dp[i][j] if (len(set(s)) == 1) or (s[:math.floor(len(s)/2)] == s[math.ceil(len(s)/2):]): print('0') else: print(f(0, n-1)) Задание 4. В былые времена существовала следующая забава. В N стопок раскладывают одинаковые предметы (например, камушки или монеты). Стопки располагают перед собой в ряд слева направо. За тем два человека делают по очереди ходы. На каждом ходе один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Необходимо написать программу, позволяющую вычислить, какое максимальное число монет может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет. Формат входных данных Первым задается число стопок N, на следующей строке идут N чисел, задающих количество предметов в стопках слева направо (количество предметов в стопке — не менее 1 и не более 20000) разделены одним пробелом, а затем число стопок K , которое можно взять первым ходом. 0 < N <= 180 0 < K <= 80 Формат выходных данных Необходимо вывести одно число — максимальное количество предметов, которое заведомо может получить первый игрок, как бы ни играл второй. Решение #include #include #include Многопрофильная олимпиада РТУ МИРЭА 2021/2022 Отборочный этап Информатика Вариант 2 int solution(vector } int ans = 0; if(arr.size() - l <= k){ for(int i = l; i < arr.size(); i++){ ans += arr[i]; } if(p == 2){ sum[l][k][p] = 0; return sum[l][k][p]; } sum[l][k][p] = ans; return sum[l][k][p]; } if(p == 1){ int temp = 0; for(int i = 1; i <= k; i++){ temp += arr[(l-1) + i]; ans = max(ans, temp + solution(arr, l+i, i, 3-p)); } sum[l][k][p] = ans; return sum[l][k][p]; } else{ int ans = INT_MAX; for(int i = 1; i <= k; i++){ ans = min(ans, solution(arr, l+i, i, 3-p)); } sum[l][k][p] = ans; return sum[l][k][p]; } } int main() { int n, k, a; vector Многопрофильная олимпиада РТУ МИРЭА 2021/2022 Отборочный этап Информатика Вариант 2 cin >> n; for(int i = 0; i > a; coins.push_back(a); } cin >> k; cout << solution(coins, 0, k, 1); return 0; } |