Page 4 of 6
Posted: Sat May 20, 2006 4:17 am
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
443 st nd rd th
Posted: Sun May 21, 2006 12:15 pm
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
443 WA
Posted: Fri Jun 16, 2006 2:55 pm
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;
}
Posted: Fri Jun 16, 2006 7:38 pm
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...
Posted: Sat Jun 17, 2006 6:28 am
by thomas1016
Can U explain what lead to this result???
443 help please
Posted: Tue Jul 04, 2006 10:17 am
by 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]
Posted: Tue Jul 04, 2006 11:54 am
by Giorgi
CAN ANYBODY HELP ME?????????????
Posted: Thu Jul 06, 2006 7:13 pm
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..
Posted: Fri Jul 07, 2006 8:04 am
by Giorgi
thank you very much, I got AC
please help me [TIME LIMIT EXEEDED] [443]
Posted: Thu Jul 27, 2006 12:29 pm
by newton
thanx
got AC!
please help me [TIME LIMIT EXEEDED] [443]
Posted: Wed Aug 16, 2006 12:31 am
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.
help me 443
Posted: Thu Aug 17, 2006 8:20 am
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;
}
Posted: Thu Aug 17, 2006 8:22 am
by jainal uddin
hello try to make another algorithm to find out humble number.
Posted: Thu Aug 17, 2006 9:10 am
by mamun
jainal uddin wrote:hello try to make another algorithm to find out humble number.
Are you answering yourself!?
443(HUMBLE NUMBER)WHY TLE?
Posted: Wed Aug 23, 2006 2:11 pm
by ishtiaq ahmed