Linear cellular automaton is an infinite sequence of cells,
each holding either 0 or 1.
Cells are indexed with integers,
extending from some chosen "zero" cell in both
positive and negative directions.
In the initial (first) state all except the finite number of cells contain 0.
Next state is computed from previous one by a simple rule:
new cell value is 1 if the cell had exactly one neighbour with value 1, otherwise 0.
Although computing states is easy and fast,
researchers are often interested in states after very many steps.
Because these states may occupy large amount of memory,
only parts of them are usually printed.
Your program must, given the initial state,
quickly find values for S-th state for cells with indexes F, F + 1, …, F + L − 1.
Input file format
Input file contains number of non-zero cells in the initial state N,
followed by their indexes i1i2… iN, and then integers SFL.
All indexes are different.
Output file format
Output file must contain L values, each of them either 0 or 1.
Constraints
1 ≤ S ≤ 109, −109 ≤ F ≤ 109, 1 ≤ L, N ≤ 2000, −1000 ≤ ik ≤ 1000
Young black-hat hacker Vasya routinely installs key loggers on every computer he can
get his hands on.
Browsing the logs collected, he sometimes can glance passwords of unaware users.
The IT department of the university where Vasya studies noticed suspicious
activity and introduced a new, more secure way to enter passwords.
Instead of password input field, window with 9 buttons is displayed.
Buttons are arranged into 3 × 3 grid as shown in the table below.
7
8
9
4
5
6
1
2
3
Each button is a square of 100 by 100 pixels. There is no space between buttons.
User must enter (digital) password by clicking buttons with a mouse.
To overcome this scheme, Vasya downloaded another cool program: mouse logger.
It saves coordinates of clicks in a file, which Vasya is later able to browse.
However, a complication has arisen: no information is saved about the position
of password window on the screen. Indeed, it might even be partially off screen!
Your program must, given the series of mouse clicks, determine all possible
corresponding passwords.
Input file format
Input file contains number of clicks N followed by integer coordinates
x1y1x2y2… xNyN.
Output file format
Output file must contain one line per possible password. Each line must consist
of exactly N digits. Lines must be sorted in lexicographical order.
If there are no possible combinations, output file must contain the string NONE.
Customer support department in an "Incomprehension Amateurs, Ltd" software company
has call center for answering users' questions.
Support prices are as follows:
1.
Answer to a question
10 USD
2.
Correct answer to a question
20 USD
3.
Correct answer to a question with explanation
40 USD
4.
Correct answer to a question which was already correctly answered before
+10 USD for each previous correct answer
So, for example, if user asks the same question three times,
first receives incorrect answer, then correct one, and the third time correct answer with explanation,
it will cost him 10 + 20 + (40 + 1 * 10) = 80 USD.
Customers are billed monthly according to call log.
Company engineers review the log and for each question determine:
unique number, so the equivalent questions have same numbers,
whether the answer was correct,
whether the answer was short or included detailed enough explanation.
Given that data, your program must calculate the payment amount.
Input file format
Input file contains number of calls N followed by N triples qiaixi, where
qi is integer question number, ai = 1 if the answer was correct, 0 otherwise,
xi = 1 if explanation was given, 0 otherwise.
Output file format
Output file must contain a single number — payment amount.
When wondering through the labyrinth, the goal is usually to find some kind of door.
Well, not this time.
A labyrinth consists of N × N cells, each 1 × 1 meter in size.
Cells are separated by doors. Each door opens in a specific direction (as shown on the picture):
left outwards;
left inwards;
right outwards;
right inwards.
So a cell can be represented by two numbers describing doors on its eastern
and southern sides according to the list above.
The doors are just slightly less then 1 meter in width.
The traveler in the labyrinth is also slightly less then 1 meter in diameter,
so he has following limitations:
He can not pull doors, only push them.
After opening the door and entering the cell it leads to,
he can not take a turn in the direction where the door opened,
because the passage is blocked by the door.
Doors have springs and close automatically when traveler leaves the cell.
Your program must find the shortest path for the traveler from north-western cell (1, 1)
to south-eastern cell (N, N).
Input file format
Input file contains labyrinth size N followed by 2 × N2 numbers
describing doors for each cell row by row.
As there are no doors leading outside of labyrinth,
values for eastern doors in the last column and southern doors in the last row are zero.
Output file format
Output file must contain the shortest path as a list of cell coordinates
(column number, then row number), including both (1, 1) and (N, N) cells.
If there are several solutions with the same length, output any one of them.
If it is impossible to get to a destination cell, output a singe zero.
In a big and rich on natural resources country,
the government started a campaign to control deforestation.
In fact the government is not too interested in how many trees get fallen,
but rather how effectively the wood is utilized.
So a law was passed which requires every logging company to pay amount
of money in proportion to amount of wood that it wastes during operation.
A felling quota on some territory was allotted to a company in this country.
Company lorries may only transport logs of exactly L meters long.
So when a tree gets sawed into logs, the remainder is wasted.
Trees in this country grow exactly 1 meter per year,
so the company may decrease the amount of tax to be
paid by simply waiting for some years.
Your task is to determine the number of years needed to achieve smallest possible tax.
If there is more than one answer, find minimal (earliest) one.
Input file format
Input file contains number of trees N, length
of log L, followed by integers i1i2… iN — heights of each tree.
Output file format
Output file must contain single integer — number of years to wait.
Text formatting functions (Format, sprintf, etc) are very common
between programming languages. Your task is to implement a simplified one.
Formatting function receives format string and several arguments.
Argument values are processed one by one and inserted into format string at
positions designated by format specifiers.
The following format specifiers must be implemented:
%s — argument as a string
%d — argument as an integer value, without any leading zeroes
%% — literal '%' character
Formatting error is generated if:
number of arguments required by format specifiers
is not equal to the number of actually supplied arguments,
argument for %d specifier contains non-digit character.
'%' character in format string is not followed by either
'%', 's' or 'd'.
Input file format
Input file contains format string followed by arguments, one per line.
Output file format
Output file must contain a single string — either formatted text
or ERROR in case of any formatting error.
Constraints
Number of arguments is not greater than 1000,
length of each line is not greater than 50000 characters.
Classic geometric construction is based on two instruments: ruler and compass.
However, some constructions are possible using only the ruler.
Specifically, let us define that if we have a set of N points,
we can select two pairs of them, draw a line through each pair,
and construct a new point as an intersection of these two lines.
New point can then be added to the set as (N + 1)-th point,
and the process repeated.
Such geometric constructions are abstract notions, and attempt to verify them
with physical pencil and ruler can lead to errors caused by imprecision of these instruments.
So you are tasked to write a program that does exact verification.
Your program must read a set of points and a sequence of constructing operations
and find out whether the point with coordinates (0, 0) is one of the constructed points.
Note that, similar to physical instruments, floating point calculations performed by
computers are also imprecise. This should not, of course, alter verification results.
Input file format
Input file contains number of points N followed by their integer coordinates
x1y1x2y2… xNyN.
Next comes number of construction operations M followed by M quads of integers
aibicidi, where k-th quad means that a new point is constructed
as an intersection of lines containing pairs of points ai, bi and ci, di.
Such a point is guaranteed to exist. Constructed point is assigned a number N + k
and can be used in following operations.
Output file format
Output file must contain a single integer — number of
the first operation which constructs a point (0, 0), or 0 (zero),
if there is no such operation.
