11669 - Non Decreasing Prime Sequence

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

Moderator: Board moderators

Post Reply
User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

11669 - Non Decreasing Prime Sequence

Post by tryit1 » Thu Sep 17, 2009 2:12 am

Can someone post input outputs for the following and additional cases ?

I get WA

Code: Select all

 38
2 10 1
2 10 2
2 10 3
2 10 4
2 10 5
2 10 6
2 10 7
2 10 8
2 10 9
2 20 10
2 500 35
2 1000 500
2 10000 5000
2 100000 50000
2 1000000 500000
2 1000000 99999
2 1000000 999993
2 1000000 999994
2 1000000 999995
2 1000000 999996
2 1000000 999997
2 1000000 999998
2 1000000 999999
1000 1000000 1000
2 100 98
2 100 99
355 678 300
855 2588 900
1055 13433 10000
2 20 6
2 20 7
2 20 8
3 20 6
3 20 7
3 20 8
5 20 6
5 20 7
5 20 8

Code: Select all

Case 1: 2
Case 2: 3
Case 3: 5
Case 4: 7
Case 5: 2 2
Case 6: 2 3
Case 7: 2 5
Case 8: 3 3
Case 9: 2 2 2
Case 10: 2 3
Case 11: 149
Case 12: 2 2 137
Case 13: 2 19 101
Case 14: 3 41 79
Case 15: 7 157 599
Case 16: 2 243431
Case 17: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Case 18: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3
Case 19: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5
Case 20: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7
Case 21: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3
Case 22: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5
Case 23: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3
Case 24: 9421
Case 25: 2 2 2 2 2 2
Case 26: 2 2 2 2 2 3
Case 27: 2 3 3 5 7
Case 28: 2 11 109
Case 29: 2 2 2 2 313
Case 30: 13
Case 31: 17
Case 32: 19
Case 33: 17
Case 34: 19
Case 35: 2 2
Case 36: 19
Case 37: 2 3
Case 38: 2 5

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11669 - Non Decreasing Prime Sequence

Post by mak(cse_DU) » Thu Sep 17, 2009 12:10 pm

To "tryit1"
I think there have no critical input for that problem.
If you structure correctly then you will get AC.
See your code carefully. I think you have typo error.

see case 15 and below and compare it to yours.

AC output to tryit1:

Code: Select all

Case 1: 2
Case 2: 3
Case 3: 5
Case 4: 7
Case 5: 2 2
Case 6: 2 3
Case 7: 2 5
Case 8: 3 3
Case 9: 2 2 2
Case 10: 2 3
Case 11: 149
Case 12: 2 2 137
Case 13: 2 19 101
Case 14: 3 41 79
Case 15: 7 157 607
Case 16: 2 243437
Case 17: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5
Case 18: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7
Case 19: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3
Case 20: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5
Case 21: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3
Case 22: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Case 23: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3
Case 24: 9433
Case 25: 2 2 2 2 2 2
Case 26: 2 2 2 2 2 3
Case 27: 2 3 3 5 7
Case 28: 2 11 109
Case 29: 2 2 2 2 313
Case 30: 13
Case 31: 17
Case 32: 19
Case 33: 17
Case 34: 19
Case 35: 2 2
Case 36: 19
Case 37: 2 3
Case 38: 2 5
Hints to someone to solve this problem.
Use segment tree data structure for query in log(N) time.
Generate prime factor then sort and then use segment tree.
hope it will help.
Mak
Help me PLZ!!

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11669 - Non Decreasing Prime Sequence

Post by tryit1 » Thu Sep 17, 2009 4:18 pm

thanks, yes it was an off by 1 , i forgot the powers of 19, only calculated until 18.

Post Reply

Return to “Volume 116 (11600-11699)”