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); } };