codeforces-scrape

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

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$.