小工具知识网

当前位置: 首页 > 行业知识 > Codeforces Round 933 (Div. 3)

行业知识

Codeforces Round 933 (Div. 3)

2026-11-18 07:18:00 来源:互联网转载

A. Rudolf and the Ticket

time limit per test: 1 second memory limit per test: 256 megabytes input: standard input output: standard output

Rudolf is going to visit Bernard, and he decided to take the metro to get to him. The ticket can be purchased at a machine that accepts exactly two coins, the sum of which does not exceed k k k.

Rudolf has two pockets with coins. In the left pocket, there are n n n coins with denominations b 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1​,b2​,…,bn​. In the right pocket, there are m m m coins with denominations c 1 , c 2 , … , c m c_1, c_2, \dots, c_m c1​,c2​,…,cm​. He wants to choose exactly one coin from the left pocket and exactly one coin from the right pocket (two coins in total).

Help Rudolf determine how many ways there are to select indices f f f and s s s such that b f + c s ≤ k b_f + c_s \le k bf​+cs​≤k.

Input

The first line contains an integer t t t ( 1 ≤ t ≤ 100 1 \le t \le 100 1≤t≤100) — the number of test cases. Then follows the description of each test case.

The first line of each test case contains three natural numbers n n n, m m m, and k k k ( 1 ≤ n , m ≤ 100 , 1 ≤ k ≤ 2000 1 \le n, m \le 100, 1 \le k \le 2000 1≤n,m≤100,1≤k≤2000) — the number of coins in the left and right pockets, and the maximum sum of two coins for the ticket payment at the counter, respectively.

The second line of each test case contains n n n integers b i b_i bi​ ( 1 ≤ b i ≤ 1000 1 \le b_i \le 1000 1≤bi​≤1000) — the denominations of coins in the left pocket.

The third line of each test case contains m m m integers c i c_i ci​ ( 1 ≤ c i ≤ 1000 1 \le c_i \le 1000 1≤ci​≤1000) — the denominations of coins in the right pocket.

Output

For each testcase, output a single integer — the number of ways Rudolf can select two coins, taking one from each pocket, so that the sum of the coins does not exceed k k k.

Example

input

44 4 81 5 10 142 1 8 12 3 44 81 2 34 2 71 1 1 12 73 4 20001 1 11 1 1 1

output

60412

Note

Note that the pairs indicate the indices of the coins in the array, not their denominations.

In the first test case, Rudolf can choose the following pairs of coins: [ 1 , 1 ] , [ 1 , 2 ] , [ 1 , 4 ] , [ 2 , 1 ] , [ 2 , 2 ] , [ 2 , 4 ] [1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4] [1,1],[1,2],[1,4],[2,1],[2,2],[2,4].

In the second test case, Rudolf cannot choose one coin from each pocket in any way, as the sum of any two elements from the first and second arrays will exceed the value of k = 4 k=4 k=4.

In the third test case, Rudolf can choose: [ 1 , 1 ] , [ 2 , 1 ] , [ 3 , 1 ] , [ 4 , 1 ] [1, 1], [2, 1], [3, 1], [4, 1] [1,1],[2,1],[3,1],[4,1].

In the fourth test case, Rudolf can choose any coin from the left pocket and any coin from the right pocket.

Tutorial

第一题怎么快怎么来,直接暴力循环破解

Solution

