## 1. Money Change

In this problem, you will design and implement an elementary greedy algorithm used by cashiers all over the world millions of times per day.

### 1.1 Problem Description

Task: The goal in this problem is to find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.

Input Format: The input consists of a single integer $m$.

Constrains: $0<m < 10^3$.

Output Format: Output the minimum number of coins with denominations 1, 5, 10 that changes $m$.

Sample 1

Input :

2


output:

2


$2 = 1 + 1$

Sample 2

Input :

28


output:

6


$28 = 10 + 10 + 5 + 1 + 1 + 1$

### 1.2 代码实现

#include <iostream>
using namespace std;
int get_change(int m) {
int n = 0;
int leave_m = m;
if(leave_m >= 10) {
n += (leave_m / 10);
leave_m = leave_m % 10;
}
while(leave_m >= 5) {
n += leave_m / 5;
leave_m = leave_m % 5;
}
n += leave_m;
return n;
}

int main() {
int m ;
cin >> m;
cout << get_change(m) << endl;
}


## 2. Fractional knapsack

### 2.1 Problem Description

Task: The goal of this code problem is to implement an algorithm for the fractional knapsack problem.

Input Format: The first line of the input contains the number $n$ of items and the capacity $W$ of a knapsack. The next $n$ lines define the values and weights of items. The $i$-th line contains integers $v_i$ and $w_i$ -the value and the weight of $i$-th item, respectively.

Constrains: $1 \leq n \leq 10^3, 0\leq W \leq 2 \cdot 10^6; 0\leq v_i \leq 2 \cdot 10^6; 0\leq w_i \leq 2 \cdot 10^6$ for all $1\leq i \leq n$. All the numbers are integers.

Output Format: Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most $10^{-3}$. To ensure this, output your answer with at least four digits after the decimal point (otherwise your answer, while being computed correctly, can turn out to be wrong because of rounding issues).

Sample 1

Input :

3 50
60 20
100 50
120 30


output:

180.0000


Sample 2

Input :

1 10
500 30


output:

166.6667


### 2.2 代码实现

#include <iostream>
#include <vector>

using std::vector;
double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
if (capacity == 0) {
return 0;
}
double max_value_per_weight = 0.;
double value_per_weight = 0.;
int max_index = 0;
// 选出单位重量价值最多的物品
for (int i = 0; i < weights.size(); i++) {
value_per_weight = (double)values[i]/(double)weights[i];
if (value_per_weight > max_value_per_weight) {
max_value_per_weight = value_per_weight;
max_index = i;
}
}
double value = 0.0;
//如果该物品能完全放入，进入下一次递归。
if (capacity >= weights[max_index]) {
capacity = capacity - weights[max_index];
value = value + values[max_index];
weights.erase(weights.begin() + max_index);
values.erase(values.begin() + max_index);

return value + get_optimal_value(capacity, weights, values);
}
//如果不能，终止递归。
else{
value = value + capacity * max_value_per_weight;
}
return value;

}

int main() {
unsigned int n, capacity;
std::cin >> n >> capacity;
vector<int> values(n);
vector<int> weights(n);
for (int i = 0; i < n; i++) {
std::cin >> values[i] >> weights[i];
}
double optimal_value = get_optimal_value(capacity, weights, values);

std::cout.precision(10);
std::cout << optimal_value << std::endl;
return 0;
}


## 3. Car Fueling

### 3.1 Problem Description

You are going to travel to another city that is located $d$ miles away from your home city. Your can can travel at most $m$ miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances $stop_1,stop_2,…,stop_n$ from your home city. What is the minimum number of refills needed?

Input Format. The first line contains an integer $d$. The second line contains an integer $m$. The third line specifies an integer $n$. Finally, the last line contains integers $stop_1,stop_2,…,stop_n$.

Assuming that the distance between the cities is $d$ miles, a car can travel at most $m$ miles on a full tank, and there are gas stations at distances $stop_1,stop_2,…,stop_n$ along the way, output the minimum number of refills needed. Assume that the car starts with a full tank. If it is not possible to reach the destination, output $−1$.

Constraints. $1 ≤ d ≤ 105. 1 ≤ m ≤ 400. 1 ≤ n ≤ 300. 0 < stop_1 < stop_2 < ··· < stop_n < d.$

Sample 1

Input :

950
400
4
200 375 550 750


output:

2


Sample 2

Input :

10
3
4
1 2 5 9


output:

-1


#include <iostream>
#include <vector>

using std::cin;
using std::endl;
using std::cout;
using std::vector;
using std::max;

