Nice editorial
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
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.
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}
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!
You have print Yes and No in new lines
You have missed endl there !
Thats it
Be careful
Thanks a lot!! It worked
Pls like my reply !
Welcome
Thanks a lot !
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(n10,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(n10,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;
}
‘’’