A big marathon is held on Al-Maza Road, Damascus. Runners came from all over the world to run all the way along the road in this big marathon day. The winner is the player who crosses the finish line first.
The organizers write down finish line crossing time for each player. After the end of the marathon, they had a doubt between 2 possible winners named "Player1" and "Player2". They will give you the crossing time for those players and they want you to say who is the winner?
First line contains number of test cases (1 ≤ T ≤ 100). Each of the next T lines represents one test case with 6 integers H1 M1 S1 H2 M2 S2. Where H1, M1, S1 represent Player1 crossing time (hours, minutes, seconds) and H2, M2, S2 represent Player2 crossing time (hours, minutes, seconds). You can assume that Player1 and Player2 crossing times are on the same day and they are represented in 24 hours format(0 ≤ H1,H2 ≤ 23 and 0 ≤ M1,M2,S1,S2 ≤ 59)
H1, M1, S1, H2, M2 and S2 will be represented by exactly 2 digits (leading zeros if necessary).
For each test case, you should print one line containing "Player1" if Player1 is the winner, "Player2" if Player2 is the winner or "Tie" if there is a tie.
3
18 03 04 14 03 05
09 45 33 12 03 01
06 36 03 06 36 03
Player2
Player1
Tie
This is the first day for you at your new job and your boss asks you to copy some files from one computer to other computers in an informatics laboratory. He wants you to finish this task as fast as possible. You can copy the files from one computer to another using only one Ethernet cable. Bear in mind that any File-copying process takes one hour, and you can do more than one copying process at a time as long as you have enough cables. But you can connect any computer to one computer only at the same time. At the beginning, the files are on one computer (other than the computers you want to copy them to) and you want to copy files to all computers using a limited number of cables.
First line of the input file contains an integer T (1 ≤ T ≤ 100) which denotes number of test cases. Each line in the next T lines represents one test case and contains two integers N, M.
N is the number of computers you want to copy files to them (1 ≤ N ≤ 1,000,000,000). While M is the number of cables you can use in the copying process (1 ≤ M ≤ 1,000,000,000).
For each test case, print one line contains one integer referring to the minimum hours you need to finish copying process to all computers.
3
10 10
7 2
5 3
4
4
3
In the first test case there are 10 computer and 10 cables. The answer is 4 because in the first hour you can copy files only to 1 computer, while in the second hour you can copy files to 2 computers. In the third hour you can copy files to 4 computers and you need the fourth hour to copy files to the remaining 3 computers.
Given string with N characters, your task is to transform it to a palindrome string. It's not as easy as you may think because there is a cost for this transformation!!
First you have to start from character at given position P. From your position you always have 2 options:
- You can move one step to the right or to the left, the cost of each movement is 1. Assume that the string is cyclic, this means if you move one step to the left you will be at position P-1 if P > 1 or at the last character if P = 1, and if you move one step to the right you will be at position P+1 if P < N or at first character if P = N.
- You can change the letter at your current position by replacing it with the next or previous one in the English alphabet (assume that the alphabet is also cyclic so ‘a’ is after ‘z’). The cost of each replacement is also 1.
You should repeat that until the transformation is finished and the string is palindrome. What is the minimum cost to do that?
The first line contains the number of test cases T ( 1 ≤ T ≤ 100 ). Each test case contains 2 lines, the first line contains two integers ( 1 ≤ N ≤ 100,000) the length of string and ( 1 ≤ P ≤ N ) the initial position. While the second line contains a string with exactly N alphabetical characters.
For each test case output one line contains the minimum cost that is needed to change the string into a palindrome one.
1
8 3
aeabdaey
8
start with P = 3 ae(a)bdaey, move right => aea(b)daey, change to next => aea(c)daey, change to next => aea(d)deay, move left => ae(a)ddeay, move left => a(e)addeay, move left => (a)eaddeay, change to previous => (z)eaddeay, change to previous => (y)eaddeay. This costs 8 (4 movements and 4 replacements)
You have been out of Syria for a long time, and you recently decided to come back. You remember that you have M friends there and since you are a generous man/woman you want to buy a gift for each of them, so you went to a gift store that have N gifts, each of them has a price.
You have a lot of money so you don't have a problem with the sum of gifts' prices that you'll buy, but you have K close friends among your M friends you want their gifts to be expensive so the price of each of them is at least D.
Now you are wondering, in how many different ways can you choose the gifts?
The input will start with a single integer T, the number of test cases. Each test case consists of two lines.
the first line will have four integers N, M, K, D (0 ≤ N, M ≤ 200, 0 ≤ K ≤ 50, 0 ≤ D ≤ 500).
The second line will have N positive integer number, the price of each gift.
The gift price is ≤ 500.
Print one line for each test case, the number of different ways to choose the gifts (there will be always one way at least to choose the gifts).
As the number of ways can be too large, print it modulo 1000000007.
2
5 3 2 100
150 30 100 70 10
10 5 3 50
100 50 150 10 25 40 55 300 5 10
3
126
Syrian Collegiate Programming Contest (SCPC) is the qualified round for the Arab Collegiate Programming Contest. Each year SCPC organizers face a problem that wastes a lot of time to solve it, it is about how should they arrange the teams in the contest hall.
Organizers know that they have t teams and n*m tables allocated in n rows and m columns in the contest hall. They don't want to put teams in a random way. Each year SCPC chief judge puts a list of paired teams (list of a,b teams) that should not sit next to each other (because they are so good or so bad!).
if pair (a,b) is in chief judge list, this means that:
- team number a should not sit in-front of team number b
- team number b should not sit in-front of team number a
- team number a should not sit right to team number b
- team number b should not sit right to team number a
Organizers wastes a lot of time to find a good team arrangement that satisfy all chief judge needs. This year they are asking you to write a program that can help them.
First line contains number of test cases. The first line in each test case contains three numbers: (1 ≤ n,m ≤ 11) and (1 ≤ t ≤ 10). Second line in each test case contains (0 ≤ p ≤ 40) number of pairs. Then there are p lines, each one of them has two team numbers a and b (1 ≤ a,b ≤ t) where a is different than b.
For each test case, print one line contains the total number of teams arrangements that satisfy all chief judge needs (We guarantee that it will be less than 9,000,000 for each test case). If there is no suitable arrangements print "impossible".
2
1 3 2
1
1 2
2 2 4
2
1 2
1 3
2
impossible
In test case 1 there are 2 teams and 3 tables in one row at the contest hall. There are only one pair (1,2), so there are 2 solutions:
team1 then empty table then team2
team2 then empty table then team1
In test case 2 there are 4 tables in 2 rows and 2 columns, and there are 4 teams. There is no arrangement that can satisfy chief judge needs.
Ahmad is one of the best students in HIAST, and also a very good problems Solver. In the time you will spend reading this problem statement Ahmad would have solved a problem. Maybe, even two... Ahmad participated so many times in programming contest (ACM-HCPC) with several teams. many of the former and present contestants at HIAST have known Ahmad for quite a few years. Some of them are proud to say that they either played in the same team with him or played in the same team with one of his teammates... Let us define ranking number as follows. Ahmad's ranking is 0, for people who played in the same team with him, the ranking is 1. For people who never played with Ahmad but played in the same team with one or more of his teammates, the ranking is 2, and so on. Your task is to automate the process of calculating the ranking numbers for each contestant at HIAST.
The first line of input file contains the number of test cases (0<T<10). Each test case will begin with one line containing the number of teams (1<N ≤ 100). In each of the following N lines you are given the names of the three members of the corresponding team. Each name is a nonempty string contains only English letters starts with capital letter, and its length is at most 20 symbols. Same student can be found in more than one team, but each student should have only one rank. Ahmad will be found in one team at least. The first letter of a name is capital and the other letters are lowercase and each name will consist of only one word.
For each test case output a line with the number of contestants, then for each contestant output a line with his name and his ranking. If the ranking is undefined, output “undefined” instead of it. The contestants must be ordered by rank from 0 to undefined and then lexicographical by name.
2
1
Ahmad Mousaab Khalid
7
Ahmad Mousaab Khalid
Ali Mousaab Nizar
Ali Bassel Nizar
Kassem Ahmad Mousaab
Saeed Kassem Fadel
Salwa Saeed Samer
Mona Abdo Qussi
3
Ahmad 0
Khalid 1
Mousaab 1
14
Ahmad 0
Kassem 1
Khalid 1
Mousaab 1
Ali 2
Fadel 2
Nizar 2
Saeed 2
Bassel 3
Salwa 3
Samer 3
Abdo undefined
Mona undefined
Qussi undefined
Alice and Bob play the following game. They choose a number N to play with. The rules are as follows:
- They write each number from 1 to N on a paper and put all these papers in a jar.
- Alice plays first, and the two players alternate.
- In his/her turn, a player can select any available number M and remove its divisors including M.
- The person who cannot make a move in his/her turn wins the game.
Assuming both players play optimally, you are asked the following question: who wins the game?
The first line contains the number of test cases T (1 ≤ T ≤ 20). Each of the next T lines contains an integer (1 ≤ N ≤ 1,000,000,000).
Output T lines, one for each test case, containing Alice if Alice wins the game, or Bob otherwise.
2
5
1
Alice
Bob
A sequence of positive and non-zero integers called palindromic if it can be read the same forward and backward, for example:
15 2 6 4 6 2 15
20 3 1 1 3 20
We have a special kind of palindromic sequences, let's call it a special palindrome.
A palindromic sequence is a special palindrome if its values don't decrease up to the middle value, and of course they don't increase from the middle to the end.
The sequences above is NOT special, while the following sequences are:
1 2 3 3 7 8 7 3 3 2 1
2 10 2
1 4 13 13 4 1
Let's define the function F(N), which represents the number of special sequences that the sum of their values is N.
For example F(7) = 5 which are : (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)
Your job is to write a program that compute the Value F(N) for given N's.
The Input consists of a sequence of lines, each line contains a positive none zero integer N less than or equal to 250. The last line contains 0 which indicates the end of the input.
Print one line for each given number N, which it the value F(N).
1
3
7
10
0
1
2
5
17
Mancala is a traditional board game played in Africa, Middle East and Asia. It is played by two players. This game board consists of two rows of holes, one row for each player. Each row has N holes, and each hole has some non-negative number of stones.
The two players will, in turn, make a move. One move is described as follows:
- the player chooses one of the holes in his row and takes all the stones from it.
- he starts to put these stones one in each hole, starting from the next hole and moving in counter-clockwise order, until there are no more stones left in his hands.
player1's row: 2 2 3
player2's row: 1 8 2
if player2 starts a move and chooses the middle hole in his row(the one with 8 stones). The board after the move will be like:
player1's row: 3 3 5
player2's row: 2 1 4
you were playing a very important game with your best friend, when suddenly you had a phone call and moved your eyes of the game. Now you lost track of the game and you need to make sure if your friend made a valid move.
You are given the final board configuration and the place where the last stone landed, Your task is to check is your friend's move is invalid, and in case of a valid move, find the state of the board before that move.
You are player1 while your friend is player2.
The input consists of several test cases, each test case starts with three numbers n(1 ≤ n ≤ 10000) (the number of holes in each of the rows), r (1 ≤ r ≤ 2) and k (1 ≤ k ≤ n) (the row and hole number where the last stone was put, respectively). Then 2n numbers follow, ai :1 ≤ i ≤ n, and bj :1 ≤ j ≤ n, where ai is the number of stones in the i-th hole in your row. bj is the number of stones in the j-th hole in your friend's row. Initially given ai and bi satisfy that: (0 ≤ ai, bj ≤ 1000000000) while ai and bj are fit in 64 bits in the state of the board before the move (if there is a valid move).
The last test case is followed by three zeros.
For each test case display the case number followed by the word "INVALID" without the quotes if the move is invalid, or 2n numbers representing the original board configuration otherwise.
3 1 3
3 3 5
2 1 4
4 2 2
1 2 3 4
5 4 3 2
4 2 2
1 2 3 4
1 2 3 4
5 2 3
2 2 2 2 2
2 2 2 2 2
0 0 0
Case 1:
2 2 3
1 8 2
Case 2:
INVALID
Case 3:
0 1 2 3
9 0 2 3
Case 4:
0 0 0 0 0
0 0 20 0 0
We will not waste your time, it is a straightforward problem. Given multiple polygons, calculate the area of their intersection. For simplicity, there will be exactly 2 polygons both of them are convex, given in the counterclockwise order and have non-zero areas. Furthermore, in one polygon a vertex won't be on the sides of the other one. The figure below demonstrates the first test case.
The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 20). each test case contains two integers (3 ≤ N, M ≤ 40) Then a line contains N pairs of integers xi, yi (-1000 ≤ xi, yi ≤ 1000) coordinates of the ith vertex of polygon A, followed by a line contains M pairs of integers xj, yj (-1000 ≤ xj, yj ≤ 1000) coordinates of the jth vertex of polygon B. The coordinates are separated by a single space.
For each test case, print on a single line, a single number representing the area of intersection, rounded to four decimal places.
2
5 3
0 3 1 1 3 1 3 5 1 5
1 3 5 3 3 6
3 3
-1 -1 -2 -1 -1 -2
1 1 2 1 1 2
2.6667
0.0000