RunningAroundPark
SRM 632 - TCO14 Wildcard Sweep · 2014-08-25 · by dreamoon
Problem Statement
Alice went jogging around the park yesterday. There is a circular track around the park, and Alice's house is right next to the track. Alice ran in the clockwise direction. She both started and ended her run at her house. In other words, she completed some positive number of full laps.
There are N trees along the track.
The trees are numbered 1 through N in the order in which Alice encounters them when running a single lap.
You are given the
Alice remembers some trees she saw during her run.
She remembers them in the order in which she encountered them.
You are given this information as a
For example, d={6,6,1} has the following meaning:
- Alice started running.
- After some time she encountered the tree number 6.
- After some more time she encountered the tree number 6.
- Even later she encountered the tree number 1.
Compute and return the smallest possible number of laps Alice completed.
Constraints
- N will be between 2 and 50, inclusive.
- d will contain between 1 and 50 elements.
- Each element of d will be between 1 and N, inclusive.
3
{1,2,3}
Returns: 1
It is possible that Alice ran just a single lap and remembered all the trees she saw.
24
{6,6}
Returns: 2
Alice ran past the tree number 6 at least twice, so there must have been at least two laps.
3
{3,2,1}
Returns: 3
50
{1,3,5,7,9,2,4,6,8,10}
Returns: 2
2
{1}
Returns: 1
Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RunningAroundPark with a public method int numberOfLap(int N, vector<int> d) · 41 test cases · 2 s / 256 MB per case