Решение задачи "Хорошие числа (простая версия)" с Codeforces

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


Единственное отличие между простой и сложной версиями — максимальное значение n.

Вам дано положительное целое число n. Вы очень любите хорошие числа, поэтому вам хочется найти минимальное хорошее число, большее или равное n.

Положительное число называется хорошим, если оно может быть представлено в виде суммы различных степеней 3 (т.е. повторения степеней 3 запрещены).

Например:

30 — хорошее число: 30=33+31,
1 — хорошее число: 1=30,
12 — хорошее число: 12=32+31,
но 2 не является хорошим числом: вы не можете представить его в виде суммы различных степеней 3 (2=30+30),
19 не является хорошим числом: вы не можете представить его в виде суммы различных степеней 3 (например, представления 19=32+32+30=32+31+31+31+30 не являются корректными),
20 тоже не является хорошим числом: вы не можете представить его в виде суммы различных степеней 3 (например, представление 20=32+32+30+30 не является корректным).
Обратите внимание, что существуют и другие представления 19 и 20 в качестве сумм степеней 3, но ни одно из них не состоит из различных степеней 3.

Для заданного положительного числа n найдите наименьшее m (n≤m) такое, что m — хорошее число.

Вам необходимо ответить на q независимых запросов.

Код

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    	int q;cin>>q;
    	while(q--)
    	{
    		long long n,k=1,p=3;cin>>n;
    		while(k<n)
    		{
    			k+=p;
    			p=p*3;
    		}
    		while(p)
    		{
    			if(k-p>=n)
    			k=k-p;
    			p=p/3;
    		}
    		cout<<k<<endl;
    	}
    }

         

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


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

Комментарии

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