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.