Case Study

ID 32973. SNTP

ID 32947. Watch

ID 38142. Comfortable cows

Farmer Eureka's pasture can be viewed as a huge 2D grid of cells (a chessboard). Initially, the pasture is empty.

Farmer Yurik adds N (\(1<=N<=10^5\)) cows to pasture one by one. ith cow will occupy the cell (xi,yi ) which is different from the cells occupied by all other cows (\(0<=x_i,y_i<=1000\)).

A cow is called "comfortable" if it has exactly three horizontal and vertical neighbors. Comfortable cows produce less milk, so Farmer Yurik wants to add cows until there are comfortable cows (including the one he will add). Note that the cows you add do not have to have  x and y coordinates in the range \(0… 1000\).

For each i in the range \(1…N\), print the minimum number of cows it needs to add so that there are no comfortable cows left, assuming that only cows are in the pasture \(1…i\).

Examples

ID 38273. New Capital

In the country from the previous task, there are many specialists not only in the protection of children, but also in the design of cities. Therefore, in order to solve the problem of traffic jams in the overcrowded capital once and for all, it was decided to build a new capital and move the entire government there. It is said — done.

The streets in the new capital form a regular rectangular grid in which all streets intersect at exactly one local length unit. Vertically running streets are called streets, and horizontally running — alleys. In total, the city got 2000 streets and 2000 alleys, therefore, in order not to come up with many new names, they were all simply numbered. The streets were numbered from west to east with numbers from −1000 to 999, and alleys — from south to north, also numbers from −1000 to 999. The city center is considered to be blocks at the intersection of streets and alleys with numbers from −100 to 100.

In order to increase the capacity of roads in the city, it was decided to make all streets and alleys one-way. On streets with even numbers it is allowed to drive only from north to south, and on streets with odd numbers — only from south to north. Similarly, even-numbered alleys can only be driven from east to west, and odd-numbered — only from west to east.

How many local units of length will the mayor of the new capital have to pass every evening, returning home from the mayor's office of the city? Both the city hall and the mayor's house are located in the city center. The mayor is driving home by the shortest route, observing, however, the rules of the road.

Input
The first line contains two numbers x1 and y1 — street number and alley number at the intersection of which the city hall is located. The second line contains two numbers x2 and y2 — street number and alley number at the intersection of which the mayor's house is located. All numbers are integers and do not exceed 100 in absolute value.

Imprint
Print one number: the length of the shortest path from the mayor's office to the mayor's house by car.-
 

Examples

ID 38292. Candy selection

Harry Potter's birthday is coming soon! Hermione wants to prepare an unusual gift for him. She wants to give Harry a set of n magic candies. Each candy is characterized by its taste — an integer t_i . The pleasure that Harry will get from a set of sweets — is the sum of the flavors of all the candies in that set. Note that the flavors of the candies, like Harry's pleasure, do not have to be positive.

Hermione has a huge box of sweets that contains exactly one candy flavor t for every integer t from - 10⁹ to 10⁹. Hermione wants to take n chocolates from this box to make Harry's set.

Hermione wants Harry to enjoy the set of sweets given to him, exactly equal to the integer s . Help her choose the right set, or determine that it's not possible.

Input
The first line of the input contains a single integer n ( 1 ≤ n ≤ 100 ) — how many sweets Hermione wants to put in the set. The second line of the input contains a single integer s ( - 10⁹ ≤ s ≤ 10⁹ ) — the pleasure Harry must get from the set.

Imprint
If it is impossible to make the desired set of candies from Hermione's, print « NO ". Otherwise, in the first line print « YES », and in the second line randomly n numbers — candy flavors in the desired set. If there are several correct answers, print any of them.

Examples

ID 38299. Checking the machine

Andryusha — young engineer. Now he is designing a modern machine for converting numbers. In the process of construction, more and more blocks are added to the automaton, and Andryusha is interested in how the automaton will work after each such modification.

