Решение задачи Прибавление степеней с Codeforces

Без пояснения   Просмотров: 40


Представим следующий алгоритм. Есть массив v1,v2,…,vn, изначально заполненный нулями. Несколько раз с массивом проделываются похожие операции — на i-м шаге (в 0-индексации) вы можете:

либо выбрать любую позицию pos (1≤pos≤n) и увеличить vpos на ki;
либо не выбирать позицию и пропустить шаг.
Вы можете выбирать, как алгоритм ведет себя на каждом шаге и когда он будет остановлен. Вопрос в следующем: можно ли сделать массив v равным некоторому массиву a (vj=aj для каждого j) после некоторого шага?

Код

#include <bits/stdc++.h>
using namespace std;
long long t, n, k, a, f[75]; 
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> t;
while (t--){
	cin >> n >> k;
	for (int i=0; i<70; i++) f[i]=0;
	for (int i=0; i<n; i++){
		cin >> a;
		for (int j=0; a; j++){
			f[j]+=a%k;
			a/=k;
		}
	}
	bool ok=1;
	for (int i=0; i<70; i++) if(f[i]>1) ok=0;
	if (ok) cout << "YES\n";
	else cout << "NO\n";
}
return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться