10922 - 2 the 9s

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

Moderator: Board moderators

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

10922 - 2 the 9s

Post by Larry » Sat Oct 01, 2005 6:59 pm

I keep getting WA, so I'm not sure if I'm understanding it right.

f(999999999999999999999) =
f(189) + 1 =
f(18) + 2 =
f(9) + 3

and since 9 has 9-degree 1 (as given), doesn't that contradict the first case?

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Re: 10922 - 2 the 9s

Post by SRX » Sat Oct 01, 2005 7:46 pm

Anonymous wrote:
Larry wrote:I keep getting WA, so I'm not sure if I'm understanding it right.

f(999999999999999999999) =
f(189) + 1 =
f(18) + 2 =
f(9) + 3

and since 9 has 9-degree 1 (as given), doesn't that contradict the first case?
it should be
It sholud be
when input 999999999999999999999
We count f (189)
sorry , I forgot log in

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

Post by Larry » Sat Oct 01, 2005 11:35 pm

Not sure what you mean...

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Re: 10922 - 2 the 9s

Post by kp » Sun Oct 02, 2005 12:43 am

Larry wrote:I keep getting WA, so I'm not sure if I'm understanding it right.

f(999999999999999999999) =
f(189) + 1 =
f(18) + 2 =
f(9) + 3

and since 9 has 9-degree 1 (as given), doesn't that contradict the first case?
Just compute the sum recursively while it >9.

But, to know that sum of 9 is 9 you should compute it once,
thats why f('9') = 1.

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

Post by Larry » Sun Oct 02, 2005 2:04 am

Thanks. I changed my input reading from gets to scanf and it worked. I guess there were spaces somewhere..

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Oct 02, 2005 4:15 am

Larry wrote:Thanks. I changed my input reading from gets to scanf and it worked. I guess there were spaces somewhere..
no , use gets can get ac

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

scanf is enough

Post by wook » Sun Oct 02, 2005 5:11 am

Code: Select all

scanf("%s", temp);
is enough.


btw, using gets, just ignoring non-digit characters, it works also :)
Sorry For My Poor English.. :)

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

Post by Larry » Sun Oct 02, 2005 11:45 am

You can always emulate scanf with gets, but the point is that's the only change I made, and got AC. I presume everything is in [0-9], so if there's a space in the beginning or the end of a line, it'll be wrong for me.. and seems to be the case.

Just a heads up to others. I'm sure you can solve it using gets, just that then you'll have another case to worry about..

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

10922 - 2 the 9s

Post by deena sultana » Mon Jun 19, 2006 6:31 pm

friends, my 10922 code got TLE.

how can speed up my code? any suggestion?

What i did, the summary is:
1. first i take all inputs in str.
2. then add themi div, and chek if (div%9==0);
3. if not then "not diveded by 9"
4.if yes then calculate the 9-degree by calling the summation n copy function untill div>9.
thats all.

now, i m looking 4 d kind person, who like 2 help me.

Code: Select all

CODE:


	
Last edited by deena sultana on Mon Jun 19, 2006 7:47 pm, edited 3 times in total.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Mon Jun 19, 2006 7:11 pm

use code tag so that codes are easily readable.

use "search" button, search for 10922, you will find already discusses topics about the problem

do not use

Code: Select all

for(int i=0;i<strlen(str);i++)
this is toooooooo slow. use

Code: Select all

for(int i = 0; str[i] ; i++)
or

Code: Select all

len = strlen(str);
for(int i = 0; i < len; i++)
your process call the function strlen(), "lenght of the string" times.

remove the copy() function
sprintf(stDiv, "%d", div); will do what you want
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Mon Jun 19, 2006 7:55 pm

Deena,
its an easy problem. Just do with Recursive method. OK
Example:

Code: Select all

999999999999999999999  = S(189) so its 1
then
189 = S(18) so its 2
then 
18 = S(9) so its 3

hope you got it. ;)
and also will get accepted.
Last edited by asif_rahman0 on Mon Jun 19, 2006 7:56 pm, edited 1 time in total.

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

thnx

Post by deena sultana » Mon Jun 19, 2006 7:56 pm

Thank u so much, ayon.
stupid strlen() was d culprit.
I get AC.

THANKS AGAIN.

take care.

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

Post by deena sultana » Mon Jun 19, 2006 8:05 pm

Asif, thanx 4 ur post.
i get d prob AC, by following Ayon's suggestion.
Thanks anyway. u people r so helpful.
take care.

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm

10922 - 2 the 9s

Post by <:3)~~ » Wed Dec 13, 2006 4:43 pm

they are saying that we have to find recursion depth..
and that 9 has a depth 1.
9-->1.
Now consider
99999...(21 9's)--->189--->18---->9--->1.
the depth shuld be 4.
but they are saying it to b 3.
Also consider 108.
108--->9--->1.
i think it should be 2.
Am i right???

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Dec 13, 2006 7:57 pm

The problem states...
A well-known trick to know if an integer N is a multiple of nine is to compute the sum S of its digits. If S is a multiple of nine, then so is N
I interpreted this line as 'take a number and sum its digits, and find the depth using that sum'.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 109 (10900-10999)”