tr

Soruda ilk olarak düşünebileceğimiz şey, fantastik sayılarda her \(n\) için \(3^n\) ya tek bir tane vardır ya da yoktur. Bunu düşünerek ilerlediğimizde herhangi her \( 3^n \) sayısından küçük eşit \( 2^n \) adet fantastik sayı olduğunu görebiliriz.

Yukardaki düşünceyi kullanarak sayıdan sırasıyla olabilecek en büyük \( 3^n \) sayılarını çıkarak sonuca oluşabiliriz. Aşşağıdaki koddaki \(solve\) fonksiyonunu açıklamak gerekirse, fonskiyon aldığı sayıyı olabilecek en büyük \(3^n\) sayısından çıkarıyor ve çözüme \(2^n\) ekliyor, sonrasında da çıkardığı sayıyla aynı işlemi tekrarlıyor. Buradaki dikkat edilmesi gereken nokta, aynı kuvvet iki kere kullanılamayacağından \(3^n\) çıkardığıldığında bile \(3^n\)'den büyük olması. Belirtilen durumda \(3^n\)'den daha düşük olan kuvvetlerin hepsi kullanılabildiği için \(2^{n+1}-1\)'i döndürüyor.

en

The first to notice in the problem is that fantastic numbers either include a single \(3^n\) or none for every n. Thinking like this, it can be seen that for a number \(3^n\) there are \(2^n\) fantastic numbers which are less than or equal to that number.

With the stated thought, the answer can be achieved by deducting the biggest possible \( 3^n \) from the number. To explain the function \( solve \) in the code below, it deducts the biggest possible \(3^n\) and adds \( 2^n\), and continues this recursively with the deducted number. The thing to watch out for is if the deducted number is still bigger than \(3^n\). This is an issue because the same power of three can't be used twice. In this case, the function simply returns \(2^{n+1}-1\) because all of the powers of three less than \(n\) can be used.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n, q;
vector<ll> v;

ll solve(ll n){
    if(n==0) return 0;
    for(int i=0;i<=37;i++){
        if(n>=v[i]){
            n-=v[i];
            if(n>=v[i]) n=v[i]-1;
            return solve(n) + pow(2, 37-i);
        }
    }
}

int main(){
    cin>>q;
    ll xx=pow(3, 37);
    while(xx>0){
        v.push_back(xx);
        xx/=3;
    }
    for(int i=0;i<q;i++){
        cin>>n;
        cout<<solve(n)<<endl;
    }

}