2019 Dec Gold Problem 2 Milk Visits: Difference between revisions
No edit summary |
No edit summary |
||
Line 7: | Line 7: | ||
The milk truck visits the cows in a sequence, visiting cow i immediately after cow i-1 for each i from 2 to M. The milk truck never visits the same cow twice. | The milk truck visits the cows in a sequence, visiting cow i immediately after cow i-1 for each i from 2 to M. The milk truck never visits the same cow twice. | ||
Solution | ==Solution== | ||
The solution to this problem is to use a dynamic programming approach. We can create an array A of size N+1, where A[i] represents the amount of milk taken away from cow i. We can then iterate through the visits and update A[i] accordingly. | The solution to this problem is to use a dynamic programming approach. We can create an array A of size N+1, where A[i] represents the amount of milk taken away from cow i. We can then iterate through the visits and update A[i] accordingly. |
Revision as of 04:59, 7 May 2023
Problem Statement:
Milk Visits
Farmer John has N cows (1 ≤ N ≤ 100,000), conveniently numbered 1..N, and M visits (1 ≤ M ≤ 100,000) from the milk truck. Each visit involves the milk truck visiting a single cow, taking away some milk, and then moving on to the next cow.
The milk truck visits the cows in a sequence, visiting cow i immediately after cow i-1 for each i from 2 to M. The milk truck never visits the same cow twice.
Solution
The solution to this problem is to use a dynamic programming approach. We can create an array A of size N+1, where A[i] represents the amount of milk taken away from cow i. We can then iterate through the visits and update A[i] accordingly.
For example, in C++:
int N, M; int A[N+1];
for (int i = 1; i <= M; i++) {
int cow; cin >> cow; A[cow]++;
}
At the end of the loop, A[i] will contain the total amount of milk taken away from cow i.