Nowadays everyone is connected, has a Facebook page, posts photos to Instagram and videos to Youtube, and so on. Even GPS systems now are based on social networks, making everything more fun (and harder to understand, but that's another problem).
Being popular on Facebook is almost a need. A person with less than 700, 800 friends may be considered almost a pariah in this new reality.
Maybe that's why some people tend to exaggerate when telling the number of friends they have. Consider a community with N people and, for each one of them, consider we know the number of friends that person says he or she has on this community. Your task is to determine if in fact it is possible that everyone is telling the truth. Remember someone cannot be his or her own friend, and two people cannot be friends more than once.
On the first line T, the number of test cases.
The first line of each test case has an integer N. The second line has N space-separated integers a1, ..., aN. The i-th person claims to have ai friends on the community.
Limits
- 1 ≤ N ≤ 105
- 0 ≤ ai ≤ 105
- The sum of N over all test cases does not exceed 5·105
For each case, print on a single line Y if it is possible that no one is lying, or N otherwise.
2
3
1 1 1
3
2 2 2
N
Y
Alexey and Boris were two KGB agents that lived in Ekaterinburg in the 70's. The city was pretty small, and as nothing happened, to avoid dying of boredom the agents decided to create a dice game. In that game each of them started with VA and VB hit points, respectively. Each had in their disposal some attacks, and they alternated in attacking each other. Each attack is described by a number of dice. To determine the damage of the attack, roll those dice and their sum is the damage.
To play, they have available honest dice with 1 to 12 faces. That is, if a die with L faces is rolled it will show an integer between 1 and L with the same probability, and independent of any dice rolled before.
Both players know their attack and their opponents and choose how to attack each turn in a way that will maximize their probability of winning. Your task is to determine that probability.
In the first line an integer T, the number of test cases.
In the first line of each case, four integers VA, VB, NA and NB. Each of the next NA lines describes an attack Alexey has, the other NB lines describe the attacks Boris has.
Each attack is described by an integer D followed by D integers L1, ..., LD, meaning that to attack the player will roll D dice, with faces L1, ... LD.
Limits
- 1 ≤ T ≤ 5
- 1 ≤ VA, VB ≤ 300
- 1 ≤ NA, NB ≤ 10
- 1 ≤ D ≤ 3
- 1 ≤ Li ≤ 12
For each case, print a single line with the probability that Alexey will win the duel, assuming he starts and both players play optimally. It will be considered correct if the absolute or relative error does not exceed 10 - 6.
2
2 12 2 1
1 12
3 4 4 5
2 1 1
5 5 1 2
1 6
2 3 5
2 1 6
0.0833333333
0.5339917695
Pyramids are frequent structures in ancient civilizations all around the world. The most famous ones, in Egypt, were built over 2000 years before Christ. Other famous pyramids are found in Mexico and Central America, connected to the Mayan and Aztec civilizations.
Little know, however, are the pyramids built in the Ural Mountains, near the city of Ekaterinburg. Such pyramids are from the beginning of the Cristian era, and it is believed that it was built by the Mongols, that invaded Europe through the Ural Mountains from Asia. Differently from the other pyramids, they had a triangular base. Therefore, these pyramids had 4 triangular faces, and since they were held by pillars, no face had to be aligned to the ground.
This was very important, since the pyramid's faces were painted with figures of ancient gods, mythological figures, planets and so on. This way, in some point in the city, a citizen could see one or more faces of the pyramid. This was important in the local religion, and finding a house whose side could see the best faces of the pyramid was greatly valued in that time.
Your task is, given the position of the vertex of the pyramid, and the position of a citizen, determine which faces the citizen can see, considering there's no obstacle between the observer and the pyramid. We consider a point X sees a face if the line segment connecting X to any point Y in the face does not intersect any other point in the pyramid.
In the first line an integer T, the number of test cases.
Each test case has 5 lines, each with 3 integers. The lines represent the points A, B, C, D and X, respectively, where X is the position of the citizen and the remaining points are the vertex of the pyramid.
Limits
- 1 ≤ T ≤ 103
- All points have coordinates with absolute value not exceeding 100.
- The points A, B, C and D are not coplanar.
- All points are distinct.
- The point X is not in the interior nor in any face of the pyramid.
for each instance, print a line with 4 characters. The first must be Y if the citizen can see the face of the pyramid opposed to the vertex A, or N otherwise. The second, third and fourth character must be printed analogously for B, C and D, respectively.
3
0 0 0
1 0 0
0 1 0
0 0 1
1 1 1
0 0 0
1 0 0
0 1 0
0 0 1
-1 -1 -1
0 0 0
1 0 0
0 1 0
0 0 1
1 1 0
YNNN
NYYY
YNNN
Poker is played with a standard 52-card deck (13 ranks and 4 suits). The ranks of the cards, in increasing order, are: 2, 3, ..., 10, Jack, Queen, King and Ace. Given a poker table, with two players, your task is to determine the winner.
Each player has two cards in his hand and there are five common cards to both players. Whichever player has the most valuable 5-card hand, choosing from his own cards and the one on the table, wins. A card on the table may be used by both players at the same time and a player may ignore zero, one or both of his own cards.
To determine the value of a 5-card hand, it is identified as one of the hand types listed below. If the same hand fits more than one type, the most valuable one is chosen. If both players' hands fit the same type, the tie is broken by some rule specific to that type.
The type list, from least to most valuable, and their respective tie-breaking rule are:
- Highest card: If the hand does not fit any of the other types. To break the tie, the five cards are compared, one by one, from highest to lowest rank, until one hand has a higher card then the other;
- One pair: Two cards of the same rank. The tie-breaker is similar the rule in Highest card, first comparing the pair, and then the other three cards;
- Two pairs: Two pairs of different rank. The tie-breaker is first by the most valuable pair, then by the second, then by the last card;
- Three of a kind: Three cards of the same rank. The tie-breaker is analogous to the one in One pair, first compare the triple, then the other two cards;
- Straight: Five cards in a sequence. In this case, the Ace may be either the highest rank (after the King) or the lowest (before the 2). The tie-breaker is done by the card of highest rank, considering that Ace has the lowest rank if it comes before a 2;
- Flush: Five cards of the same suit. The tie-breaker is done like in Highest card;
- Full House: A three of a kind with a pair. The tie-breaker is done by the rank of the three of a kind, and then by the pair;
- Four of a kind: Four cards of the same rank. The tie-breaker is done by the rank of the four of a kind, and then by the last card;
- Straight Flush: Straight and Flush at the same time. The tie-breaker is the same as in Straight.
Notice that it is possible for the tie to persist even after the tie-breaker rules are applied. The suits of a card are only used to define a Flush, and are not used in any tie-breaker rule.
On the first line, an integer T, the number of test cases.
Each test case is given in three lines. The first two lines have the description of two cards each, the cards of the first player, and of the second. The last line has the description of five cards, the cards on the table.
The description of each card is given by two characters, the rank and the suit, as given in the table.
Limits
- 1 ≤ T ≤ 105
- For each test case, all cards are valid and distinct.
For each test, print 1 if the first player wins, 2 if the second player wins, and 0 if there is a tie, even after applying the tie-breaker rules.
3
Ts Js
Tc Jc
Qs Qc Ks Kc As
As 7d
Ah 8s
Ac Ad 9s Jh Kc
As 7d
Ah 8s
Ac Ad 6s 3h Kc
1
0
2
Yekaterinburg, Russia, is a city with a curious voting system. In an election in which there are V spots for a job, each voter has the right to cast up to V votes, ordered by his preference.
The candidates with the most votes, ignoring the order of preference, are elected. Only when there is a tie that the ordering is relevant. In that case, the candidate with most votes for first position wins. If the tie persists, the candidate with most votes for the second position wins, and so on.
In the case that two or more candidates are still tied after accounting all positions, all are elected, even if it exceeds the number of jobs. Candidates with zero votes can be elected if there are still vacancies.
Your task is to manage an election in Yekaterinburg.
The first line contains a single integer, T, the number of test cases.
The first line of each test case has 3 integers, N, K and V, the number of voters, candidates, and job vacancies, respectively. Each of the next N lines begins with a begins with a number Li, the number of candidates the voter i will vote for, and then Li integers, the votes. Candidates are numbered from 1 to K.
If the vote is not for a valid, that is, outside the interval [1, K], then it is counted as a blank vote. If a voter votes more than V times, only the first V votes should be considered.
Limits
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 105
- 1 ≤ V ≤ K ≤ 100
- 0 ≤ Li ≤ 100
-
- The sum of N over all test cases will not exceed 3·105.
- The sum of Li over all test cases will not exceed 3·105.
For each test case, print in a single line the list of all elected candidates, ordered by their classification. If two or more candidates are in a tie, order them by their indices.
2
5 3 2
2 1 3
2 2 3
2 1 3
2 2 3
1 1
3 6 3
3 1 5 3
3 1 0 3
3 1 4 5
3 1
1 5 3
A company wants to demolish a building and build a garden in one of the main avenues of Yekaterinburg, but first it wants to determine for how long each day will the sun shine in the garden, since there are many other buildings around. This is important since sunbathing is a very popular activity in Yekaterinburg during the summer. The garden is considered to receive sunlight if at least a piece of it is hit by solar rays.
To make things easy, the company chose one day of the year to make the measurings. In this day the sun rises at 5:30 and sets at 21:30 (Russian summers are very long). Consider that the sun is infinitely far and moves in a constant angular velocity.
The sun rises in the east and sets in the west. The buildings are also east-west aligned; their width and the spacing between them is constant, and the garden has the same width as the buildings.
Your task is to determine for how long each day the sun will shine in the garden.
The first line has a single integer T, the number of test cases.
Each case consists of two lines. The first has 3 integers N, W and S, the number of buildings, their width, and the spacing between each adjacent pair of them, respectively.
The second line has N integers h1, ..., hN, the height of each building. The buildings are given from west to east. A height of 0 indicates that the garden will be built at that site, and exactly one height in each case is 0. All units are in meters.
Limits
- 1 ≤ T ≤ 103
- 2 ≤ N ≤ 100
- 1 ≤ W, S ≤ 100
- 0 ≤ hi ≤ 50
For each case, print a single floating point number, the time in minutes that the garden will receive sunlight each day. Errors of up to 10 - 4 are tolerated.
2
3 2 1
10 0 5
4 5 3
0 2 4 20
254.2026707524
747.7036208413
The professors in Yekaterinburg University don't like to walk long distances. Each professor wishes that all classrooms he will give lectures in are in adjacent positions. In the beginning of each semester, the responsible for the Graduation Committee is charged with determining the classrooms the professors will give lectures. Each professor knows the groups he will teach, for example, students from the third semester of Mechanical Engineering, or students from the first semester of Computer Science, etc.
The students of each group stay in the same classroom for all lectures. The important thing is that all the classrooms each professor will lecture are adjacent. It is now always possible to satisfy the professors. If, for example, prof. A gives classes to groups X and Y, prof. B to groups Y and Z and prof. C to groups X and Z, it is clearly impossible to satisfy all of them. Your task is to help the responsible for the classroom schedule, determining if it is possible to satisfy all professors.
On the first line, a single integer T, the number of test cases.
The first line of each test case has two integers C and P, the number of classrooms (and groups) and the number of professors. The classrooms are numbered from 1 to C. The i-th of the next P lines describes the i-th professor. It consists of an integer K followed by K integers, denoting the groups the professor must teach, in increasing order.
Limits
- 1 ≤ T ≤ 103
- 1 ≤ C ≤ 103
- 1 ≤ P ≤ 103
- The sum of C + P over all test cases does not exceed 2·103
- 0 ≤ K ≤ C
For each test case, your program should print a permutation of the groups that satisfies all professors. If there's no such permutation, print -1. If more than one permutation is possible, print any of them.
2
5 4
3 2 4 5
2 2 5
2 1 5
2 1 3
3 3
2 1 2
2 2 3
2 1 3
4 2 5 1 3
-1
Instruments for calculation have existed for centuries. Long before the invention of calculators in the XVII century, Chinese and Japanese made use of abacus with which they could do sophisticated mathematical operations in an astonishing speed. A similar instrument was recently discovered in digging sites near the city of Yekaterinburg. It is believed to be an abacus similar to the Japanese one, called, in Russian, sorobov (copoбob).
The sorobov has nine columns, each corresponding to a digit. The rightmost column represents the unit value, the second-to-right represents the tens, then the hundreds and so on. There are seven rows, the first two being separated from the last five by a line. In the upper part (two first lines), each column contains a single pebble that, when positioned next to the separating line, adds 5 to the value of the corresponding digit. In the lower part, each column has 4 pebbles and an empty space, and the number of pebbles between the separating line and the empty space is added to the value of the corresponding digit. That way, we say that the pebbles in the top are worth 5 units and the ones in the bottom are worth 1.
How to represent the digits from 0 to 9. Your task is: Given a number N, print its representation using the sorobov.
On the first line T, the number of test cases.
Each test case consists of a single integer N.
Limits
- 1 ≤ T ≤ 104
- 0 ≤ N < 109
For each test case, print the representation of the number N in the sorobov using the following format. The two first lines correspond to the pebbles that are worth 5 units. In the third line print --------- (nine hyphens). In the next five lines, print the pebbles that are worth 1. Each line representing pebbles should contain exactly nine characters, where "0" corresponds to an empty space and "1" to a pebble.
Print an empty line after each test case (including the last).
2
2
16
111111111
000000000
---------
000000001
111111111
111111110
111111111
111111111
111111110
000000001
---------
000000011
111111100
111111111
111111111
111111111
Many may think: "What will I do in Yekaterinburg? This city is in the end of the world!!". However, many important things have happened in this city, so it has many monuments and historical places. To name a few, Yekaterinburg has a monument that is a huge computer keyboard located in the banks of river Izet; a monument to Michael Jackson (!!); in the Ipatiev mansion some Romanovs were murdered (czar Nicolau, his wife and children); also there was an anthrax leak in 1979; an american U2 pilot was captured and convicted for espionage; among others. Therefore, there is plenty to do in the city.
Yekaterinburg's tourism central built a map with all the main tourist attractions in the city, as well as beautiful excursions connecting these attractions. This map also shows a difficulty level for each excursion (taking in account duration, paving of the streets, etc.) and the direction in which it should be traversed.
They wish to build a route that goes through all the tourist attractions and excursions. A contest was made to create this route, and also to honor one of the sister cities of Yekaterinburg: Kaliningrad, that was named Königsberg until the end of the second world war. The idea was to build a route that started in one of the attractions, and going through all excursions returned to the starting point.
We know that, as in the case of the bridges of Königsberg, it isn't always possible to build such route. That's why the central allowed excursions to be traversed more than once, if necessary. However, the central required that the total difficulty of the route (the sum of the difficulties of each excursion in it, counting repetitions) was minimal.
Your task is to find this minimal total difficulty, or determine if there exists no such route.
On the first line T, the number of test cases.
The first line of each test case has two integers N and M, the number of tourist attractions and the number of excursions, respectively. The i-th of the next M lines has three integers ai, bi and di, meaning the i-th excursion starts at ai, ends at bi and has difficulty di.
Limits
- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 50
- 0 ≤ M ≤ N2 + 103
- 1 ≤ ai, bi ≤ N
- ai ≠ bi
- 1 ≤ di ≤ 3·104
- The sum of N over all test cases won't exceed 1500.
For each test case print the minimal total difficulty of the desired route. If there is no such route, print -1.
The answer may not fit in a 32-bit integer.
3
2 2
1 2 10000
2 1 30000
4 7
1 2 1
2 1 2
2 3 4
2 3 4
3 2 3
3 4 10
4 3 100
3 2
1 2 1000
2 3 1000
40000
127
-1
During the years of the Soviet Union, the name of the city of Yekaterinburg was Sverdlovsk, in honor to the Bolshevik Iakov Sverdlov, son of a Jewish artisan, that was an excellent orator and was one of the main protagonists beside Lenin in the revolution in October 1905. He was considered honest, energetic and hard-working, and was respected by all groups of the party. He died at 34. The city got back its original name in 1991 by the initiative of Boris Yeltsin, the first Russian president, born in that city.
In April 2nd, 1979, while the city was still called Sverdlovsk, there was an anthrax leaking from a military factory in the city. This incident is often called "Biological Chernobyl", and caused approximately 100 deaths, despite the exact number of victims and contaminated are still unknown. The Soviet Union denied for years the real causes of the incident and every victim record disappeared, since they could uncover serious violations of the Biological Weapons Convention.
The Soviet authorities had to use highly sophisticated decontamination procedures, specially in rural areas. Each rectangular area of dimensions N by M was divided in N × M square sectors of one squared meter. These sectors were identified by the coordinates of their centers, numbered from west to ease and from south to north from (1, 1).
Each sector was considered decontaminated if it was covered by at least K health agents. Each agent was capable of covering a circular area. The radius of this area depended on the equipment used and the experience of the agent. Your task is to determine how many of those sectors are considered decontaminated, that is, covered by at least K agents. A sector is considered to be covered if its center is in an area covered by some agent.
On the first line, a single integer T, the number of test cases.
The first line of each test case contains two integers, N and M, the dimension of the rectangular area mentioned in the statement. The second line contains the number of agents, C, and the number K.
The c-th of the next C lines contains the description of the c-th agent, that is, three integers Xc, Yc and Rc, meaning (Xc, Yc) is the center of the circular area covered by that agent, and the radius is Rc.
Limits
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 103
- 1 ≤ M ≤ 105
- 1 ≤ K ≤ C ≤ 103
- 1 ≤ Xc ≤ N
- 1 ≤ Yc ≤ M
- 0 ≤ Rc ≤ 108
For each test case, print the number of decontaminated sectors.
2
10 10
2 1
3 3 2
8 8 2
15 15
6 2
4 4 2
5 5 1
6 6 3
7 7 2
10 10 0
11 10 1
26
20
More precisely, a sector with center (xs, ys) is covered by an agent positioned at (xa, ya) capable of decontaminating an area with radius r if
Yekaterinburg is a Russian city located in the border between Europe and Asia, in the Ural Mountains. It's the fourth largest city in Russia, with more than 1.4 million residents. Its main economical activity is related to the production of industrial machines. The city's factories produce a large part of the machines used in Russia, and they are exported to several countries. In fact, the production of industrial tools is famous in the country. The tools are build by highly specialized machines and, for each tool to be produced the machines take some pre-determined time to produce it.
One of the factories has only one of those machines and its manager need your help to increase productivity. The tool orders arrive in the factory along the day, that is, they are not necessarily known at the beginning of the day. The manager thinks the employees are not choosing a good order to process the orders, and wants to analyze orders from previous days. This way, he asks you to determine, for a given day, the minimum instant at which all orders can be processed and finalized.
On the first line, a single integer T, the number of test cases.
Each test case has a single integer N on the first line, the number of orders to process in that day. The i-th of the next N lines has two integers si and di, the time at which the i-th order is available and the time it takes to process it, respectively.
Limits
- 1 ≤ N ≤ 105
- The sum of N over all test cases won't exceed 5·105
- 1 ≤ si, di ≤ 104
For each test case, print the minimum instant at which all orders can be processed and finalized.
2
5
10 2
6 1
4 3
1 2
1 4
4
1 1
1 3
5 2
5 3
13
10