Предметный тур. Информатика. 3 этап
Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 1 с.
Ограничение по памяти: 64 Мбайт.
Имеются три гирьки одинаковые на вид, но, возможно, имеющие различную массу. Масса каждой из гирек может быть равна \(1\), \(2\), \(3\), \(5\) или \(10\) г. Обозначим массы гирек за \(x\), \(y\) и \(z\). Если положить первую и вторую гирьки на одну чашку электронных весов, то окажется, что их масса равна \(a\) г. Если аналогично взвесить первую и третью гирьки, то их масса будет равна \(b\) г. Формально это означает, что имеют место равенства \(x+y=a\) и \(x+z=b\).
Напишите программу, которая найдет любые возможные массы гирек \(x\), \(y\) и \(z\) по известным числам \(a\) и \(b\). Программа должна ответить на \(t\) независимых запросов во входных данных.
Формат входных данных
В первой строке на вход поступает одно целое число \(t\) — количество запросов, \(1\leqslant t\leqslant 100\).
Далее в \(t\) строках записаны сами запросы, по одному в каждой строке. Каждый запрос содержит два числа \(a\) и \(b\). Гарантируется, что эти числа таковы, что существует хотя бы один допустимый ответ.
Формат выходных данных
Выведите \(t\) строк с ответами на запросы. Каждый ответ должен содержать три натуральных числа \(x\), \(y\) и \(z\). Числа должны быть записаны в указанном порядке. Если возможно несколько ответов, то вывести можно один любой.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
3 7 6 20 20 6 4 |
5 2 1 10 10 10 1 5 3 |
Примечания
В третьем тестовом случае допустимы два правильных ответа: \((1, 5, 3)\) и \((3, 3, 1)\).
Наиболее простой способ решения этой задачи заключается в переборе всех возможных значений \(x\). По выбранному значению \(x\) найдем \(y\) и \(z\). Если найденные значения допустимы, то выводим ответ и прерываем цикл.
Пример программы-решения
Ниже представлено решение на языке Python.
t = int(input())
w = [10,5,3,2,1]
for _ in range(t):
a, b = map(int,input().split())
for x in w:
y = a - x
z = b - x
if y in w and z in w:
print(x,y,z)
breakТест с номером 1 совпадает с тестом из условия задачи. Баллы за него не начисляются.
Успешное прохождение каждого теста с номерами 2–11 оценивается в 1 балл.
Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 1 с.
Ограничение по памяти: 256 Мбайт.
В некоторых областях квантовых вычислений используется понятие произведения Кронекера двух матриц.
Если \[A=\left(\begin{array}{ccc} a_{11}&\cdots &a_{1n}\\ \vdots&\ddots &\vdots\\ a_{n1}&\cdots &a_{nn}\\ \end{array}\right),\qquad B=\left(\begin{array}{ccc} b_{11}&\cdots &b_{1m}\\ \vdots&\ddots &\vdots\\ b_{m1}&\cdots &b_{mm}\\ \end{array}\right),\] то их произведение Кронекера определяется как блоковая матрица следующего вида: \[A\otimes B = \left(\begin{array}{ccc} a_{11} B &\cdots &a_{1n} B\\ \vdots&\ddots &\vdots\\ a_{n1} B &\cdots &a_{nn} B\\ \end{array}\right).\]
Например, для \(A=\left(\begin{array}{cc} 1 & 2\\ 3 & 4\\ \end{array}\right)\) и \(B=\left(\begin{array}{cc} 5 & 6\\ 7 & 8\\ \end{array}\right)\) их произведение Кронекера будет равно: \[\left(\begin{array}{cc|cc} 1\cdot 5 & 1\cdot 6 & 2\cdot 5 & 2\cdot 6\\ 1\cdot 7 & 1\cdot 8 & 2\cdot 7 & 2\cdot 8\\\hline 3\cdot 5 & 3\cdot 6 & 4\cdot 5 & 4\cdot 6\\ 3\cdot 7 & 3\cdot 8 & 4\cdot 7 & 4\cdot 8\\ \end{array}\right).\]
Блоки матрицы здесь выделены линиями для наглядности.
В этой задаче мы рассмотрим матрицу \(A\) следующего вида: \[A=\left(\begin{array}{cc} 1 & 1\\ 1 & 0 \end{array}\right)\] и найдем последовательность ее степеней Кронекера \(A^1=A\), \(A^2=A\otimes A\), \(A^3=A\otimes A^2\) и так далее.
Для примера запишем \(A^2\) и \(A^3\).
\[A^2=\left(\begin{array}{cc|cc} 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0\\\hline 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{array}\right).\]
\[A^3=\left(\begin{array}{cccc|cccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\\hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right).\]
Как видно из определения, такие матрицы будут состоять из нулей и единиц.
Напишите программу, которая по номеру строки \(r\) и номеру столбца \(c\) найдет \(A^n[r, c]\), то есть элемент, который находится в матрице \(A^n\) в указанной позиции. Программа должна дать ответ для \(m\) различных позиций в одной матрице.
Формат входных данных
В первой строке на вход поступают два натуральных числа \(n\) и \(m\) — степень матрицы и количество позиций, для которых требуется найти ответ, \(1\leqslant n\leqslant 60\), \(1\leqslant m\leqslant \min(2^{2n}, 200000)\).
Далее в \(m\) строках записаны по два числа \(r_i\) и \(c_i\) — номер строки и номер столбца в матрице \(A^n\), \(1\leqslant r_i, c_i\leqslant 2^n\).
Формат выходных данных
Выведите \(m\) чисел \(0\) или \(1\) в одной строке через пробел. Число с номером \(i\) должно быть равно элементу матрицы \(A^n[r_i, c_i]\).
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
1 4 1 1 1 2 2 1 2 2 |
1 1 1 0 |
2 |
3 6 1 7 2 2 5 3 8 8 4 5 2 6 |
1 0 1 0 1 0 |
В матрице порядка \(n\) \(2^n\) строк и столбцов. Сравнив номер строки и столбца с \(2^{n-1}\), можно узнать, в какой четверти матрицы находится искомая позиция. Если она в нижней правой четверти, то ответом будет \(0\). Во всех остальных случаях можно найти координаты искомой позиции в матрице порядка \(n-1\), отняв при необходимости от номера строки или столбца \(2^{n-1}\). Этот процесс можно повторять в цикле, пока порядок матрицы больше единицы.
Пример программы-решения
Ниже представлено решение на языке Python.
n,m = map(int,input().split())
for _ in range(m):
r,c=map(int,input().split())
for i in range(n-1,-1,-1):
if r > 2**i and c > 2**i:
print(0,end=' ')
break
else:
if r> 2**i:
r -= 2**i
if c > 2**i:
c -= 2**i
else:
print(1,end=' ')Тесты с номерами 1–2 совпадают с тестами из условия задачи. Баллы за них не начисляются.
Успешное прохождение каждого теста с номерами 3–17 оценивается в 1 балл.
В тестах с номерами 3–9 степень матрицы \(n\) равна номеру теста минус один.
В тестах с номерами 10–12 количество позиций, для которых требуется найти ответ, не превосходит 100.
Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 1 с.
Ограничение по памяти: 256 Мбайт.
Алиса разрабатывает новую систему счисления. Она будет двоичной, то есть для записи чисел будут использоваться только цифры 0 и 1. Также она будет позиционной, то есть значение каждой цифры будет зависеть от ее позиции.
Алиса собирается подобрать некоторый набор оснований \(x_1, \ldots, x_n\), тогда запись \((a_n a_{n-1}\cdots a_1)_{alice}\) будет задавать число \(a_n x_n+a_{n-1}x_{n-1}+\cdots+a_1 x_1\).
Например, для набора оснований \(1, 2, 3, 7, 10\) запись \((11001)_{alice}\) будет задавать число \(1\cdot 10+1\cdot 7+0 \cdot 3 + 0\cdot 2+ 1\cdot 1=18\). Некоторые основания в системе счисления Алисы могут повторяться.
Алиса разрабатывает эту систему не просто для развлечения, она хочет с ее помощью решить все проблемы человечества! Алиса убеждена, что все беды происходят от одного несчастливого числа \(k\), поэтому целью является разработка такой системы счисления, в которой нельзя будет записать число \(k\), а все остальные натуральные числа от \(1\) до \(m\) — можно. (К сожалению, Алиса пока не понимает, что отсутствие алгебраической замкнутости в кольце целых чисел станет источником гораздо более страшных проблем, но мы не будем винить ее за это.)
Напишите программу, которая подберет набор оснований для системы счисления Алисы по заданным числам \(m\) и \(k\). Разумеется, Алиса хочет, чтобы числа в ее системе счисления записывались как можно короче, поэтому искомый набор оснований должен иметь минимальную длину. В итоге программа должна дать ответ для \(t\) независимых тестовых случаев.
Формат входных данных
В первой строке на вход поступает одно целое число \(t\) — количество запросов, \(1\leqslant t \leqslant 10000\). Далее в \(t\) строках записаны сами запросы, по одному в каждой строке. Каждый запрос содержит два числа \(m\) — максимальное число в диапазоне Алисы и \(k\) — несчастливое число, \(1\leqslant k < m\leqslant 10^{18}\).
Формат выходных данных
Выведите \(2t\) строк с ответами на запросы, каждый ответ должен занимать две строки. Первая строка ответа должна содержать одно натуральное число \(n\) — количество оснований в системе счисления. Вторая строка должна содержать сами основания \(x_1, \ldots, x_n\). В случае существования нескольких правильных ответов можно вывести любой из них. Числа можно выводить в любом порядке, они могут повторяться.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
4 100 13 20 5 10 1 8 7 |
8 1 2 4 5 14 20 33 50 6 1 1 2 6 11 16 4 2 3 4 8 4 1 2 3 8 |
Примечания
В первом тестовом случае из заданного набора оснований нельзя получить число 13, так как сумма всех чисел, меньших, чем 13, равна 12.
Все остальные числа получить можно, например, число 100 можно получить в виде суммы \(1+2+14+33+50\).
Рассмотрим процесс выбора оснований для получения чисел, меньших \(k\). Первым основанием возьмем 1. Теперь пусть существующий набор оснований позволяет получить все числа в диапазоне \([0; s]\). Тогда в качестве следующего основания можно взять любое число, не превосходящее \(s+1\). Если обозначить его за \(y\), то диапазон чисел расширится до \([0; s+y]\). Выгодно максимально расширить диапазон, но так, чтобы в него не попало число \(k\). То есть в качестве \(y\) можно взять наибольшее число, удовлетворяющее неравенствам \(y\leqslant k-1-s\) и \(y\leqslant s+1\). Объединяя их в одно, получим \(y=\min(s+1, k-1-s)\). Процесс выбора оснований надо продолжать, пока \(s < k-1\).
Теперь рассмотрим процесс выбора оснований для чисел, больших \(k\). Первым основанием возьмем \(k+1\). Это позволит получить все числа вида \(k+1+a\), где \(a\in [0; k-1]\). Таким образом, теперь можно получить все числа из \(X = [0; k-1] \cup [k+1, 2k]\). Вновь следующим основанием выгодно взять наибольшее, кроме \(k\), число, не принадлежащее множеству \(X\), то есть \(2k+1\).
Теперь дополнительно можно получить все числа вида \(2k+1+a\), где \(a\in X\). \[X'=X \cup [2k+1; 3k] \cup [3k+2; 4k+1] = [0;k-1]\cup[k+1; 3k]\cup [3k+2; 4k+1].\]
Применяя аналогичные рассуждения, можно показать, что следующим основанием можно взять \(3k+1\). Теперь можно получить все числа из \(X''\). \[\begin{aligned} X''=X\cup [3k+1; 4k]\cup [4k+2; 6k+1] \cup [6k+3; 7k+2] =\\= [0;k-1]\cup [k+1; 6k+1]\cup[6k+3; 7k+2]. \end{aligned}\]
Следующим основанием выгодно взять \(6k+2\), и, применяя аналогичные рассуждения, можно показать, что каждое следующее основание будет вдвое больше предыдущего.
Таким образом, три первых основания это: \(k+1\), \(2k+1\), \(3k+1\), а каждое следующее является удвоением предыдущего.
Пример программы-решения
Ниже представлено решение на языке Python.
t = int(input())
for _ in range(t):
n, k=map(int,input().split())
ans = []
s = 0
while s<k-1:
ans.append(min(s+1,k-1-s))
s+=ans[-1]
ans.append(k+1);
if n>2*k:
ans.append(2*k+1)
if n>3*k:
ans.append(3*k+1)
while n>=2*ans[-1]:
ans.append(2*ans[-1])
print(len(ans))
print(' '.join(map(str,ans)))Тест с номером 1 совпадает с тестом из условия задачи. Баллы за него не начисляются.
Успешное прохождение каждого теста с номерами 2–21 оценивается в \(1\) балл.
В тестах с номерами 2–11 несчастливое число \(k\) равно номеру теста минус один, а значение \(m\) не превышает \(10000\).
В тестах с номерами 12–16 для всех тестовых случаев выполняется неравенство \(k < m\leqslant 2k\).
Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 2 с.
Ограничение по памяти: 256 Мбайт.
У Алисы есть \(n\) монет, ровно одна из них фальшивая. Фальшивая монета отличается по весу от настоящих, то есть может быть легче или тяжелее. Имеются чашечные весы, при помощи которых можно сравнить вес двух наборов монет. Алиса пронумеровала все монеты числами от \(1\) до \(n\), выполнила \(m\) взвешиваний, записала результаты и передала их вам.
По имеющимся результатам взвешиваний не всегда возможно точно определить фальшивую монету, поэтому Алиса хочет составить список номеров всех монет, которые могут быть фальшивыми. Формально монета с номером \(i\) может оказаться фальшивой, если могут быть получены заданные результаты взвешиваний в предположении, что веса всех монет, кроме \(i\), совпадают, а монета \(i\) тяжелее других или, если веса всех монет, кроме \(i\), совпадают, а монета \(i\) легче других.
Напишите программу, чтобы определить номера монет, которые могут быть фальшивыми.
Формат входных данных
В первой строке на вход подаются два натуральных числа \(n\) и \(m\) — количество монет и количество взвешиваний, \(2\leqslant n\leqslant 100000\), \(1\leqslant m\leqslant 100000\).
Далее в \(m\) строках записаны результаты взвешиваний. Описание каждого результата выполнено в следующем формате: список монет на левой чашке весов, пробел, символ операции, пробел, список монет на правой чашке весов.
Списки монет заключены в квадратные скобки. Номера монет разделены запятой и пробелом. Гарантируется, что:
- номера монет являются числами от \(1\) до \(n\);
- количество чисел в левом и правом списках совпадает;
- наборы чисел в левом и правом списке не пересекаются;
- суммарное количество чисел во входных данных не превосходит \(200000\).
В качестве символа операции могут использоваться следующие знаки: <, > или =, которые показывают, что вес монет в левой чашке меньше, больше или равен весу монет в правой чашке соответственно.
Гарантируется, что входные данные являются корректными и непротиворечивыми, то есть заданные результаты взвешиваний могут быть получены, если ровно одна монета является фальшивой.
Формат выходных данных
В первой строке выведите одно натуральное число \(k\) — количество монет, которые могут оказаться фальшивыми.
Во второй строке через пробел выведите номера монет в порядке возрастания.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
9 3 < [3, 2] = [1] > [3, 1, 5] |
1 2 |
2 |
7 1 = [1, 4] |
3 3 5 6 |
3 |
7 2 > [1, 4] < [1, 2] |
2 2 4 |
Примечания
В первом тесте заданные результаты взвешиваний могут быть получены, если монета с номером 2 тяжелее остальных.
Во втором тесте монеты с номерами 1, 2, 4, 7 не могут быть фальшивыми, а об остальных монетах ничего неизвестно, значит, они могут быть фальшивыми.
В третьем тесте предположение о том, что монета c номером 2 тяжелее остальных не противоречит полученным результатам. Также результатам не противоречит предположение о том, что монета с номером 4 легче остальных.
Рассмотрим набор взвешиваний, результатом которых является неравенство. Если \(L_1, \ldots, L_m\) — множества номеров монет, которые оказались легче, то фальшивой может быть одна из монет из пересечения этих множеств. Аналогичное утверждение можно сказать и множествах номеров монет \(G_1, \ldots, G_m\), которые оказались тяжелее.
Отдельно рассмотрим набор взвешиваний, результатом которых является равенство. Если \(E_1, \ldots, E_k\) — множества номеров монет, которые участвовали во взвешиваниях с равенством, то ни одна монета из объединения этих множеств не может быть фальшивой.
Теперь ответ можно получить по формуле \[\left(\left(\bigcap\limits_{i=1}^m L_i\right) \bigcup \left(\bigcap\limits_{i=1}^m G_i\right)\right)\setminus \left(\bigcup\limits_{i=1}^k E_i\right).\]
При реализации следует позаботиться о том, чтобы операции над множествами совершались со сложностью меньшего множества.
Пример программы-решения
Ниже представлено решение на языке Python.
n, m = map(int,input().split())
less = set(range(1,n+1))
greater = set(range(1,n+1))
eq = set()
for _ in range(m):
s = input()
p = s.find(']')
a = set(map(int,s[1:p].split(',')))
b = set(map(int,s[p+5:-1].split(',')))
if s[p+2]=='=':
eq|=a
eq|=b
elif s[p+2]=='<':
less &= a
greater &= b
else:
less &= b
greater &= a
ans = (less|greater)-eq
print(len(ans))
print(*sorted(list(ans)))Тесты с номерами 1–3 совпадают с тестами из условия задачи. Баллы за них не начисляются.
Успешное прохождение каждого теста с номерами 4–28 оценивается в 1 балл.
В тестах с номерами 4–8 количество монет не превосходит 100, а количество чисел во входных данных не превосходит 500.
В тестах с номерами 9–18 количество монет не превосходит 1000, а количество чисел во входных данных не превосходит 10000.
Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 1,5 с.
Ограничение по памяти: 256 Мбайт.
Внимание. Вводная часть в этой задаче совпадает с вводной частью задачи 1.2. Если вы решили задачу 1.2, то можете пропустить ее.
В некоторых областях квантовых вычислений используется понятие произведения Кронекера двух матриц. Если \[A=\left(\begin{array}{ccc} a_{11}&\cdots &a_{1n}\\ \vdots&\ddots &\vdots\\ a_{n1}&\cdots &a_{nn}\\ \end{array}\right),\qquad B=\left(\begin{array}{ccc} b_{11}&\cdots &b_{1m}\\ \vdots&\ddots &\vdots\\ b_{m1}&\cdots &b_{mm}\\ \end{array}\right),\] то их произведение Кронекера определяется, как блоковая матрица следующего вида: \[A\otimes B = \left(\begin{array}{ccc} a_{11} B &\cdots &a_{1n} B\\ \vdots&\ddots &\vdots\\ a_{n1} B &\cdots &a_{nn} B\\ \end{array}\right).\]
Например, для \(A=\left(\begin{array}{cc} 1 & 2\\ 3 & 4\\ \end{array}\right)\) и \(B=\left(\begin{array}{cc} 5 & 6\\ 7 & 8\\ \end{array}\right)\) их произведение Кронекера будет равно: \[\left(\begin{array}{cc|cc} 1\cdot 5 & 1\cdot 6 & 2\cdot 5 & 2\cdot 6\\ 1\cdot 7 & 1\cdot 8 & 2\cdot 7 & 2\cdot 8\\\hline 3\cdot 5 & 3\cdot 6 & 4\cdot 5 & 4\cdot 6\\ 3\cdot 7 & 3\cdot 8 & 4\cdot 7 & 4\cdot 8\\ \end{array}\right).\]
Блоки матрицы здесь выделены линиями для наглядности.
В этой задаче рассмотрим матрицу \(A\) следующего вида \[A=\left(\begin{array}{cc} 1 & 1\\ 1 & 0 \end{array}\right)\] и найдем последовательность ее степеней Кронекера \(A^1=A\), \(A^2=A\otimes A\), \(A^3=A\otimes A^2\) и так далее. Для примера запишем \(A^2\) и \(A^3\).
\[A^2=\left(\begin{array}{cc|cc} 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0\\\hline 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{array}\right).\]
\[A^3=\left(\begin{array}{cccc|cccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\\hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right).\]
Как видно из определения, такие матрицы будут состоять из нулей и единиц.
С этого места начинается оригинальное условие задачи.
Рассмотрим матрицу \(A^n\) и занумеруем все единицы в ней сверху вниз и слева направо. Например, для матрицы \(A^2\) нумерация будет выглядеть следующим образом. \[A^2=\left(\begin{array}{cc|cc} 1 & 2 & 3 & 4\\ 5 & * & 6 & *\\\hline 7 & 8 & * & *\\ 9 & * & * & * \end{array}\right).\] Здесь на позициях единиц стоят их порядковые номера. Нули в нумерации не участвуют и заменены звездочками.
Напишите программу, которая найдет позиции единиц в матрице \(A^n\) по их порядковым номерам.
Формат входных данных
В первой строке на вход поступают два натуральных числа \(n\) и \(m\) — порядок матрицы и количество номеров единиц, \(1\leqslant n\leqslant 38\), \(1\leqslant m \leqslant 100000\).
Во второй строке через пробел записаны \(m\) натуральных чисел \(a_1, \ldots, a_m\) — номера единиц, \(1\leqslant a_i\leqslant 3^n\).
Формат выходных данных
В \(m\) строках выведите по два числа \(r_i\) и \(c_i\) — номер строки и номер столбца матрицы, в котором находится единица с порядковым номером \(a_i\). Строки и столбцы матрицы \(A^n\) нумеруются, начиная с единицы, сверху вниз и слева направо.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
2 9 1 2 3 4 5 6 7 8 9 |
1 1 1 2 1 3 1 4 2 1 2 3 3 1 3 2 4 1 |
2 |
38 3 256711980439665054 564682175042572888 321752549611034335 |
14898268353 240553579550 55902790145 140991532328 20547896451 5170319645 |
Запишем несколько формул, которые будут использоваться при решении задачи.
Суммарное количество единиц в матрице порядка \(n\) равно \(3^n\). Это легко понять, заметив, что при увеличении порядка матрицы на 1 количество единиц в ней увеличивается в три раза.
Далее будет удобнее считать, что нумерация строк и столбцов матрицы ведется с нуля.
Количество единиц в \(k\)-й строке матрицы порядка \(n\) можно найти по формуле \[R(n, k)=\left\{ \begin{array}{ll} 1 & n=0,\\ 2R(n-1, k) & k < 2^{n-1},\\ R(n-1, k-2^{n-1}) & k\geqslant 2^{n-1}. \end{array} \right.\]
Для обоснования формулы можно привести такие рассуждения. Если \(k\)-я строка расположена в верхней половине матрицы, то надо найти количество единиц в этой же строке в матрице меньшего порядка и умножить результат на 2, поскольку в верхней половине состоит из двух матриц меньшего порядка. Нижняя половина состоит из одной матрицы меньшего порядка, поэтому результат не изменится.
Заметим, что умножение на 2 соответствует каждому нулю двоичной записи \(k\), то есть \(R(n, k)=2^z\), где \(z\) — количество нулей в двоичной записи \(k\) с использованием ровно \(n\) разрядов.
Суммарное количество единиц в первых \(k\) строках матрицы порядка \(n\) можно найти по формуле \[S(n, k) = \left\{ \begin{array}{ll} 0 & n=0,\\ 2S(n-1, k) & k < 2^{n-1},\\ 2\cdot 3^{n-1}+S(n-1, k-2^{n-1}) & k\geqslant 2^{n-1}. \end{array} \right.\] Для обоснования формулы можно привести такие рассуждения. Если \(k\) строк расположены в верхней половине матрицы, то надо найти количество единиц в матрице меньшего порядка и умножить результат на 2. Иначе \(k\) строк занимают верхнюю половину матрицы и \(k-2^{n-1}\) строк из нижней половины. Количество единиц в верхней половине равно \(2\cdot 3^{n-1}\), а в нижней — \(S(n-1,k-2^{n-1})\).
Можно модифицировать эту формулу для решения обратной задачи — найти наибольшее количество строк, в которых не более \(m\) единиц.
\[B(n, c) = \left\{ \begin{array}{ll} 0 & n=0,\\ B(n-1, \left\lceil\frac{m}{2}\right\rceil) & m < 2\cdot 3^{n-1},\\ 2^{n-1}+B(n-1, m-2\cdot 3^{n-1}) & m \geqslant 2\cdot 3^{n-1}. \end{array} \right.\]
Далее запишем формулу для нахождения количества единиц среди \(c\) первых элементов в строке \(r\) матрицы порядка \(n\).
\[F(n, r, c) = \left\{ \begin{array}{ll} 0 & n=0,\\ F(n-1, r\mod 2^{n-1}, c) & c < 2^{n-1},\\ R(n-1, r\mod 2^{n-1})+F(n-1, r \mod 2^{n-1}, c-2^{n-1}) & c \geqslant 2^{n-1}.\\ \end{array} \right.\] Обоснование этой формулы можно выполнить той же схеме, как и в предыдущих случаях, с той разницей, что здесь рассматриваются случаи нахождения всех элементов только в левой части матрицы или в левой и правой.
Также можно записать и формулу для решения обратной задачи — нахождения наименьшего числа элементов в строке \(r\) в матрице порядка \(n\), которые содержат ровно \(m\) единиц.
\[A(n, r, m) = \left\{ \begin{array}{ll} 0 & n=0,\\ A(n-1, r\mod 2^{n-1}, m) & m < R(n-1, r\mod 2^{n-1}),\\ 2^{n-1} + A(n-1, r\mod 2^{n-1}, & \\ m-R(n-1, r\mod 2^{n-1})) & m \geqslant R(n-1, r\mod 2^{n-1}). \end{array} \right.\]
Используя эти формулы, можно записать решение. Сначала найдем номер строки матрицы по формуле \(r = B(n, m)\). Далее найдем номер единицы в строке \(r\) по формуле \(m'=m-S(n, r)\), и наконец найдем номер столбца по формуле \(A(n, r, m')\).
Пример программы-решения
Ниже представлено решение на языке Python.
pw = [2*3**(i) for i in range(40)]
def find_row(n, k):
ans = 0
while n>0:
n-=1;
if k<pw[n]:
k//=2
else:
k-=pw[n]
ans += 2**n
return ans
def block_ones(n, row):
ans = 0
for i in range(n):
if row%2 == 1:
ans+=pw[i]
else:
ans*=2
row//=2
return ans
def find_col(n,row,k):
c = 0
ans=0
for i in range(n):
if row%2==0:
if k%2==1:
ans+=2**i
k//=2
c+=1
row//=2
return ans
n, m = map(int,input().split())
for k in map(int,input().split()):
row = find_row(n,k-1)
print(row+1,find_col(n,row,k-1-block_ones(n,row))+1)Тесты с номерами 1–2 совпадают с тестами из условия задачи. Баллы за них не начисляются.
Успешное прохождение каждого теста с номерами 3–32 оценивается в 1 балл.
В тестах с номерами 3–10 степень матрицы \(n\) равна номеру теста. Эти тесты проверяют правильность работы программы для всех чисел с номерами от \(1\) до \(3^n\).
В тестах с номерами 11–17 степень матрицы \(n\) не превосходит \(13\), \(m\leqslant 10000\).
В тестах с номерами 18–22 степень матрицы \(n\) не превосходит \(18\), \(m\leqslant 10000\).
В тестах с номерами 23–27 степень матрицы \(n\) не превосходит \(38\), \(m\leqslant 10000\).
