B. Dasha and friends

Codeforces

IDCF761B

Time2000ms

Memory256MB

Difficulty—

brute forceimplementationmath

English · Original

Chinese · Translation

Formal · Original

Running with barriers on the circle track is very popular in the country where Dasha lives, so no wonder that on her way to classes she saw the following situation: The track is the circle with length _L_, in distinct points of which there are _n_ barriers. Athlete always run the track in counterclockwise direction if you look on him from above. All barriers are located at integer distance from each other along the track. Her friends the parrot Kefa and the leopard Sasha participated in competitions and each of them ran one lap. Each of the friends started from some integral point on the track. Both friends wrote the distance from their start along the track to each of the _n_ barriers. Thus, each of them wrote _n_ integers in the ascending order, each of them was between 0 and _L_ - 1, inclusively. <center>![image](https://espresso.codeforces.com/17ca2ca5016e06b66bbe8e35a8786cf54d1a71b9.png) Consider an example. Let _L_ = 8, blue points are barriers, and green points are Kefa's start (A) and Sasha's start (B). Then Kefa writes down the sequence \[2, 4, 6\], and Sasha writes down \[1, 5, 7\].</center>There are several tracks in the country, all of them have same length and same number of barriers, but the positions of the barriers can differ among different tracks. Now Dasha is interested if it is possible that Kefa and Sasha ran the same track or they participated on different tracks. Write the program which will check that Kefa's and Sasha's tracks coincide (it means that one can be obtained from the other by changing the start position). Note that they always run the track in one direction — counterclockwise, if you look on a track from above. ## Input The first line contains two integers _n_ and _L_ (1 ≤ _n_ ≤ 50, _n_ ≤ _L_ ≤ 100) — the number of barriers on a track and its length. The second line contains _n_ distinct integers in the ascending order — the distance from Kefa's start to each barrier in the order of its appearance. All integers are in the range from 0 to _L_ - 1 inclusively. The second line contains _n_ distinct integers in the ascending order — the distance from Sasha's start to each barrier in the order of its overcoming. All integers are in the range from 0 to _L_ - 1 inclusively. ## Output Print "_YES_" (without quotes), if Kefa and Sasha ran the coinciding tracks (it means that the position of all barriers coincides, if they start running from the same points on the track). Otherwise print "_NO_" (without quotes). [samples] ## Note The first test is analyzed in the statement.

在达莎所居住的国家，圆形跑道上的障碍赛非常流行，因此她在去上课的路上看到了以下情景：跑道是一个长度为 $L$ 的圆，其上在不同点处设有 $n$ 个障碍物。运动员总是沿逆时针方向跑步（从上方观察）。所有障碍物沿跑道彼此之间的距离均为整数。她的朋友鹦鹉基fa和豹子萨沙参加了比赛，每人跑了一圈。他们各自从跑道上的某个整数位置出发。两位朋友都记录了从他们的起点沿跑道到每个 $n$ 个障碍物的距离。因此，他们各自写下了 $n$ 个按升序排列的整数，每个整数都在 $0$ 到 $L - 1$ 之间（包含两端）。该国存在多条跑道，所有跑道长度相同、障碍物数量相同，但障碍物的位置可能不同。现在达莎想知道，基fa和萨沙是否在同一条跑道上跑步，还是在不同的跑道上。请编写一个程序，判断基fa和萨沙的跑道是否一致（即，一条跑道可以通过改变起点位置得到另一条）。注意，他们总是沿同一方向跑步——从上方观察时为逆时针方向。第一行包含两个整数 $n$ 和 $L$ ($1 ≤ n ≤ 50$, $n ≤ L ≤ 100$) —— 跑道上障碍物的数量和跑道的长度。第二行包含 $n$ 个按升序排列的互不相同的整数 —— 基fa的起点到每个障碍物的距离，按其出现顺序排列。所有整数均在 $0$ 到 $L - 1$ 范围内（包含两端）。第三行包含 $n$ 个按升序排列的互不相同的整数 —— 萨沙的起点到每个障碍物的距离，按其被越过顺序排列。所有整数均在 $0$ 到 $L - 1$ 范围内（包含两端）。如果基fa和萨沙跑的是相同的跑道（即，如果他们从跑道上相同的点出发，则所有障碍物的位置都重合），请输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。第一个测试用例已在题面中分析。 ## Input 第一行包含两个整数 $n$ 和 $L$ ($1 ≤ n ≤ 50$, $n ≤ L ≤ 100$) —— 跑道上障碍物的数量和跑道的长度。第二行包含 $n$ 个按升序排列的互不相同的整数 —— 基fa的起点到每个障碍物的距离，按其出现顺序排列。所有整数均在 $0$ 到 $L - 1$ 范围内（包含两端）。第三行包含 $n$ 个按升序排列的互不相同的整数 —— 萨沙的起点到每个障碍物的距离，按其被越过顺序排列。所有整数均在 $0$ 到 $L - 1$ 范围内（包含两端）。 ## Output 如果基fa和萨沙跑的是相同的跑道（即，如果他们从跑道上相同的点出发，则所有障碍物的位置都重合），请输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。 [samples] ## Note 第一个测试用例已在题面中分析。

**Definitions** Let $ n, L \in \mathbb{Z} $ with $ 1 \leq n \leq 50 $ and $ n \leq L \leq 100 $. Let $ K = (k_1, k_2, \dots, k_n) $ and $ S = (s_1, s_2, \dots, s_n) $ be two strictly increasing sequences of integers, where $ 0 \leq k_i, s_i < L $ for all $ i $, representing the distances from Kefa’s and Sasha’s starting points to the barriers, respectively, in counterclockwise order. **Constraints** 1. $ k_1 < k_2 < \dots < k_n $ 2. $ s_1 < s_2 < \dots < s_n $ 3. All $ k_i, s_i \in \{0, 1, \dots, L-1\} $ **Objective** Determine whether there exists a constant $ d \in \mathbb{Z}_L $ such that the multiset $ \{ (k_i + d) \mod L \mid i = 1, \dots, n \} $ equals the multiset $ \{ s_i \mid i = 1, \dots, n \} $. That is, the barrier positions relative to the track are identical up to a cyclic shift (rotation) of the starting point. Output "YES" if such $ d $ exists; otherwise, output "NO".

Samples

Input #1

3 8
2 4 6
1 5 7

Output #1

YES

Input #2

4 9
2 3 5 8
0 1 3 6

Output #2

YES

Input #3

2 4
1 3
1 2

Output #3

NO

API Response (JSON)

{
  "problem": {
    "name": "B. Dasha and friends",
    "description": {
      "content": "Running with barriers on the circle track is very popular in the country where Dasha lives, so no wonder that on her way to classes she saw the following situation: The track is the circle with lengt",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF761B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Running with barriers on the circle track is very popular in the country where Dasha lives, so no wonder that on her way to classes she saw the following situation:\n\nThe track is the circle with lengt...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在达莎所居住的国家，圆形跑道上的障碍赛非常流行，因此她在去上课的路上看到了以下情景：\n\n跑道是一个长度为 $L$ 的圆，其上在不同点处设有 $n$ 个障碍物。运动员总是沿逆时针方向跑步（从上方观察）。所有障碍物沿跑道彼此之间的距离均为整数。\n\n她的朋友鹦鹉基fa和豹子萨沙参加了比赛，每人跑了一圈。他们各自从跑道上的某个整数位置出发。两位朋友都记录了从他们的起点沿跑道到每个 $n$ 个障碍物的距离。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, L \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 50 $ and $ n \\leq L \\leq 100 $.  \nLet $ K = (k_1, k_2, \\dots, k_n) $ and $ S = (s_1, s_2, \\dots, s_n) $ be two strictly increasing se...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments