PlanningTrips
SRM 799 · 2021-02-04 · by IH19980412
Problem Statement
Kaede is going to travel to N locations. She has already planned everything and she knows all the travel costs.
The travel costs for Kaede's trip turned out to be quite special: the costs of all tickets are powers of the same integer a.
More precisely, the ticket to location i costs anum[i] (that is, a to the num[i]-th power) units of money.
Kaede must pay for all N tickets at the same time, and her payment must also be a power of a.
To avoid paying more than necessary, she now needs to find smallest non-negative integer k such that a payment of ak (a to the k-th power) is enough to pay for all the tickets. In other words, ak must be greater than or equal to the total cost of all tickets, and k must be as small as possible.
You are given the
Constraints
- a will be between 2 and 10^9, inclusive.
- N will be between 1 and 50, inclusive.
- num will contain exactly N elements.
- Each element in num will be between 0 and 10^9, inclusive.
10
{5, 6, 3}
Returns: 7
The individual trips have costs 10^5 = 100000, 10^6 = 1000000, and 10^3 = 1000. The total cost of all trips is 1101000. The smallest k such that 10^k is enough to pay for all the trips is k=7: 10^7 >= 1101000.
2
{13, 13}
Returns: 14
Each of the two tickets costs 2^13. The total cost of tickets is 2^13 + 2^13 = 2 * 2^13 = 2^14. Kaede can pay exactly this amount, so the smallest k in this situation is k = 14.
2
{13, 0, 13}
Returns: 15
The total cost of all three tickets in this example is 2^14 + 1. Kaede should pay 2^15.
2
{698646145,698646146,698646146,698646145,698646144,698646147,698646144,698646146,698646147,698646145,698646146,698646144,698646146,698646145,698646147,698646146,698646147,698646147,698646146,698646145,698646146,698646146,698646147,698646146,698646147,698646144,698646145,698646146,698646146,698646147,698646144,698646146,698646146,698646145,698646147,698646144,698646144,698646145,698646146,698646145,698646146,698646147,698646145,698646146,698646146,698646145,698646146,698646147,698646147,698646146}
Returns: 698646152
2
{789856736,789856735,789856738,789856732,789856733,789856737,789856736,789856734,789856736,789856735,789856733,789856737,789856734,789856737,789856736,789856733,789856737,789856732,789856733,789856732,789856736,789856738,789856733,789856738,789856735,789856736,789856737,789856732,789856732,789856732,789856735,789856736,789856733,789856736,789856735,789856736,789856737,789856734,789856734,789856738,789856733,789856735,789856735,789856732,789856735,789856733,789856737,789856738,789856738,789856734}
Returns: 789856742
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PlanningTrips with a public method int find(int a, vector<int> num) · 78 test cases · 2 s / 256 MB per case