| Problem description | | Progress |
|
Темы:
Count sort
On the distant planet Tau Ceti, there are customs that we do not understand. For example, it is very unusual for Taukitians to choose names for their children. The parents choose the name of the child in such a way that it can be obtained both by removing a certain set of letters from the father's name and by removing a certain set of letters from the mother's name. For example, if the father's name is "abacaba" and the mother's name is — "bbccaa", then their child may be named "a", "bba", "bcaa", but cannot be named "aaa", "ab" or "bbc". It is possible for a child's name to be the same as the name of the father and/or mother if it can be derived from the other parent's name by removing a few (possibly none) of the letters.
Have a father named X and a mother named Y choose a name for their newborn child. Since in Taukitian schools, students are often called to the board in the lexicographic order of the names of the students, that is, in the order of the names in the dictionary, they want to choose a name for their child so that it follows lexicographically as late as possible.
- Formally, the string S is lexicographically greater than the string T if one of two conditions is true: the string T is obtained from S by removing one or more letters from the end of the string S;
- the first (i - 1) characters of strings T and S are indistinguishable, and the letter in the i-th position of the string T follows the letter in the i-th position of the string S in the alphabet.
You need to write a program that, given the names of the father and mother, finds the lexicographically largest name for their child.
Input
The first line of the input file contains X — father's name. The second line of the input file contains Y — mother's name. Each name consists of lowercase letters of the Latin alphabet, includes at least one letter and has a length of no more than 105 letters.
Output
The output file must contain the lexicographically largest possible child name you are looking for. In case there is no suitable name for the child, the output file should be empty.
Examples
input
abcabca
abcda
output
ca
input
ccba
accbbaa
output
ccba
| |
![]()
|
ID 34821.
Gems
Темы:
Count sort
In a distant eastern country, camel caravans still roam the deserts, with the help of which merchants transport spices, jewelry and expensive fabrics. Of course, the main goal of merchants is to sell their goods at a higher price. Recently, one of the caravans arrived at the palace of a powerful shah.
The merchants want to sell the shah n gems they brought with them. To do this, they lay them out in a row before the check, after which the check evaluates these stones and decides whether he will buy them or not. There are not very many types of precious stones in the East, only 26, so we will designate the types of stones using lowercase letters of the Latin alphabet. The shah usually evaluates the stones in the following way. He predefined several ordered pairs of stone types: (a1, b1), (a2, b2), ..., (ak, bk). He calls these pairs beautiful, and we will denote their set as P. Now we represent a row of stones sold by merchants as a string S of length n consisting of lowercase Latin letters. Shah counts the number of pairs (i,j) such that 1 ≤ i < j ≤ n, and the Si and Sj stones form a beautiful pair, that is, there is such a number 1 & le; q ≤ k that Si=aq and Sj=bq.
If the number of such pairs is large enough, then the check buys all the stones. However, this time the merchants brought so many stones that the shah cannot count this number. So he summoned his vizier and entrusted him with this calculation. Write a program that finds the answer to this problem.
Input
The first line of the input file contains integers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 676) the number of stones brought by the merchants and the number of couples that the Shah considers beautiful. The second line of the input file contains the string S, which describes the types of stones brought by the merchants.
K lines follow, each containing two lowercase Latin letters and describing one of the beautiful pairs of stones.
Output
Output the answer to the — the number of pairs the vizier must find.
Examples
input
7 1
abacaba
aa
output
6
input
7 3
abacaba
ab
ac
bb
output
7
| |
![]()
|
|
Темы:
Count sort
Deciphering the Mayan script has proven to be more of a challenge than previously thought. For more than two hundred years, not much has been learned. The main results have been obtained over the past 30 years.
Mayan writing is based on small drawings known as icons that represent sounds. Mayan words are usually written with these symbols, which are arranged next to each other in some order.
One of the problems in deciphering the Mayan script is determining this order. When drawing icons for a word, Maya writers sometimes chose positions for icons based on aesthetic considerations rather than specific rules. This has led to the fact that although the sounds for many of the icons are known, archaeologists are not always sure how the recorded word should be pronounced.
Archaeologists are looking for some word W. They know the icons for it, but they don't know all the possible ways to arrange them. Because they know you will be coming to IOI ’06, they are asking for your help. They will give you g the icons that make up the word W, and the sequence S of all the icons in the inscription they are studying, in the order they appear. Help them by counting the number of possible occurrences of the word W.
Quest
Write a program that, given the signs of the word W and the sequence S of the signs of the inscription, counts the number of all possible occurrences of the word W in S, that is, the number of all different positions of consecutive g icons in the sequence S , which are some permutation of the icons of the word W .
Restrictions
1 ≤ g ≤ 3000, g – number of characters in a word W
g ≤ |S| ≤ 3 000 000 where |S| – number of icons in sequence S
Input
The input of the program is data in the following format:
LINE 1: Contains two numbers separated by a space – g and |S|.
LINE 2: Contains g consecutive characters that represent the word W . Valid characters: ‘a’-‘z’ and ‘A’-‘Z’; uppercase and lowercase letters are considered different.
LINE 3: Contains |S| consecutive characters that represent the icons in the label. Valid characters: ‘a’-‘z’ and ‘A’-‘Z’; uppercase and lowercase letters are considered different.
Output
A single line of program output should contain the number of possible occurrences of W in S.
Important for PASCAL programming
By default in FreePascal, a variable of type string has a size limit of 255 characters. If you want to use longer lines, you must add the {$H+} directive to your code, right after the line program ...;.
Examples
input
4 11
cAda
AbrAcadAbRa
output
2
| |
![]()
|
|
Темы:
Count sort
Input
Each line first contains the class number (a number equal to 9, 10 or 11), then (separated by a space) — last name of the student.
Imprint
It is necessary to display a list of students by grade: first, all students in grade 9, then — 10, then — 11. Within the same class, the order of output of last names should be the same as on the input.
Examples
input
9 Ivanov
10 Petrov
11 Sidorov
9 Grigoryev
9 Sergeev
10 Yakovlev
output
9 Ivanov
9 Grigoryev
9 Sergeev
10 Petrov
10 Yakovlev
11 Sidorov
| |
![]()
|
|
Темы:
Count sort
Petya plays with his friends a game sometimes called "Krizhanovsky's Lot". The rules of the game are as follows: in each round, each player guesses an arbitrary natural number. After that, the player who guessed the minimum number that does not repeat wins this round, and his payoff is equal to this number. For example, if 6 people play and the numbers 3, 2, 1, 1, 4 and 2 were guessed, then the first player won, and his payoff is 3. If all the guessed numbers are repeated, then the round is considered a draw and no one gets points.< br />
The total winnings of the player for the game is equal to the sum of points for all rounds played.
During the game, Petya and his friends simply call the numbers they have guessed in turn, and then determine who won and calculate the points. However, with this format of the game, in principle, you can cheat without guessing the number in advance, but, already knowing the numbers named by the previous players, choose the optimal “guessed” one for yourself. number. This is what Petya uses. He calls the last number and tries to choose the number in such a way as to maximize his winnings.
The last round of the game is underway. The points of all players before this round and the numbers named by the players are known. Find out what number should be called to Petya so that, according to the results of the game, as many players as possible have a score less than his. If there are several such numbers, then Petya wants to name the minimum possible number.
Input
The first line contains the number n - the number of players (2 <= n <= 100). The second line contains n numbers - the scores of the players before the last round (non-negative integers not greater than 100). The scores are listed in the order in which the players usually name the numbers (i.e. Petya's scores are listed last). The third line contains (n-1) number - the numbers named by the players in the last round (the numbers do not exceed 100), in the order in which they named them.
Imprint
Print a number to name Petya.
Explanations
In the second sample Petya cannot win in the last round. However, by naming the number 2, Petya does not allow the first player to win, and, thus, remains the second according to the results of the whole game. Four players have less points than Petya.
| Input |
Output |
6
0 0 0 0 0 0
2 3 4 5 6
| 1 |
6
8 3 12 5 0 9
2 1 3 1 4
| 2 |
| |
![]()
|
|
Темы:
Count sort
Egor has a very old phone. Slava sent Yegor a passphrase from Seryozha's bank account to rob him, but Yegor's phone is so old that it cannot receive long messages. He breaks them into several small random lengths, and they come to him in random order.
When Egor received all these messages, he was really upset. He cursed the phone, threw it against the wall. Unfortunately, the phone turned out to be touchy and mixed all the letters in each message, although it glued all the messages into one. Egor knew that Seryozha loves such lines that all letters in them go in descending order (in reverse alphabetical order). Help Yegor and Slava and find the passphrase from Serezha's bank account using the only remaining message on the phone.
Input
A single line of input contains the string s — message on Egor's phone (1 ≤ |s| ≤ 105). It is guaranteed that s contains only small latin letters.
Imprint
Print a passphrase from Serezha's bank account.
Examples
input
qwerty
output
ywtrqe
input
onehundredseventynine
output
yvutsronnnniheeeeedd
| |
![]()
|
|
Темы:
Count sort
Sasha and Katya are in elementary school. To study arithmetic, cards are used on which numbers are written (exactly one number is written on each card). One day they came to a math class, and Sasha, using all her cards, showed the number A, and Katya showed the number B. The teacher then wanted to give them a problem so that both Sasha and Katya could show the answer to it, each using only their own cards. At the same time, the teacher wants the desired number to be the maximum possible.
Input
Enter two non-negative integers A and B (each number on one line). The length of each of the numbers does not exceed 100 000 digits.
Imprint
Print a single number — The maximum integer that can be formed using both the digits of the first number and the digits of the second number. If none of these numbers can be formed, print -1.
Test examples
input
280138
798081
output
8810
input
123
456
output
-1
| |
![]()
|
Темы:
Count sort
Peter solves a puzzle, which is arranged as follows. A square table of size NxN is given, in each cell of which some Latin letter is written. In addition, a list of keywords is given. Petya needs to take another keyword and find it in the table. That is, find all the letters of this word in the table, and they must be arranged so that the cell in which each subsequent letter of the word is located is adjacent to the cell in which the previous letter is written (cells are called neighboring if they have a common side — i.e. side by side vertically or horizontally). For example, the figure below shows how the word olympiad can be located in the table.
| P |
O |
L |
T |
E |
| R |
W |
Y |
M |
S |
| O |
A |
I |
P |
T |
| B |
D |
A |
N |
R |
| L |
E |
M |
E |
S |
When Petya finds a word, he crosses it out of the table. Crossed-out letters cannot be used in other keywords.
After all the keywords are found and crossed out, a few more letters remain in the table, from which Petya must form the word encrypted in the puzzle.
Help Petya solve this puzzle by writing a program that, given the table and the list of keywords, writes out which letters Petya should use to form the word, that is, which letters will remain in the table after the keywords are crossed out.
Input
The first line of the input file contains two numbers N (1?N?10) and M (0?M?200). The following N lines of N capital Latin letters describe the rebus. The next M lines contain words. Words consist only of capital Latin letters, each word is not longer than 200 characters. It is guaranteed that all keywords can be found in the table and crossed out according to the rules described above.
Output
In a single line of the output file print in any order the letters that will remain in the table.
Examples
input
5 3
POLTE
RWYMS
OAIPT
BDANR
LEMES
OLYMPIAD
PROBLEM
TEST
| |
![]()
|
|
Темы:
Count sort
Greedy Algorithm
Scanning line
The new President of Far Far Away began his work with a complete revision of the country's public transport system. As a result, on the basis of sociological surveys of the population, an ideal daily schedule of intercity buses was compiled, approved by the Parliament of the Republic.
Moreover, it was decided to replace the entire bus fleet with the same new, very expensive, but much more reliable, beautiful and comfortable cars.
The bus network of the country covers N cities, numbered with integers from 1 to N.
The ideal schedule contains M daily flights, the i-th flight starts in city Fi at time Xi and ends in some other city Gi at time Yi. The duration of each flight is non-zero and strictly less than 24 hours. Flight i is performed by one of the buses located at time Xi in the city Fi.
New buses do not require repairs and can operate around the clock, so a bus that arrives at some point in time in a certain city is always ready at the same time or later to go to service any other flight from this city. The bus can leave the city only on a scheduled flight.
It is assumed that the schedule will operate indefinitely, so it may not be possible to serve it with any finite number of buses.
Determine the smallest number of new buses sufficient to keep the schedule running for an unlimited period of time.
Input
The first line contains integers N and M (1 ≤ N, M ≤ 100 000) — number of cities and bus routes respectively.
Each of the following M lines contains a description of the bus route: departure city number Fi, departure time Xi, destination city number Gi (Fi ≠ Gi), arrival time Yi, separated from each other by one space. Arrival and departure times are specified in the HH:MM format, where HH — hours from 00 to 23, MM — minutes from 00 to 59.
Imprint
Print one number — the minimum required number of buses. If the schedule cannot be served for an unlimited period of time by a finite number of buses, print the number -1.
Examples
| # |
Input |
Output |
| 1 |
4 6
1 10:00 2 12:00
1 10:00 3 09:00
3 12:00 4 23:00
2 11:00 4 13:00
4 12:00 1 11:00
4 12:00 1 10:30 |
8 |
| |
![]()
|
|
Темы:
Constructive
Count sort
Wushan decided to play a card game. He has a deck of N edible cards. The ith card has an integer Ai written on top. Wushan performs the operation described below zero or more times, so that the values written on the remaining cards will be pairwise different.
Find the maximum possible number of remaining cards. Here, N is odd, which ensures that at least one card is saved.
Operation: draw three random cards from the deck. Of these three cards, eat two: one with the highest value and the other with the lowest value. Then return the remaining one card to the deck.
Input
The first line contains an odd number N (\(3<=N<=10^5\)). The second line contains N numbers Ai (\(1<=A_i<= 10^5\))
Imprint
Output the maximum possible number of remaining cards.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
5
1 2 1 3 7
| 3 |
The optimal solution is to perform the operation once, drawing two cards from 1 and one card from 2. One card from 1 and the other from 2 will be eaten, and the remaining card with 1 will be returned to the deck.
Then the values written on the remaining cards in the deck will be pairwise different: 1, 3 and 7. |
| 2 |
15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1
| 7 |
|
| |
![]()
|
|
Темы:
Scanning line
Count sort
A new airport began to operate at the airport in the city of Che. On the first day of work, a file was recorded with the time of arrival and departure of aircraft. Aircraft that departed the next day were not recorded in the file. Determine the maximum number of planes that were at the airport at the same time and during what maximum period of time (in minutes) such a number of planes were at the airport. Only planes, information about which is recorded in the file, are taken into account.
Input
The first line contains the number N - the total number of planes for the whole day. Each of the following N lines contains a pair of values, where the first value in the pair indicates the time of arrival of the aircraft, and the second value indicates the time of departure (arrival and departure times are in the range from 00:00 to 23 :59, and it is guaranteed that the arrival time is less than the departure time) . All data in the lines is separated by a single space.
If the time coincides, it is considered that the arrival occurs earlier than the departure.
In your answer, write down two integers separated by a space: first, the maximum number of aircraft that were at the airport at the same time, then the maximum period of time (in minutes) during which there were such a number of transit aircraft at the airport.
If the plane arrived at 12:00 and departed at 12:01, then it is considered that it stayed at the airport for 2 minutes.
Assignment file
Examples
| # |
Input |
Output |
| 1 |
6
09:00 10:07
10:20 11:35
12:00 pm 5:00 pm
11:00 11:30
11:20 12:30
11:30 18:15
| 4 1 |
| |
![]()
|
|
Темы:
Count sort
USE
For the performance, the gymnasts use ribbons, which are placed on the table after the performance. The father of the best gymnast Anna K., in anticipation of the award, decided to write down the coordinates of the beginning and end of the ribbons. Do you have a file with this information. Determine at how many points of the table the greatest thickness of the coating turned out and what it is equal to. The table has a length Lmm. At the end of the performance of all the gymnasts, there was N ribbons. No ribbon protrudes beyond the table. All ribbons lie horizontally. The ribbons stack on top of each other.
Input
The first line of the file contains two numbers - L, N (1 <= L <= 10000, 1 <= N <= 10000). The following N lines contain 2 numbers each - l, r (1 <= l <= r < = L) - left and right ends of ribbons relative to the left edge of the table.
In your answer, indicate two numbers separated by a space - the maximum thickness of the tape table cover and the number of points with such a thickness.
| |
![]()
|
|
Темы:
Count sort
USE
For the performance, the gymnasts use ribbons, which are placed on the table after the performance. The father of the best gymnast Anna K., in anticipation of the award, decided to write down the coordinates of the beginning and end of the ribbons. If the tape hung from the left edge of the table, then he set the left coordinate equal to zero, if the tape hung from the right end of the table, then he set the right coordinate equal to zero. If the tape hung from both sides, then he recorded both coordinates equal to zero. Do you have a file with this information. Determine how many points of the table turned out to be the largest thickness of the coating and what it is equal to. The table has a length Lmm. At the end of the performance of all the gymnasts, there was N tapes. Some ribbons have only one end hanging off the table, some have both. All tapes lie horizontally. The ribbons stack on top of each other.
Input
The first line of the file contains two numbers - L, N (1 <= L <= 10000, 1 <= N <= 10000). The following N lines contain 2 numbers each - l, r (1 <= l <= r <= L) - left and right ends of the tapes relative to the left edge of the table.
In your answer, indicate two numbers separated by a space - the maximum thickness of the tape table cover and the number of points with such a thickness.
| |
![]()
|
|
Темы:
Count sort
There is a table of length L. N socks are laid out on the table so that no sock gets out of the table. Next, there is a smart boy Vasyok who wants (purely for selfish purposes) to measure the thickness of the table covering with socks at M points.
Input
In the input file, L, N, M are given first (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000).
Next are N pairs of numbers l ≤ r from 1 to L – left and right ends of socks.
Then there are M numbers from 1 to L points of interest to Vaska.
Output
Print M numbers – the thickness of the toe cap at each point.
| Input |
Output |
|
39 4 7
3 21
3 15
2 20
3 17
4
17
33
5
9
25
37
|
4
3
0
4
4
0
0
|
| |
![]()
|
|
Темы:
Count sort
You are given a set of N positive integers. For each number, the sum of the last two digits in its decimal notation is calculated (for single-digit numbers, the penultimate digit is considered equal to zero). It is necessary to determine what amount is obtained most often. If there are several such sums,
you need to display the largest of them.
Write a time and memory efficient program to solve this problem.
A program is considered to be time efficient if increasing the number of initial numbers N by k times increases the running time of the program by no more than k times.
A program is considered memory efficient if the memory required to store all program variables does not exceed 1 KB and does increase with N.
Maximum score for a correct (without syntax errors and giving the correct answer for any valid input data) program that is efficient in time and memory, – 4 points.
Maximum score for a correct program that is efficient only in time or only in memory, – 3 points.
Maximum mark for a correct program that does not meet performance requirements, – 2 points.
You may take one or two problem solving programs. If you take two programs, each will be graded independently of the other, the higher of the two grades will be the final score.
Before the text of the program, briefly describe the solution algorithm. Specify the programming language used and its version.
Description of input and output data
The first line of the input specifies the number of numbers N (1 ≤ N ≤ 1000).
The next N lines contain one natural number not exceeding 10 000.
Sample input:
5
15
417
123
6
4841
Sample output for the example input above:
6
The sums of the last two digits for numbers from this set are 6, 8, 5, 6, 5.
More often than others (twice each) there are 6 and 5, the larger of these sums is displayed in the answer.
| |
![]()
|
|
Темы:
Count sort
Given two arrays arr1 and arr2. The elements of the arr2 array are distinct, and all the elements of the arr2 are contained in arr1.
Sort the elements of the array arr1 so that the relative order of the elements in the array arr1 is the same as in the array arr2< /code>. Elements that are not in the array arr2 should be at the end of the array arr1 in ascending order.
Input
The first line of the input contains an integer n - the number of elements in the array arr1, the second line contains n integers - the elements of the array arr1< /code>. The third line contains an integer m - the number of elements in the array arr2, the fourth line contains m integers - the elements of the array arr2.
Input Restrictions
1 <= n, m <= 1060 <= arr1[i], arr2[i] <= 1000- All array elements
arr2 are distinct.
- Each element of the array
arr2[i] is contained in the array arr1.
Imprint
Output the array arr1.
sorted by the task condition
Examples
| # |
Input |
Output |
| 1 |
11
2 3 1 3 2 4 6 7 9 2 19
6
2 1 4 3 9 6
| 2 2 2 1 4 3 3 9 6 7 19 |
| 2 |
6
28 6 22 8 44 17
4
22 28 8 6
| 22 28 8 6 17 44 |
| |
![]()
|