Graph Reconstruction
I have an undirected graph consisting of n nodes, numbered 1 through n. Each node has at most two incident edges. For each pair of nodes, there is […]
ACM
More Reclamation
In a far away land, there are two cities near a river. One day, the cities decide that they have too little space and would […]
Palindrome
Given a string s, determine if it contains any palindrome of length exactly 100 as a subsequence. If it has any, print any one of them. If it doesn’t […]
Rectangles and Square
You are given n rectangles, labeled 1 through n. The corners of rectangles have integer coordinates and their edges are parallel to the Ox and Oy axes. The rectangles may touch each […]
Counting Skyscrapers
A number of skyscrapers have been built in a line. The number of skyscrapers was chosen uniformly at random between 2 and 314! (314 factorial, a very large number). […]
Book of Evil
Paladin Manao caught the trail of the ancient Book of Evil in a swampy area. This area contains n settlements numbered from 1 to n. Moving through the […]
Divisor Tree
A divisor tree is a rooted tree that meets the following conditions: Each vertex of the tree contains a positive integer number. The numbers written in the […]
Rational Resistance
Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value. […]
Alternating Current
Mad scientist Mike has just finished constructing a new device to search for extraterrestrial intelligence! He was in such a hurry to launch it for […]
Water Tree
Mad scientist Mike has constructed a rooted tree, which consists of n vertices. Each vertex is a reservoir which can be either empty or filled with water. […]
Pumping Stations
Mad scientist Mike has applied for a job. His task is to manage a system of water pumping stations. The system consists of n pumping stations, which […]
Xenia and Hamming
Xenia is an amateur programmer. Today on the IT lesson she learned about the Hamming distance. The Hamming distance between two strings s = s 1 s 2… s n and t = t 1 t 2… t n of equal length n is value . […]
Knight Tournament
Hooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom […]
Compartments
A team of students from the city S is sent to the All-Berland Olympiad in Informatics. Traditionally, they go on the train. All students have […]
Bags and Coins
When you were a child you must have been told a puzzle of bags and coins. Anyway, here’s one of its versions: A horse has […]
