10427 - Naughty Sleepy Boys

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

Moderator: Board moderators

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

10427 - Naughty Sleepy Boys

Post by shamim »

I am getting WA.

Could some one give me some critical test cases.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Sample:

Code: Select all

3
9
10
11
10000
50000
1000000000
5135136
351357
88456345
34135141
513341
13516167
6252345
767657
613566
5768678
63453
253478
95465462
513513511
5151356786
875673562
Results:

Code: Select all

3
9
1
0
7
1
7
4
4
1
7
0
2
0
4
0
6
1
1
2
0
5
6

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

will any one tell me the process or algorithm used befrore the problem solving..
i will be greatful..
--
anupam
"Everything should be made simple, but not always simpler"

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

for 10427..

Post by Whinii F. »

I think you don't need any "special" approaches to solve this problem.

Try analyzing it like this:

For numbers in range 1 ~ 9 (inclusive), there are 9 such numbers, each containing 1 digits.
For numbers in range 10 ~ 99 , there are 90 such numbers, each containing 2 digits.
For numbers in range 100 ~ 999 , there are 900 such numbers, each containing 3 digits.

Now you can easily come to
For numbers in range 10^(k-1) ~ 10^k - 1, there are 9 * 10^(k-1) such numbers, each containing k digits.. (If you try it, you'll find out each of the numbers in the resulting sequence will not be that big, so you don't need any longint operations.)

So for given n, you can easily calculate which digit of which number does it point to.

Good luck =)

[edit] corrected my mistake ;)
JongMan @ Yonsei

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. »

I got WA....

I've tested again my code and it's doing just fine until the input <=10000000 coz there's no output generated.....

can you help me with this problem?
here are my code :
[c]
#include<stdio.h>

#include<stdio.h>

int seek(long int n);

int main()
{ long int a;
scanf("%li",&a);
printf("%d",seek(a));
return 1;
}

int seek(long int n)
{ long int i=0,j,k=0;

while(k<n)
{ i+=1;
if(i<10)
{ j=(i);
k+=1;
if(k>=n) break;
}
else if(i<100)
{ j=(i/10);
k+=1;
if(k>=n) break;
j=(i%10);
k+=1;
if(k>=n) break;
}
else if(i<1000)
{ j=(i/100);
k+=1;
if(k>=n) break;
j=((i%100)/10);
k+=1;
if(k>=n) break;
j=((i%100)%10);
k+=1;
if(k>=n) break;
}
else if(i<10000)
{ j=(i/1000);
k+=1;
if(k>=n) break;
j=((i%1000)/100);
k+=1;
if(k>=n) break;
j=(((i%1000)%100)/10);
k+=1;
if(k>=n) break;
j=(((i%1000)%100)%10);
k+=1;
if(k>=n) break;
}
else if(i<100000)
{ j=(i/10000);
k+=1;
if(k>=n) break;
j=((i%10000)/1000);
k+=1;
if(k>=n) break;
j=(((i%10000)%1000)/100);
k+=1;
if(k>=n) break;
j=((((i%10000)%1000)%100)/10);
k+=1;
if(k>=n) break;
j=((((i%10000)%1000)%100)%10);
k+=1;
if(k>=n) break;
}
else if(i<1000000)
{ j=(i/100000);
k+=1;
if(k>=n) break;
j=((i%100000)/10000);
k+=1;
if(k>=n) break;
j=(((i%100000)%10000)/1000);
k+=1;
if(k>=n) break;
j=((((i%100000)%10000)%1000)/100);
k+=1;
if(k>=n) break;
j=(((((i%100000)%10000)%1000)%100)/10);
k+=1;
if(k>=n) break;
j=(((((i%100000)%10000)%1000)%100)%10);
k+=1;
if(k>=n) break;
}
else if(i<10000000)
{ j=(i/1000000);
k+=1;
if(k>=n) break;
j=((i%1000000)/100000);
k+=1;
if(k>=n) break;
j=(((i%1000000)%100000)/10000);
k+=1;
if(k>=n) break;
j=((((i%1000000)%100000)%10000)/1000);
k+=1;
if(k>=n) break;
j=(((((i%1000000)%100000)%10000)%1000)/100);
k+=1;
if(k>=n) break;
j=((((((i%1000000)%100000)%10000)%1000)%100)/10);
k+=1;
if(k>=n) break;
j=((((((i%1000000)%100000)%10000)%1000)%100)%10);
k+=1;
if(k>=n) break;
}
else if(i<100000000)
{ j=(i/10000000);
k+=1;
if(k>=n) break;
j=((i%10000000)/1000000);
k+=1;
if(k>=n) break;
j=(((i%10000000)%1000000)/100000);
k+=1;
if(k>=n) break;
j=((((i%10000000)%1000000)%100000)/10000);
k+=1;
if(k>=n) break;
j=(((((i%10000000)%1000000)%100000)%10000)/1000);
k+=1;
if(k>=n) break;
j=((((((i%10000000)%1000000)%100000)%10000)%1000)/100);
k+=1;
if(k>=n) break;
j=(((((((i%10000000)%1000000)%100000)%10000)%1000)%100)/10);
k+=1;
if(k>=n) break;
j=(((((((i%10000000)%1000000)%100000)%10000)%1000)%100)%10);
k+=1;
if(k>=n) break;
}
}

return j;
}
[/c]

