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

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Mon Jan 28, 2002 5:42 am

What's the way to do such as 1st 2rd 3rd etc.
mine is that if anything mod 100>10 and <20 then print th
else if anything mod 10=1 then print st,=2 then print nd,=3 then print rd,else print th
is that wrong?? here's my code:

#include <stdio.h>
#include <stdlib.h>

class chumble
{
public:
double num;
int flag;
chumble* link;
};

chumble* head;
chumble* ptr;
chumble* uptr;
chumble* temp;

int top=0;
double humblenum[5842];

void create();

void main()
{
long count=0;
int i=0;
head=(chumble *)malloc(sizeof(chumble));
head->num=1;
head->flag=0;
head->link=NULL;
for(i=0;i<5842;i++)
create();
while(scanf("%ld",&count)!=EOF)
{
if(count==0)
break;
printf("The %d",count);
// down is the output part
if(count%100>10&&count%100<20)
printf("th");
else
{
if(count%10==1)
printf("st");
else if(count%10==2)
printf("nd");
else if(count%10==3)
printf("rd");
else
printf("th");
}
printf(" humble number is %.0llf.n",humblenum[count-1]);
}
}


// create humble numbers
void create()
{
double tempnum;
int tempflag=0;
humblenum[top]=head->num;
tempnum=head->num;
tempflag=head->flag;
temp=head;
head=head->link;
free(temp);
switch(tempflag)
{
case 0:
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*2;
temp->flag=0;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*3;
temp->flag=1;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*5;
temp->flag=2;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*7;
temp->flag=3;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
break;
case 1:
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*3;
temp->flag=1;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*5;
temp->flag=2;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*7;
temp->flag=3;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
break;
case 2:
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*5;
temp->flag=2;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*7;
temp->flag=3;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
break;
case 3:
temp=(chumble *)malloc(sizeof(chumble));
temp->num=tempnum*7;
temp->flag=3;
temp->link=NULL;
ptr=head;
uptr=NULL;
while(1)
{
if(ptr==NULL)
break;
if(ptr->num>temp->num)
break;
uptr=ptr;
ptr=ptr->link;
}
if(ptr==head)
{
temp->link=head;
head=temp;
}
else
{
temp->link=ptr;
uptr->link=temp;
}
break;
}
top++;
}

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Mon May 06, 2002 11:45 am

you wouldnt print 11st, it should be 11th, and similarly for 12th and 13th

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Tue May 07, 2002 7:30 am

for "st" mod 10=1 and mod 100<>11
for "nd" mod 10=2 and mod 100<>12
for "rd" mod 10=3 and mod 100<>13

Alam
New poster
Posts: 4
Joined: Fri Apr 26, 2002 8:42 am

443

Post by Alam » Sat May 11, 2002 5:23 pm

what is the meaning of the following compiler error message

