Question

Рассмотрим все строчки длины 100, состоящие из различных чисел от 1 до 200. Выпишем все эти строки в лексикографически возрастающем порядке. Пусть строка A написана на 102-м месте. Введите первое число строки A. Введите 99-е число строки A. Введите 100-е число строки A.

Answer 1

Для решения данной задачи нам нужно определить порядковый номер строки a в лексикографически упорядоченном списке всех строк длины 100, состоящих из различных чисел от 1 до 200.

Количество всех возможных строк длины 100, состоящих из разных чисел от 1 до 200, равно 200 * 199 * 198 * ... * 102. Это можно выразить следующим образом: 200!/100!.

Нам необходимо найти 102-е место строки a. Для этого нужно знать количество строк, расположенных до этой строки в лексикографически упорядоченном списке.

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

Таким образом, для нахождения искомого номера строки a, нужно вычислить следующую сумму:

(101 * 100 * 99 * ... * 3) + (100 * 99 * 98 * ... * 3) + (99 * 98 * 97 * ... * 3) + ... + (3 * 2 * 1 * 1)

Слева от каждого знака "+" указанное число обозначает количество строк, начинающихся с номера справа от этого знака "+" и соответствующей длины. Значение в скобках обозначает количество доступных чисел для выбора на каждой позиции в строке.

После нахождения номера строки a мы можем получить ее содержимое. Первое число строки a будет равно (a-1) / 100 + 1, где символ "/" обозначает целочисленное деление. Второе и третье числа строки a будут равны ((a-1) % 100 / 1) + 1 и ((a-1) % 100 / 2) + 1 соответственно.

например, 102-е место строки a имеет значение: первое число: (102-1) / 100 + 1 = 2, 99-е число: ((102-1) % 100 / 1) + 1 = 3, 100-е число: ((102-1) % 100 / 2) + 1 = 2