Nick is developing a new web server. The feature he is working on now is
support for access control lists. Access control list allows to restrict
access to some resources on the web site based on the IP address of the
requesting party.
Each IP address is a 4-byte number that is written byte-by-byte in a decimal
dot-separated notation "byte0.byte1.byte2.byte3" (quotes are added for
clarity). Each byte is written as a decimal number from 0 to 255 (inclusive)
without extra leading zeroes. IP addresses are organized into IP networks.
IP network is described by two 4-byte numbers — network address and network
mask. Both network address and network mask are written in the same notation
as IP addresses.
In order to understand the meaning of network address and network mask you
have to consider their binary representation. Binary representation of IP
address, network address, and network mask consists of 32 bits: 8 bits for
byte0 (most significant to least significant), followed by 8 bits for byte1,
followed by 8 bits for byte2, and followed by 8 bits for byte3.
IP network contains a range of 2n IP addresses where 0 ≤ n ≤ 32.
Network mask always has 32 − n first bits set to one, and n last bits
set to zero in its binary representation. Network address has arbitrary
32 − n first bits, and n last bits set to zero in its binary
representation. IP network contains all IP addresses whose 32 − n first
bits are equal to 32 − n first bits of network address with arbitrary n
last bits.
For example, IP network with network address 194.85.160.176 and network mask
255.255.255.248 contains 8 IP addresses from 194.85.160.176 to
194.85.160.183 (inclusive).
IP networks are usually denoted as "byte0.byte1.byte2.byte3/s" where
"byte0.byte1.byte2.byte3" is the network address and s is the number of
bits set to one in the network mask. For example, the IP network from the
previous paragraph is denoted as 194.85.160.176/29.
Access control list contains an ordered list of rules. Each rule has one of
the following forms:
"deny from " — denies access to the resource
to any IP from the specified IP network.
"deny from " — denies access to the resource
to the specified IP address.
"allow from " — allows access to the
resource to any IP from the specified IP network.
"allow from " — allows access to the
resource to the specified IP address.
When some party requests some resource its IP address is first checked
against its access control list. The rules are scanned in order they are
listed, and the first matching rule is applied. If none of the rules matches
the IP address of the party, access is granted.
Given access control list and the list of requesting IP addresses, find out
for each request whether it will be granted access to the resource.
Input file format
The first line of the input file contains n — the number of rules in the
access control list. The following n lines contain rules, one per line.
IP network is always specified as "byte0.byte1.byte2.byte3/s".
The next line contains m — the number of IP addresses to check. The
following m lines contain IP addresses to check, one per line.
Output file format
For each request output 'A' if it will be granted access to the
resource, or 'D' if it will not be granted access. Output all
answers in one line, do not separate output by spaces.
Constraints
0 ≤ n ≤ 100000, 1 ≤ m ≤ 100000.
Sample tests
No.
Input file (access.in)
Output file (access.out)
1
4
allow from 10.0.0.1
deny from 10.0.0.0/8
allow from 192.168.0.0/16
deny from 192.168.0.1
5
10.0.0.1
10.0.0.2
194.85.160.133
192.168.0.1
192.168.0.2
At the entrance to the university, there is a huge rectangular billboard of
size h × w (h is its height and w is its width). The board is the
place where all possible announcements are posted: nearest programming
competitions, changes in the dining room menu, and other important
information.
On September 1, the billboard was empty. One by one, the announcements
started being put on the billboard.
Each announcement is a stripe of paper of unit height. More specifically,
the i-th announcement is a rectangle of size 1 × wi.
When someone puts a new announcement on the billboard, she would always
choose the topmost possible position for the announcement. Among all
possible topmost positions she would always choose the leftmost one.
If there is no valid location for a new announcement, it is not put on the
billboard (that's why some programming contests have no participants from
this university).
Given the sizes of the billboard and the announcements, your task is to find
the numbers of rows in which the announcements are placed.
Input file format
The first line of the input file contains three integer numbers, h, w,
and n — the dimensions of the billboard and the number of announcements.
Each of the next n lines contains an integer number wi — the width of
i-th announcement.
Output file format
For each announcement (in the order they are given in the input file) output
one number — the number of the row in which this announcement is placed.
Rows are numbered from 1 to h, starting with the top row. If an
announcement can't be put on the billboard, output "-1" for this
announcement.
Dr. Strange is a really strange lecturer. Each lecture he calculates class
fullness and if it is small, he decreases all semester grades by one. So the
students want to maximize the class fullness.
The class fullness is the minimum of row fullness and column
fullness. The column fullness is the maximum number of students in
a single column and the row fullness is the maximum number of
students in a single row.
For example there are 16 students shown on the left picture (occupied desks
are darkened). The row fullness of this arrangement is 5 (the 4-th
row) and the column fullness is 3 (the 1-st, the 3-rd, the 5-th or
the 6-th columns). So, the class fullness is 3. But if the students
rearrange as shown on the right picture then the column fullness
will become 4 (the 5-th column), and so the class fullness will
also become 4.
The students of Dr. Strange need to know the arrangement that maximizes
class fullness so they ask you to write a program that calculates
it for them.
Input file format
The first line of the input file contains three integer numbers: n, r
and c — number of students, rows and columns in the class.
Output file format
The first line of the output file must contain a single integer number —
the maximum possible class fullness.
The following r lines must contain the optimal student arrangement. Each
line must contain a description of a single row. Row description is a line
of c characters either "." or "#", where "."
denotes an empty desk, and "#" denotes an occupied one. If there
are multiple optimal arrangements, output any one.
Financial crisis forced many central banks deposit large amounts of cash to
accounts of investment and savings banks in order to provide liquidity and
save credit markets.
Central bank of Flatland is planning to put n deposits to the market.
Each deposit is characterized by its amount ai.
For example, if they already have prizes for 2, 3 and 9 dollars, and they
want to buy 2 prizes, they should buy prizes for 1 and 7 dollars. Then the
winner of the show would be able to collect prizes for any score
from 1 to 22.
The regulations of Flatland's market authorities require each deposit to be
refinanced by equal integer amount each day. That means that a deposit with
amount a and a request with length b match each other if and only if a
is divisible by b.
Given information about deposits and requests, find the number of
deposit-request pairs that match each other.
Input file format
The first line of the input file contains n — the number of deposits.
The second line contains n integer numbers: a1, a2, …, an.
The third line of the input file contains m — the number of requests.
The forth line contains m integer numbers: b1, b2, …, bm.
Output file format
Output one number — the number of matching pairs.
For sample test the following pairs match each other: (3, 1) twice
(as (a1, b1) and as (a1, b2)), (3, 3), (4, 1) twice, (4, 2), (5, 1)
twice, (6, 1) twice, (6, 2), and (6, 3).
Alice likes two things in this world — her mirror and her toy bricks.
Alice's toy bricks were designed to help the children to learn the alphabet,
so there are some letters written on their top faces. Alice likes to play
with the bricks near the mirror.
When Alice learned the alphabet, she noticed that something was wrong with
her mirror! A brick in the mirror can show a different letter on it. Alice
enjoyed this thing very much, and she invented a new game, trying to make
some funny words from the bricks in the real world and in the mirror
simultaneously.
The rules of this game are the following. Alice creates a line from some
bricks that shows the word S1. This line is shown in the mirror as some
word S2, which may be different from the reflection of S1 because the
mirror is enchanted. But the length of each of these words is equal to the
same integer number N.
Then Alice can repeat the following step. She selects some two bricks
i and j and swaps them. The reflected Alice in the mirror does exactly
the same with the mirrored line, except that she of course swaps the bricks
with positions N − i + 1 and N − j + 1 in it.
The goal is to create word T1 in the real world simultaneously with the
word T2 in the mirror. Alice wonders whether it is possible and she asks
you for help. Write a program which can determine whether the goal can be
achieved.
Input file format
The input file contains four words S1, S2, T1 and T2, in this
order, each on the separate line. All words have the same length N and
consist only of uppercase English letters.
Output file format
If the goal can be achieved, output "Yes".
Otherwise output "No".
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.
The organizers of the TV Show "Key to Success" are preparing a set of prizes
for the winner of the game. If the score of the winner is X, she must
choose prizes with a total value of exactly X dollars.
The organizers have a couple of spare prizes from the previous competitions
that have values a1, a2, … , an dollars, respectively.
Unfortunately they don't know what the score of the winner will be. So the
organizers decided to buy m more prizes in order to maximize the minimal
integer score that the winner of the show wouldn't be able to collect prizes
for.
For example, if they already have prizes for 2, 3 and 9 dollars, and they
want to buy 2 prizes, they should buy prizes for 1 and 7 dollars. Then the
winner of the show would be able to collect prizes for any score
from 1 to 22.
Input file format
The first line of the input file contains two integer numbers:
n and m — the number of prizes the organizers have and the number of
prizes they are ready to buy. The second line contains n integer numbers
ranging from 1 to 109 — the values of the prizes organizers have.
Output file format
Output m integer numbers — the values of the prizes the show organizers
should buy. Output numbers in non-decreasing order. If there are several
optimal solutions, output any one.