The automaton is a sequence of blocks of two types: maximizers and minimizers. Each block has some natural number x written on it. The maximizer takes a natural number a as input and outputs the number max ( x , a ) . The minimizer takes a natural number a as input and outputs the number min ( x , a ) .

The automaton works as follows: it takes some natural number, which it feeds to the input of the first block, then what came out of the output of the first block is fed to the input of the second block, and so on. As a result, the machine returns the number obtained at the output of the last block. In other words, the automaton simply passes the number given to it sequentially through all the blocks.

Initially, there is not a single block in the machine, and it simply returns the number it accepts.

Andryusha consistently performs actions with the machine gun. Actions are of three types:

1. Add a maximizer with the number x written on it to the end of the sequence of automaton blocks.
2. Add a minimizer with the number x written on it to the end of the automaton block sequence.
3. Feed the number x to the automaton. In this case, Andryusha wants to know what the machine will return to the exit.

Examples

ID 38491. Cards for three

Antoninus, Balbinus and Caesar play the game "Cards for three", the algorithm of which is as follows:
- first, each of the three players has a deck consisting of a certain number of cards. Each card has the letter a, b or c written on it. The order of cards in decks cannot be changed;
- The players take turns. Antonin goes first;
- if there is at least one card in the current player's deck, he must discard the top card in the deck;
- The next turn goes to the player whose name begins with the letter on the discarded card (a - Antoninus, b - Balbinus, c - Caesar );
- if the current player's deck is empty, the game ends and the current player wins the game.
You are given the starting player decks (Sa, Sb, Sc). The state of Antonin's deck is written in the line Sa, where i-th (\(1<=i<=len(S_a)\ )) character is the letter in the i-th card in the deck. The Balbin string (Sb) and the Caesar string (Sс) are described in the same way. 
Determine the winner of the game.

Input
The input is three non-zero strings Sa, Sb  and Sc, each on a new line. The length of each line is no more than 100 characters. Each line consists only of the letters a, b, or c.

Imprint
If Antonin won. then print the letter A, if Balbin - the letter B, if Caesar - the letter C.
 

Examples

aca
accc
ca

A

abcb
aacb
bcc

C

ID 38489. Raft

A rectangular raft floats in the middle of the lake. The sides of the raft are directed along parallels and meridians. Let's introduce a coordinate system in which the OX  axis is directed to the east, and the OY axis – on North. Let the southwest corner of the raft have the coordinates  (x₁, y₁), the northeast corner – coordinates (x₂, y₂).
The swimmer is at the point with coordinates (x, y). Determine which side of the raft (north, south, west, or east) or which corner of the raft (northwest, northeast, southwest, southeast) the swimmer needs to swim to get to as soon as possible to the raft.
The program receives six numbers as input in the following order: x₁, y₁ (coordinates of the southwest corner of the raft), x₂, y ₂ (coordinates of the northeast corner of the raft), x, y (coordinates swimmer). All numbers are integers and do not exceed 100 in absolute value. It is guaranteed that x₁ < x₂, y₁ < y₂, x ≠ x₁, x ≠ x₂, y ≠ y₁, y ≠ y₂, the swimmer coordinates are outside the raft.
If the swimmer should swim to the north side of the raft, the program should output the character  "N", to the south– the symbol "S", to the western – symbol "W", to the eastern – the symbol "E". If the swimmer should swim to the corner of the raft, print one of the following lines: "NW", "NE", "SW", "SE".
 

Examples

#	Input	Output	Explanation
1	-1 -2 5 3 -4 6	NW

ID 38493. Divisibility

Today at school in a math lesson they are divisible. To demonstrate the properties of divisibility, the teacher wrote down on the board all the integers from 1 to
N into several groups, and if one number is divisible by another, then they necessarily ended up in different groups. For example, if you take N = 10, you get 4 groups.

• First group: 1.
• Second group: 2, 7, 9.
• Third group: 3, 4, 10.
• Fourth group: 5, 6, 8.

