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.

For example, if A = 3, 1, 2, 3, 4.

Then

• A[1, 3] = 3, 1, 2 is very beautiful.
• A[1, 4] = 3, 1, 2, 3 is not very beautiful because A[1] = A[4].
• A[2, 5] = 1, 2, 3, 4 is very beautiful.

Please find the maximum length of very beautiful continuous subsequence of A.

Input

The first line of the input contains a number T — the number of test cases.

The first line of each test case contains a positive integer N — the length of A.

The second line of each test case contains N numbers — a₁, a₂, ..., a_N.

For each test,

1. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹ 
2. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹ 
3. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹ 
4. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹ 
5. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹ 
6. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹ 

Output

For each test case, print the maximum length of very beautiful continuous subsequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a sequence A = a₁, a₂, ..., a_N and a number K.

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called beautiful if the sum of A[L ... R] is K.

For example, if A = 3, 1, 2, 2, 4 and K = 6.

Then

• A[1, 3] = 3, 1, 2 is beautiful.
• A[1, 4] = 3, 1, 2, 2 is not beautiful because 3 + 1 + 2 + 2 is not 6.
• A[4, 5] = 2, 4 is beautiful.

Please find the number of beautiful continuous subsequence of A.

Input

The first line of the input contains a number T — the number of test cases.

The first line of each test case contains two numbers N K — the length of A and the number K described in the statement.

The second line of each test case contains N numbers — a₁, a₂, ..., a_N.

For each test,

1. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
2. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
3. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
4. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
5. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
6. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.

Output

For each test case, print the number of beautiful continuous subsequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

TL; DR

In computer science, Abstract Data Type (ADT) is some sort of data structures whose behavior is declared without definite implementation. For instance, stack is the data structure with the Last-In-First-Out principle while queue holds the First-In-First-Out one. Both of them can be implemented by either array or linked list.

In C++ Standard Template Library, these ADTs are called container adapters, implemented by template undoubtly. For instance, queue<int> is queue<int, deque<int>> and you can use a vector to be the base of a stack like: stack<int, vector<int>>. In fact, any container support .push_back(), .pop_back() methods can be deemed as a stack, so stack<char, string> is also valid.

Yet template is not generic enough sometimes. In more object-oriented languages like Java, a queue can be declared like Queue<T> q = new LinkedList<>(); or Queue<T> q = new ArrayDeque<>();. As you can see, polymorphism illusrates the relation between an ADT and its implemented data structure in a better way.

Just as Coriolis Force is not a real force, priority queue is not a queue actually but an ADT which supposed to push an element, get and pop the minimum (or maximum) element. Though a binary search tree (BST) can do these all operations in \(O(\log N)\), a heap can do the first two ones in \(O(1)\) average. Hence in pratical, priority queues are implemented by heaps mostly.

Since there are problems about polymorphic stack, queue and priority queue on the OJ and it's midterm, let's have a different ADT: double-ended priority queue (DEPQ). What a double-ended queue (deque) is to a queue is what a DEPQ to a priority queue. So a DEPQ is an ADT that supposed to push an element, get and pop the minimum and maximum elements. A BST can do everything a DEPQ should do, whereas there are other data structtures like min-max heap, double-ended heap (DEAP), symmetric min-max heap and so forth.

But don't worry! Your task is so really simple: implement the polymorphic part of two kinds of the DEPQ. For the BST kind, you can use std::multiset directly, while for the min-max heap, it's done for you in "function.h" so that you can use it!

Input

Since this problem is judged partially, you needn't be concerned about the format of input.

In case your're interested, there are at most \(100\) test cases, each of which started by an integer \(q<10^5\) indicating the number of queries. Then the following \(q\) lines are queries to push an element, print the minimum, print the maimum, pop the minimum, pop the maximum, print the size of the DEPQ.

Output

Since this problem is judged partially, you needn't be concerned about the format of output.

In case your're interested, for each test case, the judge code would print out the maximum, the minimum or the size of the DEPQ if asked by the queries.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

The CS student association held a Christmas party for students with other departments. In the party, each boy invited a girl to be his dance partner. When entering the ballroom, each of them picked up a roll of colored ribbon. The boys then lined up in one single row in the order of their arrival. 

