Your first mission is to find the password of the Martian database. To achieve this, your best secret agents have already discovered the following facts:
- The password is a substring of a given string composed of a sequence of non-decreasing digits
- The password is as long as possible
- The password is always a palindrome
A palindrome is a string that reads the same backwards. racecar, bob, and noon are famous examples.
Given those facts, can you find all possible passwords of the database?
The first line contains n, the length of the input string (1 ≤ n ≤ 105).
The next line contains a string of length n. Every character of this string is a digit.
The digits in the string are in non-decreasing order.
On the first line, print the number of possible passwords, k.
On the next k lines, print the possible passwords in alphabetical order.
8
34456788
2
44
88
1
0
1
0
You can easily convert a digit encoded as a character to an integer:
(int)('1' - '0') will give you 1 for instance, in C++ or Java.
int('4' - '0') will give you 4 in Python.
It's finally dessert time! You have k bars of chocolate of different brands: Twix, Galaxy, Mars, MilkyWay, KitKat, etc... You also have n humans and m Martians to feed.
Each living creature will be satisfied with a single bar of chocolate. However, Martians refuse to eat Mars (something about cannibalism?).
How many extra bars, if any, do you need to buy to satisfy everyone?
The first line of the input consists of 3 space-separated integers, k, n, and m (1 ≤ k, n, m ≤ 105).
Each of the next k lines contains a string. These represent the brands of chocolate bars you initially have, in no particular order. Each string consists of upper-case and lower-case English letters, and contains no more than 10 characters.
Print on a single line the number of extra bars you need to buy to satisfy everyone.
5 4 3
Twix
Galaxy
Galaxy
Mars
MilkyWay
2
3 1 3
Mars
Mars
Mars
3
EPFL (Extreme Programmers For Life) want to build their 57th art museum. This museum would be better, bigger and simply more amazing than the last 56 museums. This would make EPFL great again.
To achieve this, EPFL will not only require the help of top-notch Japanese architects, but also of all Martians. However, the Martians are spread across several galaxies and therefore have different time availabilities. You thought the time difference between Europe and USA was annoying?
Help EPFL find the maximum number of galaxies that are available at the same hour?
The first line contains the integer n, the number of galaxies (1 ≤ n ≤ 105).
On each of the next n lines, there will be two space-separated integers, a and b (0 ≤ a < b ≤ 24).
This means that the Martians of this galaxy are available from the beginning of the a-th hour to the beginning of the b-th hour.
Print the maximum number of galaxies available in any timeslot of one hour.
2
1 14
14 21
1
7
9 16
16 18
5 12
15 24
9 20
20 22
23 24
3
In the first example, the Martians of the first galaxy are available from 01:00 to 14:00, and the Martians of the second galaxy are available from 14:00 to 21:00. Therefore, at any given hour, the maximum number of available galaxies is 1.
In the second example, the timeslots in which 3 galaxies are available are: 9:00 - 12:00, 15:00 - 16:00, and 16:00 - 18:00. No one-hour timeslot has more than 3 galaxies available. Therefore, the answer is 3.
Martians use the English alphabet to communicate. However, they have an entirely different language, but it’s based on a one-to-one (bijective) mapping of letters from Martian to English. Be careful though, lower-case and upper-case letters in English aren’t necessarily the same in Martian. For example, the word "CARS" in Martian translates to "Unil" in English, whereas the word "cars" in Martian translates to "EPFL".
The Martians have invaded Earth! But, we have intercepted their communications. Help us translate their messages to English.
The first line of the input contains an integer n (1 ≤ n ≤ 100).
The second line contains a sentence in Martian, consisting of n space-separated words each consisting of lower-case and upper-case English letters. The total number of letters in the sentence is at most 105.
Print, on a single line, n space-separated words representing the English translation of the sentence.
Do not print any leading or trailing spaces, and end your output with a newline character.
1
CARS
Unil
1
cars
EPFL
3
IuVEJxTXs UvOHhng yZKfAYmaqolM
vpVZzBNtL SCubWma ocIYneAPqxDs
3
NtGQibw djPrCpek FWzL
hRkMGgJ fHrFUQTj XOwd
3
aySBaPyb RM gzYMynY
PolyProg is awesome
The Martians have invaded EPFL. Five minutes ago, they were at Esplanade and started heading towards the EPFL metro station to destroy it so that no student can return home (no one likes taking the bus anyway, and walking is just too hard!).
You are currently at Esplanade, and you need to get to the metro station before they do. Luckily, you know some secret passageways and can perhaps take a shortcut.
You are given the map to EPFL as an n x m grid, with some obstacles. Esplanade is at the top left corner with index (0, 0), and the metro station is at the bottom right corner with index (n - 1, m - 1).
The Martians (and you) can move vertically or horizontally on the grid, and need 1 minute to go from one cell to another. The cells that are obstacles cannot be traversed.
You are also given k coordinates. These are the obstacles that you can walk (or run!) through but the Martians can't because they don't know about.
Can you get to the metro station before them?
The first line will contain three space-separated integers n, m and k (1 ≤ n, m ≤ 500; 1 ≤ k ≤ 105).
Each of the next n lines will have a string si of length m, representing row i in the EPFL map. Each character in si will be either a '.' representing a clear passage or a 'x' representing an obstacle.
Each of the next k lines will contain two space-separated integers r and c, where (r, c) represents an obstacle in the original graph that you can use as a secret passage (0 ≤ r ≤ n - 1; 0 ≤ c ≤ m - 1).
All k (r, c) are obstacles in the original graph, and are pair-wise distinct.
The top left and bottom right corners of the EPFL map will not be obstacles.
Print on a single line the word YES if you can reach the metro station strictly before the Martians do. Otherwise, print NO.
5 5 1
.....
xxxx.
.....
.xxxx
.....
3 4
YES
5 5 1
..x..
...x.
x.x..
..x.x
.x.x.
3 4
NO
In the first example, the Martians need 16 minutes to reach the metro station. You, on the other hand, know the secret passage through (3, 4), which allows you to reach the metro station in 8 minutes. Even though you started 5 minutes after the Martians, you still arrive before them!
In the second example, neither you nor the Martians can reach the metro station. If only obstacle (0, 2) was also a secret passage, you would have been able to reach.
Martians have discovered the answer to life, the universe, and everything. No, not 42. Wifi trees!
Martian lungs are adapted to survive without Oxygen for a looong time, but that time is about to end.
The Martians have managed to plant n Wifi trees, each additional tree supplying them with x Mbps of Wifi. However, each Martian requires one Oxygen tree in order to survive.
The government does not want to spend money on planting new trees, but it can convert some Wifi trees to Oxygen trees. Being utilitarian by nature, it wants to maximise total happiness.
Each Martian will have 1 happiness for each Mbps of Wifi he gets. However, dead Martians cannot be happy. The total happiness is the sum of happiness of each of the Martians.
Formally, happiness of some Martian i is defined as follows: Hi = ai·t·x.
ai is 1 if that Martian is alive, 0 otherwise. t is the number of Wifi trees.
Total happiness is therefore 
.
What is the minimum number of trees the government should convert to maximise total happiness?
The first line of the input contains an integer T, the number of test cases (1 ≤ T ≤ 5).
Each of the next T input represents a test case, and consists of 3 space-separated integers n, m, and x (1 ≤ n, m ≤ 109; 1 ≤ x ≤ 5), the number of Wifi trees, the number of Martians, and the additional bitrate provided by each Wifi tree, respectively.
Print T lines of output, one for each test case. On each line print two space-separated integers.
The first integer is the minimum number of Wifi trees that should be converted to Oxygen trees.
The second integer is the maximum happiness achieved.
1
5 3 2
2 12
2
42 83 1
1000000000 1000000000 5
21 441
500000000 1250000000000000000
To avoid overflows, use 'unsigned long long' or 'long long' in C++, and 'long' in Java, instead of 'int'
This is it. The final battle between EPFL and Mars. The rules of the game are as follows.
Neither side wants to sacrifice their own people, so we will be picking two teams of Unil students to fight each other instead. You have been chosen to pick the team that will fight for EPFL's honour!
You are given a list containing the strength of each Unil student. You start by choosing one student to join your team, then the Martians will choose another student, and so on, until all n students are chosen.
If you had no extra information, clearly you'd pick the strongest Unil student in each turn. However, we managed to figure out the preference of the Martians. More specifically, we have a permutation P of the first n numbers, representing the indices of the Unil students, which the Martians prefer to pick in order.
Take a look at the example inputs to understand this further.
You want to pick the team that maximises the difference between your team's strength and theirs. What's the maximum difference?
The first line of the input has of an even integer n (2 ≤ n ≤ 100), the number of Unil students.
The next line contains n space-separated integers si, the strength of each student (1 ≤ si ≤ 107).
The last line contains n space-separated integers between 1 and n, representing the permutation P.
Print the maximum difference in strength between your team and the Martians' team.
4
3 9 1 7
4 1 2 3
12
10
1 1 2 3 4 5 6 6 8 10
9 8 7 6 5 4 10 1 2 3
14
In the first example, there are four Unil students with strengths 3, 9, 1, 7.
The Martians prefer to pick them in this order: 4, 1, 2, 3.
This means that in their first turn, they'll pick student 4 (strength = 7) if that student hadn't been picked, otherwise they'll pick the next student on their list (student 1, strength = 3).
If you had used the simple strategy of picking the strongest available student each turn, you'd have ended up with a total strength of 9 + 3 = 12, and the Martians with 7 + 1 = 8, giving you a difference of 4.
Given this extra information, you can first pick student 4 (strength = 7), then student 2 (strength = 9) in your next turn. You'd have a difference of 9 + 7 - 3 - 1 = 12. In this case, this is the best strategy.