Description

Niflheimr is playing Minecraft recently. He occupies a lot of towns, and there are many diamonds inside some of those towns.

Whenever he runs out of diamond, he has to figure out the nearest town with diamonds from his current location.

Doing this task every time waste a lot of time. He asks you to help him for the calculation. For every town, find the shortest distance to get diamonds from a nearby town which has diamonds. If the town itself has diamonds, the distance would be 0.

Hint: Use BFS (Breadth First Search) and std::queue.

If you are not familiar with BFS, you should take a look at the following article:

http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html

[IMPORTANT] For those almost run out of time, maybe this note can help you figure out BFS and solve this problem faster!

You are provided with the following code:

#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// G[i] is the neighbor towns of town i
vector<int> diamondTowns;
vector<int> G[100005];
int Dist[100005];

struct node {
    int id;
    int dist;
    node(int id, int l) {
        this->id = id;
        this->dist = l;
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        diamondTowns.push_back(x);
    }
    fill(Dist, Dist+100005, -1);

    queue<node> Q;

    // [TODO] complete the task!

    // Output
    for (int i = 1; i <= N; i++) {
        cout << Dist[i] << '\n';
    }
    return 0;
}

 You may take it as reference. You are not required to use this code, though.

Input

First line of input contains three integer N, M, K, denoting the number of towns, the amount of roads between towns and the number of towns which has diamond.

All the towns are numbered from 1 to N.

For the next M lines, each of them contains two integer a, b, meaning there is a road between a and b. All the roads are bidirectional, and the length of these roads are all 1.

The last line of input contains K distinct integers, denoting the towns which has diamonds.

It is guaranteed that:

• 1 <= K <= N <= 10⁵
• 1 <= M <= min(10⁶, N*(N+1)/2)
• All the towns can reach each other, i.e. the graph is connected.

Output

Output consists of N lines.

For i-th line, output the shortest distance Niflheimr has to travel from town i to get a diamond.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are playing a game. The goal of this game is to kill the monster when you are still alive (HP > 0, HP = health point). The monster is dead if and only if its HP <= 0.

This game consists of rounds, and you go first in each round.

You have 3 options in each round:

1. ATTACK. This will deduct the monster's HP. If your damage point is p, then you can deduct p monster's HP.
2. HEAL. You can recover some of your HP, but it can't exceed your max HP.
3. Level-up. Level-up might enhance the effect of attacking or healing, but if you are not lucky enough, sometimes it will deduct the effect of attacking and healing. Thus, choosing to level-up is not always a good choice. If you have reached max level, taking this action makes no effect.

In each round, the monster will attack you once with a fixed amount of damage points.

You start the game with full HP and level 1. What is the minimun number of rounds you need to kill the monster?

Input

First line contains 4 numbers L, HP, MHP, MDMG.

• L = max level
• HP = your max HP
• MHP = monster's HP in the beginning of game
• MDMG = monster's damage point

Each of the next L lines describes each level, i-th line of them describing level i. Each of them consists of two numbers, DMG and HL.

• DMG = your damage point when you use ATTACK at level i
• HL = amount of HP you can recover when you use HEAL at level i

Limits:

• L <= 15
• HP <= 300
• MHP <= 400
• MDMG <= 10000
• DMG <= 10000
• HL <= 50

Output

Print a single integer, denoting the mininum number of steps you need to kill the monster.

If you are unable to beat the monster, print -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Seto Kaiba is a grand master player of Yu-Gi-Oh.

Cards are necessary, and it's why Kaiba buys cards from time to time.

The cards are labeled with numbers.

The card Kaiba has the most is his ace. If there are two or more kinds of cards Kaiba has the most at the same time, the cards with maximum number is Kaiba's ace.

For example,

Buy: 2; Cards in hand: 2; Ace: 2

Buy: 1; Cards in hand: 2 1; Ace: 2 (Becasue 2 is the largest number)

Buy: 1; Cards in hand: 2 1 1; Ace: 1 (Becasue 1 is the most one)

Please find out what Kaiba's ace is whenever he buys a new card.

Input

The first line contains a number N — Kaiba buys N cards in total.

Each of the next N lines contains a number a_i — the number of the cards Kaiba buys.

testcase 1 and 2： N <= 100, a_i <= 10⁹.

testcase 3 and 4： N <= 3000, a_i <= 10¹⁸.

testcase 5 and 6： N <= 100000, a_i <= 10¹⁸.

Output

The output should contains N lines, each of which contains a number — Kaiba's ace.

Remember to add new line at last.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Note: This is just the translation of "10664 - easy 8 Puzzles" in English. Please submit your code to "10664 - easy 8 Puzzles".

