Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
You are given two strings of small Latin letters, S and T. Some letters of string S may be replaced by letters of T according to the following rules:
You program must modify string S according to the rules above to get lexicographically smallest string.
First line of input file contains string S. Second line of input file contains string T.
Output file must contain optimally modified string S.
0 < S, T ≤ 10^{5}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  I. Tuphanov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Young marine biologist Masha spent her summer in Primorye, diving and taking notes of what she saw on the seafloor. Later she found her records for one of the bays where she has been. These records were:
Help Masha to figure the minimum possible percentage of the seafloor inhabited by all three species simultaneously.
In the first example, shellfish live everywhere. Starfish and sea urchins each take 3/4 of the seafloor, which means that at least half of the seafloor is inhabited by shellfish, starfish and sea urchins simultaneously.
In the second example, there are areas where 2 out of 3 species live. But it's possible that there are no areas where all 3 species live.
Input file contains integers A, B and C.
Output file must contain a single integer from 0 to 100 — the answer, in percents.
0 ≤ A, B, C ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Vasya invented a device working similarly to finite automaton. Device accepts as input a cyclic string of characters, and has a pointer to one of characters. On each step the device reads the character at the current pointer position and executes an action according to a given table.
Action in the table is represented by four values S C Q H, where
The device will stop if:
Your program must, given input sting and a table, determine starting position and state which will cause device to execute maximum possible number of steps until stopping.
First line of input file contains input string T, consisting of small Latin letters and digits. Second line contains integer M — number of commands. Following M lines contain commands in the format described above.
Output file must contain two integers — numbers of staring position and starting state. Positions are numbered from zero. If there are several optimal solutions, output any of them.
Action table contains no more than one action for each pair (position, state).
0 ≤ S, Q < 1000,
0 ≤ H ≤ T,
0 < T ≤ 500, 0 < M ≤ 36 ⋅ 1000
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov, I. Tuphanov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
One famous university has failed to create a proper schedule of classes before the beginning of the academic year. Teachers decided to fix this. They created a list of classes that teachers have to give to some of the groups of students according to the academic plan. However, coming up with an actual schedule is difficult and feels like something that a computer can do. They came to computer science department and asked you to write a program that will generate the best schedule.
There are N teachers numbered from 1 to N. There are M groups of students numbered from 1 to M. Teachers created a list of K pairs (t, g), meaning that teacher t needs to give a class to a group g. Some pairs may repeat in the list — this is because there might be several classes per day for the same subject (e.g., Calculus).
For simplicity, suppose that all these classes should happen in one day. The length of each class is the same and equal to the length of academic "pair" — a time slot. Of course, a teacher can not give two classes at the same time, as well as a group can not attend two classes simultaneously.
The best schedule is the one that fits into the minimum number of time slots. In other words, the schedule should ensure that the last teacher and the last group of students will leave the university as soon as possible.
Input file contains integers N, M, K, followed by K pairs of integers t_{i} and g_{i}.
Output file must start with an integer — the number of time slots in the schedule, followed by time slots description. Each description starts with l_{i} — the number of classes happening in this time slot, followed by (t, g) pairs from the original list.
The output must list all pairs from the input (∑l_{i} = K).
1 ≤ N, M ≤ 100; 1 ≤ K ≤ 1000
1 ≤ t_{i} ≤ N; 1 ≤ g_{i} ≤ M
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin, M. Sporyshev  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Young programmer Vasya tinkered with robots, and decided to create a new startup Easy Patrol with the goal of producing robot guardian to replace human guards.
As a first step, he considered a single wall of N meters in length and two patrolling robots moving back and forth along it.
First robot starts patrolling at the point located x meters from the left edge of the wall, moving to the right. Second robot starts patrolling at the point located y meters from the left edge of the wall, moving to the left.
Each second, events happen in the following order:
Your program must determine maximum possible distance between two robots.
Input file contains integers N, x, y.
Output file must contain a single integer — maximum distance between robots in meters.
4 ≤ N ≤ 10^{6}
0 ≤ x, y ≤ N
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  M. Sporyshev, A. Klenin, A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
String T consists of small Latin letters.
String P consists of small Latin letters and star symbols '*
'.
Your program must find all positions in T where some cyclic shift of P occurs (that is, indexes s, for which there exists d such that P_{(i + d) mod P} = T_{s + i}, i = 0, P − 1).
Additionally, star in P may correspond to an arbitrary single character in T.
First line of input file contains string T. Second line of input file contains string P.
Output file must contain an integer K — number of positions, followed by K integers a_{i} — position indexes in ascending order. Positions are indexed from zero.
1 ≤ T ≤ 10^{5}
1 ≤ P ≤ 400
P ≤ T
Number of star symbols in P doesn't exceed 3.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Consider a set of n points on a plane, described by their coordinates: M = {(x_{i}, y_{i}): i = 0, 1, …, n − 1}.
Your program must, given two points A and B, find a point C from set M, such that triangle {A, B, C} contains maximum possible number of points from M. Points both inside and on the edges of the triangle are counted.
Input file contains integer n, followed by n pairs of integers — point coordinates (x_{i}, y_{i}). Next, four integers follow — coordinates of points A and B.
Output file must contain a single integer — index of point C. Indexes start from zero. If there are several solutions, output any of them.
Points A and B are different.
−10^{4} ≤ (x_{i}, y_{i}) ≤ 10^{4}, 0 < n ≤ 10^{5}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Young programmer Vasya lives in a city where streets can be represented by a tree. Each vertex of a tree correspond to an intersection, each edge — to a street. So number of streets in the city is 1 less than a number of intersections. It is possible to get from from each intersection to every other one by streets.
There are two kinds of streets — residential and office ones.
City administration wants to create a looping road, represented by a cycle of streets. To minimize spending, only a single road of either kind must be built, creating a cycle. To satisfy zoning regulations, cycle must consist of at least 4 streets and number of residential streets in the cycle must be equal to the number of office streets.
Young programmer Vasya is preparing a presentation for city mayor and wants to add a slide with the total number of ways to add a street to the city road system, while satisfying all requirements. Your program must calculate that number.
Input file contains integer N — number of intersections in the city, followed by N − 1 triplets of integers u, v, c — numbers of intersections connected by street (u, v) and the kind of the street. c = 0 — residential street, c = 1 — office street.
Output file must contain a single integer — number of ways.
3 ≤ N ≤ 3000
0 ≤ u, v < N
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Usmanov  Time limit:  1 sec  
Input / output:  interactive  Memory limit:  256 Mb 
This is an interactive problem.
Jury has chosen a secret integer X consisting of exactly N bits. It is known that the number contains K bits '1' and N − K bits '0'. Your program can make queries of the form "+ Y", which causes current value of X to be increased by integer Y. Bits higher than Nth are truncated, so actual operation is X = (X + Y) mod 2^{N}.
Jury's program answers every query with number of '1' bits in the current value of X. Your program must determine current value of X by making no more than ⌊ N2⌋ queries.
First line of input contains two integers N and K — total number of bits in the value and number of '1' bits in the starting value.
To make a query, your program must output "+ Y
",
where Y — integer to be added to X.
For every query jury's program will reply with a single integer —
number of '1' bits in the value of X after executing the request.
When your program determines current value of X, it must output "! X
"
and stop.
If your program will make incorrect query, it will receive "Presentation error" verdict. If your program will exceed allowed number of queries, it will receive "Wrong answer" verdict.
Every query and final output must be a single line ending with single endofline (\n
).
Output buffers must be flushed after every line:
Language  C++  Pascal  Java  Python 
Code  cout.flush() 
flush(output) 
System.out.flush() 
stdout.flush() 
1 ≤ N ≤ 60
0 ≤ K ≤ N
0 ≤ X, Y < 2^{N}
In the first sample jury has chosen number 13 (1101 in binary). After the first query the value is (13 + 9) mod 16 = 6 (0110_{2}). After the second query the value is (6 + 9) mod 16 = 15 (1111_{2}).
No.  Standard input  Standard output 

1 


2 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Rectangular jigsaw puzzle consists of two pieces.
Each piece is a 4connected set of square cells,
each cell represented by character 'X
' or 'O
'.
Your program must determine whether it is possible to separate puzzle pieces by moving either of them in vertical or horizontal direction.
In the first sample it is possible to separate pieces
by moving 'X
' piece up and/or 'O
' piece down.
First line of input contains two integers W H. Following H lines contain W characters each — puzzle representation.
Output must contain a single string YES
or NO
.
1 ≤ W, H ≤ 100. Each piece contains at least one cell.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 

