DivisorSequences
TCO19 Round 2B · 2019-04-15 · by misof
TCO19 Round 2B · 2019-04-15 · by misof · Dynamic Programming, Math
Problem Statement
Problem Statement
Given a positive integer N, find and return the length of the longest sequence a_1, ..., a_K of positive integers such that:
- The sum of all a_i is N.
- For each valid i, a_i < a_{i+1}.
- For each valid i, a_i divides a_{i+1}.
Constraints
- N will be between 1 and 2*10^9, inclusive.
Examples
0)
15 Returns: 4
The only optimal sequence is {1,2,4,8}. Clearly, 1 divides 2, 2 divides 4, 4 divides 8, and 1+2+4+8 = 15.
1)
12 Returns: 2
The are four distinct optimal sequences: {1,11}, {2,10}, {3,9}, and {4,8}. There is no valid sequence with more than two elements.
2)
34 Returns: 4
The only optimal sequence is {1, 3, 6, 24}.
3)
1 Returns: 1
4)
2 Returns: 1
Submissions are judged against all 139 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DivisorSequences with a public method int longest(int N) · 139 test cases · 2 s / 256 MB per case