Description

一個八數字推盤遊戲由3*3的棋盤組成，每一個格子上都有一個數字(0~8且不重複)，一開始盤面是亂的，

每次操作可以將0與其上.下.左.右的數字互換，經過若干次操作：

step 1 : 0往右與5互換

step 2 : 0往下與6互換

最後將盤面排回

即為正解。
Rody最近沉迷於八數字推盤遊戲當中，但最近要開始期末大爆炸了，Rody不再那麼空閒，因此他決定要先跳過太過困難的題目，等到暑假再來解。

困擾的Rody想要請你幫他鑑定題目的困難度。

Input

input第一行有一整數T(1<=T<=30)，代表底下有T筆測資。
第2~T+1行分別有9個不同的整數(0<=t1,t2,...,t9<=8)，代表一個八數字推盤遊戲。

(註:9個整數以row major方式填入3*3的盤面，如第二組測資 1 2 3 4 0 5 7 8 6 等同於下方示意圖)

Output

對於每組八數字推盤遊戲，若能在14步內完成遊戲，請輸出"You can solve it within x steps."，x為解決該遊戲所需的最少移動次數。

否則，請輸出"You'd better skip this game."

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Cat or Dog? that's a good question. " Shakespeare never said, 2019.

In this questions there are three types of animals class have to be implemented. (Cat , Dog and Caog)
Coag is a kind of special animal mixed in Cat and Dog.

Dog can only throwball
Cat can only play with carton.
Caog do those things both.

when Dog / Caog playing throwball output "it looks happy!\n"

when Cat  / Caog playing with carton output "it looks so happy!\n"

and also there's a zoo can count how many animals are in the zoo.

In this questions you have to implement 3 class (cat , dog and caog) based on the sample code.

Input

All input data would be finish in given main functions.

First number N would be N animals ( N < 10)

the following Ai numbers would types of animals.

And the T would be T instructions ( T < 30) 

the following Ti would be index and instructions

Output

When Animals born Zoo will auto output which kind of animal is born and how many animals in the zoo.

When Animals dead Zoo will auto output which kind of animal isdeadand how many animals in the zoo.

when Dog / Caog playing throwball output "it looks happy!\n"

when Cat  / Caog playing with carton output "it looks so happy!\n"

when Barking:

Cat would "meow!\n"

Dog would "woof!\n"

Caog would "woof!woof!meow!\n"

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

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

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

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

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called very beautiful if every element in A[L...R] is unique.

There will be Q queries.

In the i-th query, you'll be given L_i and R_i and you have to find the minimum number of elements needed to be removed to make the subsequence A[L_i...R_i] very beautiful.

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, 3, 4, 1] and L = 1, R = 5.

You can remove A[1] and A[3] to make A very beautiful.

On the other hand, removing one element is not enough to make A very beautiful.

Hence, the minimum 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.

Each of the next Q lines contains two integers L_i R_i, the subsequence you are queied.

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.

Output

For each query in each testcase, please print the minimum number of element needed to be removed to make the subsequence very beautiful.

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

In NTHU CS, everyone has their own programming value, whenever a student encounters problem they can't solve, he/she intends to approach his/her "electric god" for assistance, whose programming value is strictly larger than him/her, instead of doing research online. 

One day, all students in NTHU CS sit in one line, and they can only ask those who sit in their left side. Since no CS student have the ability to walk for a long distance, they will ask the electric god who sits in their nearest left. If everyone in your left side's programming value is less than yours, don't worry, Stiff Waist Beast always be with you. Stiff Waist Beast's programming value is so large that you can never imagine, and he will always sit in the 0 position to help you out!

For each person, please tell them the position of the closest electric god who sits in their left.

Input

The first line contains an integer N, and the second line contains N integer x₁ to x_N.

0 <= x_i <= 1e9.

For testcase 1~3: 1 <= N <= 1e3.

For testcase 4~6:1 <= N <= 2e5.

Output

For each person, please tell them the position of the closest electric god who sits in their left.

Please output a space after each number and output '\n' in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N bars line up in a row. The height of the i-th bar is h_i, and the width of each bar is 1. Please find the largest rectangle in it. 

Sample test:

Input

The first line has an integer T, means there are T testcases.

The first line of each testcase contains an integer N, and the second line contains N integers h₁ ~ h_N.

1 <= h_i <= 1e9.

1 <= T <= 10.

In testcase 1 ~ 4: 1 <= N <= 1000.

In testcase 5 ~ 8: 1 <= N <= 2e5.

Output

Please print the area of the largest rectangle for each testcase.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dogeon is trying to build a marble machine that can play music. The machine is composed of a series of tracks, each of which has a different length. The machine is designed to play music by releasing marbles from the top of the machine. The marbles will then roll down the tracks and hit various instruments, creating a melody.

Currently, he is designing a new track for the machine. He wants to know how it performs in different scenarios.

The track is composed of four conveyor belts with same length and same speed. Four of them are facing a gate in the middle of the track. In each second:

• Marbles can move one unit towards the gate
• Marble on the gate will be released and leave the track
• Two marbles can't be on the same unit

With given configuration of the track, Dogeon wants to know how many marbles will be released in the first \(T\) seconds.

Wintergatan - Marble Machine (music instrument using 2000 marbles)

Input

The first line of input contains three integers \(N\), \(T\), and \(L\), the number of marbles, the number of seconds, and the length of the track, respectively.

For the next \(N\) lines, \(i\)-th line contains two integers \(x_i\) and \(y_i\). Denote that marble \(i\) is \(x_i\) units away from the gate on the \(y_i\)-th conveyor belt.

\(N \quad T \quad L\)
\(x_1 \quad y_1\)
\(x_2 \quad y_2\)
\(\vdots\)
\(x_N \quad y_N\)

Constraints

• \(1 \leq N \leq 10^5\)
• \(1 \leq T \leq 10^9\)
• \(1 \leq L \leq 10^7\)
• \(1 \leq x_i \leq L\)
• \(1 \leq y_i \leq 4\)

Output

Output one line containing the number of marbles that will be released in the first \(T\) seconds.

Sample Input  Download

Sample Output  Download

Tags

Discuss