PizzaSocks company makes and delivers pizza. Pizza
is delivered on regular schedule. A schedule has a period of
1, 2, 3 or 4 weeks. Quantity of pizzas to be delivered is known for
each day of the period. First day of a period is always the
first day of the week.
So formally pizza delivery schedule can be described by the following
numbers: L — length of the schedule period (from 1 to 4),
A1, A2, …, AL × 7 — quantity of pizzas to be delivered for
each day of the period (Ai ≥ 0).
Once an absent-minded PizzaSocks manager lost a schedule for one Very
Big and Important Client. Only the history of past deliveries was preserved.
Your task is to restore the schedule from the history.
The problem is complicated by the fact that occasionally Very Big and
Important Client changed his orders, ordering either more or less
pizzas than scheduled, even sometimes cancelling the order competely
or placing an unscheduled order.
So it's often impossible to restore the original schedule exactly.
That is why your task is to find an optimal schedule, i. e.
to minimize the total number of days when historically ordered quantity
is different from the quantity according to that schedule.
The days before the first recorded order and after the last recorded one
should not be taken into consideration.
Input file format
Input file contains the following integer numbers:
N — number of fulfilled orders in the delivery history
w1d1q1w2d2q2… wNdNqN — description
of historical orders: week number, day of the week, and quantity of pizzas
delivered. For each day there is no more than one record. It's considered
that on those days that are not explicitly mentioned in the input file,
but fall between the earliest and the latest mentioned days, zero-quantity
orders were fulfilled.
Output file format
Output periodicity of the optimal schedule — integer number L
from 1 to 4. Then output numbers Ai for each i
from 1 to L × 7. If several solutions exist, output any of them.
However, make sure that the first week of your schedule corresponds
to the earliest week mentioned in the input file.
Square raster image is represented by an array of N × N pixels.
A texture tile is a square image in which the first row is equal to the last one,
and the first column is equal to the last one. This property is valuable when covering
the surface of graphics object with repeating copies of texture, because it
allows "seamless" transitions between tiles.
Your program must, given an image, find its largest subimage which is a texture tile.
Input file format
Input file contains integer N followed by N2 numbers ci, j — pixel values.
Output file format
Output file must contain numbers pqm — coordinates of top left corner and size of the
largest texture tile. If several solutions exist, output any of them.
Given a set of points with integer coordinates xi, yi, i = 1… N,
your program must find all the squares having each of four vertices in one of these points.
Input file format
Input file contains integer N followed by N pairs of integers xiyi.
Output file format
Output file must contain a single integer — number of squares found.
Constraints
−104 ≤ xi, yi ≤ 104, 1 ≤ N ≤ 2000.
All points in the input are different.
Two cars crashed on the road, receiving some damage each, and
raising the usual question: "Who to blame?". To answer this, it is essential to
thoroughly reconstruct the sequence of events. By gathering witness testimonies
and analyzing tire tracks, positions and speeds of cars just before the impact
were determined.
From these positions until the crash the cars moved straight forward.
Your program must, given the available data, calculate for each car
what part of it first came into contact with the other car. Parts are numbered as
shown on the picture.
Input file format
Input file contains twelve floating point numbers:
x1y1u1v1w1s1x2y2u2v2w2s2, where (x, y) and (u, v) — coordinates of
back-left and forward-left corners of the car, w — width of the car, s — speed of the car.
Output file format
Output file must contain two integers: p1p2, where p — number of part which
first contacted the other one (if two parts came into contact simultaneously,
output the lesser of the part numbers),
Constraints
1 ≤ xi, yi, ui, vi, wi ≤ 106, 0 ≤ si ≤ 106.
Input data is such that a crash certainly happens. Initially cars don't have common points.
A zoology research lab has a terrarium with rare species of snakes.
Terrarium is a flat box filled with soil, and has a glass top allowing to watch the snakes.
There are trenches in the soil, and snakes constantly move along the trenches.
All snakes have diameter of 1 cm and integer length of no less than 2 cm.
While watching the snakes, the zoologists discovered a pattern in their movement:
each snake moves at a speed of 1 cm per second forward, until it encounters either
a wall or another snake. Faced an obstacle, snake first tries to turn right, if there
is also obstacle on the right, then it tries to turn left. If there is obstacle on the left also,
the snake waits for a second before trying to move again.
In order to validate the discovery, it was decided to write a program that simulates snakes'
behaviour. This task was assigned to you.
The terrarium is represented by an array of N × N characters.
Each character is one of:
'.' (ASCII 46) — trench
'#' (ASCII 35) — wall
'A' to 'Z' — snake's head
'a' to 'z' — snake's body or tip of the tail
Snakes are represented by latin letters, so there are no more than 26 snakes in terrarium.
Snakes try to move in alphabetical order every second.
Your program must output the state of the terrarium after T seconds.
Input file format
First line of input file contains integers NT.
Following N lines contain N characters each — the initial state of the terrarium.
The input file guarantees unambiguous recognition of snakes — all snakes are continuous,
every character of snake's body has exactly two neighbour characters belonging
to the same snake, while head and tip of the tail have exactly one.
Output file format
Output file must contain N lines of N characters —
the state of the terrarium after T seconds.
The puzzle game of Sudoku is played on a board of N2 × N2 cells.
The cells are grouped in N × N squares of N × N cells each.
Each cell is either empty or contains a number between 1 and N2.
The sudoku position is correct when numbers in
each row, each column and each square are different. The goal of the game is, starting from
some correct position, fill all empty cells so that the final position is still correct.
This game is fairly popular in the Internet, and there are many sites which allow
visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness
of a given position.
You are to write such a routine.
Input file format
Input file contains integer N, followed by N4 integers — sudoku position.
Empty cells are denoted by zeroes.
Output file format
Output file must contain a single string 'CORRECT' or 'INCORRECT'.
As you know, all the computers used for ACM contests must be
identical, so the participants compete on equal terms. That is why
all these computers are historically produced at the same factory.
Every ACM computer consists of P parts. When all these parts
are present, the computer is ready and can be shipped to one of
the numerous ACM contests.
Computer manufacturing is fully automated by using N various
machines. Each machine removes some parts from a half-finished
computer and adds some new parts (removing of parts is
sometimes necessary as the parts cannot be added to a computer
in arbitrary order). Each machine is described by its
performance (measured in computers per hour), input and
output specification.
Input specification describes which parts must be present
in a half-finished computer for the machine to be able to operate
on it. The specification is a set of P numbers
0, 1 or 2 (one number for each part), where 0 means that
corresponding part must not be present, 1 — the part is
required, 2 — presence of the part doesn't matter.
Output specification describes the result of the operation,
and is a set of P numbers 0 or 1, where 0 means that
the part is absent, 1 — the part is present.
The machines are connected by very fast production lines
so that delivery time is negligibly small compared to
production time.
After many years of operation the overall performance of the
ACM Computer Factory became insufficient for
satisfying the growing contest needs. That is why ACM
directorate decided to upgrade the factory.
As different machines were installed in different time periods,
they were often not optimally connected to the existing factory
machines. It was noted that the easiest way
to upgrade the factory is to rearrange production lines.
ACM directorate decided to entrust you with solving this problem.
Input file format
Input file contains integers PN, then
N descriptions of the machines. The description of ith
machine is represented as by 2P + 1 integers QiSi,1Si,2… Si,PDi,1Di,2… Di,P,
where Qi specifies performance, Si, j —
input specification for part j, Di, k — output
specification for part k.
Output file format
Output the maximum possible overall performance, then M —
number of connections that must be made, then M descriptions
of the connections. Each connection between machines A and B
must be described by three positive numbers ABW,
where W is the number of computers delivered from A
to B per hour.
