Page 1 of 1

12556 - "Center" of perimeter midpoints

Posted: Tue May 20, 2014 10:16 am
by test_tset
the data set in the description "For example, if we can't use 2~6, the best solution is:2/3=1/7+1/8+1/9+1/12+1/14+1/18+1/24+1/28" is wrong,the correct answer is
2/3=1/7+1/9+1/10+1/12+1/14+1/15+1/18+1/28,I have checked this answer is correct...

by the way,I don't think 15s for 100 test cases is good,I think my code worked not too slow on every cases (worst about 1s,random about 1000 cases(including test cases in the hint),but the constant of my code is a little big,it will not run fast on small test cases.. I think constraint on case time limit is more reasonable

Re: uva 12558

Posted: Tue May 20, 2014 10:26 am
by test_tset
I have constraint on the upperbound of lcm of answer's denominator (1300*b),so I'm not sure if my code is real correct,here are some test data:

111
94 227 0
Case 1: 94/227=1/3+1/15+1/71+1/80585
94 227 1 3
Case 2: 94/227=1/4+1/9+1/19+1/4313+1/8172
94 227 2 3 4
Case 3: 94/227=1/5+1/6+1/30+1/71+1/80585
94 227 3 3 4 5
Case 4: 94/227=1/6+1/8+1/11+1/32+1/7264+1/7491
94 227 4 3 4 5 6
Case 5: 94/227=1/7+1/8+1/12+1/16+1/3178+1/10896
94 227 5 3 4 5 6 7
Case 6: 94/227=1/8+1/9+1/11+1/18+1/32+1/7264+1/7491
875 876 5 2 3 4 5 6
Case 7: 875/876=1/7+1/8+1/9+1/10+1/12+1/14+1/15+1/16+1/18+1/20+1/21+1/30+1/35+1/48+1/20440

this is test cases for k==0
Case 1: 875/876=1/2+1/3+1/7+1/48+1/1022+1/1168
Case 2: 437/438=1/2+1/4+1/5+1/21+1/10220
Case 3: 874/875=1/2+1/3+1/7+1/50+1/375
Case 4: 291/292=1/2+1/4+1/7+1/10+1/365+1/1022
Case 5: 873/875=1/2+1/4+1/5+1/21+1/10500
Case 6: 873/874=1/2+1/3+1/8+1/38+1/114+1/184
Case 7: 218/219=1/2+1/3+1/8+1/27+1/15768
Case 8: 872/875=1/2+1/3+1/7+1/50+1/2625
Case 9: 436/437=1/2+1/4+1/6+1/19+1/57+1/92
Case 10: 872/873=1/2+1/3+1/7+1/45+1/3395+1/6790
Case 11: 871/876=1/2+1/3+1/8+1/28+1/4088
Case 12: 871/875=1/2+1/3+1/14+1/15+1/50+1/250
Case 13: 871/874=1/2+1/3+1/10+1/23+1/69+1/190
Case 14: 871/873=1/2+1/4+1/8+1/9+1/97+1/776
Case 15: 871/872=1/2+1/3+1/8+1/28+1/218+1/4578
Case 16: 145/146=1/2+1/3+1/10+1/18+1/365+1/657
Case 17: 174/175=1/2+1/3+1/10+1/21+1/75
Case 18: 435/437=1/2+1/4+1/5+1/46+1/76+1/95
Case 19: 290/291=1/2+1/4+1/6+1/13+1/388+1/2522
Case 20: 435/436=1/2+1/4+1/5+1/21+1/11445
Case 21: 870/871=1/2+1/4+1/6+1/13+1/201+1/3484
Case 22: 869/876=1/2+1/5+1/6+1/8+1/2920
Case 23: 869/875=1/2+1/3+1/7+1/70+1/375
Case 24: 869/874=1/2+1/3+1/10+1/23+1/114+1/115
Case 25: 869/873=1/2+1/3+1/8+1/27+1/20952
Case 26: 869/872=1/2+1/5+1/6+1/8+1/327+1/545
Case 27: 869/871=1/2+1/4+1/6+1/13+1/268+1/2613
Case 28: 869/870=1/2+1/4+1/6+1/15+1/116+1/145
Case 29: 217/219=1/2+1/3+1/7+1/73+1/1022
Case 30: 124/125=1/2+1/4+1/5+1/25+1/500
Case 31: 434/437=1/2+1/4+1/5+1/46+1/92+1/95
Case 32: 868/873=1/2+1/3+1/9+1/22+1/291+1/1067
Case 33: 217/218=1/2+1/3+1/8+1/27+1/23544
Case 34: 868/871=1/2+1/3+1/9+1/26+1/78+1/1206
Case 35: 434/435=1/2+1/4+1/5+1/21+1/12180
Case 36: 868/869=1/2+1/4+1/5+1/22+1/316+1/4345
Case 37: 289/292=1/2+1/3+1/8+1/32+1/7008
Case 38: 867/875=1/2+1/3+1/7+1/125+1/150
Case 39: 867/874=1/2+1/3+1/7+1/133+1/231+1/253
Case 40: 289/291=1/2+1/3+1/7+1/97+1/194+1/679
Case 41: 867/872=1/2+1/3+1/8+1/28+1/4578
Case 42: 867/871=1/2+1/4+1/6+1/13+1/804+1/1742
Case 43: 289/290=1/2+1/3+1/10+1/16+1/1392
Case 44: 867/869=1/2+1/3+1/7+1/48+1/1659+1/13904
Case 45: 867/868=1/2+1/4+1/6+1/14+1/93
Case 46: 433/438=1/2+1/4+1/6+1/14+1/2044
Case 47: 866/875=1/2+1/4+1/5+1/28+1/250
Case 48: 433/437=1/2+1/3+1/9+1/23+1/342
Case 49: 866/873=1/2+1/3+1/10+1/18+1/485+1/970
Case 50: 433/436=1/2+1/4+1/7+1/10+1/3815
Case 51: 866/871=1/2+1/4+1/6+1/13+1/2652+1/3417
Case 52: 433/435=1/2+1/3+1/7+1/70+1/203

please help me to check if it is correct