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

jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

Post by jhonny_yang » Fri Oct 15, 2004 5:21 pm

Ghust_omega wrote:Hi !! jhonny_yang i summit your code like you posted here and gives AC try to summit the source code on-line

Hope it Helps
Keep posting !! :D
It's Really Strange ... Then So much my code will like this hiks ... Can you explain what's going on ?

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Oct 15, 2004 6:03 pm

Hi !! jhonny_yang I Submit your code and get AC the problem its ok, I think that if you submit the code by mail maybe there are problems, try to submit http://acm.uva.es/problemset/submit.php its better, I'm sure that your code its ok

User avatar
habibiamin
New poster
Posts: 8
Joined: Tue Oct 12, 2004 1:54 pm
Location: Iran-Tehran
Contact:

443 Can any body tell why WA ???

Post by habibiamin » Tue Oct 19, 2004 2:21 pm

I got WA .. but I don't know why??? :o
Please help me ... !!!
Thanks... :wink:

[cpp]
//http://acm.uva.es/p/v4/443.html
#include <iostream.h>
unsigned long int humbles[5843];
int humble;

void AddtoList(unsigned long int No)
{
int j,i=humble;
humble++;
for(;i>=1;i--)
{
if(No>humbles)
{
//Shifting
for(j=humble;j>=i+2;j--)
humbles[j]=humbles[j-1];

humbles[i+1]=No;
return ;
}
}

}

bool NotInList(unsigned long int No)
{
for(int i=1;i<=humble;i++)
if(humbles==No)
return false;
return true;
}

void GenerateHumbles()
{
unsigned long int n;
for(int i=2;i<=5842&&humbles<=30000;i++)
for(int j=i;j<=5842&&humbles[j]<=120000;j++)
{
n=humbles*humbles[j];
if(n>2000000000)break;
if(NotInList(n))
AddtoList(n);
}
}


int main()
{
int n;
humble=5;
humbles[1]=1;
humbles[2]=2;
humbles[3]=3;
humbles[4]=5;
humbles[5]=7;

GenerateHumbles();
while(cin>>n,n)
{
//The 1st humble number is 1.
if(!(n>10&&n<20))
if(n%10==1)
cout<<"The "<<n<<"st"<<" humble number is "<<humbles[n]<<".\n";
else if(n%10==2)
cout<<"The "<<n<<"nd"<<" humble number is "<<humbles[n]<<".\n";
else if(n%10==3)
cout<<"The "<<n<<"rd"<<" humble number is "<<humbles[n]<<".\n";
else
cout<<"The "<<n<<"th"<<" humble number is "<<humbles[n]<<".\n";
else
cout<<"The "<<n<<"th"<<" humble number is "<<humbles[n]<<".\n";
}
return 0;
}
[/cpp]

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Tue Oct 19, 2004 2:51 pm

if u can think of it .. u can do it in software.

User avatar
habibiamin
New poster
Posts: 8
Joined: Tue Oct 12, 2004 1:54 pm
Location: Iran-Tehran
Contact:

Thanks

Post by habibiamin » Wed Oct 20, 2004 9:34 am

Thank you...I got AC ! :D

willy
New poster
Posts: 11
Joined: Fri Aug 01, 2003 2:20 pm
Location: Singapore

443 Humble Numbers WA

Post by willy » Mon Nov 01, 2004 5:10 pm

[Deleted]
Last edited by willy on Wed Nov 17, 2004 5:33 am, edited 1 time in total.

willy
New poster
Posts: 11
Joined: Fri Aug 01, 2003 2:20 pm
Location: Singapore

Post by willy » Mon Nov 01, 2004 5:14 pm

btw,
[c]
if (times[1] < times[0])
times[1] = 1;
times[2] = humble * 5;
if (times[2] < times[1] || times[2] < times[0])
times[2] = 1;
times[3] = humble*7;
if (times[3] < times[2] || times[3] < times[1] || times[3] < times[0])
[/c]

is for checking for overflow

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Nov 17, 2004 5:15 am

:) Hi willy, let me give u a good news, ur code got Accepted after I add something in it......check it out......

if(n%100==11 || n%100==12 ||n%100==13)
{
printf("th");
}

add it in the code and get acc and ofcourse make it the 1st case, I mean put it in the top......

Goodluck....... :)
Jalal : AIUB SPARKS

willy
New poster
Posts: 11
Joined: Fri Aug 01, 2003 2:20 pm
Location: Singapore

Post by willy » Wed Nov 17, 2004 5:26 am

thanks!

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

443 WA i dont know why. smbd plz help

Post by Ankur Jaiswal » Sun May 07, 2006 12:22 pm

I am getting WA in this problem although i have done everything rite.
All the suffixes are correct and the values for different inputs is also correct.
But I dont know why its giving WA.
Plz help me.
Last edited by Ankur Jaiswal on Sun May 07, 2006 8:51 pm, edited 1 time in total.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Sun May 07, 2006 5:44 pm

Try this input:

Code: Select all

4121
0
Your output:

Code: Select all

The 4121st humble number is 268738560.
My AC program output:

Code: Select all

The 4121st humble number is 268435456.
Good luck... :D

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Post by Ankur Jaiswal » Sun May 07, 2006 6:07 pm

Thanx a lot.
But can u explain why this happened? My program shud generate the numbers which are 2^a*3^b*5^c*7*d.
But it isnt happening in some case. Can u explain why is this so?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sun May 07, 2006 6:51 pm

I'm not sure how it works in C++, but in Java some of those would overflow - it would multiply two ints and then cast them to a 64-bit (long long in your case)

I guess you check it here:

Code: Select all

if(pro>2000000000||pro<0) break;
but overflow doesn't have to give you a negative integer (I think) and it looks wrong for some reason :)

Maybe that's a problem?

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Post by Ankur Jaiswal » Sun May 07, 2006 7:04 pm

that means if i change the condition to (pro<(long long)2000000000 && pro<(long long)0)

then wud it be ok?

... neways i think that this cud have been the problem bcoz i changed my variables from int to long long and now the program gives correct output.
i havent submitted it yet but now it might be accepted.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon May 08, 2006 7:48 am

Cast to long long *before* multiplying and then it should work.

Of course, if you use long longs everywhere, it eliminates that problem.

Post Reply

Return to “Volume 4 (400-499)”