Given a 3×3 board with 9 tiles and every tile has one number from 0 to 8. 

We can swap ‘0’ with its four adjacent (left, right, above, and below) tiles. For example:

step 1 : swap 0 with ‘5’

step 2 : swap 0 with ‘6’

The objective is to place the numbers on tiles to match the following configuration.

(Noting important in this paragraph, something like Rody is too busy and needs your help to solve this problem.) 

Input

Given T (1<=T<=30) in the first line, saying that there will be T test cases.

From 2nd line to (T+1)-th line, each line contains 9 distinct integers from 0 to 8, representing an 8-puzzle game. Nice integers will be filled to the 3×3 board in a row-major manner. For example, 1 2 3 4 0 5 7 8 6 will become the configuration as shown in the following figure.

Output

For each 8-puzzle game, if it can be solved in 14 steps, print out "You can solve it within x steps.", x is the minimum number of steps to solve this puzzle. Otherwise, print out "You'd better skip this game.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N animals standing in line.

The strength of the i-th animal is s_i and the height of the i-th animal is h_i.

The i-th animal is said to be better than the j-th animal if （s_i > s_j） or （s_i = s_j and h_i > h_j）.

For each i = 1, 2, ..., N, find the largest j such that j < i and the j-th animal is better than the i-th animal.

Input

The first line of the input contains an integer T, the number of testcases.

The first line of each testcase contains an integer N, the number of animals.

The second line of each testcase contains N integers, s₁, s₂, ..., s_N, the strength of animals.

The third line of each testcase contains N integers, h₁, h₂, ..., h_N, the height of animals.

For test 1 to 3, N <= 10³.

For test 4 to 6, N <= 10⁵.

T <= 10, s_i,  h_i <= 10⁹.

Output

For each testcase, please print N integers j₁, j₂, ..., j_N seperated by space.

j_i represent the largest number such that j_i < i and the j_i-th animal is better than the i-th animal.

If such j_i doesn't exist, print 0 instead.

Remember to print a new line at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a sequence A = a₁, a₂, ..., a_N.

However, for any a_i ≠ a_j, a_i hates a_j and a_j hates a_i. Two distinct elements don't want to be together.

You are given Q queries.

In each query, you are given L_i, R_i, and X_i. You have to find the number of elements needed to be removed to make A[L_i...R_i] contain X_i only.

It is guaranteed for each i = 1, 2, ..., Q - 1, L_i ≤ L_i+1 and R_i ≤ R_i+1.

For example, if A = [1, 3, 2, 3, 3] and L = 1, R = 5, and X = 3.

Then you have to remove A[1] and A[3] to make A contain 3 only.

Hence, the number of elements needed to be removed is 2 in this example.

It is recommended to include<stdio.h> and use scanf/printf instead of cin/cout to speed up input and output.

You may need to select c++11, c++14, c++17 as the compiler to avoid compile error.

Input

The first line of the input contains an integer T, the number of testcases.

The first line of each testcase contains two integers N Q, the length of A and the number of queries.

The second line of each testcase contains N integers, a₁, a₂, ..., a_N.

The next Q lines contains three integers L_i, R_i, and X_i as described in the statement.

For each test,

1. N ≤ 100, Q ≤ 100
2. N ≤ 100, Q ≤ 100
3. N ≤ 1000, Q ≤ 1000
4. N ≤ 1000, Q ≤ 1000
5. N ≤ 200000, Q ≤ 100000
6. N ≤ 200000, Q ≤ 100000

T ≤ 10, 1 ≤ a_i ≤ 10⁹, 1 ≤ L_i ≤ R_i ≤ N, 1 ≤ X_i ≤ 10⁹.

Output

For each query in each testcase, please print the number of elements needed to be removed to make A[L_i...R_i] contain X_i only.

You have to print an extra new line at the end of each testcase, including the last one.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We have a long piece of wood whose length is \(L\).

There are \(Q\) queries each consisting of a character and an integer \((c_i, x_i)\):

• \(c_i=\)'a', cut the wood at postion \(x_i\) from left end.
• \(c_i=\)'b', print out the length of piece to which postion \(x_i\) belong.

It's guranteed that it wouldn't be cut at postion \(x_i\) when you're asked to print out the length.

Input

There are two integers \(L, Q\) in the first line respectively.

The following \(Q\) lines contain a character and an integer \(c_i, x_i\).

Output

For queries where \(c_i=\)'b', print out the length of piece to which postion \(x_i\) belong. Remember to put a new line character at the end of each such query.

Sample Input  Download

Sample Output  Download

Tags

Discuss