It is the year of 2016 and Mars is still not colonized. A daring group of immortal, rich explorers based in São Carlos decided that it is about time to do something about it, so they founded a space exploration company called GEMA - Go Explore Mars Already!
Fast forward to 2017. The first mission of GEMA has finally landed on Mars, but it seems like the rocket fell in the middle of some ancient ruins that form a giant maze resembling a snail. The maze is composed of N circular sectors all centered at the crash site of the rocket.
The circular sectors of the maze all have a railway running through their middle, and some portions of the walls are open, making it possible to leave to the next sector. The rails connecting sectors are straight, radial lines through the opening, connecting the rails of the two sectors. There is always a straight line connecting the crash site to the first sector railway through the openings. The only safe way to travel in this maze is by using these rails.
The crew of the GEMA mission wants to leave the maze as soon as possible. Luckily, they are in possession of small carts that fit the railway. Help them find the path with the minimum length to leave the maze. You are out of the maze as soon as you cross the boundary of the outermost wall.
The above figure illustrates the first sample test case. Dashed lines represent the railways that run through the middle of the sectors, whose boundaries are represented by solid circles. The best solution in this case is to go from points A, B, C, D and then E, going through the sectors railways through points X, Y, W and Z, as indicated by the green line.
The input begins with an integer N (1 ≤ N ≤ 105), the number of circular sectors of the Snail Maze. The next line has N integers r, the radius of each of the sectors (1 ≤ r ≤ 109). The next line contains an integer Q (N ≤ Q ≤ 105), the number of openings. The next Q lines contains an integer and a real number each. The first integer, ri (1 ≤ ri ≤ 109) gives the radius of a wall (that radius will be one of the N numbers given in the second line), and the real number d, gives the angle, in radians, where the opening is located (0 ≤ d ≤ 2π). The angle is measured in clockwise direction with respect to west (the positive x-axis).
It is guaranteed that there is a path to leave the maze, i.e., every wall has at least one opening. There will not be two openings closer than 10 - 4 radians.
Output the length of the shortest path to leave the maze. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
3
4 10 6
4
4 1.0472
4 1.5707
6 4.7123
10 4.1857
27.30323
Life on a different planet is hard. It is usually all about science, research and cold nights and days. It is no different on Mars.
To entertain people, GEMA brought with the mission a group of talented musicians to write ballads about the new and exciting world. They were instructed to write a very long and optimistic song called Martian Sunrise and play it all day around the research and living facilities.
No musician could write, alone, a song with thousands of notes, so they divided their task. GEMA was on a tight budget, and ended up hiring musicians that can only write and play songs in their own favourite single key signature. A key signature is a set (out of 16 possible sets) of notes that can be used. In the end, the ballad was composed of different parts in various key signatures.
Now that cash is flowing in, the high commanders have decided to bring new, more talented musicians that can play up to two different key signatures to play the Mars Jam. It was decided that the musicians will take turns playing, and no musician will play again after having finished their part. GEMA has all the musicians on Earth at their disposal, since the mission is very highly regarded. This means that for any pair of key signatures, they can find infinitely many musicians that can play it.
Even with endless cash, it is good to be optimal. It is up to you to figure out the minimum number of musicians necessary to play the whole song.
The input will begin with an integer M, the number of existing key signatures (1 ≤ M ≤ 16). The next M lines of the input will be composed of a set of 7 words each, denoting the notes used in this signature. The words representing notes will have a maximum of two characters each, and will be in the format [A-G][b#]?, that is, start with an uppercase character between 'A' and 'G' and optionally have a '#' or a 'b', for a sharp or flat.
The next line of the input contains an integer N (1 ≤ N ≤ 104). The following line contains the N notes of the original Martian Sunrise, separated by a space. Every note of the song is present in at least one of the M key signatures.
Please note that, although in musical terms C# equals Db, in this problem a musician that can play C# cannot necessarily play Db.
Output the minimum number of musicians necessary to play the Martian Sunrise.
10
C# D# E# F# G# A# B#
Cb Db Eb F Gb Ab Bb
C# D# E F# G# A B
C D E F G A B
C D E F# G A B
C D Eb F G A Bb
C# D E F# G# A B
C D E F G A Bb
C Db Eb F G Ab Bb
C# D# E# F# G# A# B
3
F# Bb B#
1
8
Cb Db Eb F Gb Ab Bb
C# D# E F# G# A# B
C# D# E# F# G# A# B
C D Eb F G Ab Bb
C# D# E# F# G# A# B#
C Db Eb F Gb Ab Bb
C D E F# G A B
C# D E F# G A B
6
C F# G# D B# Db
2
It is nighttime in the Earth Colony on Mars and everyone is getting ready to sleep. It is common to sleep in pairs, so that if anything were to happen during the night people could aid each other.
To decide who is a suitable candidate to sleep with whom, the leaders of GEMA asked everyone to answer a questionnaire about attributes they desire their partner to have from a list of M possible items.
To choose the pairs, GEMA uses the Jaccard index between the desired attributes of both persons. The Jaccard index for two sets A and B is defined as 
, that is, the size of the intersection between A and B divided by the size of their union. They allow a pair to be formed if the Jaccard index of the two attribute sets for the pair is at least K.
Thanks to GEMA, there are too many people living on Mars these days. Help the high commanders decide how many allowed pairs there are out of the N people living there.
The input begins with two integers, N and M (1 ≤ N ≤ 105, 1 ≤ M ≤ 10), the number of people on Mars and the number of possible attributes on the questionnaire.
Then follow N lines, each beginning with an integer Q (1 ≤ Q ≤ M), the number of desired attributes on the list of the i-th person. Then follow Q integers q (1 ≤ q ≤ M), encoding these attributes. There numbers are all different.
The last line of input contains a real number K (0 ≤ K ≤ 1), the minimum required Jaccard index for a pair.
Output the number of pairs that are allowed.
2 5
2 1 3
5 3 1 5 4 2
0.66489
0
3 1
1 1
1 1
1 1
0.85809
3
"Sit back, children, for I will tell you about the first love story between Mars and Earth."
Everyone knows the story of Gabriela, the lady that managed to send thousands of love messages through the first mission's main science channel to her beloved back on Mars. What few people know is that, although she was an artist, she used a very unique algorithm to do that.
Back in the first days of GEMA, communicating between Mars and Earth was kept only for scientific research, for budget reasons. The mission was using a very simple way of verifying if a message was related to science. They asked for a number, K, to be attached to the message. This number was the answer to an algorithmic puzzle. The puzzle went like this, as written in the missions's log:
The number K should be calculated as follows.
First, two strings S and T must be built.
To build S, consider a sequence of strings composed by the first M suffixes of the message after having ordered all of them lexicographically. Then, choose a subsequence of this sequence, S will be the concatenation of the strings in the chosen subsequence.
To build T, consider a sequence of strings composed by the first M suffixes of the message, after having them sorted by length in descending order. Then, choose a subsequence of this sequence, T will be the concatenation of the strings in the chosen subsequence.
The number K is the length of the longest S and T that can be built, such that S = T.
Did this guarantee that only science people would get their message through? Probably not, as history shows, but it was enough for higher management. Your job here is to be as awesome as Gabriela was in the good old days and write an algorithm to calculate K for a given message.
The input contains two lines, the first line contains two integers N, M (1 ≤ N ≤ 5 × 103, 1 ≤ M ≤ min{N, 100}) which are the length of the message and the number of suffixes to consider, when building S and T (as explained above). The second line contains the message A, containing only lower case english letters.
Print K.
3 2
aaa
3
6 5
ooouch
15
A subsequence is a sequence with some elements removed without changing their order.
In the first sample, the message is AAA.
S : A | AA
T : AAA
In previous Mars missions the surface has been explored and mapped. A number of spots have been found where GEMA wants to collect interesting rock samples. GEMA is a bit on a tight budget, but luckily they recovered the old NASA Mars rover, and were able to repurpose it for this.
The rover is quite old and has very limited power. On the hilly Mars landscape it is limited in how much weight it can carry along, depending on how steep a slope it has to take uphill. You are tasked to decide which rock samples to collect in one single haul to maximize the total weight of rock samples.
To simplify matters, only a 1D section of the Mars surface (along the x coordinate) is given with height (y coordinate) along the that section. The base where the rover starts and has to return is at x = 0. The rover can only climb uphill if the slope s > 0 satisfies s ≤ P / M where P is the power of the rover, and M is its total weight, including any rocks already collected.
The first line of the input contains four integers: N (2 ≤ N ≤ 100), the number of points describing the landscape, R (1 ≤ R ≤ 100), the number of rock samples, m (1 ≤ m ≤ 1 000), the weight of the rover, and P (1 ≤ P ≤ 500), the power of the rover. The next N lines each contain two integers xi, yi with 0 ≤ xi, yi ≤ 1 000. The sequence of xi is strictly increasing and x1 = 0. The landscape is given by straight lines connecting sequential points (xi, yi). The next R lines each contain two integers Xi, mi with 1 ≤ Xi ≤ xN the x-coordinate of the rock sample and 1 ≤ mi ≤ 105 its weight.
Print a single line containing an integer: the maximum weight of the rock samples that can be collected.
3 2 50 20
0 5
20 5
30 10
4 42
28 10
42
4 3 50 500
0 0
20 100
70 50
100 0
10 10000
21 445
83 10
10445
In the first sample test case the rover cannot reach all of the surface, since the slope from x2 to x3 is too steep. In the second sample the rover can reach the whole surface, but can only climb uphill from x3 to x2 with either one of the rocks with weight 445 or 10.
It is lunch time on Mars! Everyone has got that big smile on their faces, all eager to see what the GEMA restaurant is serving for dessert. Everything is pretty much like Earth, but nobody knows why, GEMA decided to invent new types of utensils. Somehow, the food research group concluded that the usual fork, knife and spoon would not be so adequate on Mars.
There are K types of utensils and if you want to have some food, you must use all K of them (one of each). You like to have lunch with your N friends, and when you are leaving, you want to distribute the utensils among you and all your friends equally (everyone having the same amount of utensils). In addition to that, you want each one of your friends (you included) to carry only one type of utensil (it speeds up the process of leaving the restaurant, and your friends get really mad when it takes more time than usual for them to get back to work).
Given N and K, answer if it is possible for you and your friends to leave the restaurant with everyone carrying the same number of utensils and each one carrying only one type of utensil.
Two integers N and K (0 ≤ N, K ≤ 100 and K > 0). (You and your friends form a group of N + 1 people).
Print "yes" (if it is possible) or "no" without quotes.
1 2
yes
1 3
no
As you may already know, there are a lot of scientists working on Mars. They come from various different fields of studies, all very excited with the exploration. Nevertheless, right now, they decided to go on strike and have not done any work for the past two weeks.
What they've been complaining about for quite a while is that there is only one super computer on the whole planet, so the waiting list is huge and sometimes they have to wait for months in order to use it. As an attempt to calm the scientists a little, GEMA decided to implement a new policy for the waiting list: When a job is added, it is placed on the top of the list. If a job is changed, it is moved to the top of the list as well.
Even though this policy would be considered stupid by most, the scientists decided to try it, but you know, scientists are very devious people (specially GEMA scientists). Quite soon they began to use time traveling machines to go back and forth in time and change other scientists' jobs, making them go to the top of the list, or even removing them from the list. Now your task is to implement something that could process some queries for the waiting list. There are 4 types of queries:
- t 'c' jobid: at time t move the job whose id equals jobid to the top of the list, if there are no jobs with this id, create it and add it to the list.
- t 'r' jobid: at time t remove the job whose id equals jobid from the list
- t 'f': print the id of the first job in the list (top) at time t
- t 's': print the id of the second job in the list at time t
t, jobid are integers and 'c','r','f','s' represent the characters themselves, see the sample test cases for better understanding.
Initially, at time 0, there are no jobs in the list.
A job will be removed from or added to the list only once. However, the creation time can change (take a look at the second example).
To process the i-th query with time ti, you must consider the actions of the queries 1, ..., i - 1 with time t ≤ ti. If there are two queries i and j, with i < j and ti = tj, you must consider the action of the ith query first.
If you are processing a query that requests the removal of a job at time t, you may assume that there has been a query that created this job at a time t' ≤ t. You can also assume that there won't be any queries for this job with time t' > t and that the following queries for this job (if any) will have t' < t.
The input starts with an integer Q(1 ≤ Q ≤ 5000). Then follow Q lines, each with a query following the format described above (1 ≤ t, jobid ≤ 109).
For each query of type 'f' and 's' print the id of the job which satisfies the condition of the query asked, or print - 1 if there is no job which satisfies the condition of the query.
5
3 c 1
10 f
4 r 1
10 f
3 f
1
-1
1
6
5 c 1
6 c 2
3 f
1 c 2
1 c 1
3 s
-1
2
9
5 c 7
2 f
1 c 8
2 f
3 c 7
5 s
10 f
9 r 7
10 f
-1
8
8
7
8
10
1 c 1
1 c 2
1 c 3
1 f
1 c 1
1 c 2
1 s
1 r 3
2 c 1
2 f
3
1
1
In the first sample, the first query adds the job 1 to the list at time 3. Then, it is asked what is the first job in the list at time 10, which is job 1, (notice that to answer this query you just consider the queries you have already processed).
Query 3 says that at time 4, job 1 is removed. The fourth query asks the same as the second query, but now as the past was changed by the third query, there are no jobs at time 10.
The last query, we are at t = 3, which the only job in the list hasn't been removed yet, so the answer is 1.
A lot of people, still living on Earth, dream of one day getting the opportunity to go to Mars and be a GEMA explorer. It's so glamorous and important, everything is so exciting, so different from the regular boring life on Earth.
However, the reality of the regular folk on Mars is not as nearly glamorous as everyone thinks. A day of an average explorer is at least as boring as a day of any Earth-living human. Every week, GEMA assigns tasks to each explorer in the expedition. Most of the times, these tasks are just very long and detailed reports they have to make. The worst part is that, after completing it, you would still have to review reports from your colleagues and correct them if mistakes are found.
One type of report consists of reporting collected data, but, before making the report, one should verify the consistency of the data. This is obviously the most boring part, so it is not surprising that some people prefer to skip it and just write the report without any verification.
To make matters worse, when reviewing a report containing contradictory data, instead of canceling the report, some explorers choose to manipulate the data, changing some numbers, so it would become consistent. This happens because canceled reports are seen as a great incompetence of the whole team who worked on it.
You are a GEMA explorer and you've just received a report. You need to manipulate the data on it, in order to make it seem correct. The data of the report is a bunch of positive or negative numbers. The data is considered consistent if and only if every sub-array of length k has a positive result when all numbers in it are multiplied together.
Formally, if the report is an array A of N positive and/or negative numbers, the report is consistent, if and only if, for all 1 ≤ i ≤ N - k + 1, we have:
Answer what is the least number of changes you have to make in the report so it would become consistent. A change in the report is changing the value of one of its numbers.
The input begins with two integers N and k (1 ≤ k ≤ N ≤ 5 × 105) in a single line. The next line will contain N integers ai ( - 100 ≤ ai ≤ 100 and ai ≠ 0).
One integer, the answer to the task.
3 1
10 -100 33
1
5 5
1 -1 -2 3 4
0
5 3
1 -1 -2 3 4
1
The high commanders of GEMA are very interested in how to boost the productivity of the explorers and tried to do so in many ways. Their latest attempt is to paint the research labs in avant-garde (weird) ways. The research lab can be represented as a matrix with N rows and M columns and N * M tiles.
This time, the high commanders want to paint the tiles of the floor of the lab, but they could not decide on what colors to use. After a long useless discussion, they decided that they will give Q instructions to paint a rectangular area of the floor. As they want their job to be as easy as possible, all the rectangles have constant height H and width W and may overlap. To check if the floor is fully painted, they want to know, after each instruction, how many tiles are still unpainted.
The thing is, GEMA explorers are highly skilled scientists and hate petty jobs, but somebody has got to do them. Margarida was chosen to paint the floor of the main research lab. She is very sly and lazy, so she interpreted the instructions in a way that she would check the left border of the rectangle and if all of its tiles are painted, she wouldn't paint any tile. Also, if there was an unpainted tile in the left border, she would paint all the unpainted tiles reachable from that tile. One tile is reachable from another if it is possible to reach it using only unpainted tiles inside the rectangle.
The first line contains five integers N, M (1 ≤ N, M ≤ 105 and 1 ≤ N * M ≤ 3 * 106), H, W (1 ≤ H ≤ N, 1 ≤ W ≤ M) and Q (1 ≤ Q ≤ 105). Then, Q lines follow. The i-th line contains two integers ri and ci (1 ≤ ri ≤ N - H + 1, 1 ≤ ci ≤ M - W + 1) — the upper left tile of the rectangular area to be painted. The topmost leftmost tile of the research lab is (1, 1).
Output the number of unpainted tiles after each instruction that Margarida has executed.
10 8 4 4 4
3 1
6 4
4 4
4 3
64
49
49
48
10 10 3 2 10
1 3
3 1
1 5
7 1
8 5
6 8
4 3
5 5
6 9
2 9
94
88
82
76
70
64
58
52
52
46
Out of all science labs constructed by the GEMA mission on Mars, the DSL - Dangerous Species Lab is the most dangerous of them all. The laboratory is so dangerous that you have to go through N doors in succession to get to it. Each one of those doors can only be opened by one key di (notice, however, that there may be different doors that can be opened by the same key).
A nameless lazy biologist (we'll call him LB) from GEMA needs to open all those doors first thing in the morning, every day. He has all the keys necessary to open them, but he finds carrying all of them in his pockets too much of a mess.
To be more organized and lose the title of being a lazy biologist, LB purchased K key-chains and is planning to distribute all the keys among them. His plan of distribution is very simple. For each key, randomly choose a key-chain with uniform probability and put this key on it.
When opening the doors, LB will hold one key-chain and will keep the others in his pocket (initially all of them are in his pocket). Whenever he gets to a door that needs a key that is not on the key-chain he is holding, he will swap it with the key-chain that has this key. Getting the first key-chain from his pocket is not considered a swap.
You have to help LB and find what is the expected number of key-chain swaps he will have to do when opening the doors the next morning.
Input begins with N and K (1 ≤ N ≤ 105, 1 ≤ K ≤ N), the number of doors and the number of key-chains. On the next line there are N numbers di (1 ≤ di ≤ 106), the identifier of the key that opens the i-th door.
Output the expected number of swaps. Your answer will be considered correct if the absolute and relative error are less than 10 - 6.
3 3
1 2 3
1.333333333
1 1
2
0.000000000
5 2
1 2 3 2 1
2.000000000
Half a century after the Mars arrival by GEMA, we are finally here. The mission is finally starting to build artificial rivers on mars.
That is possibly the most important event on Mars since the GEMA arrival.
In order to carry on with it, the mission have mapped the surface as 2-dimensional plane, and has identified N points in it that are going to work as reference points to build a river system. There will be a dock constructed in each of these points to help on transportation efforts and collect data for the mission.
The goal of the mission is to connect all the docks with rivers. The lead researcher of the team responsible for that, doctor Maya Waters, has identified the main requirements to build a healthy river system. These are:
- There are N docks. There should be a way to navigate between any two docks only through water;
- The system must have exactly N rivers - no more, no less;
- At most four rivers can meet at any single dock;
- Any river should flow in a straight line between points A and B;
- There should be no river crossings apart from the rivers meeting at docks. Note that a river passing through a dock counts as a crossing.
Help doctor Maya figure out which points to connect to build such river system and finally Make Mars Wet Again!
Input begins with N (3 ≤ N ≤ 103), the number of points. Follows N lines, each with two integers xi, yi ( - 109 ≤ xi, yi ≤ 109), the coordinates of the pivotal points.
Output N lines. In each line, output two integers , a and b - the indexes of the pivotal points that must be connected by a river. Indexing begins in 1. If there are multiple solutions, output any.
If it is an impossible task, output -1.
5
-1 0
2 3
3 2
5 4
6 1
3 2
3 4
5 3
1 5
2 4
3
0 0
1 2
3 6
-1