Представим следующий алгоритм. Есть массив $$$v_1, v_2, \dots, v_n$$$, изначально заполненный нулями. Несколько раз с массивом проделываются похожие операции — на $$$i$$$-м шаге (в $$$0$$$-индексации) вы можете:
Вы можете выбирать, как алгоритм ведет себя на каждом шаге и когда он будет остановлен. Вопрос в следующем: можно ли сделать массив $$$v$$$ равным некоторому массиву $$$a$$$ ($$$v_j = a_j$$$ для каждого $$$j$$$) после некоторого шага?
В первой строке задано одно целое число $$$T$$$ ($$$1 \le T \le 1000$$$) — количество наборов входных данных. В следующих $$$2T$$$ строках заданы сами наборы входных данных, по две строки на каждый набор.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 30$$$, $$$2 \le k \le 100$$$) — размер массивов $$$v$$$ и $$$a$$$, и число $$$k$$$, используемое в алгоритме.
Во второй строке набора входных данных заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{16}$$$) — массив, который вы хотите получить.
Для каждого набора тестовых данных выведите либо YES (регистр не важен), если можно получить массив $$$a$$$ после некоторого шага, либо NO (регистр не важен), если это невозможно.
5 4 100 0 0 0 0 1 2 1 3 4 1 4 1 3 2 0 1 3 3 9 0 59049 810
YES YES NO NO YES
В первом наборе тестовых данных можно остановить алгоритм до $$$0$$$-го шага, или не выбирать никакую позицию и остановить алгоритм позже.
Во втором наборе можно прибавить $$$k^0$$$ к $$$v_1$$$ и остановить алгоритм.
В третьем наборе невозможно получить два элемента, равных $$$1$$$, в массиве $$$v$$$.
В пятом наборе можно пропустить $$$9^0$$$ и $$$9^1$$$, прибавить $$$9^2$$$ и $$$9^3$$$ к $$$v_3$$$, пропустить $$$9^4$$$ и, наконец, прибавить $$$9^5$$$ к $$$v_2$$$.
Название |
---|