Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
171. Sly Number
Олимпиадные задачи на английском языке| 31/03/2007 | Тренировка (задачи ACM ICPC SE RC 2002) (H) |
Ограничения: время – 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
