ModuloCounters
TCO13 Wildcard Round · 2013-02-19 · by rng_58
TCO13 Wildcard Round · 2013-02-19 · by rng_58 · Math
Problem Statement
Problem Statement
There is a directional corridor for Foxes. Every day some foxes pass through the corridor. There are n+2 positions in the corridor, and the positions are numbered 0 through n+1. It is known that foxes pass through the corridor in the following way:
Fox Ciel got interested in the number of foxes that pass through the corridor. She got n counters and placed them on positions 1 through n. Initially, each of those counters was set to zero. Each time a fox steps on a position, the particular counter is incremented. Unfortunately, the counters can only store integers from 0 to M-1 and therefore they are counting modulo M. In other words, after M foxes step on a particular position, the corresponding counter will show zero again.
You are given along M and a long[] counter. The i-th (0-based) element of counter is the value the counter at position i+1 shows at the moment. Return the minimal possible number of foxes that passed through the corridor since Ciel installed the sensors.
- Each fox enters the corridor at position 0.
- After some fox steps at position i, he will step at either position i+1 or position i+2 next.
- Each fox leaves the corridor at position n+1.
Fox Ciel got interested in the number of foxes that pass through the corridor. She got n counters and placed them on positions 1 through n. Initially, each of those counters was set to zero. Each time a fox steps on a position, the particular counter is incremented. Unfortunately, the counters can only store integers from 0 to M-1 and therefore they are counting modulo M. In other words, after M foxes step on a particular position, the corresponding counter will show zero again.
You are given a
Notes
- The answer will always fit into a signed 64bit integer.
Constraints
- M will be between 2 and 10^12, inclusive.
- counter will contain between 1 and 50 elements, inclusive.
- Each element of counter will be between 0 and M-1, inclusive.
Examples
0)
10
{0, 0, 1}
Returns: 10
There could have been 10 foxes. Out of those, nine stepped on positions 0, 2, 4, and one stepped on positions 0, 2, 3, 4. Note that all 10 foxes stepped on position 2, which is consistent with the counter showing 0. There is no way to reach the given state of counters with fewer than 10 foxes.
1)
1000000000000
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: 0
2)
1000000000000
{0}
Returns: 0
3)
2
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: 0
4)
2
{0}
Returns: 0
59)
1000000000000
{2013, 2013, 2013, 2013, 2013}
Returns: 2013
There could have been 2013 foxes. All foxes stepped at all positions.
60)
10
{0, 0, 0}
Returns: 0
There can be no foxes.
Submissions are judged against all 64 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ModuloCounters with a public method long long minFoxes(long long M, vector<long long> counter) · 64 test cases · 2 s / 256 MB per case