A: Cake



A rectangular cake is transported via a truck to a restaurant. On the way to the destination, the truck hits a pothole, which shatters the cake in NN perfectly rectangular pieces of width wiw_i and length lil_i, for 1iN1 \le i \le N.

At the destination, the damage is assessed, and the customer decides to order a replacement cake of the same dimensions. Unfortunately, the original order form was incompletely filled and only the width WW of the cake is known. The restaurant asks for your help to find out the length LL of the cake.

Fortunately, all pieces of the cake have been kept.

Input🔗

The input consists of the following integers:

  • on the first line, the width WW of the cake;
  • on the second line, the number NN of shattered pieces;
  • on each of the next NN lines, the width wiw_i and length lil_i of each piece.

1N50000001 \le N \le 5000000 1W,L100001 \le W, L \le 10000 1wi,li100001 \le w_i, l_i \le 10000

Output🔗

The output should be the integer LL.

Sample Input🔗

4
7
2 3
1 4
1 2
1 2
2 2
2 2
2 1
Plain text

Sample Output🔗

6
Plain text

B: Hunter



Spike is a bounty hunter and he is currently tracking a criminal! To investigate he uses his spaceship, the Swordfish II, and travels to NN different places on 2D Euclidean space before returning to his crew at the starting location with all the information he has gathered. The starting location is the leftmost place (with the lowest xx-coordinate) and Spike wants to travel to every other place before returning. However space fuel costs a lot of Woolongs and Spike would rather spend his money on special beef with bell peppers. Therefore he wants to travel the minimum possible distance.

On top of that he is being chased by the Red Dragon crime syndicate. To make sure they don’t catch him he can only visit places in increasing order of their xx-coordinate until he reaches the rightmost place (with the largest xx-coordinate), then he can turn around and visit places in decreasing order of their xx-coordinate until he reaches his starting location again.

Input🔗

The input starts with an integer TT (1T1001 \le T \le 100) specifying the number of test cases that follow.

Each test case consists of an integer NN (2N5122 \le N \le 512) specifying the number of places in the tour. The coordinates of these places are given as integers in the next NN lines, xx-coordinate first, yy-coordinate second (0x,y50000 \le x, y \le 5000). The places are given in ascending order of the xx-coordinate.

Every place has a unique xx-coordinate.

Output🔗

For each test case, output on a single line the minimum travel distance needed to complete the tour. Your output should have an absolute or relative error of at most 10210^{-2}.

Sample Input🔗

2
5
0 1
1 2
2 0
3 2
4 1
3
100 1
200 1
300 1
Plain text

Sample Output🔗

9.300563079746
400
Plain text

C: Jewelry



To guard the art jewelry exhibition at night, the security agency has decided to use a new laser beam system, consisting of sender-receiver pairs. Each pair generates a strip of light of one unit width and guards all objects located inside the strip. Your task is to help the agency and to compute for each exhibition room the minimum number of sender-receiver pairs which are sufficient to protect all exhibits inside the room.

Any room has a rectangle shape, so we describe it as an [0,N]×[0,M][0, N] × [0, M] rectangle in the plane. The objects we need to guard are represented as points inside that rectangle. Each sender is mounted on a wall and the corresponding receiver on the opposite wall in such a way that the generated strip is a rectangle of unit width and length either NN or MM. Since the new laser beam system is still not perfect, each sender-receiver pair can only be mounted to generate strips the corners of which have integer coordinates. An additional drawback is that the sender-receiver pairs can protect only items inside the strips, but not those lying on their borders. Thus, the security agency arranged the exhibits in such a way that both coordinates of any point representing an exhibit are non-integers.

The figure below (left) illustrates eight items arranged in [0,4]×[0,4][0, 4] × [0, 4] (the second sample input). In the room, up to eight sender-receiver pairs can be mounted. The figure to the right shows an area protected by three sender-receiver pairs.

Jewelry Exhibition

Input🔗

The input starts with the number of exhibition rooms R10R \le 10. Then the descriptions of the RR rooms follow. A single description starts with a single line, containing three integers: 0<N1000 < N \le 100, 0<M1000 < M \le 100, specifying the size of the current room and 0<K1040 < K \le 104, for the number of exhibits.

Next KK lines follow, each of which consists of two real numbers x,yx, y describing the exhibit coordinates. You can assume that 0<x<N0 < x < N, 0<y<M0 < y < M and that xx and yy are non-integer.

Output🔗

For every room output one line containing one integer, that is the minimum number of sender-receiver pairs sufficient to protect all exhibits inside the room.

Sample Input🔗