Girls then entered the ballroom and picked up the other end of the color ribbon from the boys and stretched the ribbon as they lined up in a parallel row of boys. When everyone was set, there are one row of N boys and the other row of N girls, with N ribbons that paired them.

The party host wanted to select some pairs for the first dance. The host decided to cut off the least number of ribbons to make the remaining ribbons not crisscrossed. Then those pairs were selected. In the below example, 4 pairs were selected for the first dance by way of cutting off 2 ribbons. Note that 4 pairs is also the maximum that can be achieved in the example. Given different arrival configurations, your task is to the maximum pairs could be selected for the first dance.

Hint

Look at the figure above. The above row are boys where \(i=1,2,3,4,5,6\), while the below row are girls, where \(a_i=1,6,2,3,5,4\). 

First it's obvious for us to observe that if we select girl \(a_i\) (e.g. \(a_2=6\)), then we couldn't select greater \(a_i\) afterwards since it would result in crisscross. That is, we must always select some increasing ones.

Furthermore, to find the answer of this problem, we could rather find all the answers that the last girl we select is \(a_i\). In this way, we have that it is the maximum of the answers of girls before and less than her.

Eventually, for any boy \(i\), if \(\exists j, a_j<a_i\) and the answer of \(a_j\) is less than \(a_i\), then we would never select \(a_i\). Again, the ones we select always increasing.

Input

For each test case, the first line contains one integer, \(N\), where \(N<10^6\), indicating the number of boys. The second line contains \(N\) distinct integers. The first integer \(i\) menas that the first boy invited the \(i^{th}\) girl to dance and so on.

In \(40\%\) of test cases, \(N<5000\). In \(20\%\) of test cases, \(N<200\).

Output

Print out the number of pairs selected for the first dance. Remember to print a newline character at the end.

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

"One, two 福利，one, two 福利，happy~every day~" Haven't you ever heard of "Free Bear"? If not, don't worry. Free Bear, 福利熊，is the mascot of PX Mart 全聯福利中心。Once upon its first appearence in 2017, it went viral on Internet.

However, this problem is not mainly based on Free Bear. Three years later, Free Bear had got some friends 水果探險隊 (sorry for that I failed to find their official English name; let's call them Fruit Explorer Dogs, though) consisting of 蘋狗 (Bingo, namely Apple Dog), 香蕉狗 (Jungle, namely Banana Dog) and 奇異狗 (Kiwiko, namely Kiwi Dog) initially in 2020.

(I didn't expect that they even have a family tree diagram; maybe somebody could derive another problem...)
Last year (2022), Fruit Explorer Dogs welcomed the two brand new members: 芭樂狗 (Balego, namely Guava Dog) and 旺來狗 (Wanlaigo, namely Pineapple Dog).

It's known that PX Mart seems to never have enough number of clerks for its customers to checkout and one could often hears "We need backup（請支援收銀）". As a consequence, the first and the foremost tasks for Fruit Explorer Dogs is to back up the cashiers.

Since PX Mart has plenty of stores all over Taiwan, it requires quite a few number of fruit dogs. So suppose that PX Mart recruits far more fruit dogs. Note that some fruit dogs might belong to the same fruit, and PX Mart marks each type of fruit an unique ID.

Furthermore, it is difficult for a single fruit dog to handle the cashier. Therefore, they tend to team up. More formally, any fruit dogs with consecutive fruit ID could team up. For instance, if apple, banana, kiwi, guava and pineapple have ID 0, 1, 2, 8 and 9, respectively, then Bingo, Jungle and Kiwiko could form a team, whilst Balego and Wanlaigo could make another team.

You're the staff director of PX Mart and you'd like to determine the lower bound (minimum number) of teams Fruit Explorer Dogs could build. Write a program to resolve the bound!!

Input

There would be an integer \(n\) in the first line, indicating the number of members of Fruit Explorer Dogs that PX Mart currently recruits.

The next line would follow by an array \(a\) of \(n\) integers, where \(a_i\) denotes the fruit ID of \(i^\text{th}\) fruit dog.

It's guaranteed that \(n<2\times10^5\land a_i<10^9\) and for half of the test cases there's no any two fruit dogs belong to the same kind of fruit (thus no team would be overlapped to any other).

Output

Please print out an integer representing the lower bound (minimum number) of teams Fruit Explorer Dogs could build.

Sample Input  Download

Sample Output  Download

Tags

Discuss