Page 2 of 2

Posted: Wed Jun 13, 2007 6:40 pm
by helloneo
Thanks.. :-)
Got AC..~

Posted: Wed Jun 13, 2007 6:55 pm
by sjn
can anybody check it for me?

Code: Select all

Input:
49
2 10
11 20
90000 4560 
489000 94561
334142 334142
334143 500000
2 334141
2 100000
100000 200000
200000 300000
300000 400000
400000 500000
2 100
100 200
200 300
300 400
400 500
500 600
600 700
700 800
800 900
900 1000
1000 1100
1100 1200
1200 1300
1300 1400
1400 1500
1500 1600
1600 1700
1700 1800
1800 1900
1900 2000
2000 2100
2100 2200
2200 2300
2300 2400
2400 2500
2500 2600
2600 2700
2700 2800
2800 2900
2900 3000
3000 3100
3100 3200
3200 3300
3300 3400
3400 3500
3500 3600
3600 3700
Output:
Case #1:
3
Case #2:
4
Case #3:
12
Case #4:
14
Case #5:
14
Case #6:
12
Case #7:
13
Case #8:
12
Case #9:
13
Case #10:
12
Case #11:
14
Case #12:
12
Case #13:
6
Case #14:
7
Case #15:
7
Case #16:
8
Case #17:
8
Case #18:
7
Case #19:
8
Case #20:
7
Case #21:
8
Case #22:
8
Case #23:
8
Case #24:
7
Case #25:
9
Case #26:
7
Case #27:
7
Case #28:
9
Case #29:
7
Case #30:
9
Case #31:
8
Case #32:
9
Case #33:
8
Case #34:
7
Case #35:
8
Case #36:
8
Case #37:
8
Case #38:
9
Case #39:
9
Case #40:
8
Case #41:
8
Case #42:
7
Case #43:
8
Case #44:
8
Case #45:
8
Case #46:
7
Case #47:
8
Case #48:
8
Case #49:
8

Posted: Wed Jun 13, 2007 8:57 pm
by Jan
Your cases are correct.

Posted: Thu Jun 14, 2007 4:25 am
by sjn
Thanks Jan!

but then, any other tricky I/Os?
really have no idea why keeping WA :(

Posted: Thu Jun 14, 2007 9:50 am
by ayeshapakhi
hello...

try these.

input

Code: Select all

10
2 2
3 2
2 3
2 100
100 101
300 300
1000 1000
10001 1000
500000 500000
100 500000
output

Code: Select all

Case #1:
1
Case #2:
1
Case #3:
1
Case #4:
6
Case #5:
5
Case #6:
2
Case #7:
4
Case #8:
11
Case #9:
3
Case #10:
14

Posted: Thu Jun 14, 2007 3:08 pm
by sjn
ACed finally!
Very silly bug :oops:

thank you for all your helps! :wink:

Re: 11226 - Reaching the fix-point

Posted: Mon Jan 05, 2009 8:15 pm
by mukit
hi I am getting WA in this problem
please give some that can fix my code. I've already tested with all board I/O.

Code: Select all

Cur after AC
Thank's in advance.

Re: 11226 - Reaching the fix-point

Posted: Tue Jan 06, 2009 3:32 pm
by mukit
Ok, I found my bug. It was a silly one :wink:

Re: 11226 - Reaching the fix-point.

Posted: Wed May 06, 2015 1:14 am
by amrondonp
I got AC in 0.355s Without using shieve.
Fisrt- Found a way of factoring a number, I do the TRIAL DIVISION, (just like factoring by hand) anyway. I think that if you could do it in less time, would be great.
Given the factoring, computing alpha(n) is easy. (I did it in the same function)

Second, Memorize alpha and beta (Use dynamic programming) beta can be computed recursevely. the base case is when n==alpha(n), beta(n)=1 otherwise beta(n) = beta(alpha(n))+1
you memorize that so you don't have to re-compute all the stuff.

I saw that linear search is sufficent. so try it in the array "beta" generated.

But i tought that linear search wouldn't work so I made a "SEGMENT TREE". A segment tree is a wonderful datastructure which is iniatialized in O(n) and the querys are done in O( log(n) )

Hope this will help you.

I attach some useful links;:
Segment tree: http://www.geeksforgeeks.org/segment-tr ... mum-query/
Factoring and trial division: https://www.topcoder.com/community/data ... -function/
Dynamic Programing: https://www.youtube.com/watch?v=OQ5jsbhAv_M