Let us define that a positive integer A is simpler than a
positive integer B if the decimal representation of A requires
less different digits than the decimal representation of B.
For example, number 55 is simpler than 12 which in turn is simpler than 123.
Your program will be given a number N and must find the largest integer X
such that X < N and X is simpler than N.
Input file format
Input file contains integer N.
Output file format
Output file must contain integer X.
If there is no integer simpler than N, output file must contain 0 (zero).
Some applications (such as compression algorithms) require searching
a memory area for arbitrary bit strings.
Your program must find the first occurrence of the given bit string in
the sequence of numbers generated by an arithmetic progression:
a, a + b, a + 2b, …, a + N × b.
Numbers are stored in a continuous memory area as 32-bit unsigned integers
in the little-endian byte order.
Bits in byte are counted from the least significant to the most significant one.
For example, number 123456 will be stored as a sequence of four
bytes with hexadecimal values "40 E2 01 00", interpreted as bit string
"00000010 01000111 10000000 00000000" (spaces inserted for readability only).
So the occurrence of the bit substring "1001" would be at position 7.
Note that the occurrence can cross boundaries between numbers.
Input file format
First line of input file contains integers abN.
Second line of input file contains a string of '0' and '1'
characters, each character representing one bit of the string to search for.
Output file format
Output file must contain a single integer — the position of
the bit string in the memory area, starting from 1.
If the bit string is not found, output file must contain 0 (zero).
String concatenation is the operation of joining two character strings end to end.
For example, the strings "foo" and "bar"
may be concatenated to give "foobar".
You program will be given N strings a1, …, aN and will
have to perform M concatenations represented by pairs of integers
(p1, q1), …, (pM, qM).
Each pair (pj, qj) means that a new string aN + j
is the concatenation of strings apj and aqj, where 1 ≤ pj, qj < N + j.
For example, strings "a" and "bc" and pairs (1, 2), (3, 3)
mean that new strings "abc" and "abcabc" are generated.
Your program must output a substring of aN + M
from position L to position R, counting from 1.
Input file format
First line of input file contains integers NMLR.
Following N lines contain strings ai — one string per line.
Each of the following M lines contain two integers pjqj.
Output file format
Output file must contain a string of R − L + 1 characters.
Resource sharing is an important problem in parallel programming.
When parallel tasks must use common resource, such as
input/output channel, they serialize their access by using locks.
Two basic locking primitives are provided:
LOCK r — marks resource as
locked by the calling task. If the resource is already locked
by the same task, it does nothing. If it is locked by a different task,
calling task is blocked (i.e. pauses execution and waits)
until the resource is unlocked.
UNLOCK r — unlocks given resource
if it is locked by the current task, and does nothing otherwise.
After the execution of the last locking primitive of the task,
all resources locked by that task are unlocked.
Locking guarantees that only a single task can access the
resource at a time. However, carelessly written programs may
still lead to some unfortunate situations.
If task A has already locked resource P and tries to lock Q,
while task B has already locked Q and tries to lock P,
they will both wait endlessly.
This condition is called "deadlock".
Your program must, given lock/unlock sequences executed by
two parallel tasks while accessing M resources,
determine whether a deadlock is possible between them.
Input file format
First line of input file contains integers N1N2M.
Following lines contain N1 locking primitives called by the first task,
then N2 primitives called by the second task, in the order of calling.
Each primitive is located on a separate line and consists of a string
LOCK or UNLOCK followed by one or more spaces and
a resource number r (1 ≤ r ≤ M).
Output file format
Output file must contain integers D1D2,
designating that deadlock can occur when
the first task is trying to execute primitive number D1 (1 ≤ D1 ≤ N1) while
the second task is trying to execute primitive number D2 (1 ≤ D2 ≤ N2).
If there is more than one possible deadlock, output the one with minimal D1.
If there is still more then one, output the one with minimal D2.
If the deadlock is not possible, output file must contain a single 0 (zero).
Young system administrator Vasya is moving into a new server room.
The room has a shape of convex polygon with LCD monitors
mounted on some of the walls.
Monitors display the health data of various servers, so Vasya
wishes to place his rotating chair such that he could observe
them all without need to leave it.
He moved all obstacles out of the way, so he can see any point
of any monitor from any place inside the room.
The only problem is that the image on LCD monitors deteriorates at
large viewing angles.
Viewing angle is an angle between the line connecting the eye of viewer
with the point on monitor and the normal vector at that point.
The angle can have values in range from 0 to π / 2.
Vasya wants to place his chair at
a point which minimizes a maximum viewing angle from him to any point
of any monitor.
For example, in a picture line segment AB represents a monitor,
point C — a chair, angles A′AC and B′BC are viewing angles,
and the second of them is the maximum one.
Input file format
Input file contains the number of monitors N followed by N triplets of integers
xiyiai, where xiyi — coordinates of room vertexes in counter-clockwise order,
ai = 1 if the wall between the i-th vertex and the next one is covered by a monitor,
ai = 0 otherwise.
Output file format
Output file must contain floating point values xy —
coordinates of point to place a chair. The point must lie inside the room.
If there is more than one solution, output any of them.
The maximum viewing angle from point (x, y) must differ
from the correct answer by at most 10 − 3 (measured in radians).
Floating point numbers can be presented by a computer program in various formats,
either exponential or fixed.
For example, a number 1234.5 can be presented as "1234.5", "123.45e1", "0.12345e4",
"12345e-1" and so on.
You program must find the shortest possible representation of a given floating point number.
Representation is allowed to omit both leading and trailing zeros,
but must preserve all the other digits.
Input file format
Input file contains a single floating point number.
Note that it may be too long to be stored in built-in floating point types
without loss of precision.
Output file format
Output file must contain a single string — the shortest representation of
the input number.
If there is more than one shortest representation, you must choose the one in fixed format,
or, failing that, the one with the lowest absolute value of exponent.
Constraints
Input number contains from 1 to 1000 digits and is either 0 or in
range from 10 − 2000 to 102000.
Both input and output numbers must contain at least one digit on each side
of the decimal point (if the point is present)
and must denote exponent with the lowercase letter 'e'.
Young programmer Vasya has a little sister. She likes to play tabletop games,
and constantly nags her brother to play with her.
One game she particularly enjoys is played with a dice and a long board.
The board is divided into a sequence of N cells. A player starts from the first cell.
Each turn, the player throws the dice, obtaining an evenly distributed random number
from 1 to 6. The player advances forward by the number of cells equal to the number
on the dice.
Destination cell is either empty, or contains instruction "jump to the K-th cell".
In the latter case, the player immediately moves to the K-th cell
instead of the destination cell.
The game ends when the number on the dice is equal to or greater
than the number of cells left to the end of the board.
Vasya finds the game rather boring, especially the fact that
the instructions on the cells keep sending you back again and again,
dragging the game indefinitely.
Vasya wants to calculate the expected value (also known as
the mathematical expectation) of the number of moves, so he could estimate
the average time required to finish the game.
Input file format
Input file contains an integer N, followed by N integers di,
where di = 0 if the cell is empty or contains the number of cell (from 1 to N − 1)
where the player must move instead of the i-th cell.
Output file format
Output file must contain a single floating point number — expected value of
the number of turns with the absolute error of at most 10 − 3.
Constraints
2 ≤ N ≤ 25, d1 = dN = ddi = 0
There is always at least one sequence of dice throws allowing to finish the game.
When young programmer Vasya was even younger, he found a book on organic chemistry.
He did not understand a thing, but liked the pictures of structural chemical formulae
in the book and started to draw many similar ones.
Years later, while clearing his room, Vasya found his old drawings and wondered
which of them were correct. Since there were many of them, he decided to write
a program for that task.
The structural formula of a chemical compound is a graphical representation
of the molecular structure showing how the atoms are arranged.
Atoms are denoted by letters, and chemical bonds between them — by line segments.
Formula is represented in input file as a two-dimensional array of characters.
Each character may be:
'.' (ASCII 46) — empty space,
'C' — carbon atom,
'H' — hydrogen atom,
'O' — oxygen atom,
'|' (ASCII 124),
'/' (ASCII 47),
'\' (ASCII 92),
'-' (ASCII 45) — chemical bonds.
Bonds in correct formula are drawn as straight vertical,
horizontal or diagonal lines without intersections.
Atoms represented by adjacent letters are not considered bonded.
Correct formula must contain at least one atom and must be connected
(there must be a path from each atom to each other passing through bonds).
Additionally, Vasya wants to check that the number of bonds for each atom
is equal to the valency number of the corresponding chemical element.
For simplicity, he decided that number would be always equal to 4 for carbon,
2 for oxygen and 1 for hydrogen.
Input file format
First line of input file contains integers NM.
Following N lines contain M characters each — formula representation.
Output file format
Output file must contain a single string: GOOD,
if the drawing represents correct formula,
VALENCY if the formula is correct in everything except valencies,
and BAD otherwise.
He moved all obstacles out of the way, so he can see any point
of any monitor from any place inside the room.
The only problem is that the image on LCD monitors deteriorates at
large viewing angles.
The structural formula of a chemical compound is a graphical representation
of the molecular structure showing how the atoms are arranged.
Atoms are denoted by letters, and chemical bonds between them — by line segments.