codeforces-scrape

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

2182C.md (3510B)


      1 Source: https://codeforces.com/problemset/problem/2182/C
      2 
      3 C. Production of Snowmen
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 To create a truly festive atmosphere, Santa's helpers have opened a factory for producing snowmen!
     22 
     23 Each snowman consists of three snowballs — a head, a torso, and legs. For the snowman to be stable, the ball forming the legs must be strictly larger than the ball forming the torso; in turn, the ball forming the torso must be strictly larger than the ball forming the head. Formally, if we denote the sizes of the head, torso, and legs as $a, b, c$ respectively, the snowman will be stable if and only if $a \lt b \lt c$.
     24 
     25 At the snowman production factory, there are three conveyors, each containing $n$ snowballs. The first conveyor contains balls of sizes $a_1, a_2, \dots, a_n$; the second contains balls of sizes $b_1, b_2, \dots, b_n$; the third contains balls of sizes $c_1, c_2, \dots, c_n$. The conveyors are cyclic; in other words, after the element numbered $n$, the element numbered $1$ follows again, and we can consider that the ball numbered $i$ and the ball numbered $i+n$ (as well as the ball numbered $i+2n$, $i+3n$, and so on) are the same ball.
     26 
     27 To produce snowmen, it is necessary to specify three parameters $i, j, k$ ($1 \le i, j, k \le n$), indicating which balls on each conveyor the production starts from. After that, the snowmen will be assembled from the balls as follows:
     28 
     29 * the first snowman will have a head of size $a_i$, a torso of size $b_j$, and legs of size $c_k$;
     30 * the second snowman will have a head of size $a_{i+1}$, a torso of size $b_{j+1}$, and legs of size $c_{k+1}$;
     31 * and so on;
     32 * the $n$-th (last) snowman will have a head of size $a_{i+n-1}$, a torso of size $b_{j+n-1}$, and legs of size $c_{k+n-1}$.
     33 
     34 The parameters $i, j, k$ must be chosen in such a way that all $n$ snowmen are stable. Your task is to count the number of suitable combinations of parameters.
     35 
     36 Input
     37 
     38 The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.
     39 
     40 Each test case consists of four lines:
     41 
     42 * the first line contains one integer $n$ ($1 \le n \le 5000$);
     43 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3n$);
     44 * the third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 3n$);
     45 * the fourth line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 3n$).
     46 
     47 Additional constraint on the input: the sum of $n$ across all test cases does not exceed $5000$.
     48 
     49 Output
     50 
     51 For each test case, output one integer — the number of combinations of parameters $i, j, k$ for which all $n$ snowmen will be stable.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 4
     59 
     60 2
     61 
     62 1 2
     63 
     64 3 4
     65 
     66 5 4
     67 
     68 3
     69 
     70 1 1 1
     71 
     72 2 2 2
     73 
     74 3 3 3
     75 
     76 4
     77 
     78 1 2 1 2
     79 
     80 3 3 2 2
     81 
     82 5 5 5 5
     83 
     84 5
     85 
     86 1 4 2 3 5
     87 
     88 6 4 5 7 6
     89 
     90 7 5 8 10 10
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 4
     97 
     98 27
     99 
    100 0
    101 
    102 10
    103 ```
    104 
    105 Note
    106 
    107 In the first example, suitable sets of parameters $i, j, k$ are as follows:
    108 
    109 * $i = 1, j = 1, k = 2$: then the snowmen will be $(1, 3, 4)$ and $(2, 4, 5)$;
    110 * $i = 1, j = 2, k = 1$: then the snowmen will be $(1, 4, 5)$ and $(2, 3, 4)$;
    111 * $i = 2, j = 1, k = 2$: then the snowmen will be $(2, 3, 4)$ and $(1, 4, 5)$;
    112 * $i = 2, j = 2, k = 1$: then the snowmen will be $(2, 4, 5)$ and $(1, 3, 4)$.
    113 
    114 In the second example, all combinations of parameters are suitable.
    115 
    116 In the third example, for any combination of parameters, a snowman with a head size of $2$ and a torso size of $2$ will be produced, which is not stable.