int compute_min_refills(const int dist, const int tank, const vector<int>& stops) {
int num_stops = 0;
int dist_min = 10000;
int dist_tmp = 0;
unsigned int index_min = 0;
// 如果tank >= dist, 终止递归
if (tank >= dist) {
return 0;
}
if (stops > tank) {
return -1;
}

for (size_t i = 1; i < stops.size(); i++) {
if ((stops[i] - stops[i-1]) > tank) {
return -1;
}
}
num_stops ++;
for (size_t i = 0; i < stops.size(); i++) {
if(tank >= stops[i]) {
dist_tmp = tank - stops[i];
if(dist_tmp < dist_min) {
dist_min = dist_tmp;
index_min = i;
}
}
else {
continue;
}
}
//选取最远的停车点
int dist_updated = dist - stops[index_min];
vector<int> stops_updated(stops.size() - index_min - 1);

for (size_t i = index_min+1; i < stops.size(); i++) {
stops_updated[i - index_min - 1] = stops[i] - stops[index_min];
}
// 递归
return num_stops + compute_min_refills(dist_updated, tank, stops_updated);
}

int main() {
int d = 0;
cin >> d;
int m = 0;
cin >> m;
int n = 0;
cin >> n;

vector<int> stops(n);
for(size_t i = 0; i < n; ++i) {
cin >> stops[i];
}
cout << compute_min_refills(d, m, stops) << endl;
return 0;
}


### 4.1 Problem Description

You have $n$ ads to place on a popular Internet page. For each ad, you know how much is the advertiser willing to pay for one click on this ad. You have set up $n$ slots on your page and estimated the expected number of clicks per day for each slot. Now, your goal is to distribute the ads among the slots to maximize the total revenue.

Given two sequences $a_1,a_2,…,a_n$ ($a_i$is the profit per click of the i-th ad) and $b_1,b_2,…,b_n$ ($b_i$ is the average number of clicks per day of the i-th slot), we need to partition them into n pairs ($a_i,b_j$) such that the sum of their products is maximized.

Input Format. The first line contains an integer $n$, the second one contains a sequence of integers $a_1,a_2,…,a_n$ , the third one contains a sequence of integers$b_1,b_2,…,b_n$.

Constraints. $1 ≤ n ≤ 10^3; −10^5 ≤ a_i,b_i ≤ 10^5 \quad for \quad all \quad 1 ≤ i ≤ n.$

Output Format. Output the maximum value of $\sum_{i=1}^N a_i c_i$, where $c_1,c_2,…,c_n$ is a permutation of $b_1,b_2,…,b_n$.

Sample 1

Input :

3
1 3 -5
-2 4 1


output:

23


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long max_dot_product(vector<int> a, vector<int> b) {
std::sort(begin(a), end(a));
std::sort(begin(b), end(b));
long long result = 0;
for (size_t i = 0; i < a.size(); i++) {
result += ((long long) a[i]) * b[i];
}
return result;
}

int main() {
size_t n;
cin >> n;
vector<int> a(n), b(n);

for(size_t i = 0; i < n; i++) {
cin >> a[i];
}
for(size_t i = 0; i < n; i++) {
cin >> b[i];
}
cout << max_dot_product(a, b) << endl;
}


## 5. Collecting Signatures

### 5.1 Problem Introduction

You are responsible for collecting signatures from all tenants of a certain building. For each tenant, you know a period of time when he or she is at home. You would like to collect all signatures by visiting the building as few times as possible. The mathematical model for this problem is the following. You are given a set of segments on a line and your goal is to mark as few points on a line as possible so that each segment contains at least one marked point.

### 5.2 Problem Description

Task. Given a set of n segments ${[a_0,b_0],[a_1,b_1],…,[a_{n−1},b_{n−1}]}$ with integer coordinates on a line, find the minimum number m of points such that each segment contains at least one point. That is, find a set of integers X of the minimum size such that for any segment $[a_i,b_i]$ there is a point x ∈ X such that $ai ≤ x ≤ bi$.

Input Format. The first line of the input contains the number n of segments. Each of the following n lines contains two integers $a_i$and $b_i$ (separated by a space) defining the coordinates of endpoints of the i-th segment.

Constraints. $$1 ≤ n ≤ 100; 0 ≤ a_i ≤ b_i ≤ 10^9 for \ all \ 0 ≤ i < n$$.

Output Format. Output the minimum number m of points on the first line and the integer coordinates of m points (separated by spaces) on the second line. You can output the points in any order. If there are many such sets of points, you can output any set. (It is not difficult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)

Sample 1

Input :

3
1 3
2 5
3 6


output:

1
3


Sample 2

Input :

4
4 7
1 3
2 5
5 6


output:

2
3 6


#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
struct Segment {
int start, end;
};

bool SortFunction(Segment i, Segment j) {
return (i.end < j.end);
}
vector<int> optimal_points(vector<Segment> &segments) {
vector<int> points;
std::sort(segments.begin(), segments.end(), SortFunction);
int point = segments.end;
points.push_back(point);
for (size_t i = 1; i < segments.size(); i++) {
if (point < segments[i].start || point > segments[i].end) {
point = segments[i].end;
points.push_back(point);
}
}
return points;
}

int main() {
int n;
cin >> n;
vector<Segment> segments(n);
for(size_t i = 0; i < segments.size(); i++) {
cin >> segments[i].start >> segments[i].end;
}
vector<int> points = optimal_points(segments);
cout << points.size() << endl;
for(size_t i = 0; i < points.size(); i++) {
std::cout << points[i] << " ";
}
}