ColorfulCoins
SRM 616 · 2013-12-22 · by tourist
Problem Statement
- The denominations are distinct positive integers.
- There is a coin type with denomination 1.
- For each pair of different coin types, the denomination of one coin type divides the denomination of the other one.
Coins of different denominations look exactly the same except that they have different colors. Each coin in Colorland has exactly one color. The coin colors follow these even simpler rules:
- All coins of the same type are of the same color.
- No two coins of different types are of the same color.
For each denomination, you'd like to know the color of coins of this denomination. To accomplish this, you've got a credit card with an infinite amount of money. You can perform queries to an ATM which can also provide you with an infinite amount of money. Each query is described by a positive integer X, which means that you want to receive exactly X units of money from the ATM. The ATM will provide you with the requested amount. You also know that the requested amount will be paid using the smallest possible number of coins. (Note that this rule always uniquely determines the set of coins chosen to make the payment.)
Return the smallest number of queries you need to determine the corresponding color for each of the denominations. (Note that this can always be done in a finite number of queries.)
Constraints
- values will contain between 1 and 60 elements, inclusive.
- Each element of values will be between 1 and 10^18, inclusive.
- values will be sorted in strictly ascending order. Note that this also implies that all the elements of values will be distinct.
- For each pair of different elements in values, the smaller one will be a divisor of the larger one.
- values[0] will be 1.
{1}
Returns: 1
There is just one coin type. We have to make a query to learn the color of coins.
{1, 3}
Returns: 1
Just one query with X = 5 is one possible solution. As the ATM gives the smallest number of coins, it will give one coin of denomination 3 and two coins of denomination 1. That means, for example, that if you get one red coin and two blue coins, you'll understand that coins of denomination 3 are red, and coins of denomination 1 are blue.
{1, 2, 4}
Returns: 2
One optimal solution is to make two queries, first X = 5 and then X = 6. After the first query you'll receive one coin from each of denominations 1 and 4, and after the second query you'll receive one coin from each of denominations 2 and 4. Now you can uniquely determine the color of each denomination. For example, coins of denomination 4 have the color which appears twice among the received coins.
{1, 2, 4, 8, 16}
Returns: 3
{1, 2, 6, 30, 90, 270, 810, 2430, 7290, 29160, 87480, 262440, 787320, 3149280,
9447840, 28343520, 56687040, 170061120, 510183360, 1530550080, 3061100160,
9183300480, 27549901440, 82649704320, 247949112960, 1239745564800, 3719236694400,
14876946777600, 44630840332800, 223154201664000, 669462604992000, 2008387814976000,
6025163444928000, 12050326889856000, 24100653779712000, 72301961339136000,
289207845356544000, 867623536069632000}
Returns: 4
Submissions are judged against all 192 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ColorfulCoins with a public method int minQueries(vector<long long> values) · 192 test cases · 2 s / 256 MB per case