Approach
1. Sort the given scores as described in the problem.
2. Find out the score at Kth place
3. Go through the array, count how many scores are same to the score at Kth place.
Source Code
1: bool sortScore( pair<int,int> a, pair<int,int> b)
2: {
3: if(a.first != b.first) return a.first > b.first;
4: return a.second < b.second;
5: }
6:
7: int main()
8: {
9: ios_base::sync_with_stdio(false);
10:
11: int N,K;
12: cin>>N>>K;
13:
14: vector< pair<int,int> > score(N);
15:
16: REP(i,0,N)
17: {
18: int p,t;
19: cin>>p>>t;
20: score.push_back( make_pair(p,t) );
21: }
22:
23: sort( score.begin(), score.end(), sortScore );
24:
25: pair<int,int> sc = score[K-1];
26: int same = 0;
27: for(int i=0; i < N; i++)
28: if(score[i] == sc)
29: same++;
30:
31: cout<<same<<endl;
32:
33: return 0;
34: }bool sortScore( pair<int,int> a, pair<int,int> b)
35: {
36: if(a.first != b.first) return a.first > b.first;
37: return a.second < b.second;
38: }
39:
40: int main()
41: {
42: ios_base::sync_with_stdio(false);
43:
44: int N,K;
45: cin>>N>>K;
46:
47: vector< pair<int,int> > score(N);
48:
49: REP(i,0,N)
50: {
51: int p,t;
52: cin>>p>>t;
53: score.push_back( make_pair(p,t) );
54: }
55:
56: sort( score.begin(), score.end(), sortScore );
57:
58: pair<int,int> sc = score[K-1];
59: int same = 0;
60: for(int i=0; i < N; i++)
61: if(score[i] == sc)
62: same++;
63:
64: cout<<same<<endl;
65:
66: return 0;
67: }
C- Median
Approach
1. Find X.
If X does not exist, add X to the given array.
2. Sort the array.
3. Find the median.
If the median < X, add a number to the right.
If the median > X, add a number to the left.
4. Do number 3 until the median == X
The above step takes
O(NlogN + N) => O(NlogN)
Source Code
1: int main()
2: {
3: ios_base::sync_with_stdio(false);
4:
5: int N, X;
6: cin>>N>>X;
7:
8: deque<int> arr(N);
9: REP(i,0,N)
10: cin>>arr[i];
11:
12: int ans = 0;
13:
14: if(count(arr.begin(), arr.end(), X) == 0)
15: {
16: ans++;
17: arr.push_front(X);
18: }
19:
20: sort(arr.begin(), arr.end());
21:
22: int mid = ((arr.size() + 1) / 2) - 1;
23:
24: while(arr[mid] != X)
25: {
26: if(arr[mid] < X) arr.push_back(0);
27: else arr.push_front(0);
28: mid = ((arr.size() + 1) / 2) - 1;
29: ans++;
30: }
31:
32: cout<<ans<<endl;
33:
34: return 0;
35: }
D - Shoes Store
Approach
There are two approaches
1) Greedy Algorithm
2) Dynamic Programming
Greedy Algorithm
Goal : Sell as many highest priced shoes as possible.
Steps.
1. Sort shoes by size
2. For each shoe, find out which customers can buy it.
3. Sort shoes by cost
4. For each shoe, do follow
1) See if a customer who can buy the current shoe has already bought a shoe or not.
2) If not, sell this shoe to the current customer
3) If yes, let j = the shoe that the current customer bought.
See if any other customer can buy shoe j.
If yes, sell the current shoe to the current customer.
If not, move on to the next customer.
Dynamic Programming
- Coming soon
Source Code - Greedy Algorithm
1: /*
2: This code belongs to Avalenche.
3: I only placed comments and change variable names
4: to help me better understand his code.
5: */
6: const int maxN = 100010;
7:
8: struct obj
9: {
10: int cost, size, id;
11: obj(int c = -1, int sz = -1, int idx = -1): cost(c), size(sz), id(idx) {}
12: };
13:
14: bool compSize(obj a, obj b)
15: {
16: return a.size < b.size;
17: }
18:
19: bool compCost(obj a, obj b)
20: {
21: return a.cost > b.cost;
22: }
23:
24:
25: //waitList[i] = waiting list of customer ids who can buy shoe i
26: vector<int> waitList[maxN];
27:
28: //purchase[i] = shoe id that customer i actually purchased
29: //It is -1 if customer i did not purchase anything
30: int purchase[maxN];
31:
32: //sold[i] = true if shoe i is sold
33: bool sold[maxN];
34:
35: //returns true if shoe x is successfully purchased
36: bool buy(int x)
37: {
38: //you cannot buy what is already sold
39: if(sold[x]) return false;
40:
41: //Shoe is x is now being sold to...
42: sold[x] = true;
43:
44: //Let's decide who buys this shoe
45: for(int i=0; i < waitList[x].size(); i++)
46: {
47: int pot = waitList[x][i]; //potential customer id
48:
49: /*
50: If the potential customer has not made any purchases,
51: or if somebody else can buy what he previously bought
52: (there is another person who can buy he has already purchased
53: */
54: if( purchase[pot] == -1 || buy( purchase[pot] ))
55: {
56: //the current potential customer takes this shoe
57: purchase[pot] = x;
58: return true; //successful purchase
59: }
60: }
61: //Every already bought other shoes
62: return false;
63: }
64:
65: obj shoes[maxN]; //info on shoes
66: obj cus[maxN]; //info on customers
67: ll cost[maxN];
68:
69: int main()
70: {
71: ios_base::sync_with_stdio(false);
72: int N,M;
73: cin>>N;
74: for(int i=0; i < N; i++)
75: {
76: cin>>shoes[i].cost>>shoes[i].size;
77: shoes[i].id = i;
78: cost[i] = shoes[i].cost;
79: }
80:
81: sort(shoes, shoes+N, compSize);
82:
83: cin>>M;
84: for(int i=0; i < M; i++)
85: {
86: cin>>cus[i].cost>>cus[i].size;
87: cus[i].id = i;
88: }
89:
90: for(int i=0; i < M; i++)
91: {
92: int idx = int(lower_bound(shoes, shoes+N, obj(-1,cus[i].size,-1), compSize) - shoes);
93:
94: while( shoes[idx].size == cus[i].size || shoes[idx].size == (cus[i].size + 1) )
95: {
96: if(shoes[idx].cost <= cus[i].cost)
97: waitList[shoes[idx].id].push_back( cus[i].id );
98: idx++;
99: }
100: }
101:
102: sort(shoes, shoes + N, compCost);
103:
104: memset(purchase, -1, sizeof(purchase));
105:
106: for(int i=0; i < N; i++)
107: {
108: memset(sold, false, sizeof(sold));
109: buy( shoes[i].id );
110: }
111:
112: ll total = 0LL;
113: vector< pair<int,int> >ans;
114:
115: for(int i=0; i < M; i++)
116: {
117: if(purchase[i] == -1)
118: continue;
119:
120: total += cost[ purchase[i] ];
121: ans.push_back( make_pair( i+1, purchase[i] + 1) );
122: }
123:
124: cout<<total<<endl;
125: cout<<ans.size()<<endl;
126:
127: for(int i=0; i < ans.size(); i++)
128: cout<<ans[i].first<<" "<<ans[i].second<<endl;
129:
130: return 0;
131: }
E - Tetrahedron
Approach
We need to find how many ways an ant can go from D to D without staying at one vertice for more than one turn.
Fix first and last vertice as D.
There are 4 vertex : A,B,C and D
Then at each step, we have 3 vertex (our ant cannot stay at the current vertice) to move to.
So there are 3^(N-2) possible routes from first vertex to last vertex.
Note that at the (last - 1) step, the vertice cannot be D because our ant cannot stay at D.
So we need to eliminate cases where (last-1) step ends at vertice D.
Let ans(i) = answer to the question when (n == i).
Then ans(i) = 3^(N-2) - ans(i-1)
Source Code
1: int mod = 1000000007ll;
2:
3: int main() {
4: int N;
5: cin >> N;
6:
7: ll ans = 0;
8: if (N == 1) {
9: cout << 0;
10: return 0;
11: }
12:
13: ll threes = 1;
14: ll prev = 0;
15: ll cur = 0;
16: for (int i = 2; i <= N; i++) {
17: threes = 3ll*threes;
18: cur = threes - prev;
19: if (cur < 0) cur +=mod;
20: threes %= mod;
21: cur %= mod;
22: prev = cur;
23: }
24:
25: cout << cur;
26: return 0;
27: }
Nice Explanations..(y)
ReplyDeleteThanks :-)
Delete