Examples

ID 38513. Equations of Mathematical Magic

Colossal! — exclaimed the hunchback. — Programmer! We need a programmer.
Arkady and Boris Strugatsky, Monday starts on Saturday
Studying the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta discovered an interesting equation: a−(a⊕x)−x=0 for a given a, where   ⊕   stands for bitwise exclusive OR (XOR) of two numbers (this operation is denoted as ^ or xor in many modern programming languages). Since this equation was intended to be solved on the Aldan-3 machine, all calculations were performed on non-negative integers modulo 2³². Oira-Oira quickly found x, which is a solution, but Cristobal Junta found Oira-Oira's result not interesting enough, so he asked a colleague how many solutions there are to this equation. Since all calculations are done modulo 2³², Cristobal Junto is interested in the number of solutions x such that 0 ≤ x≤ 2³². Such a task turned out to be too difficult for Oira-Oira, so he turned to you for help.

Input
The first line contains a single integer a (0 ≤ a ≤ 2³²−1).

Imprint
Print a single integer — the number of non-negative solutions of the equation.

Note
Let's define the bitwise OR (XOR) operation. Let two non-negative integers x and y be given, consider their binary representations (possibly with leading zeros): x_k...x₂x₁x₀ and y_k...y₂y₁y₀ . Here x_i is the i-th bit of x and y_i is the i-th bit of y. Let r=x⊕y — the result of an XOR operation on the numbers x and y. Then the binary representation of r is r_k...r₂r₁r₀, where:

Examples

ID 38749. Vote

The shorties decided to take Dunno or Donut on a flight to the moon. Unable to reach an agreement, they decided to vote. Dunno and Donut watch the voting summary. The Shorties show Dunno and Donut the ratio of the current number of votes received by Dunno and Donut, but not the actual number of votes. Dunno and Donut looked at the report N times, and when they looked at it the i (1<=i<=N) times, the ratio was Pi:Ni. Dunno and Donut are known to have had at least one vote when they first saw the report. Find the minimum possible total number of votes Dunno and Donut received when they checked the report for the Nth time. It can be assumed that the number of votes received by Dunno and Donut never decreases.

Input
The first line specifies an integer N (1<=N<=1000). The following N lines contain 2 numbers each Pi and Ni  ;(1<=P_i,N_i<=1000). Pi and Ni  are relatively prime numbers. 

Imprint
Output the minimum possible total number of votes. It is guaranteed that the correct answer is no more than 10¹⁸.
 

Examples

ID 39390. Social distancing I

A terrible disease afflicts the cows. Farmer John wants to protect them.
The FD Barn is a narrow long building containing N stalls in a row (2≤N≤105). Some of these stalls are already occupied by cows, some are free. After reading about the need for social distancing, the FD wants to maximize D, where D is the distance between the two closest occupied stalls. For example, if stalls 3 and 8 are the closest that are occupied, then D=5.

Two new cows have been added to FD's herd, and he must decide which unoccupied stall to place each of them in. Determine how k he should place these cows so that the result D, becomes the maximum possible. The FD cannot move any existing cows, he can only assign stalls to new cows.

Input
The first line of input contains N. The next line contains a string of length N, consisting of 0 and 1, describing the sequence of stalls in the barn. 0 means an empty stall, 1 means an occupied stall. There are at least two zeros in the string, which is enough to accommodate two cows.
Imprint
Output the largest value of D (the smallest distance between two occupied stalls) that the FD can obtain by adding two new cows in an optimal way.

Examples

ID 44504. frogs

Three frogs sit on a number line at three different points with integer coordinates a, b, c. The frogs are afraid to retreat too far from each other, so only one of the extreme frogs (such that there are no other frogs to the left or right of it) can jump, and only to an integer point between the other two frogs, if there is one. Note that in some positions none of the frogs can jump, let's call them stable .

1
3
4

1
1

1
10
2

2
7

1
2
3

0
0

2
1
5

2
2