Description

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.

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

Discuss

Description

Notice: You need to enable the flag -std=c++11 to compile the code!

• In codeblocks, go to Settings->Compiler->check the option "Have g++ follow the C++11 ISO C++ language standard [-std=c++11]"->OK
• In dev-c++, go to Tools->Compiler options->check "Add the following commands ..."->type in "-std=c++11"(without qoute) ->OK

Once upon a time a farmer went to a market and purchased X wolfs, Y goats, and Z cabbages.

On his way home, the farmer came to the left river bank and rented a boat. To cross the river by a boat, the farmer could carry only himself and at most one of his purchases: a wolf, a goat, or a cabbage.

At both left and right banks, if the farmer is not there and the wolves are more than the goats (#W>#G), the wolves will eat the goats. Also, if the farmer is not there and the goats are more than the cabbages (#G>#C), the goats will eat the cabbages.

In this problem, you have to find all solutions that the farmer can carry himself and all his purchases from the left to the right bank.

For each solution, you cannot produce duplicate states.

For example: 

This solution isn't allowed because there are duplicate states.

Hint: You can use set<State> _explored to store each state.

Input

The input has only single line containing three integer X Y Z, representing the number of purchased wolves, goats and cabbages.

Output

List all solutions one by one.
"Done" denotes the end of a solution.
A solution contains several moves. Each move is represented by a line with the format of:

(#W at the left, #G at the left, #C at the left)(#W at the right, #G at the right, #C at the right) [left/right]

W: wolf, G: goat, C: cabbage, left/right: position of the boat.

For example: 

We've created the function to print outputs from the variable set, so you just need to add your solutions to the variable set<list<State>> _solutions. You don't have to worry about the order of your solutions.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

You might remember that we had a problem to merge two sorted linked lists at the beginning of the semester. Now we've learnt C++ ans thus the problem evolved a bit: templates, operator overloading are introduced, and we also micmic the behaviour of containers and iterators.

We declare the linked_list class with template, which has 2 member types (nested structs / classes), node & iterator.  The former is for our private internal design purposes only, whereas the latter is public to others.

Most of the member functions have been done. You only need implement 3 ones: dereference iterators, forward iterators and merge two sorted linked lists. Make sure to read the instructions in the header carefully.

Input

No parameter. The function would be called when *itr.

No parameter, too. The function would be called when ++itr.

The 2 parameters are the head of 2 sorted linked list.

It's guarantees that the sum of the total length of the linked list is less than 200000.

Output

For the dereference operator of iterator, you should return the reference to which the iterator / node point to.

As for the pre-increment operator of iterator, you should forward that iterator and return the iterator itself.

Lastly, for the merge method of linked list, you should return the head of the merged list. Linear time complexity is expected .

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

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

Discuss

Description

There are \(N\) stones, numbered \(1,2,...,N\).

There is a frog who is initially on Stone \(x\). He will repeat the following action some number of times to reach Stone \(N\):

• If the frog is currently on Stone \(i\), jump to Stone \(i + d\) or Stone \(i - d\) where \(d\) is a divisor of \(i\).

Here, an integer \(b\) is said to be a divisor of \(a\) if there exist an integer \(c\) such that \(a = b \times c\).

For each starting stone \(1 \leq x \leq N\), find the minimum number of jumps to reach Stone \(N\).

Input

The only line contains an integer \(N\).

\(N\)

Constraints

• \(1 \le N\le 10^6\)

Output

Please output \(N\) integers in a line, each followed by a space.

Sample Input  Download

Sample Output  Download

Discuss

Description

In computational geometry, managing the relationship between spatial objects is a fundamental task. In this problem, you are required to implement a Rectangle Algebra System using C++ Classes and Operator Overloading.

Your goal is to treat geometric rectangles as algebraic elements, where the Intersection and Bounding Box operations are represented by standard operators.

1. Geometric Definition

Each rectangle in this system is a Axis-Aligned Bounding Box and is defined by two points (x1 , y1) and (x2 , y2) on its diagonal. You need to implement the constructor to store these information in a useful way.

2. Algebraic Operators

You must overload the following operators to support complex geometric expressions:

• Intersection (A & B):

  Returns a new Rectangle representing the overlapping area.

  • If A and B do not overlap, or one's area is 0, then it should return a zero-area rectangle.

• Modified Union, or Bounding Box (A | B):

  Returns a new Rectangle that is the smallest axis-aligned rectangle containing both A and B.

  • Identity Logic: If A is a zero-area rectangle, A | B should return B.

• Assignment (A = B):

  Ensures that rectangles can be assigned to one another safely.

3. Area Calculation

The system must be able to calculate the area of the resulting rectangle.

Constraints

• 1 <= N <= 100.
• -10⁶ <= x, y <= 10⁶

Input

The first line contains an integer N, the number of rectangles.

The next N lines each contain Name x1 y1 x2 y2.

• Name: A unique string ID.

• x1 y1 x2 y2: Coordinates of two opposite corner.

The final line is a space-separated algebraic string. Operators include & (Intersection), | (Bounding Box). You must evaluated it from left to right.

Output

A single line containing the area of the final resulting rectangle, with '\n'.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

Given an array of integers nums and an integer target, find the indices of the two numbers such that they add up to the target.

Input

The first line contains an integer t, representing the number of test cases. For each test case:

• The first line contains an integer, representing the target.

• The second line contains an integer n, indicating the size of the array.

• The third line contains n space-separated integers, representing the elements of the array.

Constraints:

• 1 <= t <= 1000

• 0 <= target <= 2147483647

• 2 <= n <= 2500

• 0 <= nums[i] <= 1000000000

Output

For each test case:

• Output two space-separated integers representing the distinct indices (0-indexed) of the two numbers that add up to the target. The smaller index must be printed first.

• If no such pair exists, output "None".

• It is guaranteed that there is at most one solution per test case.

Note: Remember to print '\n' at the end of the output.

Hint: Use std::map from the STL to achieve an O(nlogn) time complexity.

Sample Input  Download

Sample Output  Download

Discuss