2
1 5 3
0.2 1.5
0.3 4.8
0.4 3.5
4 4 8
0.7 0.5
1.7 0.5
2.8 1.5
3.7 0.5
2.2 3.6
2.7 2.7
1.2 2.2
1.2 2.7
Plain text

Sample Output🔗

1
3
Plain text

D: Dice



Gunnar and Emma play a lot of board games at home, so they own many dice that are not normal 6-sided dice. For example they own a die that has 1010 sides with numbers 47,48,...,5647, 48, ..., 56 on it.

There has been a big storm in Stockholm, so Gunnar and Emma have been stuck at home without electricity for a couple of hours. They have finished playing all the games they have, so they came up with a new one.

Each player has 22 dice which he or she rolls. The player with a bigger sum wins. If both sums are the same, the game ends in a tie.

Given the description of Gunnar’s and Emma’s dice, which player has higher chances of winning?

All of their dice have the following property: each die contains numbers a,a+1,...,ba, a + 1, ..., b, where aa and bb are the lowest and highest numbers respectively on the die. Each number appears exactly on one side, so the die has ba+1b - a + 1 sides.

Input🔗

The first line contains four integers a1,b1,a2,b2a_1, b_1, a_2, b_2 that describe Gunnar’s dice. Dice number ii contains numbers ai,ai+1,...,bia_i, a_i + 1, ..., b_i on its sides. You may assume that 1aibi1001 \le ai \le bi \le 100 . You can further assume that each die has at least four sides, so ai+3bia_i + 3 \le b_i .

The second line contains the description of Emma’s dice in the same format.

Output🔗

Output the name of the player that has higher probability of winning. Output "Tie" if both players have same probability of winning.

Sample Input 1🔗

1 4 1 4
1 6 1 6
Plain text

Sample Output 1🔗

Emma
Plain text

Sample Input 2🔗

1 8 1 8
1 10 2 5
Plain text

Sample Output 2🔗

Tie
Plain text

Sample Input 3🔗

2 5 2 7
1 5 2 5
Plain text

Sample Output 3🔗

Gunnar
Plain text

E: Road



Per is repairing roads. The job is concentrated on roads with one lane in each direction. Thus, when Per closes down the lane in one direction, all traffic has to go through the other lane. This is done by allowing only one direction of travel at any time. Per is often assigned the task of directing the traffic through this lane.

No car drives before being given a “go” signal from Per, and all the cars drive through the maintained segment at the same speed. Because there is only one lane, cars in one direction must leave the segment before cars in the other direction can enter. For safety reasons, cars driving in the same direction have to keep a distance of at least 33 seconds between each other.

For example, if cars AA and BB arrive at the west endpoint at second 1010, Per can let them go at earliest second 1010 and 1313 in the order they arrived. If it, in this example, takes 88 seconds to pass and car CC arrives at the east endpoint at second 1717, then car CC has to wait 44 seconds until Per lets it go at second 2121.

There is a problem of drivers getting irritated with Per; they think they have to stop for too long. Per has been logging how long they can bear to wait before they get irritated. One day, to be able to evaluate his work, Per noted down when the cars arrived at the two endpoints of the segment. Per’s question is the following: what is the least number of drivers that can be irritated? We assume that a driver gets irritated if the time between the moment he arrives at the maintained segment and the moment he is actually given the “go” exceeds his irritation time limit.

Input🔗

The first line of the input contains two integers tt and nn (4t180,1n2504 \le t \le 180, 1 \le n \le 250), where tt is the time in seconds needed for a car to pass the segment under maintenance, and nn is the total number of cars arriving at the segment. The following nn lines describe the cars. The ii-th line contains the description of the ii-th car in the following format:

  • one character dd, being WW for cars arriving at the west endpoint of the segment, and EE for the ones that arrive at the east endpoint;
  • two integers aa and rr (0a<86400,0r36000 \le a < 86 400, 0 \le r \le 3 600), where aa denotes the arrival time in seconds after midnight, and rr denotes the time in seconds it takes for the driver to get irritated.

The cars arrive in the order specified in the input and they cannot overtake each other. In particular, a car whose driver is already irritated has to stay in the queue until eventually receiving the “go” and passing the maintained segment.

Output🔗

Output one line with the least possible number of irritated drivers.

Sample Input 1🔗

8 3
W 10 0
W 10 3
E 17 4
Plain text

Sample Output 1🔗

0
Plain text

Sample Input 2🔗

100 5
W 0 200
W 5 201
E 95 1111
E 95 1
E 95 11
Plain text

Sample Output 2🔗

1
Plain text

F: Trays



