Snow has contracted a strange infectious disease, covered with rashes and experiencing intense itching and pain all over her body, even the doctors cannot diagnose the condition. Just as she is distressed, a mysterious old lady suddenly appears, claiming to have a miraculous ancestral remedy that can cure Snow's illness. However, this remedy requires four specific ingredients: A, B, C, and D, and must be prepared in a special ratio.
Each type of ingredient is divided into N small packets of different sizes, and each packet cannot be further divided or combined. For example, for each type of material, there are five small packets. The portions of material A in the five small packets are 2, 9, 5, 8, and 1, while the portions of material B in the five small packets are 8, 3, 1, 4, and 5, and so on. If the optimal ratio for the remedy is 1:2:1:3, we can take the first small packet of material A, the fourth small packet of material B, the fourth small packet of material C, and the third small packet of material D to prepare the remedy according to the correct ratio.
Please write a program to determine if it is possible to make the remedy according to the specified ratio.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line of input consists of four positive integers A, B, C, and D (all numbers not exceeding 5), representing the ratio of the four materials used to make the remedy. It is guaranteed that one number is 1. The second line contains an integer N (3 ≤ N ≤ 10), which represents the number of packages into which each of the four materials is divided. Finally, there are four lines, each containing N integers X (1 ≤ X ≤ 100, 1 ≤ i ≤ N), representing the quantity of each small package of the respective material. | Output a single line containing the quantity of each material needed to make the remedy. If it is not possible to make the remedy, output -1. It is guaranteed that there is at most one valid solution. |
| 1 2 1 3 5 2 9 5 8 1 8 3 1 4 5 1 6 5 2 7 4 3 6 9 8 | 2 4 2 6 |
| 1 2 1 3 3 2 9 5 8 3 1 1 6 5 4 3 1 | -1 |
| 2 2 1 3 7 7 10 8 6 3 2 7 2 7 10 1 2 4 3 4 1 10 5 9 8 6 4 8 2 1 8 3 3 | 2 2 1 3 |
Thought Process
You can use an array to store the proportions and then declare a vector<map> to store the quantities of each type of medicine separately.
Run a for loop, and when the current medicine proportion is 1, use its quantity as the reference to search for other three medicines that match the proportion. Store the answers in an array.
Sample Code－ZeroJudge K514: Medicine
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int ratio[4] = {}, N;
for (int & i : ratio) cin >> i;
cin >> N;
vector<map<int, int>>v;
for (int i = 0; i<4; i++) {
map<int, int>MAP;
for (int j = 0; j<N; j++) {
int tmp;
cin >> tmp;
MAP[tmp]++;
}
v.push_back(MAP);
}
bool no = true;
for (int i = 0; i<4; i++) {
if (ratio[i] == 1) {
bool finish = false;
for (auto it:v[i]) {
const int num = it.first;
int ans[4] = {};
ans[i] = num;
bool ok = true;
for (int j = 0; j<4; j++) {
if (i == j) continue;
if (v[j][num*ratio[j]] > 0) ans[j] = num*ratio[j];
else {
ok = false;
break;
}
}
if (ok) {
for (int j = 0; j<4; j++) cout << ans[j] << " ";
cout << "\n";
finish = true;
break;
}
}
if (finish) {
no = false;
break;
}
}
}
if (no) cout << -1 << "\n";
}
//ZeroJudge K514
//Dr. SeanXD