SRM 504.5 DIV2

话不多说，直接说解题思路……

250分：

Problem Statement
John has recently won a jackpot, but he doesn't need the money. He decided to share it with his friends instead. He knows how much money each of his friends has, and he will use this information to perform the distribution. While he still has money left, he will repeat the following steps: Choose the poorest friend. If there are multiple poorest friends, choose one of them randomly. Give 1 dollar to the chosen friend. You are given an int jackpot, the number of dollars John has won, and a vector <int> money, where the i-th element is the number of dollars currently owned by the i-th friend. Return a vector <int> containing the same number of elements as money. The return value must contain the number of dollars owned by each friend after John has performed the above distribution, sorted in non-decreasing order.
Definition
Class: TheJackpotDivTwo Method: find Parameters: vector <int>, int Returns: vector <int> Method signature: vector <int> find(vector <int> money, int jackpot) (be sure your method is public)
Constraints
-	money will contain between 1 and 47 elements, inclusive.
-	Each element of money will be between 1 and 1,000,000, inclusive.
-	jackpot will be between 1 and 1,000,000, inclusive.
Examples
0)
{1, 2, 3, 4} 2 Returns: {2, 3, 3, 4 } First, John will give one dollar to the first friend. Then he will give another dollar to the first or the second friend.
1)
{4, 7} 1 Returns: {5, 7 } Just one action here.
2)
{1} 100 Returns: {101 } Just one friend here.
3)
{21, 85, 6, 54, 70, 100, 91, 60, 71} 15 Returns: {21, 21, 54, 60, 70, 71, 85, 91, 100 } 解题思路： 这道题比较简单，直接就是使用一个优先队列来每次取出一个最小值，然后加上1，不过这个时间可能耗费比较大，但是TC一般不计较时间，只要可以过测试数据就行了。 下面贴上代码： // BEGIN CUT HERE // END CUT HERE #line 5 "TheJackpotDivTwo.cpp" #include <string> #include <vector> #include <queue> using namespace std; class cmp { public: bool operator()(const int &a,const int &b) const { return a>b; } }; class TheJackpotDivTwo { public: vector <int> find(vector <int> money, int jackpot) { priority_queue <int,vector<int>,cmp> pq; int i; if(pq.size()==1) { vector<int>t; t.push_back(money[0]+jackpot); return t; } for(i=0;i<money.size();i++) pq.push(money[i]); int a; int n=jackpot; while(n>0) { a=pq.top(); pq.pop(); pq.push(a+1); n--; } vector<int> ans; while(!pq.empty()) { ans.push_back(pq.top()); pq.pop(); } return ans; } }; 500分： Problem Statement John believes that the digits 4 and 7 are lucky, and all other digits are unlucky. A positive integer is called a lucky number if its last digit is lucky. For example, 4, 14 and 207 are lucky numbers, while 40, 741 and 3 are not lucky numbers. John would like to represent the int n as a sum of only lucky numbers, and he would like to do this using the minimal possible number of summands. Return the number of summands in the representation, or -1 if it is impossible to achieve the goal. Definition Class: TheNumbersWithLuckyLastDigit Method: find Parameters: int Returns: int Method signature: int find(int n) (be sure your method is public) Constraints - n will be between 1 and 1,000,000,000, inclusive. Examples 0) 99 Returns: 4 One of the possible representations is 99=14+24+27+34. 1) 11 Returns: 2 11=4+7. 2) 13 Returns: -1 It is impossible to achieve the goal. 3) 1234567 Returns: 1 解题思路： 这道题本来应该被秒杀掉的，但是因为考虑到快到12点宿舍会关门，就有了思路后匆匆就写了交了，殊不知有一个考虑错了。还是我们来看具体的思路吧，首先我们考虑4和7的一些列组合可以组成的位数分别为0、1、2、3、4、5、6、7、8、9的最小的数，这个是很好得到的，然后给出的数大于或者等于这个最小的数都是可以有4和7的一些个组合组成。因为如果十位以上的如果打了，我们很好进行补充，主要是个位。 然后对应的进行输出就可以了，如果这个数小于最小的以该个位结尾的数，那么就是-1. 我的代码： // BEGIN CUT HERE // END CUT HERE #line 5 "TheNumbersWithLuckyLastDigit.cpp" #include <string> #include <vector> class TheNumbersWithLuckyLastDigit { public: int find(int n) { int num[10]={5,2,3,5,1,3,4,1,2,4}; int level[10]={20,11,12,23,4,15,16,7,8,19}; int mod=n%10; if(n%10==4||n%10==7) return 1; if(n<level[mod]) return -1; else return num[mod]; } }; 1000分： Problem Statement John has two tickets for the basketball game - one for himself and one for a friend. However, he has n friends who want to go with him. He decides to use the following strategy to choose one of them. First, he tells his friends to form a straight single file line. Then, he repeats the following step until he has made a choice. If there is only one friend in line, John chooses him. Otherwise, he throws a standard six-sided die. If the number 4 is on top, he chooses the friend who is currently first in line. Otherwise, if the number is odd, the first friend in line must move to the end of the line, and if the number is even, the first friend in line must leave the line and go home. While the initial John's intention is to throw a die until some friend is chosen, in practice he gets tired quickly. If after k throws of a die he still hasn't chosen a friend, he prefers to stop the process and to choose the friend who is currently first in line. You are given an int m, the 1-based index of a friend in the initial line. The index of the first friend is 1, and the index of the last friend is n. Return the probability that the m-th friend in the initial line is ultimately chosen by John. Definition Class: TheTicketsDivTwo Method: find Parameters: int, int, int Returns: double Method signature: double find(int n, int m, int k) (be sure your method is public) Notes - The returned value must be accurate to within a relative or absolute value of 1E-9. Constraints - n will be between 1 and 10, inclusive. - m will be between 1 and n, inclusive. - k will be between 1 and 10, inclusive. Examples 0) 2 1 1 Returns: 0.16666666666666666 There is 1/6 probability that John will choose the first friend after the first throw of a die. 1) 2 1 2 Returns: 0.5833333333333334 The first friend will go to the game if John chooses him after the first throw, or if he goes to the end of the line after the first throw and Jonh doesn't choose the second friend after the second throw. The overall probability is 1/6 + 1/2 * 5/6. 2) 7 7 4 Returns: 0.0 There's no chance for the last friend in the line to be chosen. 3) 4 2 10 Returns: 0.25264033564814814 解题思路： 这道题由于时间关系，没有怎么思考，也没有交，只是打开了题目看了下就走了。不过我想真正的看还是没有太好的思路，不过后来考虑了，有了些思路。 我们发现从一个状态到另外一个状态，都是只有三种可能，并且一直走一直走，走到一些情况就应该返回一些值了。这个就是典型的递归的思路，并且每一种状态都是相同的三种进行扩展的子问题，所以可以用递归来解决。同时我们发现这个排队的过程，和其他每一个人的编号没有直接的关系，之后第m个人的位置有关系，所以我们不需要关系其他人到底在那个位置，只需要关心第m个人所在的位置就行了。 我的代码： // BEGIN CUT HERE // END CUT HERE #line 5 "TheTicketsDivTwo.cpp" #include <string> #include <vector> double dfs(int n,int m,int k) { if(k==0) { if(m==1) return 1.0; else return 0.0; } if(n==1) return 1.0; int i,tm; double ans=0; for(i=1;i<=6;i++) { if(i==1||i==3||i==5) { tm=m-1; if(tm==0) tm=n; ans+=1.0/6.0*dfs(n,tm,k-1); } else if(i==2||i==6) { if(m!=1) ans+=1.0/6.0*dfs(n-1,m-1,k-1); } else { if(m==1) ans+=1.0/6.0; } } return ans; } class TheTicketsDivTwo { public: double find(int n, int m, int k) { return dfs(n,m,k); } };