Problem description

Back
Show PDF
Podział na zbiory trójkowiaste
(B)
Limit pamięci: 32 MB
Limit czasu: 2.00 s

Wielozbiór (czyli zbiór, w którym dopuszczamy powtarzające się elementy) liczb nazwiemy trójkowiastym, jeśli suma jego elementów jest podzielna przez 3. Przykładowo, zbiory {1, 2, 3} oraz {12} są trójkowiaste, a zbiór {2, 2, 2, 2} – nie.

Napisz program, który dla danego zbioru N liczb naturalnych {A1, A2, …, An} sprawdzi, czy można go rozbić na K niepustych, rozłącznych podzbiorów, z których każdy jest trójkowiasty.

Wejście

W pierwszym wierszu znajduje się liczba naturalna T, oznaczająca liczbę testów. W kolejnych 2T wierszach znajdują się dane dla kolejnych testów.

Dane dla każdego testu zapisane są w dwóch wierszach:

  • W pierwszym z nich znajdują się liczby naturalne N i K.
  • W drugim z nich znajduje się N liczb naturalnych A1, A2, …, An.

Wyjście

W i-tym wierszu należy wypisać wynik dla i-tego testu, którym jest jedno słowo:

  • TAK – jeśli zbiór {A1, A2, …, An} można rozbić na K niepustych, rozłącznych podzbiorów trójkowiastych,
  • NIE – w przeciwnym przypadku.

Ograniczenia

1 ≤ T ≤ 15, 1 ≤ N, K ≤ 1 000 000, 1 ≤ Ai ≤ 1018.

Przykład

Wejście Wyjście Wyjaśnienie 
2
3 3
1 2 3
10 4
1 2 7 23 1 7 8 61 32 8

NIE
TAK

Dla N = 3, K = 3 oraz zbioru {1, 2, 3} odpowiedzią jest NIE, ponieważ z tych liczb można utworzyć tylko dwa niepuste zbiory trójkowiaste.

Dla N = 10, K = 4 oraz zbioru {1, 2, 7, 23, 1, 7, 8, 61, 32, 8} odpowiedzią jest TAK. Przykładowe rozbicie na zbiory trójkowiaste: {7, 32}, {61, 2}, {1, 7, 1}, {8, 23, 8}.