codeforces-scrape

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

1968D.md (3131B)


      1 Source: https://codeforces.com/problemset/problem/1968/D
      2 
      3 D. Permutation Game
      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 Bodya and Sasha found a permutation $p_1,\dots,p_n$ and an array $a_1,\dots,a_n$. They decided to play a well-known "Permutation game".
     22 
     23 A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     24 
     25 Both of them chose a starting position in the permutation.
     26 
     27 The game lasts $k$ turns. The players make moves simultaneously. On each turn, two things happen to each player:
     28 
     29 * If the current position of the player is $x$, his score increases by $a_x$.
     30 * Then the player either stays at his current position $x$ or moves from $x$ to $p_x$.
     31 
     32 The winner of the game is the player with the higher score after exactly $k$ turns.
     33 
     34 Knowing Bodya's starting position $P_B$ and Sasha's starting position $P_S$, determine who wins the game if both players are trying to win.
     35 
     36 Input
     37 
     38 The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of testcases.
     39 
     40 The first line of each testcase contains integers $n$, $k$, $P_B$, $P_S$ ($1\le P_B,P_S\le n\le 2\cdot 10^5$, $1\le k\le 10^9$) — length of the permutation, duration of the game, starting positions respectively.
     41 
     42 The next line contains $n$ integers $p_1,\dots,p_n$ ($1 \le p_i \le n$) — elements of the permutation $p$.
     43 
     44 The next line contains $n$ integers $a_1,\dots,a_n$ ($1\le a_i\le 10^9$) — elements of array $a$.
     45 
     46 It is guaranteed that the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     47 
     48 Output
     49 
     50 For each testcase output:
     51 
     52 * "Bodya" if Bodya wins the game.
     53 * "Sasha" if Sasha wins the game.
     54 * "Draw" if the players have the same score.
     55 
     56 Example
     57 
     58 Input
     59 
     60 ```
     61 10
     62 
     63 4 2 3 2
     64 
     65 4 1 2 3
     66 
     67 7 2 5 6
     68 
     69 10 8 2 10
     70 
     71 3 1 4 5 2 7 8 10 6 9
     72 
     73 5 10 5 1 3 7 10 15 4 3
     74 
     75 2 1000000000 1 2
     76 
     77 1 2
     78 
     79 4 4
     80 
     81 8 10 4 1
     82 
     83 5 1 4 3 2 8 6 7
     84 
     85 1 1 2 1 2 100 101 102
     86 
     87 5 1 2 5
     88 
     89 1 2 4 5 3
     90 
     91 4 6 9 4 2
     92 
     93 4 2 3 1
     94 
     95 4 1 3 2
     96 
     97 6 8 5 3
     98 
     99 6 9 5 4
    100 
    101 6 1 3 5 2 4
    102 
    103 6 9 8 9 5 10
    104 
    105 4 8 4 2
    106 
    107 2 3 4 1
    108 
    109 5 2 8 7
    110 
    111 4 2 3 1
    112 
    113 4 1 3 2
    114 
    115 6 8 5 3
    116 
    117 2 1000000000 1 2
    118 
    119 1 2
    120 
    121 1000000000 2
    122 ```
    123 
    124 Output
    125 
    126 ```
    127 Bodya
    128 Sasha
    129 Draw
    130 Draw
    131 Bodya
    132 Sasha
    133 Sasha
    134 Sasha
    135 Sasha
    136 Bodya
    137 ```
    138 
    139 Note
    140 
    141 Below you can find the explanation for the first testcase, where the game consists of $k=2$ turns.
    142 
    143 |  |  |  |  |  |  |  |
    144 | --- | --- | --- | --- | --- | --- | --- |
    145 | Turn | Bodya's position | Bodya's score | Bodya's move | Sasha's position | Sasha's score | Sasha's move |
    146 | first | $3$ | $0 + a_3 = 0 + 5 = 5$ | stays on the same position | $2$ | $0 + a_2 = 0 + 2 = 2$ | moves to $p_2=1$ |
    147 | second | $3$ | $5 + a_3 = 5 + 5 = 10$ | stays on the same position | $1$ | $2 + a_1 = 2 + 7 = 9$ | stays on the same position |
    148 | final results | $3$ | $10$ |  | $1$ | $9$ |  |
    149 
    150 As we may see, Bodya's score is greater, so he wins the game. It can be shown that Bodya always can win this game.