SRM 195 DIV2 1100

Problem Statement

Johnny Indecision has a change purse with some change in it. However, he is deathly afraid of having to figure out what might happen if he has to spend some of it. This fear arises because there may be more than one way to give out a certain amount of change. For example, if he has 1 dime (worth 10 cents) and 2 nickels (worth 5 cents apiece), there are two ways to make 10 cents. He also does not want to incur any more change, so he wants to be sure that he has exact change for any amount up to the amount of money he has.

So he would like to exchange his current change with some more predictable coins at the bank. As the bank clerk, you must solve Johnny's dilemma by giving him enough change to allow him to be able to spend any amount of money up to the amount he currently has, but the coins you give him must provide exactly one way to make each of those amounts. If multiple ways exist to give Johnny change, return the one with the most coins of the highest denomination. If multiple ways exist which have the most coins of the highest denomination, return the one with the most coins of the second-highest denomination, and so on. For example, if Johnny brings 49 cents to the bank, and the only coins available are 1, 10, and 25 cent pieces, there are three valid options:

1. one 25-cent piece and 24 1-cent pieces
2. four 10-cent pieces and nine 1-cent pieces
3. 49 1-cent pieces

Each of these combinations results in only one way to make 1 to 49 cents, and even though it does not produce the fewest coins, the first way is preferable because it contains a high-valued 25 cent piece.

You will be given a vector  coinTypes, which will be a list containing the value of each type of coin in the given monetary system (which will always include a coin valued at 1). You will also be given an int value specifying the amount of money Johnny has. The return value should be a vector indicating how many coins of each type you should give Johnny back. Element i of the return value should be how many coins valued at coinTypes[i] should be given to Johnny.

Definition

Class:	ChangePurse
Method:	optimalCoins
Parameters:	vector , int
Returns:	vector
Method signature:	vector optimalCoins(vector coinTypes, int value)
(be sure your method is public)

Limits

Time limit (s):	2.000
Memory limit (MB):	64

Constraints

-

coinTypes has between 1 and 50 elements, inclusive.

-

Each element of coinTypes is between 1 and 1000000, inclusive.

-

There will be no repeated values in coinTypes.

-

There will be exactly one element in coinTypes equal to 1.

-

value is between 1 and 1000000000, inclusive.

Examples

0)

{1,25,10}

49

Returns: { 24,  1,  0 }

The example from the problem statement.

1)

{1,7}

49

Returns: { 49,  0 }

Note that {7,6} is an invalid return because even though it equals 49 cents, and it allows all values between 1 and 49, it would allow multiple ways to make 7 cents. This is the thing that Johnny fears the most.

2)

{11,5,10,1}

109

Returns: { 9,  0,  0,  10 }

3)

{29210, 58420, 350520, 708072, 720035, 230, 42355,
 1, 59006, 985, 236024, 163, 701040}

929579039

Returns: { 1,  5,  1,  0,  0,  126,  0,  229,  0,  0,  0,  0,  1325 }

4)

{795, 5536, 26, 915, 18590, 60840, 49140, 2,
 119700, 162235, 369000, 383936, 478800, 505995,
 949, 95984, 455, 8, 420, 239400, 276800, 191968,
 619305, 654810, 706420, 393120, 738000, 767872,
 425880, 786240, 830400, 676, 4500, 851760, 957600,
 648940, 1, 112, 180, 457}

687245439

Returns: 
{ 0,  0,  0,  0,  0,  0,  0,  3,  0,  0,  0,  1,  0,  0,  0,  1,  0,  13,
  0,  0,  0,  1,  0,  0,  0,  0,  0,  894,  0,  0,  0,  0,  0,  0,  0,
  0,  1,  856,  0,  0 }

5)

{494208, 722376, 731798, 809064, 920448, 1, 988416, 9152, 158,
 991014, 282720, 40132, 608, 143, 289755, 734, 579510, 828400,
 330338, 816, 460224, 27456, 675783, 331, 436, 82368, 729, 306,
 202266, 247104, 414200, 705}

419088383

Returns: 
{ 1,  0,  0,  0,  0,  142,  423,  2,  0,  0,  0,  0,  0,  63,  0,  0,
  0,  0,  0,  0,  0,  2,  0,  0,  0,  2,  0,  0,  0,  1,  0,  0 }

题目的大意是给你一个value值，现在有一组coinTypes，没有重复面值，且其中一定有面值为1的coinType（从而保证程序有解）。你要保证以下几点： 1.使得[1,values]里的每个面值都能够组成 2.使得[1,values]里的每个面值都能够唯一方法组成 3.如果有多解，请先使用大的面值 测试样例足够强大了，个人认为如果能够过样例，后台的数据应该不会挂吧。 思路：由于上面要保证的条件其实已经非常的强大了，所以coinTypes先按照从大到小排序，并进行扫描coinTypes。关键点在于（虽然我不能证明）： 当value用当前coinType组合，并且剩余为当前coinType的面值-1那一定是可取的。 // BEGIN CUT HERE /* */ // END CUT HERE #line 7 "ChangePurse.cpp" #include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> using namespace std; #define PB push_back #define MP make_pair #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI; typedef vector<string> VS; typedef vector<double> VD; typedef long long LL; typedef pair<int,int> PII; struct node { int v, idx; bool operator < (const node& aa) const { return v > aa.v; } }t[55]; class ChangePurse { public: vector <int> optimalCoins(vector <int> coinTypes, int value) { int size = coinTypes.size(); for (int i = 0; i < size; i++) { t[i].v = coinTypes[i]; t[i].idx = i; } sort(t, t + size); //for (int i = 0; i < size; i++) { //printf("%d ", t[i].v); //} //printf("\n"); int ans[100]; for (int i = 0; i + 1 < size; i++) { if (value % t[i].v == t[i].v - 1) { ans[t[i].idx] = value / t[i].v; value %= t[i].v; } else { ans[t[i].idx] = 0; } } ans[t[size - 1].idx] = value; vector<int> res(ans, ans + size); return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const vector <int> &Expected, const vector <int> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected ==Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: "<< print_array(Received) << endl; } } void test_case_0() { int Arr0[] = {1,25,10}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 49; int Arr2[] = { 24, 1, 0 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(0, Arg2, optimalCoins(Arg0, Arg1)); } void test_case_1() { int Arr0[] = {1,7}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 49; int Arr2[] = { 49, 0 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(1, Arg2, optimalCoins(Arg0, Arg1)); } void test_case_2() { int Arr0[] = {11,5,10,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 109; int Arr2[] = { 9, 0, 0, 10 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(2, Arg2, optimalCoins(Arg0, Arg1)); } void test_case_3() { int Arr0[] = {29210, 58420, 350520, 708072, 720035, 230, 42355, 1, 59006, 985, 236024, 163, 701040}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 929579039; int Arr2[] = { 1, 5, 1, 0, 0, 126, 0, 229, 0, 0, 0, 0, 1325 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(3, Arg2, optimalCoins(Arg0, Arg1)); } void test_case_4() { int Arr0[] = {795, 5536, 26, 915, 18590, 60840, 49140, 2, 119700, 162235, 369000, 383936, 478800, 505995, 949, 95984, 455, 8, 420, 239400, 276800, 191968, 619305, 654810, 706420, 393120, 738000, 767872, 425880, 786240, 830400, 676, 4500, 851760, 957600, 648940, 1, 112, 180, 457}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 687245439; int Arr2[] = { 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 1, 0, 13, 0, 0, 0, 1, 0, 0, 0, 0, 0, 894, 0, 0, 0, 0, 0, 0, 0, 0, 1, 856, 0, 0 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(4, Arg2, optimalCoins(Arg0, Arg1)); } void test_case_5() { int Arr0[] = {494208, 722376, 731798, 809064, 920448, 1, 988416, 9152, 158, 991014, 282720, 40132, 608, 143, 289755, 734, 579510, 828400, 330338, 816, 460224, 27456, 675783, 331, 436, 82368, 729, 306, 202266, 247104, 414200, 705}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 419088383; int Arr2[] = { 1, 0, 0, 0, 0, 142, 423, 2, 0, 0, 0, 0, 0, 63, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0 }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); verify_case(5, Arg2, optimalCoins(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE int main() { ChangePurse ___test; ___test.run_test(-1); return 0; } // END CUT HERE