Codeforces 626A Robot Sequence(模拟)

A. Robot Sequence

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

Calvin the robot lies in an infinite rectangular grid. Calvin's source code contains a list of n commands, each either 'U', 'R', 'D', or 'L' — instructions to move a single square up, right, down, or left, respectively. How many ways can Calvin execute a non-empty contiguous substrings of commands and return to the same square he starts in? Two substrings are considered different if they have different starting or ending indices.

Input

The first line of the input contains a single positive integer, n (1 ≤ n ≤ 200) — the number of commands.

The next line contains n characters, each either 'U', 'R', 'D', or 'L' — Calvin's source code.

Output

Print a single integer — the number of contiguous substrings that Calvin can execute and return to his starting square.

Examples

Input

6
URLLDR

Output

2

Input

4
DLUU

Output

0

Input

7
RLRLRLR

Output

12

Note

In the first case, the entire source code works, as well as the "RL" substring in the second and third characters.

Note that, in the third case, the substring "LR" appears three times, and is therefore counted three times to the total result.

题目链接:http://codeforces.com/contest/626/problem/A

题意:在一块方格里,给出一串指令包含U,D,L,R这些字母,分别表示上下左右移动一格。问有多少个子串(包含自身)能使得物体回到出发位置。

分析:模拟一下找子串的个数即可!

解释下样例3:子串为:RL,RLRL,RLRLRL,LR,LRLR,LRLRLR,RL,RLRL,LR,LRLR,RL,LR,共12条,所以输出为12

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 inline int read()
 4 {
 5     int x=0,f=1;
 6     char ch=getchar();
 7     while(ch<'0'||ch>'9')
 8     {
 9         if(ch='-')
10             f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9')
14     {
15         x=x*10+ch-'0';
16         ch=getchar();
17     }
18     return x*f;
19 }
20 int n;
21 char s[255];
22 int main()
23 {
24     n=read();
25     cin>>s;
26     int e=0;
27     for(int i=0;i<n;i++)
28     {
29         int a=0,b=0,c=0,d=0;
30         for(int j=i;j<n;j++)
31         {
32             if(s[j]=='U')
33                 a++;
34             if(s[j]=='D')
35                 b++;
36             if(s[j]=='L')
37                 c++;
38             if(s[j]=='R')
39                 d++;
40             if(a==b&&c==d)
41                 e++;
42         }
43     }
44     cout<<e<<endl;
45     return 0;
46 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏函数式编程语言及工具

Scala Macros - 元编程 Metaprogramming with Def Macros

    Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具,可以通过它来解决一些用普通编程或者类层次编程(type level pr...

32090
来自专栏mathor

KMP(3)

140100
来自专栏跟着阿笨一起玩NET

C# 中用 yield return 关键字实现获取树型数据结构的所有子节点

通常,我们在获取树形结构数据所有子节点时,需要写一个递归调用的方法,循环调用,这是数据结构算法里的通用写法。

21420
来自专栏我是业余自学C/C++的

线性表——链式描述(双向链表)

15030
来自专栏Petrichor的专栏

tensorflow: Shapes and Shaping 探究

10810
来自专栏邵靖的专栏

Python 字符串子串定位性能比较

本文想探讨的是在给定了key字段在字段列表中开始下标和key字段个数后,如何在整行字符串中定位到key字符串的起始位置。

94810
来自专栏mathor

回文自动机、AC自动机和后缀自动机介绍(1)

 我们还从一个非常经典的题目出发,最长公共子串问题。给定两个字符串S和T,求S和T的最长公共子串的长度。比如abcdefg和abacabca的最长公共子串是ab...

32330
来自专栏小俊博客

微软 KMS 客户端密钥

27650
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

29510
来自专栏应用案例

数据结构试题库答案算法设计题

算法设计题(10分) (1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x; scanf(...

27580

扫码关注云+社区

领取腾讯云代金券