Running in Circles Solution | Round H 2022 - Kick Start 2022

 

Running in Circles Solution (6pts, 9pts)

Problem

Ada has decided that this year, she will take part in the annual marathon that takes place in her city. Since this is the first time she would be running such a long distance, she has decided to start practising for it by running in the circular track of length L$L$ units near her house.

Ada wants to focus only on running, so she decides to use a machine to count the number of laps she has run. The machine is placed at the starting line of the circular track and starts the count from 0$0$. Every time Ada arrives at the starting line running in the same direction as the last time she departed from the starting line, the machine increases the number of laps that Ada has run by 1$1$. If she crosses the starting line or changes direction at the starting line, the machine considers the new direction as the direction she last touched the starting line. The machine only remembers the last direction in which Ada touched the starting line. During a lap, Ada can change directions any number of times, but as long as she eventually touches the starting line in the same direction as she last touched it, the count of laps in the machine increases by 1$1$.

This is the first time Ada has practised running long distances, so she cannot run continuously. She runs some distance, then takes a break to regain her energy. However, when she starts running again after taking a break, she cannot remember which direction she was running in previously. So she picks one of the directions, clockwise or anticlockwise, and starts running from the same position where she stopped.

Ada begins at the starting line and is initially facing in the direction of her first run. She runs a total of N$N$ times, taking breaks in between. Given the information of the distance Di${\mathbf{D}}_{\mathbf{i}}$ units Ada has run, and the direction Ci${\mathbf{C}}_{\mathbf{i}}$ she has taken (clockwise or anticlockwise) when she ran the i$i$-th time, for all i$i$ from 1,…,N$1,\dots ,\mathbf{N}$, can you tell the number of laps that would be reported by the machine at the end?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
The first line of each test case contains two positive integers L$L$ and N$N$, the length of the circular track in units, and the number of times Ada has run respectively.
The next N$N$ lines describe Ada's runs. The i$i$-th line contains a positive integer Di${\mathbf{D}}_{\mathbf{i}}$ and a character Ci${\mathbf{C}}_{\mathbf{i}}$, the distance in units Ada has run and the direction she has taken (clockwise or anticlockwise) respectively during the i$i$-th run. Ci${\mathbf{C}}_{\mathbf{i}}$ will always be either 'C' (denoting clockwise direction) or 'A' (denoting anticlockwise direction).

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is a non negative integer denoting the number of laps reported by the machine at the end.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤L≤109$1\le \mathbf{L}\le {10}^9$.
1≤N≤104$1\le \mathbf{N}\le {10}^4$.
1≤Di≤109$1\le {\mathbf{D}}_{\mathbf{i}}\le {10}^9$, for all 1≤i≤N$1\le i\le \mathbf{N}$.

Test Set 1

Time limit: 20 seconds.
Ci${\mathbf{C}}_{\mathbf{i}}$ is always 'C', for all 1≤i≤N$1\le i\le \mathbf{N}$.

Test Set 2

Time limit: 40 seconds.
Ci${\mathbf{C}}_{\mathbf{i}}$ can be either 'C' or 'A', for all 1≤i≤N$1\le i\le \mathbf{N}$.

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input

2
5 3
8 C
3 C
6 C
8 4
5 C
9 C
8 C
20 C

Sample Output

Case #1: 3
Case #2: 5

In Sample Case #1, the length of the circular track is 5$5$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs 8$8$ units in the clockwise direction, touching the starting line in the process, and the number of laps in the machine increases by 1$1$. The machine now reports 1$1$ lap. Ada is now 3$3$ units from the starting line in the clockwise direction.
• Next, she runs 3$3$ units in the clockwise direction. This time, she touches the starting line again and the number of laps in the machine increase by 1$1$. The machine now reports 2$2$ laps. After this, she is 1$1$ unit from the starting line in the clockwise direction.
• Finally, she runs 6$6$ units in the clockwise direction, and she touches the starting line again, increasing the number of laps in the machine by 1$1$. At the end, the machine reports 3$3$ laps.

In Sample Case #2, the length of the circular track is 8$8$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs 5$5$ units in the clockwise direction. Ada is now 5$5$ units from the starting line in the clockwise direction.
• Next, she runs 9$9$ units in the clockwise direction, touching the starting line. The number of laps in the machine increases by 1$1$. The machine now reports 1$1$ lap. After this, she is 6$6$ units from the starting line in the clockwise direction.
• Next, she runs 8$8$ units in the clockwise direction. She touches the starting line again, increasing the number of laps in the machine by 1$1$. The machine now reports 2$2$ laps. After this, she is 6$6$ units from the starting line in the clockwise direction.
• Finally, she runs 20$20$ units in the clockwise direction. This time, she touches the starting line a total of 3$3$ times, increasing the number of laps in the machine by 3$3$. At the end, the machine reports 5$5$ laps.

Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input

