11226 - Reaching the fix-point.

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

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Jun 13, 2007 6:40 pm

Thanks.. :-)
Got AC..~

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

Post by sjn » Wed Jun 13, 2007 6:55 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jun 13, 2007 8:57 pm

Your cases are correct.
Ami ekhono shopno dekhi...
HomePage

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

Post by sjn » Thu Jun 14, 2007 4:25 am

Thanks Jan!

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

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Thu Jun 14, 2007 9:50 am

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
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Thu Jun 14, 2007 3:08 pm

ACed finally!
Very silly bug :oops:

thank you for all your helps! :wink:

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

Re: 11226 - Reaching the fix-point

Post by mukit » Mon Jan 05, 2009 8:15 pm

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
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

Re: 11226 - Reaching the fix-point

Post by mukit » Tue Jan 06, 2009 3:32 pm

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

amrondonp
New poster
Posts: 5
Joined: Fri Apr 03, 2015 2:29 am

Re: 11226 - Reaching the fix-point.

Post by amrondonp » Wed May 06, 2015 1:14 am

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

Post Reply

Return to “Volume 112 (11200-11299)”