2/20/24, 9:36 PM Problem - 1644E - Codeforces

|
stdfloat | Logout

HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP

PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST

Educational Codeforces Round

E. Expand the Path 123 (Rated for Div. 2)

time limit per test: 2 seconds Finished

memory limit per test: 256 megabytes Practice
input: standard input
output: standard output

Consider a grid of size n × n. The rows are numbered top to bottom from 1 to n, the columns
are numbered left to right from 1 to n. → Virtual participation 

The robot is positioned in a cell (1, 1) . It can perform two types of moves:
→ Clone Contest to Mashup 
D — move one cell down;
R — move one cell right.
→ Submit?
The robot is not allowed to move outside the grid.
Language: GNU G++20 11.2.0 (64 bit, w
You are given a sequence of moves s — the initial path of the robot. This path doesn't lead the
Choose
robot outside the grid. Choose File No file chosen
file:

You are allowed to perform an arbitrary number of modifications to it (possibly, zero). With one Submit
modification, you can duplicate one move in the sequence. That is, replace a single
occurrence of D with DD or a single occurrence of R with RR.

Count the number of cells such that there exists at least one sequence of modifications that → Contest materials
the robot visits this cell on the modified path and doesn't move outside the grid.
Announcement
Input Tutorial
The first line contains a single integer t (1
4
≤ t ≤ 10 ) — the number of testcases.

The first line of each testcase contains the single integer n (2 ≤ n ≤ 10

8
) — the number of
rows and columns in the grid.

The second line of each testcase contains a non-empty string s , consisting only of characters
D and R, — the initial path of the robot. This path doesn't lead the robot outside the grid.
5
The total length of strings s over all testcases doesn't exceed 2 ⋅ 10 .

Output
For each testcase, print a single integer — the number of cells such that there exists at least
one sequence of modifications that the robot visits this cell on the modified path and doesn't
move outside the grid.

Example
input Copy

3
4
RD
5
DRDRDRDR
3
D

output Copy

13
9
3

https://codeforces.com/problemset/problem/1644/E 1/2
2/20/24, 9:36 PM Problem - 1644E - Codeforces
Note
In the first testcase, it's enough to consider the following modified paths:

RD → RRD → RRRD → RRRDD → RRRDDD — this path visits cells (1, 1) , (1, 2) ,
(1, 3) , (1, 4) , (2, 4) , (3, 4) and (4, 4) ;
RD → RRD → RRDD → RRDDD — this path visits cells (1, 1) , (1, 2) , (1, 3) , (2, 3) ,
(3, 3) and (4, 3) ;
RD → RDD → RDDD — this path visits cells (1, 1) , (1, 2) , (2, 2) , (3, 2) and (4, 2) .

Thus, the cells that are visited on at least one modified path are: (1, 1) , (1, 2) , (1, 3) , (1, 4) ,
(2, 2) , (2, 3) , (2, 4) , (3, 2) , (3, 3) , (3, 4) , (4, 2) , (4, 3) and (4, 4) .

In the second testcase, there is no way to modify the sequence without moving the robot
outside the grid. So the only visited cells are the ones that are visited on the path DRDRDRDR.

In the third testcase, the cells that are visited on at least one modified path are: (1, 1) , (2, 1)
and (3, 1) .

Here are the cells for all testcases:

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform
Server time: Feb/20/2024 21:18:22UTC+5 (f1).
Desktop version, switch to mobile version.
Privacy Policy

Supported by

https://codeforces.com/problemset/problem/1644/E 2/2