Circular Toy Shopping
National Olympiad — National round (2013 season)
Submission name: shopping.cpp
Problem summary
Choose a consecutive group of toys around a circle, using each toy at most once. Each banknote is worth d, and exact payment is required. Find the largest number of toys whose total price is divisible by d.
Input
N and d; then N positive prices in clockwise order.
Output
The largest feasible group size, or 0 if no nonempty group can be paid exactly.
Constraints
1 ≤ N ≤ 1000; 1 ≤ d ≤ 1,000,000,000; 1 ≤ each price ≤ 1,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
6 5 31 10 16 18 12 17
Output
4
Solution analysis
- For every possible starting position, extend the group by 1 through N toys. Use index (start+length−1)%N to wrap around the circle.
- Maintain its price sum. Whenever sum%d is zero, update the best length. N≤1000 makes checking at most one million groups practical.
- Starting at price 12, the four toys cost 12+17+31+10=70, payable with fourteen 5-unit notes. No longer group works, so the answer is 4.
Why it works
Every circular consecutive group has a starting position and a length from 1 to N, so the loops examine it. A group can be paid exactly with d-unit notes precisely when its sum is divisible by d. The maximum accepted length is therefore optimal.
Watch out. Allow groups crossing the end of the input. Do not select a toy twice. Use long long for sums up to 10^12.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
long long denomination;
cin >> n >> denomination;
vector<long long> prices(n);
for (long long &price : prices) {
cin >> price;
}
int answer = 0;
for (int start = 0; start < n; start++) {
long long sum = 0;
for (int length = 1; length <= n; length++) {
// Modulo indexing lets a group cross the end of the input.
sum += prices[(start + length - 1) % n];
if (sum % denomination == 0) {
answer = max(answer, length);
}
}
}
cout << answer << '\n';
}