Имя: Пароль: Зарегистрироваться Восстановить пароль
24/02/2024 04:46:50

# Рабочее место участника

## Задачи

171. Sly Number

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)

Let's consider so called "sly number" which is given as an array A of N integers from set {0,1,2}. For example A[0]\ =\ 1, A[1]\ =\ 1, A[2]\ =\ 0 and A[3]\ =\ 2. A sly number is called "ONE", if A[0]\ =\ 1 and A[\ i]\ =\ 0 for i\ =\ 1,\ 2,…,\ N\ -\ 1. Consider following operation with two sly numbers A and B called "Star Multiplication":
C[k]\ =\ sum_{i=0}^k\ A*B[k\ -\ i]\ +\ sum_{i=k+1}^_{N-1}\ A[i]*B[N\ +\ k\ -\ i]
here C – the result of the operation, even also presented in an array – not necessarily sly number. This operation we will denote by '*' symbol. Moreover, there is also module operation over the results of "Star Multiplication":
(C\ mod\ Q)[\ i]\ =\ C[\ i]\ mod\ Q,
where Q is a positive integer. We are given a sly number A and a module Q. We need to find such inverse sly number B:
(A*B)\ mod\ Q\ =\ "ONE".
[i]Input
The input file contains K data sets in text format. The first line of this file contains the number K of test cases. Each test consists of two lines. First line contains two integers separated by spaces: Q (2\ ≤\ Q\ ≤\ 100) and N (5\ ≤\ N\ ≤\ 50). Second line contains N integers from set {0,1,2} separated by spaces, which present sly number A.
Output
The output should be printed on the standard output. It should contain K lines – one line for each test case. If a solution exists, the line should contain the string "A solution can be found" (In the first sample one possible inverse sly number could be (0 0 1 1 1)). In case there is no solution, the line should consist of string "No solution".

Sample Input

2
2 5
1 0 1 0 1
65 8
1 2 2 2 1 1 2 2


Sample Output

A solution can be found
No solution

Source: ACM ICPC SEERC, 2002