As is well known by any cultured person, rats are the smartest beings on earth. Followed directly by dolphins.
MaratonIME knows about the species hierarchy and uses this knowledge in it's regard. Usually, when they need some resource, they know it's always useful to have a smart rat available. Unfortunately, rats are not very fond of us, primates, and will only help us if they owe us some favour.
With that in mind, MaratonIME decided to help a little rat called Pablito. Pablito is studying rat's genealogy, to help with cloning and genetic mapping. luckily, the way rats identify themselves make the job much easier.
The rat society is, historically, matriarchal. At first, there were little families, each of which had it's own leading matriarch. At that time, it was decided that rats would organize themselves according to the following rules:
- Each martiarch had an id number greater than one.
- Each of these ids were chosen in a way such that they would have the least amount of divisors possible.
- Each family member had the same id as the matriarch.
- The id of any newborn rat would be the product of its parents id's.
For instance, the offspring of a rat with id 6 and another with id 7 is 42.
Pablito needs to know if two given rats have a common ancestor, but his only tool is the id number of each of the two rats, which is always a positive integer greater than 1 with no more than 16 digits. Can you help him?
Create a program that decides if a pair of rats have some common ancestor.
The input begins with a positive integer t ≤ 105, the number of test cases.
After that, follows t lines, each with two integers ai e bi identifying two rats.
Every rat's id is a positive integer greater than 1 and with no more than 16 digits.
For each test case, print "Sim" if the rats ai and bi share a common ancestor and "Nao" otherwise.
2
2 4
3 5
Sim
Nao
The MaratonIME members like to have fun. As they enjoy having fun so much, they have invented a game named "Cîrokime". The game works as follows:
First, n cups with Cîroc1 are lined up. In front of the i-th cup a number ai is written. It is guaranteed that ai < ai + 1, for all 1 ≤ i < n. Then, the numbers are covered and the game starts.
The player must then find the cup that has a certain number x. It is guaranteed that this cup exists. For this, he has to choose a cup i and drink the beverage. Then, the cup's number ai is revealed and if this number is equal to x the game finished. Otherwise, the player has to choose another cup and so on.
"Cîrokime" is a traditional game among MaratonIME members, they play it every party. At the last party, Sussu had to drink all of the n cups because he found the right cup only at the end. He got sick for drinking so much and had to be carried home3
However, the DESMAME4 is scheduled for May 13 and Sussu wants to restore his dignity. For this, he wants to know, in the worst case, what is the maximum number of cups that he will have to drink if he plays in the optimal way.
The first line has a single integer n, the number of cups. The second line has n integers ai, the values hidden in each cup.
- 1 ≤ n ≤ 105
- For all i, 1 ≤ ai ≤ 109
- For i < n, ai < ai + 1
The output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way.
3
2 5 7
2
8
1 2 3 4 5 6 7 8
4
1: Cîroc is a vodka brand made in France, known by its high sales price in market2
2: Balalaika also works
3: Based on real facts
4: Pre-BIFE5 party
5: University games that IME6 attends
6: Institute of Mathematics and Statistics
You open your eyes, but everything remains dark. The world is dark, and everything shakes. You realize you are locked in, but before desperation takes hold, you hear the door opening and the light invades your sight and blinds you for a few moments.
They help you out, you had been locked inside a trunk. You don't know the masked faces before you, but remember that in the last competitive programming practice they told you that "the beginning is yet to come". "So this is the fabled MaratonUSP's initiation challenge", you had heard rumors of this event, and you feel honored to be chosen.
After walking into and abandoned building, they sit you on an old chair. The first test is to watch a soccer game without any show of excitement. Easy. The second is to install Linux on a notebook in less than 5 minutes. You were prepared, carrying the Arch Linux pendrive as usual, just in case. You face more tests, and manage to pass all of them despite a few difficulties.
Hours go by, the members remove their masks, and each take a coin out of their pocket. "I won! And I even got rich" you think, but realize they place the coins in a table in front of you, divided in two piles. Renzo, MaratonUSP's great boss, takes a chair and sits in front of you. You will play a match of Nim, and if you win you will become an honorary member of MaratonUSP, that is, you win a balloon.
Nim is a game of two players, alternating their turns. Two piles of coins are placed on a table and in each turn you can remove any non zero quantity of coins from one of the piles. The last player to take their turn (leaving both piles empty) wins.
You start the game. So it would not be unfair, it is guaranteed that it is possible for you to win. Write a program than beats Renzo 100% of the time.
In the first line, two integers, x and y, the size of the piles, such that 0 ≤ x, y ≤ 104. It is guaranteed that you can win the game.
In your turn, print two integers, i and x, where i is the number of the pile from which you will remove the coins (
), and x is the number of coins you will remove (x ≥ 1, such that i has at least x coins).
In Renzo's turn, read two integers, in the same format as in your turn.
2 1
1 1
1 1
2 1
Of course we do not do an initiation challenge like this :P
In the example, we have a pile with 2 coins and another with 1. You remove 1 coin from the first pile, and now no matter what coin Renzo removes, you can remove the other and win.
Remember, after printing your play, flush the output, like: fflush(stdout); in C, cout.flush(); in C++, or sys.stdout.flush() in Python.
Our dear Nathan, when a little child, used to like chess a lot, but this was a long time ago. One of these days he was challenged by @luisgust to a chess match and, as he is a guy that likes hard challenges, he accepted it. The problem is that Nathan keeps forgetting the rules of the game, so he asked you to help him determine if a given opponent's piece can be captured in one move.
Chess, in MaratonIME, is represented as a matrix of characters. Instead of playing with black and white pieces, they play with uppercase and lowercase letters. Nathan has chosen to play with the lowercase letters.
Besides that, as usual, the positions on the matrix are given in the following coordinates system: Each position is a pair with a character between a and h (inclusive), representing the column, and an integer between 1 and 8 (inclusive), representing the row. For exemple, the position d2 refers to the fourth column (from left to right) and second row (from bottom to top), and the position f6 refers to the sixth column and sixth row. Lowercase letters start on the bottom of the grid, on lines 1 and 2.
Here position A is adjacent position B if A shares a vertex with B, that is, if the distance between their rows is at most one and the distance between their columns is at most one. For example, the position c4 is adjacent to 8 positions: b3, b4, b5, c3, c5, d3, d4 and d5.
They decided to play a simplified version of chess. To help you, they gave you the following manual on how to play it:
- The pawn, represented by p or P, can capture pieces that share a diagonal and is in front of it, that is, the lowercase pawn on c4 can capture pieces at b5 or d5.
- The knight, represented by c or C, makes L-shaped moves in any of the 8 possible directions, that is, it moves two positions in any direction and after that one position in a direction that is perpenticular to the first one. A knight on c4 can capture, in one move, pieces on positions a3, a5, b2, b6, d2, d6, e3 and e5.
- The rook, represented by t or T, can capture pieces that are on the same row or the same column as it, as long as no other piece lies between them. For example, a rook on c4 can capture any piece on column c or row 4, as long as there is no other piece in between. If the rook is on c4 and there is another piece on c6, the rook can't capture pieces on c7 and c8.
- The bishop, represented by b or B, can capture any piece on one of its diagonals as long as there are no piece between them (diagonaly). For example, the bishop on c4 can capture a piece on f7 as long as there are no piece on d5 and e6.
- The queen, represented by r or R, can capture any piece that lies on the same row, column or diagonal, given there are no pieces in between, as if it were a bishop and a rook at the same time.
- The king, represented by k or K, can capture any piece that is adjacent to it.
- The character . represents an empty position.
Given a matrix representing a chess board and an opponent's piece, your program needs to determine whether you can capture it with one of your pieces. It is guaranteed that each player has at most two bishops, two rooks, two knights, eight pawns, one king and one queen.
The input begins with 8 lines with 8 characters each, representing the chess board. The first line contains the characters on the positions a8, b8, ... , h8. The second line contains the characters on positions a7, b7, ... , h7, and so on. After that follows a line containing the position of the opponent's piece you wish to capture.
Print a single line containing the word Sim if it is possible to capture the piece or Nao otherwise.
TCBRKBCT
PPPPPPPP
........
........
........
........
pppppppp
tcbrkbct
d8
Nao
........
........
........
..R.....
...p....
........
........
........
c5
Sim
To make the trip to the subway less boring and tiring, the SPSU, Sao Paulo State University, tried one of its most famous inventions: buses with Infinite Inner Length! In such a modern engineering wonder, there's always a couple of empty seats for the students to sit and chat during the trip.
MaratonIME crew is very popular, so popular that they have friends at every SPSU institute. Like everyone else from this university, they need to take the bus after a long day learning how to fix the Wi-Fi network. Because they don't practice sports like rowing, every SPSU student sits right after entering the bus, making pairs whenever possible. Thinking about that, Gi, an ICPC expert, comes with a problem to think on the way to the subway: given a number n which indicates the number of institutes at SPSU and n integers ai representing the amount of people waiting for the bus at the institute i, Gi wants to know for m pairs lj, rj (lj ≤ rj) if all the people waiting for the bus at any point between lj e rj (inclusive) took an empty bus, they could sit together in pairs (nobody would sit alone).
The input consist in one line with two integers n and m, the number of institutes and the number of Gi's questions. In the second line there are n integers ai, the number of people waiting for the bus at the ith institute. Then follows m lines with two integers each, li and ri, the first and last institute of Gi's question.
- 1 ≤ n, m ≤ 105
- 0 ≤ ai ≤ 105
- 1 ≤ li ≤ ri ≤ n
Output "Sim" if it is possible to organize all the pairs in a way nobody sits alone or "Nao" otherwise.
5 2
1 4 10 3 2
3 5
2 3
Nao
Sim
In the first sample we have 5 institutes with 1, 4, 10, 3 and 2 students. Gi asks if it is possible to form only couples if the ones between the 3rd and the 5th institutes takes an empty bus and the ones between the 2nd and the 3rd. For the first we have 15 so we can't and for the second we have 14 so we can.
In MaratonIME, as many other groups, some students want to attend lectures just enough to not be flunked by frequency (as we know, in USP, University of Sao Paulo, it is necessary to have 70 percent frequency), however some others are dedicated and try to accomplish the most frequency percent possible, going to school even when they are ill or tired. Curiously, there is not any other kind of students in MaratonIME.
Wood, an old MaratonIME's member, needs help. He is taking the course MAC4815162342, and attended k of m lectures that were given. Consider that MAC4815162342 has n lectures in total per semester. He ask you to help finding the best way to accomplish his objectives, but, as you are new in MaratonIME, you don't know the kind of student that he is. Embarassed to ask more, you decide to solve two problems, so there is not way to go wrong.
The input consists of a just one line. In this line, you are given three integers n, m and k, with 1 ≤ n ≤ 107 and 0 ≤ k ≤ m ≤ n.
n is the number of lectures of MAC4815162342 per semester, m is the quantity of lectures that were given and k is the number of lectures attended by Wood.
In the first line, print the minimum number of lectures that Wood needs to attend to accomplish at least 70% frequency, or - 1 if it is impossible to accomplish 70% frequency.
In the second line, print the maximum frequency percent that Wood can accomplish, if he goes to all of the lectures from the next lecture. This value has to be rounded down to the closest integer. Don't print '%'.
10 5 2
5
70
11 2 1
7
90
On the second example, the maximum percentage that Wood can get is 90.9090.
As common sense tells us, competitive programmers excel at rowing. The olympic lane is a wonderful place to row, run and work out. What few take their time to appreciate are the capybaras that inhabit the region. Capybaras are fascinating animals! Aside from their beauty, they possess many interesting behaviours. Did you know that capybaras can live in packs as big as 100 individuals?
In a pleasant sunny morning, Yan was running, as usual. Watching the capybaras, he noticed that they would line up to sunbath. Each capybara was paired with another one, and only another one. Two capybaras can be paired if and only if both see each other. A capybara sees everything in the direction it is looking.
Curious, Yan decided to represent the capybaras by the letters A and B, where A indicates that the capybara is looking right, and B indicates that the capybara is looking left.
For example, the sequence AABABB accurately represents capybaras sunbathing, because it is possible to pair every capybara according to the rules above. Yan was so fascinate by this that he slipped and felt into the water, messing his representations. He was able to recover some, but now they are all messed up with each other. Can you help him and find out if a given sequence represent capybaras sunbathing?
Every instance contains a sequence S of characters, composed only of 'A' and 'B' – Yan's representation. You may assume that 1 ≤ |S| ≤ 105.
The output should contain a single line. Print "Sim" if the sequence represents capybaras sunbathing, or "Nao" otherwise.
AABABB
Sim
Believe it if you can, studies show that we in MaratonIME live not only out of competitive programming.
In a saturday, after taking part in a virtual contest, our heroes decide to enjoy the afternoon watching a movie session. But they didn't choose any movie, but an n-D movie, that is, a movie with n dimensions.
During a chase scene, the main character jumps over a chain in the parking lot. Of course this was done in a very athletic way, and for some reason that drove Yan, one of the competitive programmers, mad.
"Hollywood makes everything seem easy, but jumping over a chain is really hard!"
The rest of the crowd, after the movie, argued with Yan that the actor surely jumped over the chain, but Yan disagreed, saying that it was done by some camera trick or by special effects.
To prove his point, he bought another ticket for the movie and this time he took highly precise measuring instruments to the session. Yan's plan was to show that the distance from the actor's foot to the floor was smaller than the distance from the chain to the floor, and that would prove that the actor didn't actually jump over the chain.
But math in n dimensions is hard. Everyone knows that distance in the 2D plane between two points (x0, y0) and (x1, y1) is given by the formula
Most people also know that distance between two points (x0, y0, z0) e (x1, y1, z1) in 3D space is given by the formula
Both formulas describe the euclidean distance, in the 2 and 3 dimensional case. Your task is, given three points in an n dimensional space, tell if the the closest ones are the foot and the floor or the chain and the flooor, according to euclidean distance.
The input begins with an integer n, followed by three lines, each with the representation of a point in an n-dimensional space.
Dimensions confuse us, humans, so you can assume that 1 ≤ n ≤ 105.
The second line represents the coordinates of the floor, and contains n integers a1, ..., an.
The third line represents the coordinates of the foot of the main character, and contains n integers b1, ..., bn.
The fourth line represents the coordinates of the chain, and contains n integers c1, ..., cn.
The movie theather is not arbitrarily large, so you can assume that the absolute value of these coordinates are not greater than 104.
Print who wins the argument, that is, print "Yan" if the distance between the floor and the foot is not greater than the distance between the floor and the chain, or "MaratonIME" otherwise.
2
0 0
1 1
2 2
Yan
4
0 0 0 0
2 2 2 2
1 1 1 1
MaratonIME
Nathan and Yan are very dedicated programmers. They apply their knowledge in algorithms in problems beyond the programming competitions themselves, optimizing even the most trivial every day things.
Some question if they aren't just crazy, and if it wouldn't be better to just do what has to be done.
Anyhow, eventually some conflicts happen when their approaches differ about what has to be done. That always happens when they decide to go to japanese restaurants.
Everybody knows that the objective in an all-you-can eat it to try to eat many distinct kinds of food. Nathan and Yan differ in opinions on how to achieve that. Both competitors, when sitting to eat an asian delicacy, eat until nothing is left on their plates.
The difference is that Yan, respecting the wisdom of the nipponic masters, eats in the order the food arrives, whereas Nathan claims that the food is better the latter it arrives, to spare the most expensive ingredients, and so asks that his plates come in inverted order.
Given the default order the dishes will arrive and the time Nathan and Yan will stay at the restaurant, determine who is going to eat the most different kinds of food, or if both ate the same number of different kinds of food, given that Yan eats the food in order and Nathan in inverted order.
The first line of input has two integers: 0 < n ≤ 105, how many plates will be served and 0 < T ≤ 106, how long (in minutes) Yan and Nathan will stay at the restaurant.
In the following line, n integers 0 < ti ≤ 103, ti is how long it takes to eat the i-th dish (in minutes).
The restaurants are very well administrated, so you can assume that when one of the competitors finishes his dish, the following dish is already on the table.
If Yan is going to taste more dishes than Nathan, print "Yan". If Nathan is going to taste more dishes than Yan, print "Nathan". Otherwise, if we have a tie, print "Empate".
10 45
1 2 3 4 5 6 7 8 9 10
Yan
10 45
10 2 3 4 5 6 7 8 9 1
Nathan
After a long day of hard training, MaratonIME (マラトニメ) members decided to go to a Japanese restaurant. Yeah, we love Japanese food.
After a lot of sushi boats, when everyone was more than satisfied, they asked the sushi-man Sussushi (ススシ) for the last boat. Sussushi felt challenged and answered:
– You want one more boat? You shall have one more boat...
The sushi boat that he brought was the biggest that any contestant had ever seen. Some contestants even dare saying that was the biggest sushi boat that ever existed, exceeding the previous limit of 105 sushis made by the suhiwoman Gioza (ジョザ) in 742, in a festival for the king that year, Carlos-sama (カーロス様).
Besides that the contestants accepted the challenge, and together they managed to eat all the sushis. After that, the contestants we're so full that they couldn't touch each other. They couldn't even think about programming problems. Help them find what pair of friends are touching themselves, so they can move away from each other.
The contestant are represented as circles in plane, and two contestants touch each other if the circles touch each other. It's guaranteed that the intersection area of any two circles is null.
In the first line there is a single integer, n indicating the number of contestants (2 ≤ n ≤ 1000).
Each one of the next n lines has 3 integers xi, yi e ri, the (i + 1)-th line describes the ith contestant. (xi, yi) are the coordinates of the center of the circle, and ri is the radius. ( - 104 ≤ xi, yi ≤ 104, 1 ≤ ri ≤ 2·104)
It is guaranteed that the intersection area of any two circles is null.
For each pair of circles that touch each other, print in one line the indexes of these circles. The collisions can be printed in any order, the indexes of both circles can also be printed in any order.
Don't print the collisions more than once, that means, if i intersects with j, print i j or j i, but not both.
3
0 0 2
5 0 3
10 10 1
1 2
After thousands of years repeating the title of this problem statement, always with an excited and inviting tone, Nathan finally persuaded his colleagues to go to the karaoke. He is feeling radiant with this achievement.
But there is a problem. After so much time trying to make his friends go to the karaoke, Nathan is afraid of embarrassing himself when he goes to sing the following classics of Brazilian music:
- Waitress – Reginaldo Rossi
- Blue Nightclub – Joaquim and Manuel
- Paper Heart – Sérgio Kings
- Love Bubble – Fagner
- You did not teach me to forget – Fernando Mendes
To avoid the humiliation, and to not discourage his fellows in future hang outs at the karaoke, Nathan decided to print all the song’s ciphers that are available in the karaoke, to check while he sings. However, this resulted in a colossal amount of paper, that he is not able to carry.
But the perseverance and ingenuity of an envious programmer is not something you should underestimate.
Nathan realized that, after all, there were only 7 musical notes. The specialists in this matter used to represent this notes with the letters A, B, C, D, E, F and G. Even more, it’s common that the same note appears several times in sequence. He decided then, to compress the songs, changing every occurrence of repeated notes with the note followed by how many times it occurs.
For instance, given the sequence
[(A,A,A,B,B,B,C,G,G,G,G,G,G,G,G,G,G,G)] the compressed version is [A3B3C1G11]
Unfortunately, Nathan also needs to pack his floral suit and to comb his beard – two homeric jobs – and he is out of time to compress the notes. Help him to not embarrass himself by writing a program that can solve this task.
Each input consist of a single line, a sequence of caracteres S such as |S| ≤ 105, formed only by the letters A, B, C, D, E, F and G.
For each input, print in a single line, such as each sequence of similar notes are replaced by the note that occurs and how many times it occurs, as showed in the example.
ABBGA
A1B2G1A1
AAABBBCGGGGGGGGGGG
A3B3C1G11
Once after a contest, the competitive programmers were sad because of bad results. Seeing the situation, Renzo, MaratonIME's coach, suggested they should do something fun to relax. After a big discussion, they decided to go karting. Looking for a place that was viable to all students, they found Kartforces, a kart track near Cidade Universitária. However, the track was too small and only fitted two racers by race. As passionate competitive programmers, they organised a fair tournament where everyone raced against everyone, two by two, only once. In each race, the winner got one point on the scoreboard. Draws were allowed and no one scored in this case. The winner was the biggest scorer. There were N competitive programmers present and:
- Each competitive programmer had a skill hi.
- If hi > hj where 1 ≤ i, j ≤ N and i ≠ j, then the competitive programmer i won the race against j.
You had access to the skills of all competitive programmers and now asks who was the champion.
The first line consists on a single integer N, the number of competitive programmers. The second line contains N integers hi, the skill of the i - th competitive programmer.
- 1 ≤ N ≤ 105
- 0 ≤ hi ≤ 109
The output consists in a single integer i, the champion competitive programmer. If it's not possible to determine the champion, print - 1.
3
2 4 6
3
Popular among the most traditional coders, the Summer Camp is famous for its fancy parties. After each party all attendees must return to their homes, but the way back home is not always easy: mildly drunk coders walk weird and often find or lose money along the way. However, MaratonIME always has a sober member in the group, who assures no one will lose money, except when they are robbed.
On its way back MaratonIME knows that they can call their coach, Renzo, who will pick them up immediately. Instead of doing that right after the party, they want to know what is the maximum amount of money they can carry back to their homes.
Your task is to write a program that solves this problem. Consider the following facts:
- The city map can be seen as an N by M grid;
- Members of MaratonIME are initially at the top left corner, and start walking right, carrying no money;
- Whenever they reach the end of a row, they walk to the row below and start walking in the opposite direction (if they were walking right, they walk left the next row, and vice-versa);
- They cannot go past the last row;
- Whenever they meet a burglar, they lose all their money;
- They can call Renzo at anytime, and he will pick them up instantly.
The first line of the input contains two integers N and M (1 ≤ N, M ≤ 103), respectively, the number of rows and columns of the grid. Then follows N lines, each containing M characters, representing the city map. Each cell of the city map can be either:
-
, meaning there is nothing at this cell of the grid; -
, meaning there is a coin worth 1 unit of money at this cell; -
, meaning there is a burglar at that cell.
The output must contain a single integer: the maximum amount of money MaratonIME can carry back home.
3 3
__.
_._
L._
2
In the example above, MaratonIME follows the following path: (1, 1) 
(1, 2) (1, 3) (2, 3) (2, 2) (2, 1) (3, 1) (3, 2) (3, 3). When they reach (2, 2) or (2, 1) they will have 2 coins, and that is the highest value they can get before calling Renzo.