for _ in range(int(input())):    n, m, k = map(int, input().split())    b = list(map(int, input().split()))    c = list(map(int, input().split()))    print(sum(b[i] + c[j] = 0:            a[i + 1] -= a[i] * 2            a[i + 2] -= a[i]            a[i] = 0        else:            ans = "NO"            break    if a[-1] or a[-2]:        ans = "NO"    print(ans)

C. Rudolf and the Ugly String

time limit per test: 2 second memory limit per test: 256 megabytes input: standard input output: standard output

Rudolf has a string s s s of length n n n. Rudolf considers the string s s s to be ugly if it contains the substring † ^\dagger † “pie” or the substring “map”, otherwise the string s s s will be considered beautiful.

For example, “ppiee”, “mmap”, “dfpiefghmap” are ugly strings, while “mathp”, “ppiiee” are beautiful strings.

Rudolf wants to shorten the string s s s by removing some characters to make it beautiful.

The main character doesn’t like to strain, so he asks you to make the string beautiful by removing the minimum number of characters. He can remove characters from any positions in the string (not just from the beginning or end of the string).

† ^\dagger † String a a a is a substring of b b b if there exists a consecutive segment of characters in string b b b equal to a a a.

Input

The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer n n n ( 1 ≤ n ≤ 1 0 6 1 \le n \le 10^6 1≤n≤106) — the length of the string s s s.

The next line of each test case contains the string s s s of length n n n. The string s s s consists of lowercase Latin letters.

The sum of n n n over all test cases does not exceed 1 0 6 10^6 106.

Output

For each test case, output a single integer — the minimum number of characters that need to be deleted to make the string s s s beautiful. If the string is initially beautiful, then output 0 0 0.

Example

input

69mmapnapie9azabazapi8mappppie18mapmapmapmapmapmap1p11pppiepieeee

output

202602

Note

In the first test case, for example, you can delete the 4 4 4th and 9 9 9th characters to make the string beautiful.

In the second test case, the string is already beautiful.

Tutorial

遇到 map 或者 pie 都需要在三个数字中选择一个字母删除,但遇到 mapie 时只需要删除中间的 p 即可,所以答案就是 map 的数量 + pie 的数量 - mapie 的数量

Solution

for _ in range(int(input())):    n = int(input())    s = input().strip()    print(s.count("map") + s.count("pie") - s.count("mapie"))

D. Rudolf and the Ball Game

time limit per test: 2 second memory limit per test: 256 megabytes input: standard input output: standard output

Rudolf and Bernard decided to play a game with their friends. n n n people stand in a circle and start throwing a ball to each other. They are numbered from 1 1 1 to n n n in the clockwise order.

Let’s call a transition a movement of the ball from one player to his neighbor. The transition can be made clockwise or counterclockwise.

Let’s call the clockwise (counterclockwise) distance from player y 1 y_1 y1​ to player y 2 y_2 y2​ the number of transitions clockwise (counterclockwise) that need to be made to move from player y 1 y_1 y1​ to player y 2 y_2 y2​. For example, if n = 7 n=7 n=7 then the clockwise distance from 2 2 2 to 5 5 5 is 3 3 3, and the counterclockwise distance from 2 2 2 to 5 5 5 is 4 4 4.

Initially, the ball is with the player number x x x (players are numbered clockwise). On the i i i-th move the person with the ball throws it at a distance of r i r_i ri​ ( 1 ≤ r i ≤ n − 1 1 \le r_i \le n - 1 1≤ri​≤n−1) clockwise or counterclockwise. For example, if there are 7 7 7 players, and the 2 2 2nd player, after receiving the ball, throws it a distance of 5 5 5, then the ball will be caught by either the 7 7 7th player (throwing clockwise) or the 4 4 4th player (throwing counterclockwise). An illustration of this example is shown below.

The game was interrupted after m m m throws due to unexpected rain. When the rain stopped, the guys gathered again to continue. However, no one could remember who had the ball. As it turned out, Bernard remembered the distances for each of the throws and the direction for some of the throws (clockwise or counterclockwise).

Rudolf asks you to help him and based on the information from Bernard, calculate the numbers of the players who could have the ball after m m m throws.

Input

The first line of the input contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains three integers n , m , x n, m, x n,m,x ( 2 ≤ n ≤ 1000 2 \le n \le 1000 2≤n≤1000, 1 ≤ m ≤ 1000 1 \le m \le 1000 1≤m≤1000, 1 ≤ x ≤ n 1 \le x \le n 1≤x≤n) — the number of players, the number of throws made, and the number of the player who threw the ball first, respectively.

The next m m m lines contain information about each throw in order. Each of them contains an integer r i r_i ri​ ( 1 ≤ r i ≤ n − 1 1 \le r_i \le n - 1 1≤ri​≤n−1) — the distance at which the i i i-th throw was made, and a symbol c i c_i ci​, equal to ‘0’, ‘1’, or ‘?’:

  • if c i c_i ci​=‘0’, then the i i i-th throw was made clockwise,
  • if c i c_i ci​=‘1’, then the i i i-th throw was made counterclockwise,
  • if c i c_i ci​=‘?’, then Bernard does not remember the direction and the i i i-th throw could have been made either clockwise or counterclockwise.

    It is guaranteed that the sum n ⋅ m n \cdot m n⋅m ( n n n multiplied by m m m) over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.

    Output

    For each test case, output two lines.

    In the first line, output the number of players k k k ( 1 ≤ k ≤ n 1 \le k \le n 1≤k≤n) who could have the ball at the end of the game.

    In the next line, output k k k numbers b i b_i bi​ ( 1 ≤ b i ≤ n 1 \le b_i \le n 1≤bi​≤n) — the numbers of the players in increasing order. All numbers must be different.

    Example

    input

    56 3 22 ?2 ?2 ?12 1 23 110 7 42 ?9 14 ?7 02 08 15 ?5 3 14 04 ?1 ?4 1 12 ?

    output

    32 4 6 111 43 5 7 9 32 3 5 13 

    Note

    Below is an illustration of three throws for the first test case. The arrows denote possible throw directions. Players who could have the ball after the throw are highlighted in gray.

    Tutorial

    从初始值开始,根据情况暴力模拟出每种情况即可

    Solution

    #include using namespace std;#define endl '\n'#define int long longvoid solve() {    int n, m, x;    cin >> n >> m >> x;    vector now(1, x);    while (m--) {        int r;        char c;        set s;        vector mid(now);        cin >> r >> c;        if (c == '0') {            for (int ai : mid) {                s.insert((ai + r) % n ? (ai + r) % n : n);            }        } else if (c == '1') {            for (int ai : mid) {                s.insert((ai - r + n) % n ? (ai - r + n) % n : n);            }        } else {            for (int ai : mid) {                s.insert((ai + r) % n ? (ai + r) % n : n);                s.insert((ai - r + n) % n ? (ai - r + n) % n : n);            }        }        now.clear();        for (int ai : s) {            now.emplace_back(ai);        }    }    cout         cout     cin.tie(nullptr)-sync_with_stdio(false);    cout     int n, m, k, d;    cin  n > m >> k >> d;    vector pre(n);    for (int i = 0; i > a[j];        }        priority_queue q;        q.emplace(1, 0);        for (int j = 1; j  m >> k;    vector a(n), d(m), f(k);    for (int &ai : a) {        cin >> ai;    }    for (int &di : d) {        cin >> di;    }    for (int &fi : f) {        cin >> fi;    }    sort(d.begin(), d.end());    sort(f.begin(), f.end());    function check = [&](int mid) -> bool {        int cnt = 0, idx = 0;        for (int i = 1; i  mid) {                if (++cnt > 1) { // 需要分割的区间最多只能有一个                    return false;                }                 idx = i;            }        }        if (not cnt) { // 已经满足条件            return true;        }        int down = a[idx] - mid, up = a[idx - 1] + mid; // 肯定是把数组塞到这个区间内        for (int left = 0, right = k - 1; left  up) {                --right;            }            if (~right and d[left] + f[right] >= down) {                return true;            }        }        return false;    };        int left = 0, right = 2e9 + 1;    while (left + 1 > 1;        (check(mid) ? right : left) = mid;    }    cout     cin.tie(nullptr)-sync_with_stdio(false);    cout     int n, m, b, e;    cin > n >> m;    vector g(n + m + 1);    map mp;    while (m--) {        int u, v, c;        cin >> u >> v >> c;        if (not mp.count(c)) { // 对每个颜色建一个虚拟点            mp[c] = ++n;        }        // 每到一个新颜色就加一        g[u].emplace_back(mp[c], 1);        g[v].emplace_back(mp[c], 1);        g[mp[c]].emplace_back(u, 0);        g[mp[c]].emplace_back(v, 0);    }    cin >> b >> e;    function dijkstra = [&]() -> int {        priority_queue q;        vector dis(n + 1, INF);        vector memo(n + 1);        dis[b] = 0;        q.emplace(0, b);        while (q.size()) {            auto [dist, u] =  q.top();            q.pop();            if (u == e) {                return dis[e];            }            if (memo[u]) {                continue;            }            memo[u] = true;            for (auto [v, w] : g[u]) {                dis[v] = min(dis[v], dist + w);                q.emplace(dist + w, v);            }        }        return 0;    };        cout     cin.tie(nullptr)-sync_with_stdio(false);    cout 

上一篇:打造魅力HTML层叠圈,揭秘实用技巧与秘籍!

下一篇:服务器怎么不让他黑屏?