codeforces-scrape

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

1473B.md (1535B)


      1 Source: https://codeforces.com/problemset/problem/1473/B
      2 
      3 B. String LCM
      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 Let's define a multiplication operation between a string $a$ and a positive integer $x$: $a \cdot x$ is the string that is a result of writing $x$ copies of $a$ one after another. For example, "abc" $\cdot~2~=$ "abcabc", "a" $\cdot~5~=$ "aaaaa".
     22 
     23 A string $a$ is divisible by another string $b$ if there exists an integer $x$ such that $b \cdot x = a$. For example, "abababab" is divisible by "ab", but is not divisible by "ababab" or "aa".
     24 
     25 LCM of two strings $s$ and $t$ (defined as $LCM(s, t)$) is the shortest non-empty string that is divisible by both $s$ and $t$.
     26 
     27 You are given two strings $s$ and $t$. Find $LCM(s, t)$ or report that it does not exist. It can be shown that if $LCM(s, t)$ exists, it is unique.
     28 
     29 Input
     30 
     31 The first line contains one integer $q$ ($1 \le q \le 2000$) — the number of test cases.
     32 
     33 Each test case consists of two lines, containing strings $s$ and $t$ ($1 \le |s|, |t| \le 20$). Each character in each of these strings is either 'a' or 'b'.
     34 
     35 Output
     36 
     37 For each test case, print $LCM(s, t)$ if it exists; otherwise, print -1. It can be shown that if $LCM(s, t)$ exists, it is unique.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 3
     45 baba
     46 ba
     47 aa
     48 aaa
     49 aba
     50 ab
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 baba
     57 aaaaaa
     58 -1
     59 ```
     60 
     61 Note
     62 
     63 In the first test case, "baba" = "baba" $\cdot~1~=$ "ba" $\cdot~2$.
     64 
     65 In the second test case, "aaaaaa" = "aa" $\cdot~3~=$ "aaa" $\cdot~2$.