EnergySource
TCO19 SRM 738 · 2018-09-29 · by wild_hamster
Problem Statement
You have been given a single source of energy. Its initial power is power.
You can split this source of energy into multiple smaller sources. You have to do this in a series of one or more steps. In each step you can choose an existing energy source with some power P, choose a positive integer x that divides P, and split the chosen energy source into x separate new energy sources, each with power (P/x).
Given a collection of energy sources, its spread is the product of all their powers.
Find all different collections of energy sources that can be produced from the one given energy source.
Let A be the number of those collections.
Let B be the sum of all their spreads.
Return a
Constraints
- power will be between 1 and 90, inclusive.
3
Returns: {2, 4 }
There are two possible collections of energy sources: {3}: you keep the original source {1, 1, 1}: you split the original source into three smaller sources, each with power 1 The first collection has spread 3, the second collection has spread 1*1*1 = 1, thus the sum of their spreads is 3+1 = 4.
10
Returns: {9, 103 }
There are 9 distinct collections of energy sources that can be produced: {10}, {5, 5}, {2, 2, 2, 2, 2}, {5, 1, 1, 1, 1, 1}, {2, 2, 2, 2, 1, 1}, {2, 2, 2, 1, 1, 1, 1}, {2, 2, 1, 1, 1, 1, 1, 1}, {2, 1, 1, 1, 1, 1, 1, 1, 1} and {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}. Sum of their spreads (in the order in which we listed them) is 10+25+32+5+16+8+4+2+1=103
1
Returns: {1, 1 }
90
Returns: {98014, 45465390986863499 }
This is the largest possible input (but not necessarily the largest possible output). Is your solution fast enough?
48
Returns: {6978, 9697161469 }
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EnergySource with a public method vector<long long> countDifferentSources(int number) · 90 test cases · 2 s / 256 MB per case