André Claude Marzipan is the head chef at the French restaurant Le Chaud Chien. He owns a vast number of baking trays, which come in two sizes: 11 foot by 11 foot, and 11 foot by 22 feet. He stores them along 33-foot deep shelves of various lengths. For example, on a shelf that is 55 feet long, he might store baking trays in either of the two ways shown below:

Figure G.1

Of course, there are many more than just these two ways, and in his off hours André often wonders how many different ways he can place trays on a given shelf. André is a bit of un maniaque du rangement (neat freak), so he insists that the trays are always aligned along the two axes defined by the shelf edges, that the edges of the trays are always 11 foot multiples away from any edge, and that no portion of a tray extends beyond the shelf. The matter is complicated by the fact that often there are locations on the shelf where he does not want to put any baking trays, due to leaks above the shelf, dents in the shelf’s surface, etc. Since André is more adept at cuisine than counting, he needs a little help.

Input🔗

The input consists of two lines: the first line will contain two integers m,nm, n, where 1m241 \le m \le 24 indicates the length of the shelf (which is always 33-feet deep) and nn indicates the number of bad locations on the shelf. The next line will contain nn coordinate pairs xyx y indicating the locations where trays should not be placed, where 0<x<m0 < x < m and 0<y<30 < y < 3. No location will have integer coordinates and coordinates are specified to the nearest hundredth. If n=0n = 0, this second line will be blank.

Output🔗

Output the number of ways that trays could be placed on the shelf.

Sample Input 1🔗

4 0
Plain text

Sample Output 1🔗

823
Plain text

Sample Input 2🔗

4 2
0.29 2.44 2.73 1.8
Plain text

Sample Output 2🔗

149
Plain text

G: Hat



In the wizarding world of security, there are two kinds of researcher: the idealist arranging hat and the mercenary deranging hat.

As we learned last year, an arranging hat carefully sorts out any list of letters given to it into ascending order. However, a deranging hat performs the exact opposite function: putting a sorted string of letters back into its original order.

The tool of choice for today’s discerning headwear is a sorting network: a sequence of instructions represented by a list of pairs of numbers AiA_i and BiB_i, meaning that if at step ii the AA-th item in the string is not already smaller than the BB-th item, they should be swapped immediately.

Given a specific word WW, output a sorting network that the deranging hat can use to form the word from its original sorted letters.

Input🔗

One line containing one string of lowercase Latin letters (‘a’-‘z’), SS, containing at most 10001000 characters.

Output🔗

Output at most 10000 lines, each containing two integers AiA_i and BiB_i (1Ai,BiS1 \le A_i, B_i \le |S| ) giving the ii-th operation to perform.

Sample Input 1🔗

bab
Plain text

Sample Output 1🔗

2 1
Plain text

Sample Input 2🔗

dude
Plain text

Sample Output 2🔗

4 3
3 2
Plain text

H: Hiker



Times are hard at the Association of Chartered Mountaineers.

The growth of their pedestrian sport has slowed to a crawl. Instead of taking up mountaineering, younger potentials are gravitating towards warmer indoor activities such as snooker, musical chairs, and programming contests.

To win over more members, the Association is going to organise a series of new time trial orienteering events next year. The route for the first race will be a short run through the Cairngorms, with every contestant following the same route designated by marker points but all starting at different times.

Because hiking can be dangerous, and many of the contestants will be inexperienced, the competition committee drew up two rules:

  • Every contestant needs to keep a specific maximum distance away from the next-closest contestant, in either direction, at all times.
  • Every contestant should be given personal space. If a contestant needs a personal space of DD metres, nobody else should ever come closer than that at any time. This distance varies according to level of experience.

The hardest part of orienteering is the pathfinding; once a contestant knows where to go next, they can get there in almost no time (for the purposes of this problem, instantaneously).

In fact, while the inaugural ACM "Icy-Cold Peak Contest" is already underway, pathfinding is turning out to be a problem: nobody is sure whether they can move next without breaking any of the conditions on minimum and maximum distance.

Help the runners reach the end of their route by computing a list of who should move to the next goal point, and at what time.

Input🔗

  • One line containing an integer BB (1B500001 \le B \le 50000), the maximum separation allowed between any two runners.
  • One line containing an integer PP (3P10003 \le P \le 1000), the number of marker points along the route.
  • One line containing PP unique space-separated integers d1...dPd_1 ... d_P (0di1060 \le d_i \le 10^6), with did_i being the distance of the ii-th vertex from the starting point d1=0d_1 = 0.
  • One line containing an integer KK (2K10002 \le K \le 1000), the number of hikers on the landscape.
  • KK further lines, each containing the pair of space-separated integers AiA_i and ViV_i (1Ai106;1ViP1 \le A_i \le 10^6; 1 \le V_i \le P), the minimum separation distance and current marker position respectively for the ii-th person.

