A game development company has started prototyping a new game, which is played on a field based on a hexagonal grid.
The first task is to display a part of the grid in the player's viewport.
To speed up the prototyping phase, it was decided to use text-based representation instead of graphics.
The hexagonal grid is composed of nearly perfect hexagons with the side of N characters.
In every hexagon, the top and the bottom sides are composed of N "_" characters (ASCII 95),
the right-top and the left-bottom sides are composed of N "\" characters (ASCII 92),
the left-top and the right-bottom sides are composed of N "/" characters (ASCII 47).
All other characters of the field are "." (ASCII 46).
The grid is assumed to be infinite, with the position (0; 0) corresponding to the
leftmost character of the top side of a hexagon.
The player's viewport is a rectangle displaying some part of the field.
You program must, given the coordinates x, y of the top left corner of the viewport
and w, h — the viewport width and height, output the content of the viewport.
Input file format
Input file contains integers Nxywh.
Output file format
Output file must contain h lines of w characters each — the viewport content.
According to ISO stadnard Metric tire code, tire dimensions are described by a string of letters and numbers
in the following format:
3-digit nonzero number: The nominal section width of the tire in millimeters,
the widest point from both outer edges.
/: Slash character for separation.
2- or 3-digit nonzero number: The aspect ratio of the sidewall height to the nominal section width of the tire, as a percentage.
Letter R indicating radial construction of the fabric carcass of the tire.
2-digit nonzero number: Diameter in inches of the wheel disk that the tires are designed to fit.
Rules of ACM (Any Car Modification) race specify a fixed tire dimensions for all participating cars.
Young racer Vasya has not been able to find this type of tire.
However, his car will still be approved for the race by judges only if radius of the wheel
(wheel disk radius plus sidewall height) differs by at most K percent from that of the specified tire.
Note: 1 inch = 25.4 millimeters. Number a differs from b by at most c percent when 100 × |a − b| / b ≤ c.
Input file format
First line of input file contains integer K.
Second and third lines contain Metric tire codes of specified tire and Vasya's tire respectively.
Tire codes contain only digits, R and slash (ASCII 47) characters.
Output file format
Output file must contain a single string — APPROVED if Vasya's car is approved to the race or DISAPPROVED otherwise.
Young programmer Vasya was not at all interested in car races, but many of his friends were.
One day, friends persuaded Vasya to come with them to a sports bar to drink beer and watch
some very important race involving N cars —
they told Vasya the name of the race, but he immediately forgot it.
At first Vasya was not keen to go, but the perspective of a good beer won him over.
After an hour at the bar, Vasya understood that that the endless images
of the cars driving around and around were just as boring with beer as without it.
His friends, however, got quite excited and started to place bets on race results.
Due to the amount of beer consumed, the bets were wild and some of them did not reflect
actual chances at all. In total, M bets were suggested.
Since Vasya was unable to have fun, he decided at least to make some profit.
All bets are of the form "I bet A roubles versus B roubles that car p will come ahead of car q".
That means betting person agrees to pay A roubles if he was wrong (i.e. q will come ahead of car p),
and requires the other side to pay him B roubles if he was right.
By betting on the same cars with different friends, Vasya would in some cases guarantee himself a net
win, even if he loses some of the bets.
So as not to alienate too many of his friends, Vasya decided to accept only two bets.
Find two bets for Vasya which will guarantee him the largest profit in the worst case.
Input file format
Input file contains integers NM followed by M bet descriptions.
Each bet description contains integers AiBipiqi.
Output file format
Output file must contain a single integer — the maximum amount of guaranteed profit.
If there is no way to select two bets to be always profitable, output must contain 0.
Underwater arithmetic is very elementary.
There are just two operations: WITH and WITHOUT
which mean addition and subtraction respectively.
Underwater mathematicians did not yet invent brackets,
so all expressions are calculated from right to left.
For example, the expression 3 WITH 5 WITHOUT 4 WITHOUT 7
is calculated as (3 + (5 − (4 − 7))).
Scientists of Nearsea Institute of Underwater Arithmetic
need a program to evaluate such expressions.
Input file format
First line of input file contains a single integer N.
Following 2 × N + 1 lines describe the expression.
Odd lines contain integer operands, even lines contain operations.
Output file format
Output file must contain a single integer — calculation result.
Young programmer Vasya is learning the beginnings of the algorithm complexity theory.
For starters, he wants to be able to quickly estimate the number of iterations
of nested loops.
As a first example, he wrote the following code:
C
Pascal
long long f(int n)
{
long long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++)
for (int k = j+1; k <= n; k++)
ans++;
return ans;
}
function f(n: integer): int64;
var i, j, k: integer;
begin
result := 0;
for i := 1 to n do
for j := i+1 to n do
for k := j+1 to n do
inc(result);
end;
Using your knowledge of the subject,
help Vasya calculate f(n) for given n.
During the course on compiler construction, students were assigned a task: implement
a parser for expressions with array access according to Pascal programming language syntax.
Student Vasya has slacked on this task, and implemented only a very small language subset,
consisting of a single integer constant 0 and accesses to a single two-dimensional array a.
In other words, his "language" has the following grammar:
expr ::= 0 | a[expr,expr]
After seeing this sad result, a teacher assigned an additional task to Vasya:
suppose an array a is defined as
a: array [0..N - 1, 0..N - 1] of 0..N.
Given N and the values of array elements,
generate the shortest possible expression in Vasya's language which will have the value of N.
Input file format
Input file contains an integer N, followed by N2 integers — values aij,
in row-by-row order.
Output file format
Output file must contain a single string — an expression in Vasya's language.
The expression must exactly correspond to the grammar above.
If there is no expression with the value of N, output string IMPOSSIBLE.
If there are several shortest expressions, output any of them.
Many compression algorithms are based on finding frequently repeating substrings
in the input data. Since it is often impractical to search the whole input
for repetitions, only a limited compression window is considered
on each step.
While researching a new compression algorithm, young computer scientist Vasya
encountered the following problem.
Given input string of N bits, let the compression window be any substring of M bits.
Inside each compression window, find the maximum number of occurrences of
any substring of length L (L ≤ M).
In the sample input 1 below, compression window length is equal to string length,
so there is only a single window. Most frequent substring of length 2 is 01,
which occurs 5 times.
Input file format
First line of input file contains integers LM.
Second line input file contains a string of length N, each character either 0 or 1.
Output file format
Output file must contain N − M + 1 integers — maximum substring frequencies for each compression window.
One famous car race takes place on a stadium with a racetrack.
Spectators watching the race sit on a stand consisting of H rows with W seats each.
During the race, some seats are occupied by spectators, and others are empty.
Marketing research demonstrated that if one spectator will loudly shout out a nicely rhymed slogan,
spectators on seats located immediately to the left, right, above and below him will repeat it.
Their neighbors, in turn, will catch up, and the slogan will spread throughout the stand.
An advertisement company invented a new slogan and wants it to spread among as many
spectators as possible.
To simulate "spontaneous" appearance of the slogan the company hired an agent
who will move to one of the unoccupied seats and shout the slogan from there.
You program must determine the position of the agent which will result in maximum
slogan penetration.
Input file format
Input file contains integers WH in the first line, followed by H lines of W characters each.
Each character is either a '.' (ASCII 46) or '#' (ASCII 35), denoting free and occupied seat correspondingly.
There is at least one free seat.
Output file format
Output file must contain two integers — xy, denoting seat number and row number for the agent to take.
Rows are numbered starting from 1, top to bottom. Seats are numbered starting from 1, left to right.
If there are several optimal solutions, output any of them.
