443 - Humble Numbers

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brunokbcao
New poster
Posts: 4
Joined: Sun May 14, 2006 4:22 pm
Location: Recife, PE
Contact:

Post by brunokbcao »

TanveerAhsan wrote: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 :lol:

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

443 st nd rd th

Post by 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
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

443 WA

Post by 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
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by 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... :wink:

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

Post by thomas1016 »

Can U explain what lead to this result???

:o

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

443 help please

Post by Giorgi »

I don't think that my solution is wrong and I can't understand why it
gives WA. :x 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
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi »

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

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:

Post by 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
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi »

thank you very much, I got AC :)

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

please help me [TIME LIMIT EXEEDED] [443]

Post by newton »

thanx


got AC!
Last edited by newton on Tue Sep 05, 2006 2:27 pm, edited 1 time in total.

milacao
New poster
Posts: 5
Joined: Mon Aug 14, 2006 7:57 pm

please help me [TIME LIMIT EXEEDED] [443]

Post by 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
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm

help me 443

Post by 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
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm

Post by jainal uddin »

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

jainal uddin wrote:hello try to make another algorithm to find out humble number.
Are you answering yourself!? :o

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

443(HUMBLE NUMBER)WHY TLE?

Post by ishtiaq ahmed »

Code: Select all

the code is removed after ac.
Last edited by ishtiaq ahmed on Sun Feb 17, 2008 7:29 pm, edited 3 times in total.

Post Reply

Return to “Volume 4 (400-499)”