3
5 3
8 C
4 A
5 C
4 5
2 C
8 A
3 A
5 C
8 A
4 3
3 C
2 A
5 C

Sample Output

Case #1: 1
Case #2: 5
Case #3: 1

In Sample Case #1, the length of the circular track is 5$5$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs 8$8$ units in the clockwise direction, touching the starting line in the process, and the number of laps in the machine increases by 1$1$. The machine now reports 1$1$ lap. Ada is now 3$3$ units from the starting line in the clockwise direction.
• Next, she runs runs 4$4$ units in the anticlockwise direction. She touches the starting line, but since she touches it running in the opposite direction to what she was running previously, this does not increase the number of laps in the machine. She is now 1$1$ unit from the starting line in the anticlockwise direction.
• Finally, she runs 5$5$ units in the clockwise direction. This time, again, she touches the starting line, but since she last touched it in the anticlockwise direction, this is not counted by the machine. She does not touch the starting line again and at the end, the machine reports 1$1$ lap.

In Sample Case #2, the length of the circular track is 4$4$ units. Ada is facing the clockwise direction in the beginning.

• First, Ada runs 2$2$ units in the clockwise direction. Ada is now 2$2$ units from the starting line in the clockwise direction.
• Next, she runs runs 8$8$ units in the anticlockwise direction. She touches the starting line, but since she touches it running in the opposite direction to what she was running previously, this does not increase the number of laps in the machine. She then continues running and ends up touching the starting line again. This time the number of laps reported by the machine increases by 1$1$. The machine now reports 1$1$ lap. After this run, she is 2$2$ units from the starting line in the anticlockwise direction.
• Next, she runs 3$3$ units in the anticlockwise direction. She touches the starting line, and the number of laps in the machine increases by 1$1$. The machine now reports 2$2$ laps. After this run, she is 1$1$ unit from the starting line in the anticlockwise direction.
• Next, she runs 5$5$ units in the clockwise direction. She touches the starting line, but this is not counted by the machine. She keeps running and then touches the starting line at the end of her run, increasing the number of laps in the machine by 1$1$. The machine now reports 3$3$ laps. After this run, she is at the starting line facing the clockwise direction.
• Finally, she runs 8$8$ units in the anticlockwise direction. At the beginning of this run, she changes her direction at the starting line, and the machine now considers the new direction, anticlockwise, as the direction she last touched the starting line. She continues running and touches the starting line twice in the anticlockwise direction, increasing the number of laps in the machine by 2$2$. At the end, the machine reports 5$5$ laps.

In Sample Case #3, the length of the circular track is 4$4$ units. Ada is facing in the clockwise direction in the beginning.

• First, Ada runs 3$3$ units in the clockwise direction. After this, she is 3$3$ units from the starting line in the clockwise direction.
• Next, she runs 2$2$ units in the anticlockwise direction. During this run, she does not touch the starting line, so the machine still considers the clockwise direction as the last direction. After this run, she is 1$1$ unit from the starting line in the clockwise direction.
• Finally, she runs 5$5$ units in the clockwise direction. She crosses the starting line once, running in the same direction, clockwise, as the last time she departed from it and the count of number of laps in the machine increases by 1$1$. At the end, the machine reports 1$1$ lap.

Solution :

The main idea is that we will check the last direction with the current one.

If it matches we add it to our distance else we subtract it from our distance covered.

If we cross the starting line by completing the round we increase our answer else we need to change the direction of completing the laps.

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

  int x = 1;

  while (b)

  {

    if (b & 1) x *= a;

    a *= a;

    b >>= 1;

  }

  return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

  const char* comma = strchr (names + 1, ',');

  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

void solve(int tc) {

int l,n;

cin>>l>>n;

vector<pair<int,char>> v(n);

int ans=0;

for (int i = 0; i < n; i++)

{

    cin>>v[i].first;

    cin>>v[i].second;

}

char last='K';

int d=0;

for (int i = 0; i < n; i++)

{    

// for the first running

    if(last=='K'){

      d+=v[i].first;

      last=v[i].second;

    }// checking from the last one and it matches

    else if(last==v[i].second){

      d+=v[i].first;

    }// not matches with last one

    else{

      d-=v[i].first;

// if we cross the staring point in opposite direction we need to change our dir

      if(d<=0)last=v[i].second;

      d=abs(d);

    }

    ans+=d/l;

    d%=l;

}

cout<<"Case #"<<tc<<": "<<ans<<endl;

}

int32_t main()

{

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;

  cin >> t;

  int k=1;

  while (t--) solve(k++);

  return 0;

}