shireishou
New poster
Posts: 1
Joined: Thu Jun 05, 2003 2:12 pm
Contact:

Post by shireishou »

:( I'm sad, I use 3 algortym to solve this problem but all failed. I iuse algorythm like R.Z. BUt even though the program outp[ut coorect, but judge resu;lt is, "TIME LIMIT EXEEDED!" Hixs..... :cry:
I also created the new one.. like this... maybe I made a mistakes. But whete? Can U help me?

#include <stdio.h>

void main()
{
unsigned long int x,xx,input,ctr=0,ctr2=0;
char str[10],flag='t';
scanf("%lu",&input);
for(x=1;x<=input;x++)
{
sprintf(str,"%lu",x);
for(xx=0;str[xx];xx++)
{
ctr++;
ctr2++;
if(ctr==input) { flag='f'; break; }
}
if(flag=='f') break;
else ctr2=0;
}
printf("hasil %c \n",str[ctr2-1]);
}
help meeee

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm

Post by zubair »

you can not solve 10427 in that way. it will definitely get "tle".
u should follow Whinii F.'s given method. u can count the total number of digit by the following method:

For numbers in range 1 ~ 9 (inclusive), there are 9 such numbers, each containing 1 digits.
For numbers in range 10 ~ 99 , there are 90 such numbers, each containing 2 digits.
For numbers in range 100 ~ 999 , there are 900 such numbers, each containing 3 digits.
then you can count the digit number by just multiplying the number of digit
with the total number between the range. i.e total number of digits between 10~99 is 180. so you should calculate total number of digit
as long as it does not exceed the given value then you can easily find the number in which the nth digit will appear.
zubair-CUET old sailor

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

i remember i made a formula for finding the number when i got ac. but now i forgot that. if you need that you can me.

chicapi
New poster
Posts: 6
Joined: Thu Apr 24, 2003 9:08 pm
Location: Buenos Aires

output limit?!

Post by chicapi »

I found an easy way to calculate the answer...
BUTTTT...
Your program output is greater (4236247 bytes) than the maximum allowed for any problem by this judge (4194304 bytes).
You must interprete this as a Wrong Answer (in fact, is wrong!).
By some reason your program is writing an unlimited output.
I don't understand WHY because I include this sentence:
[cpp]if (cifra <10 )printf("%d\n",cifra);[/cpp]
cifra is the digit you are looking for.
I can include my code but I don't know if that's legal?!
byebyes
maru 3.1415926

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Usually, when you get OLE, it's because you don't end reading the input... print how you read the input..

chicapi
New poster
Posts: 6
Joined: Thu Apr 24, 2003 9:08 pm
Location: Buenos Aires

dont kill me plz

Post by chicapi »

maybe in windows it's different (?) because I have no problem with this:

[cpp]long int n;
scanf("%d",&n);[/cpp]

thank you. :D
maru 3.1415926

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

long int is %ld, I think, but ya, you still got to check how you terminate your program.. that's probably the reason..

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

Zubire wrote
you can count the digit number by just multiplying the number of digit
with the total number between the range. i.e total number of digits between 10~99 is 180. so you should calculate total number of digit
as long as it does not exceed the given value then you can easily find the number in which the nth digit will appear
To solve this problem, first you need to find the number which digit will be print. to do this do some sample calculation i.e.,
from 1 to 10 the number are one digit
from 11 to 190 the number are two digit
and so on...

then find the number.

to do this, just make a simple calculation.

M H Rasel
CUET Old Sailor

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

Zubire wrote
you can count the digit number by just multiplying the number of digit
with the total number between the range. i.e total number of digits between 10~99 is 180. so you should calculate total number of digit
as long as it does not exceed the given value then you can easily find the number in which the nth digit will appear
To solve this problem, first you need to find the number which digit will be print. to do this do some sample calculation i.e.,
from 1 to 10 the number are one digit
from 11 to 190 the number are two digit
and so on...

then find the number.

to do this, just make a simple calculation.

M H Rasel
CUET Old Sailor

chicapi
New poster
Posts: 6
Joined: Thu Apr 24, 2003 9:08 pm
Location: Buenos Aires

Post by chicapi »

I got the same error with another problem, so I figured out!!!
[cpp]pp = fgets(s,100,stdin);
if (pp== NULL) return 0;
sscanf (s,"%ld",&n);[/cpp]
That was the problem... I didn't break the rutine if there was no input...
Thank you all... :wink:
maru 3.1415926

Post Reply

Return to “Volume 104 (10400-10499)”