2019 Dec Gold Problem 2 Milk Visits: Difference between revisions
(Created page with "== Problem == == Solution == == Code == Category:Yearly_2019_2020 Category:Gold") |
No edit summary |
||
Line 1: | Line 1: | ||
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. | |||
[[Category:Yearly_2019_2020]] | [[Category:Yearly_2019_2020]] | ||
[[Category:Gold]] | [[Category:Gold]] |
Revision as of 04:57, 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.