Connection Status:
Competition Arena > ModuloCounters

ModuloCounters

TCO13 Wildcard Round · 2013-02-19 · by rng_58

TCO13 Wildcard Round · 2013-02-19 · by rng_58 · Math
Class Name: ModuloCounters
Return Type: long
Method Name: minFoxes
Arg Types: (long long, vector<long long>)
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:
  • 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 long 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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous