(追記) (追記ここまで)

26436번 - Running in Circles 서브태스크다국어

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
서브태스크 참고 (추가 시간 없음)	1024 MB	96	37	27	37.500%

문제

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 $\mathbf{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ドル$. 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ドル$. 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ドル$.

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 $\mathbf{N}$ times, taking breaks in between. Given the information of the distance $\mathbf{D_i}$ units Ada has run, and the direction $\mathbf{C_i}$ she has taken (clockwise or anticlockwise) when she ran the $i$-th time, for all $i$ from 1,ドル \dots, \mathbf{N},ドル can you tell the number of laps that would be reported by the machine at the end?

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains two positive integers $\mathbf{L}$ and $\mathbf{N},ドル the length of the circular track in units, and the number of times Ada has run respectively.

The next $\mathbf{N}$ lines describe Ada's runs. The $i$-th line contains a positive integer $\mathbf{D_i}$ and a character $\mathbf{C_i},ドル the distance in units Ada has run and the direction she has taken (clockwise or anticlockwise) respectively during the $i$-th run. $\mathbf{C_i}$ will always be either 'C' (denoting clockwise direction) or 'A' (denoting anticlockwise direction).

출력

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

제한

1ドル \le \mathbf{T} \le 100$.
1ドル \le \mathbf{L} \le 10^9$.
1ドル \le \mathbf{N} \le 10^4$.
1ドル \le \mathbf{D_i} \le 10^9,ドル for all 1ドル \le i \le \mathbf{N}$.

Test Set 1 (6점)

시간 제한: 20 초

$\mathbf{C_i}$ is always 'C', for all 1ドル \le i \le \mathbf{N}$.

Test Set 2 (9점)

시간 제한: 40 초

$\mathbf{C_i}$ can be either 'C' or 'A', for all 1ドル \le i \le \mathbf{N}$.

예제 입력 1

예제 출력 1

Case #1: 3
Case #2: 5

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

First, Ada runs 8ドル$ units in the clockwise direction, touching the starting line in the process, and the number of laps in the machine increases by 1ドル$. The machine now reports 1ドル$ lap. Ada is now 3ドル$ units from the starting line in the clockwise direction.
Next, she runs 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ドル$. The machine now reports 2ドル$ laps. After this, she is 1ドル$ unit from the starting line in the clockwise direction.
Finally, she runs 6ドル$ units in the clockwise direction, and she touches the starting line again, increasing the number of laps in the machine by 1ドル$. At the end, the machine reports 3ドル$ laps.

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

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

예제 입력 2

예제 출력 2

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

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

First, Ada runs 8ドル$ units in the clockwise direction, touching the starting line in the process, and the number of laps in the machine increases by 1ドル$. The machine now reports 1ドル$ lap. Ada is now 3ドル$ units from the starting line in the clockwise direction.
Next, she runs runs 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ドル$ unit from the starting line in the anticlockwise direction.
Finally, she runs 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ドル$ lap.

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

First, Ada runs 2ドル$ units in the clockwise direction. Ada is now 2ドル$ units from the starting line in the clockwise direction.
Next, she runs runs 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ドル$. The machine now reports 1ドル$ lap. After this run, she is 2ドル$ units from the starting line in the anticlockwise direction.
Next, she runs 3ドル$ units in the anticlockwise direction. She touches the starting line, and the number of laps in the machine increases by 1ドル$. The machine now reports 2ドル$ laps. After this run, she is 1ドル$ unit from the starting line in the anticlockwise direction.
Next, she runs 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ドル$. The machine now reports 3ドル$ laps. After this run, she is at the starting line facing the clockwise direction.
Finally, she runs 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ドル$. At the end, the machine reports 5ドル$ laps.

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

First, Ada runs 3ドル$ units in the clockwise direction. After this, she is 3ドル$ units from the starting line in the clockwise direction.
Next, she runs 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ドル$ unit from the starting line in the clockwise direction.
Finally, she runs 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ドル$. At the end, the machine reports 1ドル$ lap.

힌트

출처

Contest > Google > Kick Start > Google Kick Start 2022 > Round H A번

채점 및 기타 정보

예제는 채점하지 않는다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC