2156B.md (4073B)
1 Source: https://codeforces.com/problemset/problem/2156/B 2 3 B. Strange Machine 4 5 time limit per test 6 7 1.5 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 are given $n$ machines arranged in a circle, where $n$ is at most $20$. Each machine is either of type A or type B. The machines are numbered clockwise from $1$ to $n$, and the type of the $i$-th machine is denoted by $s_i$. Each machine takes an integer $x$ and updates it according to its type: 22 23 * Type A: Decrease $x$ by $1$. Formally, update $x := x - 1$. 24 * Type B: Replace $x$ with the floor of half its value. Formally, update $x := \left\lfloor\frac{x}{2}\right\rfloor$, where $\lfloor y\rfloor$ denotes the [floor](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) of $y$, which is the greatest integer less than or equal to $y$. 25 26 You are given $q$ queries, each consisting of a single integer $a$. In each query, you start at machine $1$ holding an integer $a$. Each second, the following two actions occur in order: 27 28 1. The current machine updates $a$ according to its type. 29 2. Then, move one step clockwise to the next machine. Formally 30 * If you are at machine $i$ where $1 \le i \le n - 1$, move to machine $i + 1$. 31 * If you are at machine $n$, move to machine $1$. 32 33 This process continues until your integer $a$ becomes $0$. For each query, determine the number of seconds required for $a$ to reach $0$. 34 35 Note that all queries are independent of each other. 36 37 Input 38 39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 40 41 The first line of each test case contains two integers $n$ and $q$ ($1\le n\le 20$, $1\le q\le 10^4$) — the number of machines, and the number of queries, respectively. 42 43 The second line of each test case contains a string $s$ ($|s| = n$ and $s_i = \mathtt{A} \text{ or }\mathtt{B}$) — the types of the machines. 44 45 The third line of each test case contains $q$ integers $a_1, a_2, \ldots, a_q$ ($1\le a_i\le 10^9$) — the initial integer of each query. 46 47 Note that there are no constraints on the sum of $n$ over all test cases. 48 49 It is guaranteed that the sum of $q$ over all test cases does not exceed $10^4$. 50 51 Output 52 53 For each test case, output $q$ integers representing the answers to each query. 54 55 Example 56 57 Input 58 59 ``` 60 3 61 62 2 2 63 64 BA 65 66 3 4 67 68 1 1 69 70 B 71 72 20 73 74 6 4 75 76 BAABBA 77 78 2 8 32 95 79 ``` 80 81 Output 82 83 ``` 84 2 85 86 3 87 88 5 89 90 2 91 92 5 93 94 8 95 96 11 97 ``` 98 99 Note 100 101 In the first test case, the queries are as follows: 102 103 * Query $1$: $a = 3$ 104 1. Start at machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{3}{2}\right\rfloor = 1$. 105 2. Move to machine $2$. Machine $2$ decreases $a$ by $1$. Now, $a = 1 - 1 = 0$.Therefore, it takes $2$ seconds for $a$ to reach $0$. 106 * Query $2$: $a = 4$ 107 1. Start at machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{4}{2}\right\rfloor = 2$. 108 2. Move to machine $2$. Machine $2$ decreases $a$ by $1$. Now, $a = 2 - 1 = 1$. 109 3. Move back to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{1}{2}\right\rfloor = 0$.Therefore, it takes $3$ seconds for $a$ to reach $0$. 110 111 In the second test case, there is only one query with $a = 20$: 112 113 1. Start at machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{20}{2}\right\rfloor = 10$. 114 2. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{10}{2}\right\rfloor = 5$. 115 3. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{5}{2}\right\rfloor = 2$. 116 4. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{2}{2}\right\rfloor = 1$. 117 5. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{1}{2}\right\rfloor = 0$. 118 119 Therefore, it takes $5$ seconds for $a$ to reach $0$.