CKWLK - Editorial

Nice editorial

@vijju123 can you help me in this? seems like editorialist is busy.

if ans==30 it should print “No”

thanks, @raisinten can you help, why this logic giving the wrong answer

public class Test{

public static long by10(long temp){
       while(true){
           if(temp%10==0)
             temp = temp/10 ;
         else break ;
       }
       return temp ;

}

public static long by20(long temp){
    while(true){
           if(temp%20==0)
             temp = temp/20 ;
         else break ;
       }
       return temp ;
}

public static void main (String[] args){
      Scanner in = new Scanner(System.in);
      int t = in.nextInt();
      in.nextLine();
      for(int tc =0 ;tc<t;tc++){
      long n = in.nextLong();

       long a = by20(n);
       long b = by10(a);
       if(n<=1)System.out.println("No");
       else{
       if(b ==1)
        System.out.println("Yes");
       else{
          long c = by10(n);
          long d = by20(c);
          if(d==1)
            System.out.println("Yes");
          else
            System.out.println("No");

    }

     }

}

}
}

I feel both your solutions are correct. Your second solution assumes K \leq 10^6 which you should mention :stuck_out_tongue:

1 Like

yes. I am eager to know solution for K~10^12 or K~10^18(if exist) as editorialist mentioned. i am still noob in number theory.
Thanks

It won’t work because you’re assuming that the number N can be reduced greedily.

Did you give a thought to number 2000?

If we divide it greedily by 20 as long as possible, we are left with 5, which can’t be divided further by 20 or 10.

Let’s do this the other way round.

If we divide it greedily by 10 as long as possible, we are left with 2, which can’t be divided further by 20 or 10.

However, we can produce 2000 by the product of the sequence 10, 10 and 20.

Hope this helps. :slightly_smiling_face:

1 Like

It was only my guess that there “might” be some solution for K = 10^{12} or K = 10^{18} My solution too works up to K = 10^6 currently, will try for K = 10^{12}

2 Likes

I still think a recursive approach is so much easier.

My code is working in other IDE(like codeblocks,online compiler,C++shell) but not in codechef ide.Please help!!.Here is my code:
#include<bits/stdc++.h>
using namespace std;

int main()
{
int T;
cin>>T;
while(T–)
{long long int n,count=0;
cin>>n;
while((n%10)==0)
{n/=10;
count++;}
if(ceil(log2(n)) == floor(log2(n)) && count>=ceil(log2(n)))
cout<<“Yes”;
else
cout<<“No”;

}

}

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

1 Like

You have print Yes and No in new lines
You have missed endl there !
Thats it
Be careful

3 Likes

Thanks a lot!! It worked

Pls like my reply !
Welcome :slightly_smiling_face::smile:

Thanks a lot !

2 Likes

https://www.codechef.com/viewsolution/28422827
Please let me know where i’m wrong

Consider the testcase:

1
40

//My approach

int c1;
int isPowerOfTwo(int n)
{
c1=0;
while (n != 1)
{

    n = n/2;  
    c1++;
}  
return c1;  

}

int main()
{
int t;
cin>>t;

while(t–)
{
ll n;
cin>>n;
string s=to_string(n);
int p=-1;
for(int i=s.size()-1;i>=0;i–)
{
if(s[i]!=‘0’)
{ p=i;
break;
}
}

ll sum=0;
ll a=0;
for(int i=0;i<=p;i++)
{
sum=10*sum+(s[i]-‘0’);
}
if(__builtin_popcount(sum)==1)
{
int h=isPowerOfTwo(sum);
if(s.size()-p>h)
cout<<“Yes”<<endl;
else
cout<<“No”<<endl;
}
else
{ int f=0;
while(n!=1)
{
if(n%10==0)
n/=10;
else if(n%10!=0)
{cout<<“No”<<endl;
f=1;break;}
}
if(f==0)cout<<“Yes”<<endl;
}
}
return 0;
}

Is this a problem of Dynamic Programming?

#include
#define ll long long
using namespace std;

bool check(ll int n,ll int lim)
{
if(n==lim)
{
return true;
}
if(n>lim)
{
return false;
}
bool a=check(n20,lim);
bool b=check(n
10,lim);
return a|b;
}
int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
ll int n;
cin>>n;
if(check(1LL,n))
{
cout<<“Yes”<<endl;
}
else
{
cout<<“No”<<endl;
}
}
return 0;
}

,
#include
#define ll long long
using namespace std;

bool check(ll int n,ll int lim)
{
if(n==lim)
{
return true;
}
if(n>lim)
{
return false;
}
bool a=check(n20,lim);
bool b=check(n
10,lim);
return a|b;
}
int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
ll int n;
cin>>n;
if(check(1LL,n))
{
cout<<“Yes”<<endl;
}
else
{
cout<<“No”<<endl;
}
}
return 0;
}
‘’’