Description

Declaration
# Name Difficulty Score
1 Broken Chronograph Easy 20
2 Late Autumn Night’s Dream Easy+ 20
3 Starry Road to Tomorrow Medium 20
4 From Dawn Till Dusk Medium 20
5 Moonlit Sorcery Hard 20
There is no need to validate the inputs because they are all guaranteed to be valid and follow the constraints.
Some of the input-output cases have explanations, which are to help you understand the problem.
In case the assignment is too difficult, we make a solution video for you:
BV1GJ411x7h7.
1. Broken Chronograph
Description
Alice Megatron is tired of solving integrals, and she wants a computer program to do it for her. However, she is busy designing problems for OJ, so she asks you to write part of the program for her, just needs you to implement the function of polynomial integration.
Input
The first line contains one integer n, indicating that there are n terms in the polynomial.
The second line contains n floating numbers, the i-th number ai is the coefficient of the term xi.
The third line contains 2 floating numbers, which are the integral bounds l and r.
More specifically, you are asked to calculate this integral:
r
∫ (a0 + a1x + a2x2 + ⋯ + an−1xn−1)dx
l
Output
Output the result of the integral.
Your answer is considered correct if its absolute error doesn’t exceed 10−4.
Constraint
For all the test cases, 1 ≤ n ≤ 20, −100 ≤ ai, l, r ≤ 100.
It is guaranteed that the absolute value of the integral result will not exceed 106.
Samples
Input 1

Output 1

2. Late Autumn Night’s Dream
Description
Here is the description of eight queens puzzle from Wikipedia: The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal.
Input
The first line contains one integer T, indicating that there are T test cases.
There are T lines following, each line as the input for one test case. Each line contains 8 strings, each string contains a letter a, b, c, d, e, f, g, h concatenated with a letter 1, 2, 3, 4, 5, 6, 7, 8, and locates a grid on chessboard.
a b c d e f g h

Output
Output T lines, each line represents the output for one test case, respectively.
For each test case, if it is a solution, output Yes , if not, output No .
Constraint
For all test cases, 1 ≤ T ≤ 100.
Samples
Input 1

Output 1

Explanation to sample 1

Input 2

Output 2

3. Starry Road to Tomorrow
Description
Carol invited N pigeon friends to his home for dinner and prepared N seats. The pigeon friends all agreed and reneged, so the angry Carol has to drive the pigeons to the seats herself. To simplify the problem, assume that N pigeons’ homes (starting positions) and N seats are on a straight line and that their coordinates are represented by an integer with the pigeons’ home coordinates s1,s2,…,sn, and the coordinates of the seats are d1,d2,…,dn. The pigeons rush at the same speed, 1 per second. In order to start as soon as possible, Carol wants to give each pigeon a destination so that they can sit in their seats in the shortest possible time, so she finds a clever friend to help her figure out this shortest possible time.
Constraint
For 50% test cases, 1 ≤ N ≤ 8, 0 ≤ si,di ≤ 103.
For all test cases, 1 ≤ N ≤ 104, 0 ≤ si,di ≤ 107.
Input
The first line contains one integer N.
The second line contains N integers s1,s2,…,sn.
The third line contains N integers d1,d2,…,dn.
Output
Output one single integer as the answer.
Samples
Input 1

Output 1

Explanation to sample 1
It takes the only pigeon 4 seconds to move from 1 to 5 .
Input 2

Output 2

Explanation to sample 2
You can arrange the pigeons so that it takes 81 seconds for all pigeons to sit.
Input 3

Output 3

4. From Dawn Till Dusk
Description
Dave is invited to Steve’s world. Let’s simply consider this world to be a two-dimensional plane with a Cartesian coordinate system. Steve allows Dave to place blocks at coordinates (xi, yi), where xi and yi are both integers, and coordinates (xi, yi) is
adjacent to the coordinates (xi − 1, yi), (xi + 1, yi), (xi, yi − 1), (xi, yi + 1).
Given an integer n, Dave wants to create an “Artwork”. In detail, he wants to place some blocks to form a shape that satisfies the following conditions:
1. The shape is connected, i.e. any two blocks are either adjacent or connected by other blocks.
2. Each block is adjacent to an even number of blocks.
3. There are exactly n blocks that all their adjacent coordinates have blocks.
It is strongly advised not to exchange ideas before passing the problem. The process of thinking is interesting!
Constraint
For 30% test cases, n is even.
For 60% test cases, n can be factorized into at least two integers.
For all test cases, 1 ≤ n ≤ 500.
Input
The only line contains an integer n.
Output
In the first line, print an integer k – the number of blocks you place, and please make sure 0 ≤ k ≤ 105.
In the following k lines, each line contains two integers xi, yi – the coordinates of the ith blocks you place, and please also make sure the absolute value of coordinates doesn’t exceed 109.
Sample
Input 1

Output 1

Explanation to sample 1
Note: your program’s output does not have to be identical to the sample.

5. Moonlit Sorcery
Description
Constraint
For 70% test cases, 0 ≤ r ≤ 103.
For 90% test cases, 0 ≤ r ≤ 106.
For all test cases, 0 ≤ r ≤ 109.
Hint
To get full score on this problem, you should optimize the program so that it iterates less than r times.
Input
The first line contains one integer r.
Output
Output one single integer as the answer.
Samples
Input 1

Output 1

Explanation to sample 1
There are 4 points meeting the requirement, (0,4),(4,0),(0,−4),(−4,0).
Input 2

Output 2

Explanation to sample 2
There are 12 points meeting the requirement, (0,5),(3,4),(4,3),….