443 - Humble Numbers

[brunokbcao]

You can't run such a loop. It will take more than a minute (probably).

Generate all the numbers whose prime factors are 2, 3, 5, 7 and insert them in a sorted list like we do in insertion sort. For example, 1 is a humble number. Now multiply it with 2, 3, 5 and 7 and the new list will be 1 2 3 5 7. Next take the 2nd humble number i.e. 2 and multiply it with 2, 3, 5, and 7 and the new list will be 1 2 3 4 5 6 7 10 14. Now take 3 and repeat the process. Repeat the same as required.

Yes... I used this method, and got accepted. There's a another way to do it:


int pos = 0;
int i, j, k, l

for (i = 0; i < limit; i++) {
for (j = 0; j < limit; j++) {
for (l = 0; l < limit; l++) {
for (m = 0; m < limit; m++) {
array[pos] = 2 ^ i * 3 ^ j * 5 ^ k * 7 ^ l; // 2 elevated to i, ...
pos++;
}
}
}
}

qsort(array, ...);

you can do it too. I don't tested if it gets and TLE

[Spykaj]

char* end(int n){
if((n%100)/10==1)return "th";
if(n%10==1)return "st";
if(n%10==2)return "nd";
if(n%10==3)return "rd";
return "th";
}

printf("The %d%s humble number is %d.\n",n,end(n),T[n]);

Enjoy all and get AC

[thomas1016]

why did it gave me WA it is alright while num<100?
it seems logically right ,did it?

Code: Select all

#include <iostream>
#include <cmath>
using namespace std;
int check(int);

int main(void){
unsigned long long int k,a,pa;
    while(cin>>k){
                  pa=0;
                  a=2000000100;
                  if(k==0){break;
                           }
              cout<<"The "<<k;
              switch(k%10)
              {
                          case 1:
                               cout<<"st";
                               break;
                          case 2:
                               cout<<"nd";
                               break;
                          case 3:
                               cout<<"rd";
                               break;
                          default:
                                  cout<<"th";
                                  break;
                          
                          }
              cout<<" humble number is ";
                  while(check((a+pa)/2)!=k){
                                            //cout<<"pa="<<pa<<"   "<<"a="<<a<<"   "<<(a+pa)/2<<" ans "<<check((a+pa)/2)<<endl;
                                            if(check((a+pa)/2)>k){ 
                                                                 // if(a!=(pa+a)/2){
                                                                  a=(pa+a)/2;//}
                                                                 // else{
                                                                //       a--;
                                                                 //      }
                                                                  
                                                                  }
                                            else{
                                                                //   if(pa!=(pa+a)/2){
                                                                  pa=(pa+a)/2;
                                                                //  }
                                                              //    else{
                                                              //         pa++;
                                                                       
                                                                      //}
                                                 
                                                 }
                                            
                                            }
                  cout<<(a+pa)/2<<"."<<endl;
                  
                  }





   // system("pause");
    return 0;
    }
int check(int a){
    int i,j,k,l,m;
    m=0;
    unsigned long long int q=1,w=1,e=1,r=1,y=1,t=1,u=1;

    for(i=0,q=1;i<=log(a)/log(2);i++,q*=2){           
    for(j=0,w=1;j<=log(a)/log(3) && q*w<a;j++,w*=3){

    for(k=0,e=1;k<=log(a)/log(5) && q*w*e<a;k++,e*=5){
   
    for(l=0,r=1;l<=log(a)/log(7) && q*w*e*r<a;l++,r*=7){
             
             
            
                                     m++;                                      
                                                                                     
                                  
                                  }}}}
   
   return m+1;
    }

[jan_holmes]

Your Code produced Wrong Answer for these inputs :

input == 99,output should be 448
input == 98,output should be 441
input == 97,output should be 432

Yours produced :

input == 99,your output 446
input == 98,your output 438
input == 97,your output 431

Hope it helps...

[thomas1016]

Can U explain what lead to this result???

[Giorgi]

I don't think that my solution is wrong and I can't understand why it
gives WA. I generate all numbers and then i print them.
help please

Code: Select all

var  a:array[1..5842] of int64;
i,j,n:longint;
k,p:int64;

procedure find(t:int64);

  begin
   for j:=i-1 downto 1 do
     if (a[j]*t>k) then if (a[j]*t<p) then
      p:=a[j]*t else else break;

  end;

   procedure make;
  begin
   a[1]:=1; k:=1;
    for i:=2 to 5842 do
     begin
     p:=maxlongint;
      find(2);
      find(3);
      find(5);
      find(7);
  a[i]:=p; k:=p;
     end;
  end;





begin
  
  make;
  readln(n);
   while n<>0 do
    begin
      write('The ',n);
      if n = 11 then write('th') else if n=12 then write('th') else
      if n = 13 then write('th') else
      if n mod 10 = 1 then write('st') else if n mod 10=2 then write('nd')
      else if n mod 10=3 then write('rd') else write('th');
      writeln(' humble number is ',a[n],'.');
    readln(n);
    end;


 end.

[/quote]

[/b]

[Giorgi]

CAN ANYBODY HELP ME?????????????

[albet_januar]

i don't know your code is correct or not, coz i dont know PASCAL..
but there is a bug in your code..

i think your code it will give 113 as '113rd', it should be '113th'..
i hope this will help u..

God Bless U..

[Giorgi]

thank you very much, I got AC

[newton]

thanx


got AC!

[milacao]

Hi Newton,
I haven't tried yet this problem, but I see several things in your code:
1) GOTO: Although goto perhaps improves performance, it violates good structured programming conventions, so you should avoid it
2) With your loop, your code would fail if you have, i.e., number 2310, since it is a multiple of 2, 3, 5 and 7 (giving 'temp%a[j]==0' true), but not only, because it is also multiple of 11, so instead you should use something like:

while (temp%a[j] == 0) ...

but...
3) ... if you look at simple inputs and outputs, 5842nd humble number is 2000000000, so, to check this, you will have to do millions of divisions, and it is computationally really expensive.
I hope this helps,
Milacao.

[jainal uddin]

please help me why time limit exeeded?

Code: Select all

#include<stdio.h>
int main()
{

       long long n,count,i,a,mod,h;
       while((scanf("%lld",&n))!=EOF){
       count=0;
       for(h=1;count<n;h++)
       {
               a=h;

               while(a%2==0)
                       a=a/2;

               while(a%3==0)
                       a=a/3;

               while(a%5==0)
                       a=a/5;

               while(a%7==0)
                       a=a/7;
               if( a == 1 )
                       count++;

       }
       mod=n%10;
       if(mod==1)
               printf("The %lldst humble number is %lld.\n",n,h-1);
       else if(mod==2)
               printf("The %lldnd humble number is %lld.\n",n,h-1);
       else if(mod==3)
               printf("The %lldrd humble number is %lld.\n",n,h-1);
       else
               printf("The %lldth humble number is %lld.\n",n,h-1);

       }
       return 0;
}

[jainal uddin]

hello try to make another algorithm to find out humble number.

[mamun]

hello try to make another algorithm to find out humble number.

Are you answering yourself!?

[ishtiaq ahmed]

Code: Select all

the code is removed after ac.