11226 - Reaching the fix-point.

[helloneo]

Thanks..
Got AC..~

[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

[Jan]

Your cases are correct.

[sjn]

Thanks Jan!

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

[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

[sjn]

ACed finally!
Very silly bug

thank you for all your helps!

[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.

[mukit]

Ok, I found my bug. It was a silly one

[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