The initial configuration of hikers will be legal according to the minimum and maximum distance rules. The hikers will be given in increasing order of distance from the start.

Output🔗

If it is not possible to get everyone to the end of the route without breaking minimum or maximum distance requirements, output impossible.

Otherwise, output a space-separated list of moves on one line, each describing which person should make the next move.

If anyone falls off the landscape, your answer will not be judged as correct. However, once someone has arrived at the end of their journey they cease to count towards any rule violations.

Sample Input 1🔗

3
8
0 1 2 3 4 5 6 7
2
2 1
2 4
Plain text

Sample Output 1🔗

1 2 1 2 1 2 1 2 1 1 1
Plain text

Sample Input 2🔗

10
10
0 1 3 6 10 14 17 19 20 21
3
3 1
1 3
3 5
Plain text

Sample Output 2🔗

2 1 1 3 2 1 3 2 1 3 3 2 1 3 2 2 1 2 1 1 1
Plain text

Sample Input 3🔗

5
5
0 2 5 9 14
2
2 1
2 2
Plain text

Sample Output 3🔗

impossible
Plain text

I: Settlements



Following tremendous advances in space flight control software and equally impressive innovations in reality TV crowdfunding, humans have successfully settled a number of planets, moons, asteroids, and various other kinds of funny-shaped rocks across our solar system.

To celebrate, the Galactic President has elected to create a new holiday called "Solar Night". At the crux of the event, she decrees, every settlement will simultaneously launch colourful fireworks into the darkness of night.

Night, like most things, is a difficult problem in space. Every spacebound object has its own day length and period of rotation. Thankfully all of the settlements did, at least, start their clocks at the same moment. Settlements may have started in daylight or darkness and so it is possible that the first recorded sunrise can be either before or after the first hour of sunset.

By convention, the President’s term lasts for exactly 18251825 days as measured by the planet with the longest period of rotation. The celebration needs to happen within that time or it will not serve its intended purpose.

Determine how many hours must pass for us to find a suitable time to celebrate Solar Night.

Input🔗

  • One line containing the integer NN (1N201 \le N \le 20), the number of settlements.
  • NN lines, each containing three integers:
    • HH (2H1002 \le H \le 100), the number of hours in this settlement’s solar day.
    • RR and TT (0R,TH1,RT0 \le R, T \le H - 1, R \neq T), the hours of sunrise and sunset respectively.

At sunrise and sunset, a settlement is in darkness. At times strictly in between sunrise and sunset, a settlment is in daylight.

Output🔗

Output the number of hours that must pass from when the settlement clocks began until each settlement is in darkness. If no suitable time occurs in the first 18251825 days, output impossible.

Sample Input 1🔗

2
24 7 19
24 18 6
Plain text

Sample Output 1🔗

6
Plain text

Sample Input 2🔗

3
10 8 2
15 5 10
20 15 10
Plain text

Sample Output 2🔗

12
Plain text

Sample Input 3🔗

2
6 4 2
12 7 5
Plain text

Sample Output 3🔗

impossible
Plain text

Sample Input 4🔗

2
10 5 6
10 6 5
Plain text

Sample Output 4🔗

5
Plain text

J: Ceremony



For the grand opening of the algorithmic games in NlogNsglow, a row of tower blocks is set to be demolished in a grand demonstration of renewal. Originally the plan was to accomplish this with controlled explosions, one for each tower block, but time constraints now require a hastier solution.

To help you remove the blocks more rapidly you have been given the use of a Universal Kinetic / Incandescent Energy Particle Cannon (UKIEPC). On a single charge, this cutting-edge contraption can remove either all of the floors in a single tower block, or all the xx-th floors in all the blocks simultaneously, for user’s choice of the floor number xx. In the latter case, the blocks that are less than xx floors high are left untouched, while for blocks having more than xx floors, all the floors above the removed xx-th one fall down by one level.

Given the number of floors of all towers, output the minimum number of charges needed to eliminate all floors of all blocks.

Input🔗

The first line of input contains the number of blocks nn, where 2n1000002 \le n \le 100 000. The second line contains nn consecutive block heights hih_i for i=1,2,...,ni = 1, 2, ..., n, where 1hi10000001 \le h_i \le 1 000 000.

Output🔗

Output one line containing one integer: the minimum number of charges needed to tear down all the blocks.

Sample Input 1🔗

6
2 1 8 8 2 3
Plain text

Sample Output 1🔗

5
Plain text

Sample Input 2🔗

5
1 1 1 1 10
Plain text

Sample Output 2🔗

2
Plain text