:( wh00854705_24.c:67: syntax error before `You'

[/c]

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

HI~~

Post by 10153EN » Sat May 11, 2002 5:33 pm

Can you post the codes from line 60 - line 70 (or the whole program) so that we can take a look at what's wrong with the error message at line 67??

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

443... Why I still got WA in presentation...(may be )

Post by Sanghack » Tue Jul 23, 2002 7:51 pm

I still got WA in 443...
I changed some ordinal expressions but i can't got accepted.
What am I wrong in this code?

If you want to solve this problem for yourself... then
d o n ' t s e e ~ -_-~




















Code: Select all

[cpp]//@JUDGE_ID: 21160AX 443 C++ "no precalc. "
//@BEGIN_OF_SOURCE_CODE
#include <stdio.h>

int result_array[5843];
int* X2_pointer=result_array;
int X2_value=2;
int* X3_pointer=result_array;
int X3_value=3;
int* X5_pointer=result_array;
int X5_value=5;
int* X7_pointer=result_array;
int X7_value=7;
int result_index=1;

int minimum(){
	int min1,min2;
	min1=(X2_value<X3_value)? X2_value:X3_value;
	min2=(X5_value<X7_value)? X5_value:X7_value;
	return (min1>min2)? min2:min1;
}

void main(){
	int n_th_index;
	int result;
//	freopen("hum.txt","rt",stdin);
	result_array[0]=1;
	while(true){
		scanf("%d\n",&n_th_index);
		if(n_th_index){
			if(result_array[n_th_index-1]==0){
				for(result_index=result_index;result_index<n_th_index;result_index++){
					result_array[result_index]=result=minimum();
					if(result==X2_value){
						X2_pointer++;
						X2_value=2*(*X2_pointer);
					}
					if(result==X3_value){
						X3_pointer++;
						X3_value=3*(*X3_pointer);
					}
					if(result==X5_value){
						X5_pointer++;
						X5_value=5*(*X5_pointer);
					}
					if(result==X7_value){
						X7_pointer++;
						X7_value=7*(*X7_pointer);
					}
				}
			}
			if((n_th_index%100)/10==1){	// ??1? then th.
				printf("The %dth humble number is %d.\n",n_th_index,result_array[n_th_index-1]);
			}
			else{
				switch(n_th_index%10){
				case 0:	case 4:	case 5:	case 6:	case 7:	case 8:	case 9:
					printf("The %dth humble number is %d.\n",n_th_index,result_array[n_th_index-1]);
					break;
				case 1:
					printf("The %dst humble number is %d.\n",n_th_index,result_array[n_th_index-1]);
					break;
				case 2:
					printf("The %dnd humble number is %d.\n",n_th_index,result_array[n_th_index-1]);
					break;
				case 3:
					printf("The %drd humble number is %d.\n",n_th_index,result_array[n_th_index-1]);
					break;
				}
			}
			//The 4th humble number is 
		}
		else break;
	}
}
//@END_OF_SOURCE_CODE[/cpp]

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

Post by cyfra » Tue Sep 17, 2002 5:31 pm

Hi!

I got your program Accepted without any changes ...

Change your mail client :wink:

Good Luck :wink:

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

443 - Humble Numbers

Post by awik_10 » Wed May 21, 2003 9:35 am

i want to ask, is there a way to get my program faster ? it used 10.031 seconds, it's more 0.031 seconds to get acc :( .
here is my code :

[c]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main()
{
int in;
double j;
unsigned long a,i,ctr=1,d,temp;
do{
scanf("%d",&in);
fflush(stdin);
}while(in<1||i>5842);
if(in==1) printf("%d ", in);
for(i=2;;i++)
{
d=i;
if(d%7==0)
{
for(j=11;j>0;j--)
{
temp=pow(7,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d%5==0)
{
for(j=13;j>0;j--)
{
temp=pow(5,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d%3==0)
{
for(j=19;j>0;j--)
{
temp=pow(3,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d%2==0)
{
for(j=30;j>0;j--)
{
temp=pow(2,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d==1)
{
ctr++;
}
if(ctr==in)
{
printf("%lu\n ",i);
break;
}
}
return 0;
}
[/c]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed May 21, 2003 9:58 am

try to generate all answers in table ....

BTW - you was killed after 10.03 sec, and it doesn't mean that your program stop after this time ....

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

runtime in humble number (443)

Post by awik_10 » Wed May 21, 2003 11:21 am

is there anyway to faster my program?? :( this is my code :

[c]

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int main()
{
int in[100],k=0,l,mod,m,n,o;
double j;
char seal[20],an[3];
unsigned long a,i,ctr=1,d,temp,z[100],ans;
for(;;)
{
scanf("%d",&in[k]);
fflush(stdin);
if(in[k]==0) break;
if(in[k]>0&&in[k]<=5842) k++;
}
for(l=0;l<k;l++)
{
if(in[l]==1)
{
z[l]=1;
continue;
}
ctr=1;
for(i=2;;i++)
{
d=i;
ans=i;
if(d%7==0)
{
for(j=11;j>0;j--)
{
temp=pow(7,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d%5==0)
{
for(j=13;j>0;j--)
{
temp=pow(5,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d%3==0)
{
for(j=19;j>0;j--)
{
temp=pow(3,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d%2==0)
{
for(j=30;j>0;j--)
{
temp=pow(2,j);
if(d%temp==0)
{
d=d/temp;
break;
}
}
}
if(d==1)
{
ctr++;
}
if(ctr==in[l])
{
z[l]=ans;
break;
}
}
}
for(l=0;l<k;l++)
{
printf("The %d",in[l]);
/* to take the two last number*/
m=in[l];
n=0;
/* converting from number to string but it's reverse*/
do{
mod=m%10;
seal[n]=mod+'0';
m=m/10;
n++;
}while(m!=0);
seal[n]=NULL;
/* take the last two number from the string */
n=0;
do{
an[n]=seal[1-n];
n++;
}while(n!=2);
an[n]=NULL;
n=0;
for(m=0;m<2;m++)
{
n=an[m]-'0'+n*10;
}
n=n/10;
if(in[l]%10<4&&n!=1)
{
switch(in[l]%10)
{
case 1 : printf("st "); break;
case 2 : printf("nd "); break;
case 3 : printf("rd "); break;
}
}
else
{
printf("th ");
}
if(in[l]==1)
{
printf("humble number is 1.\n");
}else
{
printf("humble number is %lu.\n",z[l]);
}
}
return 0;
}

[/c]

waiting for your replies
best regards,
awik

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Fri Oct 24, 2003 2:34 am

hi... may i asked some help ? i still got WA for 443 ...

strange ... logically, if you can solve 136 (ugly number ) u can solve 443 (humble number) ,right ? its almost the same...

can anybody give me a sample input and output ? thanx before ... :)
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Sat Oct 25, 2003 2:24 am

i've found it!!! its all about grammar in english.... i forgot 111 and 1111 is not follow by th but by st..... its also for 112, 1112, 113 and 1113.....
really embarassing :oops: ...... [/b]
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

Post by osan » Thu Nov 06, 2003 10:14 pm

Dear Shaka_RDR

i think you are wrong about
i've found it!!! its all about grammar in english.... i forgot 111 and 1111 is not follow by th but by st..... its also for 112, 1112, 113 and 1113..... really embarassing ......
Here some input and output of 443

Input
1
2
3
11
12
13
21
32
43
111
112
113
Output
The 1st humble number is 1.
The 2nd humble number is 2.
The 3rd humble number is 3.
The 11th humble number is 12.
The 12th humble number is 14.
The 13th humble number is 15.
The 21st humble number is 28.
The 32nd humble number is 54.
The 43rd humble number is 90.
The 111th humble number is 576.
The 112th humble number is 588.
The 113th humble number is 600.
this time WA
what next...............?

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Sat Nov 08, 2003 3:38 pm

Hi Shaka, have you solved it now??
if you have, could you mail me your program?
I solved this in 25ms and I'm still curious with those guys solved this prob in 0.000 sec.
Thanx!!

Btw, I'm binusian too (2006). And that picture in your avatar, is that Shaka the Virgo Gold Saint from the anime Saint Seiya??
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Mon Nov 10, 2003 6:40 am

osan wrote:Dear Shaka_RDR

i think you are wrong about
i've found it!!! its all about grammar in english.... i forgot 111 and 1111 is not follow by th but by st..... its also for 112, 1112, 113 and 1113..... really embarassing ......
Here some input and output of 443

Input
1
2
3
11
12
13
21
32
43
111
112
113
Output
The 1st humble number is 1.
The 2nd humble number is 2.
The 3rd humble number is 3.
The 11th humble number is 12.
The 12th humble number is 14.
The 13th humble number is 15.
The 21st humble number is 28.
The 32nd humble number is 54.
The 43rd humble number is 90.
The 111th humble number is 576.
The 112th humble number is 588.
The 113th humble number is 600.

sorry... my grammar is very very bad :oops: , but i've solved it now... thanx for the correction....

to Joseph : hi... dont you know me? we are classmates in 03PBT for PBO class (suharjito is the lecturer right?) my real name is ricky (so, remember me now ? the sleepy ast in the class ) i've send my code by private message ... and about my avatar, yes.. its shaka virgo gold saint... he is my fave characther (eventhough i'm scorpio, hehheh ) ...

to all : thanx for helping me...... :D
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Post Reply

Return to “Volume 4 (400-499)”