Fenwick tree is a data structure effectively supporting prefix sum
queries.
For a number t denote as h(t) maximal k such that t is divisible by
2k. For example, h(24) = 3, h(5) = 0. Let l(t) = 2h(t),
for example, l(24) = 8, l(5) = 1.
Consider array a[1], a[2], …, a[n] of integer numbers. Fenwick tree
for this array is the array b[1], b[2], …, b[n] such that
b[i] = ∑ij = i − l(i) + 1a[j].
So
b[1] = a[1],
b[2] = a[1] + a[2],
b[3] = a[3],
b[4] = a[1] + a[2] + a[3] + a[4],
b[5] = a[5],
b[6] = a[5] + a[6],
...
For example, the Fenwick tree for the array
a = (3, −1, 4, 1, −5, 9)
is the array
b = (3, 2, 4, 7, −5, 4).
Let us call an array self-fenwick if it coincides with its Fenwick
tree. For example, the array above is not self-fenwick, but the array
a = (0, −1, 1, 1, 0, 9) is self-fenwick.
You are given an array a. You are allowed to change values of some
elements without changing their order to get a new array a' which must be
self-fenwick. Find the way to do it by changing as few elements as possible.
Input file format
The first line of the input file contains n — the number of elements in
the array. The second line contains n integer numbers — the elements of
the array.
Output file format
Output n numbers — the elements of the array a'. If there are several
solutions, output any one.
Constraints
1 ≤ n ≤ 100000.
The elements of the input array do not exceed 109 by their absolute
values.
The Hilbert Mole is a small and very rare mole. The first and only specimen
was found by David Hilbert at his backyard. This mole lives in a huge burrow
under the ground, and the border of this burrow forms a Hilbert curve of
n-th order (Hn).
Hilbert curves can be defined as follows. H1 is a unit square with open
top side (fig. 1a), Hn consists of four copies of Hn − 1: bottom
left and bottom right are copied without changes, top left is rotated
90∘ counter-clockwise and top right is rotated 90∘ clockwise.
These small copies are connected by three segments of unit length
(fig. 1b,c,d).
Trying to exterminate the mole, Mr. Hilbert fills the burrow with water
(fig. 2). But air inside the burrow prevents water from filling it entirely.
In this problem we suppose that air and water are incompressible and cannot
leak throw the borders of the burrow. Your task is to find the total area of
the burrow, filled with water.
Note that water can flow over the obstacle only when its level is
strictly higher. See examples on fig. 3 for further clarification.
Input file format
The first line of the input file contains two integer numbers: n and
α — order of Hilbert curve and slope angle of surface in degrees.
Output file format
The first line of the output file must contain a single real number — the
total area of the burrow, filled with water. The relative error of the
answer must not exceed 10−7.
You may have seen a mechanic typewriter — such devices were widespread just
15 years ago, before computers replaced them. It is a very simple thing. You
strike a key on the typewriter keyboard, the corresponding type bar rises,
and the metallic letter molded into the type bar strikes the paper. The art
of typewriter typing, however, is more complicated than the art of computer
typing. You should strike keys with some force otherwise the prints will not
be dark enough. Also you should not overdo it otherwise the paper will be
damaged.
Imagine a typewriter with very sharp letters, which cut the paper instead of
printing. It is clear that digit 0 being typed on the typewriter makes a
nice hole in the paper and you receive a small paper oval as a bonus. The
same happens with some other digits: 4, 6, 9 produce one hole, and 8
produces two touching holes. The remaining digits just cut the paper without
making holes.
The Jury thinks about some exhibition devoted to the oncoming jubilee of
Pascal language. One of the ideas is to make an art installation, consisting
of an empty sheet of paper with exactly h holes made by typing a
non-negative integer number on the cutting typewriter described above. The
number must be minimal possible and should not have leading zeroes.
Unluckily we are too busy with preparing the ACM quarter- and semifinals, so
we need your help and ask you to write a computer program to generate the
required number.
Nick bought a new motherboard for his computer and it seems that it does not
work properly. The motherboard is pretty complicated but it has only few
important wires that have binary states: live or dead. Nick wants to know
the states of these wires.
Unfortunately, important wires are not directly accessible. But Nick found a
maintenance socket. Each output pin of this socket is connected to some of
important wires via an integrated circuit. Fortunately, Nick found the
circuit layout in the Internet. To specify it, he marked important wires by
lowercase letters and socket's output pins by uppercase letters. After that
he wrote down Boolean formula for each output pin. In these formulae live
wires and pins are represented by true and dead wires — by
false.
Nick used following notation for formulae (operations are listed from the
highest priority to the lowest):
Pin names — letters from 'a' to 'k';
Parentheses — if E is a formula, then (E) is another;
Negation — ¬ E is a formula for any formula E;
Conjunction — E1 ∧ E2 ∧ ⋯ ∧ En;
Disjunction — E1 ∨ E2 ∨ ⋯ ∨ En;
Implication — E1⇒ E2⇒ ⋯ ⇒ En.
Implication is evaluated from right to left:
E1⇒ E2⇒ E3 means
E1⇒ (E2⇒ E3);
Equivalence — E1 ≡ E2 ≡ ⋯ ≡ En.
This expression is by definition computed as follows:
(E1 ≡ E2) ∧ (E2 ≡ E3) ∧ ⋯ ∧ (En − 1 ≡ En).
Nick has lots of various gates at hand, so he can build a new circuit that
implements any formula. The variables of this formula are states of
maintenance socket's pins. First of all, Nick wants to construct a circuit
that takes all maintenance socket's pins as inputs and has a single output
wire that is always live. Write a program to help him.
Input file format
The first line of the input file contains a single integer number n — the
number of pins in the maintenance socket. The following n lines contain
description of one pin each.
Each pin description consists of a pin name and corresponding formula
delimited by ':=' token. Pin name is a uppercase English letter.
Formula is represented by a string consisting of tokens
'a'..'k', '(', ')', '~',
'&', '|', '=>', and '<=>'.
The last five tokens stand for ¬, ∧, ∨, ⇒ and
≡ respectively. Tokens can be separated by an arbitrary number of
spaces.
Output file format
The first line of the output file must contain "Yes" if there
exists a circuit which output wire is always live and "No"
otherwise.
In the former case the following line must contain the formula for the
constructed circuit in the same format as in the input file. Remember that
the formula must contain each of pin names at least once and it must not
contain the wire names. The line must not exceed 1000 characters.
Constraints
1 ≤ n ≤ 10.
Each pin description contains 1000 characters at most.
Sample tests
No.
Input file (important.in)
Output file (important.out)
1
3
A := (a=>c )& (b<=>d)
C:= a | b
B := c | d
Since mass transit was invented, people who buy tickets look for lucky
ticket numbers. There are many notions of lucky tickets, for example
sometimes tickets are considered lucky if the sum of first half of the
digits is equal to the sum of the second half, sometimes the product is used
instead of the sum, sometimes permutation of digits is allowed, etc.
In St Andrewburg integer numbers from 1 to n are used as ticket numbers.
Bill considers a ticket lucky if its number is divisible by the sum of its
digits. Help Bill to find the number of lucky tickets.
