SequenceSums

TCO09 Round 1 · 2009-02-24 · by legakis

TCO09 Round 1 · 2009-02-24 · by legakis · Math, Simple Search, Iteration

Show categories

Class Name: SequenceSums

Return Type: int[]

Method Name: sequence

Arg Types: (int, int)

Problem Statement

Given a number N and a length L, find the shortest list of at least L consecutive non-negative integers whose sum is N. If the length of that list is 100 or smaller, return the sequence as a int[] in ascending order. If there is no such sequence or its length is larger than 100, return { }.

Constraints

N will be between 1 and 1000000000, inclusive.
L will be between 2 and 100, inclusive.

Examples

18
2
Returns: {5, 6, 7 }

18 can be expressed as 5 + 6 + 7 or 3 + 4 + 5 + 6. Both of these lists contain more than 2 elements, so you should return the shortest among them.

18
3
Returns: {5, 6, 7 }

18
4
Returns: {3, 4, 5, 6 }

Now the correct answer is 3 + 4 + 5 + 6 because 5 + 6 + 7 contains less than 4 elements.

18
5
Returns: { }

Both possible presentations of 18 contain less than 5 elements, so there's no answer for this case.

2
4
Returns: { }

4950
100
Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99 }

Exactly 100 elements

104950
26
Returns: {1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011, 1012, 1013, 1014, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035, 1036, 1037, 1038, 1039, 1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 1048, 1049, 1050, 1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063, 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080, 1081, 1082, 1083, 1084, 1085, 1086, 1087, 1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095, 1096, 1097, 1098, 1099 }

Again 100 elements

10)

5050
26
Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100 }

and again 100

11)

5151
52
Returns: { }

101 would work, but in fact no solution

12)

2
2
Returns: { }

12-17 are very small cases

18)

636291
27
Returns: {16726, 16727, 16728, 16729, 16730, 16731, 16732, 16733, 16734, 16735, 16736, 16737, 16738, 16739, 16740, 16741, 16742, 16743, 16744, 16745, 16746, 16747, 16748, 16749, 16750, 16751, 16752, 16753, 16754, 16755, 16756, 16757, 16758, 16759, 16760, 16761, 16762, 16763 }

18-27 are random yes cases

28)

451
30
Returns: { }

28-32 are random no cases

33)

561202155
12
Returns: {37413470, 37413471, 37413472, 37413473, 37413474, 37413475, 37413476, 37413477, 37413478, 37413479, 37413480, 37413481, 37413482, 37413483, 37413484 }

33-42 are random yes with large N

43)

101316086
69
Returns: { }

43-44 are random no cases with large N

Submissions are judged against all 91 archived test cases, of which 14 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SequenceSums with a public method vector<int> sequence(int N, int L) · 91 test cases · 2 s / 256 MB per case