codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2094D.md (1783B)


      1 Source: https://codeforces.com/problemset/problem/2094/D
      2 
      3 D. Tung Tung Sahur
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You have two drums in front of you: a left drum and a right drum. A hit on the left can be recorded as "L", and a hit on the right as "R".
     22 
     23 The strange forces that rule this world are fickle: sometimes, a blow sounds once, and sometimes it sounds twice. Therefore, a hit on the left drum could have sounded as either "L" or "LL", and a hit on the right drum could have sounded as either "R" or "RR".
     24 
     25 The sequence of hits made is recorded in the string $p$, and the sounds heard are in the string $s$. Given $p$ and $s$, determine whether it is true that the string $s$ could have been the result of the hits from the string $p$.
     26 
     27 For example, if $p=$"LR", then the result of the hits could be any of the strings "LR", "LRR", "LLR", and "LLRR", but the strings "LLLR" or "LRL" cannot.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) – the number of independent test cases.
     32 
     33 The first line of each test case contains the string $p$ ($1 \le |p| \le 2 \cdot 10^5$) consisting only of the characters "R" and "L", where $|p|$ denotes the length of the string $p$.
     34 
     35 The second line of each test case contains the string $s$ ($1 \le |p| \le |s| \le 2 \cdot 10^5$) consisting only of the characters "R" and "L".
     36 
     37 It is guaranteed that the sum of $|s|$ does not exceed $2\cdot 10^5$ across all test cases.
     38 
     39 Output
     40 
     41 For each set of input data, output "YES" if $s$ can be the heard sound, and "NO" otherwise. You may output in any case.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 R
     51 
     52 RR
     53 
     54 LRLR
     55 
     56 LRLR
     57 
     58 LR
     59 
     60 LLLR
     61 
     62 LLLLLRL
     63 
     64 LLLLRRLL
     65 
     66 LLRLRLRRL
     67 
     68 LLLRLRRLLRRRL
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 YES
     75 YES
     76 NO
     77 NO
     78 YES
     79 ```