Alaa is on her last day in Singapore, she wants to buy some presents to her family and friends. Alaa knows that the best present in the world will be a chocolate plate for each one of her family members and friends.
Alaa goes to Lucky Plaza shopping mall in Orchard road in order to find all chocolate she needs. Lucky Plaza is a big mall and have many shops that sell chocolate.
On the entrance of Lucky Plaza Alaa wondered if she wants to buy k chocolate plates, what is the probability that she will buy the kth chocolate plate from the nth shop she will visit, knowing that she can visit each shop at most one time. Also she can buy at most one chocolate plate from each shop, and the probability to do that is p. (This probability is the same for all shops in Lucky Plaza)
Alaa wants to finish her mission as soon as possible, so she starts visiting the shops, also she asked you to calculate the answer of her hard question. Can you?
The first line contains three integers m, n, k and real number p (1 ≤ m, n, k ≤ 105) (0 ≤ p ≤ 1), where m is the number of shops that sell chocolate in Lucky Plaza, n is the number of shops Alaa will visit, k is the number of chocolate plates Alaa wants to buy, and p is the probability that Alaa will buy a chocolate plate from any shop that sell chocolate.
The probability p is given with exactly three digits after the decimal point
On a single line print y, where y is the sought probability computed modulo 109 + 7.
The answer y is defined precisely as follows. Represent the probability that Alaa will buy the kth chocolate plate from the nth shop she will visit as an irreducible fraction p / q. The number y then must satisfy the modular equation y × q ≡ p (mod 109 + 7), and be between 0 and 109 + 6, inclusive. It can be shown that under the constraints of this problem such a number y always exists and is uniquely determined.
5 1 1 0.500
500000004
9 4 2 0.800
417600003
100 5 5 0.200
714240005
In the first test case there are 5 shops that sell chocolate in Lucky Plaza, and Alaa wants to buy only 1 chocolate plate. In this case Alaa wants to know what is the probability that she will buy the 1st chocolate plate from the 1st shop she will visit. The probability is 1 / 2, and the answer is 500000004, since (500000004 * 2) % (109 + 7) = 1 % (109 + 7).
In the second test case there are 9 shops that sell chocolate in Lucky Plaza, and Alaa wants to buy only 2 chocolate plates. In this case Alaa wants to know what is the probability that she will buy the 2nd chocolate plate from the 4th shop she will visit. The probability is 48 / 625, and the answer is 417600003, since (417600003 * 625) % (109 + 7) = 48 % (109 + 7).
Elissa is so clever girl, even though her age is 5 years only. Yesterday she spent all the day learning how to count. Currently she is able to solve many complex counting questions, so she decided to invent a new counting problem in order to help preparing this contest.
Elissa will give you a string s consisting of digits only (from '0' to '9'), and your task is to count in how many ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string.
A beautiful sub-string b is a sub-string from string s, such that b contains unique digits only (i.e. each digit from '0' to '9' can exist at most one time).
Elissa thinks that no one can solve this problem because it is very hard. Can you?
The first line contains an integer n (1 ≤ n ≤ 104), where n is the length of the string s. The second line contains a string s consisting of digits only.
Print the number of ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string. Since the number of ways may be too large, print the answer modulo 109 + 7.
4
1213
6
5
12345
16
7
5112516
28
A sub-string of the string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.
In the first test case you can divide the given string in 6 ways, which are:
Alaa and Duaa spent a long day in Universal Studios in Sentosa island, and now it's time to go back to home. The best way to get home is by using the train, starting from "HarbourFront" station and ending at "Serangoon" station.
Because the journey to home is long, Alaa and Duaa decided to invent a new game and play with it to spend time. In this game, they will use the train system map in Singapore (which called MRT map). The game goes as follow:
The cost to go from station u to station v, is the number of common letters in the names of the two station. For example, the cost to go from "HarbourFront" station to "Serangoon" station is 4, because there exist 4 common letters, which are 'a', 'n', 'o' and 'r'. Note that each letter will be count once only (e.g. the letter 'o' exist two times in "HarbourFront" and two times "Serangoon", but it will add only 1 to the cost).
The letters in the names are case insensitive. For example the cost to go from city with name "AbC" to city with name "aBc" is 3, because the three letters in both names are common regardless of the state of the letter (uppercase or lowercase).
Alaa and Duaa need your help to find the shortest distance from the starting station to the end station, to announce the winner's name. Can you?
The first line contains two integers n and m (2 ≤ n ≤ 104) (n - 1 ≤ m ≤ min(105, 
)), where n is the number of stations in the map, and m is the number of links between the stations.
Then n lines follow, each line i contains the name of the ith station in the map. The name of each station is a non-empty string consisting of English letters only, and with length no more than 20.
Then m lines follow, each line contains two integers u and v (1 ≤ u, v ≤ n), which mean that there is a link between stations u and v. It is guaranteed that no link will connect a station with itself, and there is at most one link between any two stations.
You can use the given links only to move between stations.
The next line contains two integers s and e (1 ≤ s, e ≤ n), where s is the starting stating (which were chosen by Alaa), and e is the end station (which were chosen by Duaa). It is guaranteed that you can go from any station to any other station in the map.
Print the shortest distance from the starting station s to the end station e.
6 5
Bishan
Marymount
Caldecott
BotanicGardens
LorongGhuan
Serangoon
1 2
2 3
3 4
1 5
5 6
4 6
19
13 13
BuonaVista
OneNorth
KentRidge
HawParVilla
PasirPanjang
LabradorPark
TelokBlangah
HarbourFront
Commonwealth
Queenstown
Redhill
TiongBahru
OutramPark
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 9
9 10
10 11
11 12
12 13
13 8
10 8
14
Two days ago, Husam was very busy in preparing for the 2017 JUST Programming contest 2.0. He was creating user name and password for each team, each password he creates must meet the following conditions:
Can you help us to complete the passwords before the contest day start!
The first line contains an integer n (1 ≤ n ≤ 100), where n is the number of teams in the contest.
Then n lines follow, each line contains a password. The length of each password is between 9 and 100 (inclusive).
Print "The last character must be a letter.", if the last character must be a letter.
Print "The last character must be a digit.", if the last character must be a digit.
Print "The last character must be a symbol.", if the last character must be a symbol.
Print "The last character can be any type.", if the last character can be any type.
2
@az19g3544@
zz6?7aa89
The last character must be a letter.
The last character must be a symbol.
1
!ab55ab!66
The last character can be any type.
Abdalrahman Ali is one of the best ACMers in JUST, after the last contest he got a lot of simple bugs. So he decided to train him self to be more careful in writing solutions, he started to play simple games to make his mind more trained to write correct and perfect codes without bugs.
The first simple game he plays was as following; the game gives Abdalrahman a string S consisting of lowercase English letters. He has to find X such that it will result the minimal cost of the string.
He can find the cost of string S by applying this equation:
Abdulrahman already found the solution, Can you find it now?
The only line of input contains a string S of length between 1 and 105 consisting of lowercase English letters.
Print X the solution of the problem which will produce the minimal cost of string S. If there are multiple valid solutions, print the minimal one.
acm
2
aababaa
5
abcabcabc
3
Dr. Samer have made an agreement with GX company to design certificates for each lecture in Innovation Programming Lab.
GX company gave Dr. Samer n offers, where the ith offer contains ai certificates. If Dr. Samer wants to take the ith offer, he must buy all the certificates given by this offer.
Dr. Samer wants to buy x certificates for each lecture and he wants to get the offer because it will reduce the cost to more than 50% for some offers. For each lecture, Dr. Samer will buy the minimum number of certification such that he will be able to give each student a certification. with the guarantee that he will spend the minimal amount of money.
Can you help Dr. Samer to know what is the number of certificates he need to buy for each lecture to get any acceptable offer?
The first line contains an integer n (1 ≤ n ≤ 105), where n is the number of offers given by GX company.
The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 109), where ai is the number of certificates in the ith offer.
The third line contains an integer m (1 ≤ m ≤ 105), where m is the number of lectures in Innovation Programming Lab.
The fourth line contains m integers x1, x2, ... xm (1 ≤ xi ≤ 109), where xi is the number of certificates needed for the ith lecture.
Print m lines. The ith line must contain an integer x, where x is the number of certificates that Dr.Samer will buy for the ith lecture.
If Dr. Samer cannot take any offer for the ith lecture, print "Dr. Samer cannot take any offer :(." (without quotes).
5
2 4 6 8 10
4
2 3 7 1
2
4
8
2
3
100 5 50
5
15 2 10 200 5
50
5
50
Dr. Samer cannot take any offer :(.
5
Dr. Wail Mardini is the chairman of computer science department. Today he wants to distribute the graduation project groups between the supervisors in the department.
Dr. Wail wants to achieve a fair distribution, and this can be achieved by splitting the groups between the supervisors equally (i.e. each supervisor must take the same number of groups).
Dr. Wail is very busy currently, and you are visiting the department, so he gives you the number of supervisors and the number of graduation project groups, and he asked you to check if he can reach a fair distribution or not. Can you?
The first line contains two integers n and m (1 ≤ n, m ≤ 103), where n is the number of supervisors, and m is the number of graduation project groups.
If Dr. Wail can divide the groups between the supervisors equally print "YES" (without quotes). Otherwise, print "NO" (without quotes).
4 8
YES
7 5
NO
In the first test case there is 8 groups and 4 supervisors. Each supervisor can take an equal number of groups (which is 2 groups), so the distribution is fair, and the answer is "YES".
In the second test case you cannot divide 5 groups between 7 supervisors equally, so the answer is "NO".
Today Abdalrahman and Ali have one hour break, so they decided to spend it in the Innovation Programming Lab to invent new game.
After a deep thinking they invented a new game that is played using an array a. The goal of the game is to find for each value in the array the nearest larger value to it from the right. (i.e. for the ith value in the array, the goal is to find the value in the nearest jth index, such that (1 ≤ i < j ≤ n) and (aj > ai)). If the nearest larger value does not exist, then the answer is "-1".
Abdalrahman and Ali thought that this game is very hard and no one can solve it, so they wrote it in the white board inside the lab, and under it they wrote the following statement: "If you solve this game correctly we will give you a very big pizza".
Yosef enter the lab after Abdalrahman and Ali left it. When he saw the game, he decided to solve it to take the pizza. Yosef is very hungry currently so you decided to help him to solve the game as soon as possible. Can you?
The first line contains an integer n (1 ≤ n ≤ 105), where n is the length of the array a.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 50), giving the array a.
Print n integers b1, b2, ..., bn, where bi is the nearest larger value for the ith value in array a. If such value does not, then bi must be "-1" (without quotes).
5
2 1 3 9 4
3 3 9 -1 -1
7
5 9 7 3 2 1 4
9 -1 -1 4 4 4 -1
In his last birthday, Husam received a special present from his best friend, it was a beautiful array a consisting of n positive integers. Husam loved this present so much, so he used it to build another table t such that for each i and j (1 ≤ i, j ≤ n) tij = ai × aj.
Unfortunately, today Husam was looking for his array a, but he was not able to find it. Husam was very sad, so he asked you to help him. Husam does not remember anything about array a, but he will show you the table t. Can you help Husam to build the array a again?
The First line contains an integer n (1 ≤ n ≤ 100), where n is the size of the array a.
Next n lines follow, each line contains n positive integers (1 ≤ tij ≤ 104), giving the table t.
In a single line print n positive integers a1, a2, ..., an – the array a.
It is guaranteed that there exists a unique answer for each test case. Your answer will consider correct if you can use the printed array a to build the given table t, such that for each i and j (1 ≤ i, j ≤ n) ti, j = ai × aj.
3
9 6 15
6 4 10
15 10 25
3 2 5
5
16 28 8 36 4
28 49 14 63 7
8 14 4 18 2
36 63 18 81 9
4 7 2 9 1
4 7 2 9 1
After you helped Husam and rebuilt his beautiful array a he became very happy. To avoid losing his array again, Husam made n copies from it, and distributed it to n of his friends. After that Husam became sure that he can rebuild the array a again if he lost it, so he destroyed the table t.
Today, Husam was looking for his array a, but he was not able to find it. Husam visited all his n friends to take a copy from the array. Unfortunately, all his friends thought that the length of the array a was very long, so instead of keeping the array itself, each friend i take a subarray (li, ri) from the array and kept it in a safe place, and get rid of the rest of the array.
Now Husam has n subarrays from the array a, but he cannot remember the original array or even its length. Husam now needs your help again, he will give you the n subarrays, and your task is to build a new array a such that it contains all the given subarrays inside it as subarrays, and its length must be as minimal as possible. Can you?
The first line contains an integer n (1 ≤ n ≤ 15), where n is the number of friends Husam has.
Then n lines follow, each line i begins with an integer mi (1 ≤ mi ≤ 100), where mi is the length of the subarray the ith friend has. Then mi integers follow, representing the ith subarray. All values x in the subarrays are in the range (1 ≤ x ≤ 109).
Print the minimal length of the new array a, such that a contains all the given subarrays in the input inside it as subarrays.
3
2 1 2
4 3 4 5 6
3 2 3 4
6
5
3 4 7 5
4 7 9 2 5
3 7 5 2
4 5 1 4 7
4 9 2 5 1
9
A subarray of the array a is a sequence al, al + 1, ..., ar for some integers (l, r) such that (1 ≤ l ≤ r ≤ n).
In the first test case the array a can be [1, 2, 3, 4, 5, 6]. Its length is as minimal as possible, and it contains all the the given subarrays in the input inside it as subarrays.