Well-known Internet company "Dalstolb" created an on-line marketplace,
where individuals and companies can sell some products.
After purchasing and testing the product, buyer can rate the seller with an integer number
from 1 to 10.
For each seller, website displays number of ratings N and their average A
so that prospective buyers can choose better sellers.
If a company is not satisfied with its rating, it might either improve the quality
of their goods and services, or create some fake accounts and give high ratings from those
accounts to itself.
That practice is called astroturfing.
"Dalstolb" is aware of astroturfing and implemented following limits to make it harder:
each buyer may give only one rating to a given seller;
all ratings strictly greater than twice the current average
are flagged for manual inspection.
Your program must calculate the minimum number of fake accounts required to raise the rating
to at least B, while not triggering manual inspection.
Note that all calculations by "Dalstolb" server are assumed to be absolutely exact,
with no loss of precision at all.
In the first example, ratings and averages are as follows:
Fake account no.
Fake rating
Average rating
1
4
2.40000
2
4
2.66667
3
5
3.00000
4
6
3.37500
5
6
3.66667
6
7
4.00000
Input file format
Input file contains integers NAB.
Output file format
Output file must contain a single integer — minimum number of fake accounts.
Young web developer Vasya was hired by "Dalstolb" company.
Company maintains a popular news website with many advertisement banners.
Marketing department of "Dalstolb" has proposed a new idea for
animated transition between two text messages on the banner.
Message is a single line of characters.
First message has length L1, second has length L2 ≥ L1.
Since the banner width is only enough to fit L1 characters,
the message after the transition should contain any substring the
second message of length L1.
Transition should be performed as a series of animation frames.
Each frame, message is either
scrolled to the right by removing leftmost character and appending arbitrary new character from the right,
or
scrolled to the left by removing rightmost character and appending arbitrary new character from the left.
You program must, given two messages, find a shortest possible transition between them.
Input file format
First line of the input file contains the first message.
Second line of the input file contains the second message.
Messages are composed of small Latin letters.
Output file format
First line of output file must contain integer N — minimum number of frames.
Following N lines must contain two-character string each — frame descriptions.
First character must be either L or R, denoting
right or left scrolling correspondingly. Second character
must be a small Latin letter which should be appended to the message.
C---- language was designed specifically for students
who failed standard course of Compiler Programming.
C---- program is a list of statements. Each statement is one of:
{ — start of the block;
} — end of the block;
int var — variable declaration;
var1=var2 — assign var2 to var1;
var=constant — assign constant to var;
print var — print value of var.
Variable names are single small Latin letters.
Constants are integers in range from 0 to 109.
There are no spaces anywhere except after int and print keywords.
Each variable is declared at most once in the block, but variables with same name may
be declared in different blocks. It that case, name refers to the variable declared
in the nearest enclosing block.
Note that variables may be defined in the middle of the block.
The program is guaranteed to be correct — all blocks are properly balanced,
variables are referenced only after declaration, variables are always initialized before reading, etc.
Program contains at least one print statement.
Your program must execute a given C---- program.
Input file format
First line of input file contains integer N. Following N lines contain one C---- statement each.
Output file format
Output file must contain a sequence of integers — one integer for each print statement.
Constraints
3 ≤ N ≤ 1000
Sample tests
No.
Input file (input.txt)
Output file (output.txt)
1
10
int a
int x
{
a=50
int a
a=60
x=a
print x
}
print a
A sculpture of dragon is established in the campus of Far Eastern Federal University.
There are long claws on dragon's paws.
According to a legend, when a student passes the session successfully,
the claws grow a little (by several nanometers).
That's why students took an interest how much the area of the claw
will increase when the claw grows by d mm.
Students constructed the following mathematical model of dragon's claw growth.
The claw has the shape of a convex polygon with a base on the abscissa axis.
The claw grows equally in all directions and doesn't grow below its base.
When the claw grows by d mm, all its sides shift in parallel
by d mm to the outside (see the figure).
The base of the claw remains at the same place, so
one should intersect the new polygon with the abscissa axis.
Your program must calculate the area of the claw before and after its growing.
Input file format
Input file contains integers Nd, followed by N pairs of integers
xiyi — coordinates of vertices of the polygon in millimeters in the clockwise order.
The polygon is non-degenerate.
Output file format
Output file must contain 2 real numbers: the area of the claw before and after
growing in mm2 with at least 4 correct digits after the decimal point.
Constraints
3 ≤ N ≤ 40; 1 ≤ d ≤ 100;
− 100 ≤ xi ≤ 100; 0 ≤ yi ≤ 100;
y1 = yn = 0.
FEFU computer scientists use a duplication method to detect errors
in network data transfer. Each bit of data is duplicated.
The duplicate follows the original bit.
Each byte therefore is transferred as a message of two bytes.
The first byte of the message encodes high bits of the original byte,
the second byte encodes low bits.
For example, a byte 67 is encoded as follows:
6710 = 010000112;
the sequence 01000011 is encoded as 0011000000001111;
the sequence 0011000000001111 is split into 00110000 and 00001111;
001100002 = 4810, 000011112 = 1510, so the result is 4815
Scientists received two bytes. Now they need to find out what the original byte was.
Input file format
Input file contains two integers designating two received bytes.
Output file format
Output file must contain a single integer — the original byte,
or − 1 if there was an error during transfer.
Constraints
Both input integers are in the range from 0 to 255.
Vladivostok fortress is a unique distributed system of fortifications.
City government made a museum on a nearby island with n fortifications
(we will call them »sites»), and has developed an unusual tourist route.
Sites are numbered from 1 to n.
The site i may have an arrow (not more then one), pointing to another site ai.
The value ai = 0 means that there is no arrow on the site i.
A tourist is disembarked from a helicopter to a random site i
(the probability is equal for all sites).
He stays at the site i for a while,
and then follows the arrow to the next site ai.
On the new site the tourist is doing the same thing.
If ai = 0, the tourist just stays where he is.
If ai was already visited by the tourist, he also stays where he is.
In the evening the helicopter picks up the tourist.
Arrows are placed properly, which means that there exists a site
(maybe more then one), that will be visited by a tourist disembarked at any site.
The more sites the tourist has visited, the happier he is.
So the government have decided to increase the
expected number of sites visited by a tourist.
Due to insufficient funding, they've just decided to change ak for a single site k.
Help the government to choose k and a new ak, such that
arrows are still placed properly and the expected number of visited sites
is maximized.
Consider the example below. There are 8 sites. Arrows are placed properly
since from any site a tourist will get to the site 1.
The expected number of visited sites is 1 / 8 * (1 + 2 + 3 + 2 + 3 + 4 + 4 + 5) = 3.0.
After the change, arrows are still placed properly
since from any site a tourist will get to sites 1, 4, 5, 7, and 8.
The expected number of visited sites is 1 / 8 * (5 + 6 + 7 + 5 + 5 + 6 + 5 + 5) = 5.5.
Any other value of a1 would not give a better answer.
Changing ak for any k ≠ 1 would not give a better answer.
Input file format
Input file contains an integer n followed by n integers ai.
Output file format
Output file must contain two integers — k and a new ak.
If there is more then one optimal solution, output any of them.
If it's impossible to increase the expected number of visited sites,
output 0 0.
Two fathers and two sons walked together...
It is well known that this could describe a group of either 3 or 4 people.
Now let's say that A fathers and B sons walked together.
Could it be that this group consisted of exactly N different persons?
A person is counted as a father if there is his son among the group.
A person is counted as a son if there is his father among the group.
Each father can have one or more sons, each son must have exactly one father.
Father of a person can not be this person's descendant.
Each person must me either a son, a father, or both.
Your program must, given numbers ABN, output
corresponding father-son relationship or determine that it does not exist.
Input file format
Input file contains integers ABN.
Output file format
Output file must contain a number of father-son relationships M
followed by M pairs aibi where ai is a number of the
father, bi is a number of the son (1 ≤ ai, bi ≤ N).
All pairs must be different. If there are several solutions, output any of them.
If it is impossible for a group to consist of N persons,
output file must contain a single integer 0.
Vladivostok Hackathon was an event where several student teams were invited to
invent and prototype their fresh and useful software ideas in several days.
Young programmer Vasya and his team suggested original and exciting game: Tetris.
Game implementation turned to be more complex than young programmers expected,
so they simplified the rules.
A game is played on a rectangular field of H rows and W columns of cells.
Each cell is either occupied or free.
A piece takes a single cell.
New piece appears at some cell on the top row, and starts to fall down in steps.
On every step a player can choose any free cell of the three cells in a row below the piece —
directly under it, a single cell to the right or a single cell to the left.
A piece stops dropping when it either reaches the bottom row,
or the row below it is occupied and the player did not choose to move the piece right or left.
After the piece stops, next piece immediately appears.
Nothing else happens in the game — no rows disappearing, no score, etc.
While Vasya's team was presenting the game to the jury, it crashed and refused to start again.
The only proof that the game ever worked is the log file which it wrote on the previous run.
Log file contains data about N pieces — the column where the piece appeared and
the column where it stopped.
Your program must, given field a description and a game log,
determine whether the log could be the result of a correct game, and,
if not, what is the first piece which could not fall as described in the log.
In the sample 2, after first 6 pieces fall and 7th one appears, the field looks as follows:
.#....
..#...
..#...
..#...
.##..#
It is impossible to move the piece to the 6th column, so the log in incorrect.
Input file format
Input file contains integers WHN, followed by N pairs of integers x1x2 —
initial and final column of each piece.
Output file format
Output file must contain a single integer — the number of first incorrectly positioned piece,
or 0 if all pieces are positioned correctly.
A professor of Fences, Entrances and Frames University has developed a new Fence Inclination theory.
According to that theory, a fence is modeled as a sequence of planks.
Every plank is either slanted right, represented by character / (ASCII 47),
or left, represented by character \ (ASCII 92).
For example, a fence of three right-slanted planks followed by two left-slanted planks
would be represented by string ///\\.
Fence Inclination theory predicts that plank slants change in steps.
On a single step, the fence is first subdivided into a minimal possible number of plank groups.
Each group consists of R ≥ 0 right-slanted planks followed by L ≥ 0 left-slanted planks.
In the sample 1 below an initial state is subdivided into 3 groups,
while in the sample 2 — into 4 groups.
Next, for every group: if R > L, all planks in the group become right-slanted,
if R < L, all planks in the group become left-slanted,
if R = L, plank of the group remain unchanged.
So after the first step the fence in sample 1 will change into the state //////\\\\.
Steps are repeated until the fence state stops changing.
You program must, given the the initial fence state,
output its final state after the changes stop.
Input file format
Input file contains a single string of / and \ characters —
representation of the initial fence state.
Output file format
Output file must contain a single string of / and \ characters —
representation of the final fence state.
Constraints
The length of the input string is between 1 and 1001 characters.
A sculpture of dragon is established in the campus of Far Eastern Federal University.
There are long claws on dragon's paws.
According to a legend, when a student passes the session successfully,
the claws grow a little (by several nanometers).
That's why students took an interest how much the area of the claw
will increase when the claw grows by d mm.
