| Problem description | | Progress |
|
Темы:
Stack
Implement the "stack" data structure. Write a program that describes the stack and simulates how the stack works by implementing all the methods listed here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should output one line. Possible commands for the program:
push n
Push the number n onto the stack (the value of n is given after the command). The program should output ok.
pop
Remove the last element from the stack. The program should output its value.
back
The program should output the value of the last element without removing it from the stack.
size
The program should print the number of elements on the stack.
clear
The program should clear the stack and output ok.
exit
The program should output bye and exit.
Input:
Stack management commands are entered in the format described earlier, 1 per line.
It is guaranteed that the set of input commands satisfies the following requirements: the maximum number of elements on the stack at any time does not exceed 100, all pop and back are correct, that is, when they are executed, the stack contains at least one element.
Output:
It is required to display the log of work with the stack, 1 message per line
Examples
input
push 3
push 14
size
clear
push 1
back
push 2
back
pop
size
pop
size
exit
output
ok
ok
2
ok
ok
1
ok
2
2
1
1
0
bye
| |
![]()
|
|
Темы:
Stack
Implement a "stack" data structure. Write a program containing a description of the stack and simulating the operation of the stack, implementing all the methods indicated here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should output one line. Possible commands for the program:
push n
Push the number n onto the stack (the value of n is given after the command). The program should output ok.
pop
Remove the last element from the stack. The program should output its value.
back
The program should output the value of the last element without removing it from the stack.
size
The program should print the number of elements on the stack.
clear
The program should clear the stack and print ok.
exit
The program should print bye and exit.
Before executing the back and pop operations, the program must check whether the stack contains at least one element. If the back or pop operation occurs in the input data, and the stack is empty, then the program should output the string error instead of a numeric value.
Input: Stack management commands are entered, one per line
Output: The program should print the stack log, one message per line
Examples
input
size
push 1
size
push 2
size
push 3
size
exit
output
0
ok
1
ok
2
ok
3
bye
| |
![]()
|
|
Темы:
Stack
Every day, many patients come to Gregory House, and everyone has their hemoglobin levels measured. Data for all patients are entered into the database.
But lupus comes across once in a million, and working with the rest is not interesting. To prevent House from expelling patients, Cuddy sometimes asks for statistics on k last patients: she wants to know the sum of their hemoglobin levels.
Also House — misanthrope: he looks at the hemoglobin level of the patient, who came to him later than everyone else, and, seeing that it is definitely not lupus, discharges him from the hospital and deletes information about him from the database.
Case was tasked by House to automate the process. But for some reason Chase could not cope with this task and asked you to help him.
Input: The first line of the input file is a number n ( 1<= n ;<= 100000 ) — number of database hits. Database queries look like this: + x ( 1 <=x < = 10 9 ) — add a patient with a hemoglobin level x to the database, - — remove the last patient from the database, ? k ( 1 <= k <= 100000 ) — display the total hemoglobin of the last k patients. It is guaranteed that k does not exceed the number of elements in the base. It is also guaranteed that there are no requests for deletion to an empty database. The database is empty before starting.
Output: For each request " - " display the level of hemoglobin in the patient's blood, and for each query " ? k " — total hemoglobin in the last k admitted patients. Output the answers in the order in which requests are received.
Examples
| # |
Input |
Output |
| 1 |
7
+1
+2
+3
?2
-
-
?1 |
5
3
2
1 |
| |
![]()
|
Темы:
Stack
The XML format is a common way to exchange data between different programs. Recently, the programmer Ivanov wrote a small program that saves some important information as an XML string.
An XML string consists of opening and closing tags.
An opening tag begins with an opening angle bracket (<), followed by the tag name — a non-empty lowercase English string followed by a closing angle bracket (>).
Examples of opening tags: <a>, <dog>.
The end tag begins with an opening angle bracket, followed by a forward slash (/), then the tag name — a non-empty string of lowercase Latin letters followed by a closing angle bracket.
Examples of closing tags: </a>, </dog>.
An XML string is correct if it can be obtained according to the following rules:
- An empty string is a valid XML string.
- A and B — valid XML strings, then the string AB obtained by appending string B to the end of string A is also a valid XML string.
- If A — a valid XML string, then the string <X>A</X>, obtained by prepending A the opening tag, and at the end — closing with the same name is also a valid XML string. Here X — any non-empty string of lowercase Latin letters.
For example, the following lines:
<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>
are valid XML strings, and strings such as:
<a></b>
<a><b>
<a><b></a></b>
are not valid XML strings.
Ivanov sent the file with the saved XML string by e-mail to his colleague Petrov. Unfortunately, however, the file got corrupted during the transfer: exactly one character in the string was replaced by some other character.
It is required to write a program that, based on the string that Petrov received, will restore the original XML string that Ivanov sent.
Input: The input file contains a single string that can be made into a valid XML string by replacing exactly one character. The string length is between 7 and 1000, inclusive. The string contains only lowercase Latin letters and the characters "<" (ASCII code 60), ">"(ASCII code 62), and "/"(ASCII code 47).
A line in the input file ends with a newline.
Output: The output file must contain a valid XML string that can be obtained from a string in the input file by replacing exactly one character with another. If there are several answers, you can display any one.
Examples
| # |
Input |
Output |
| 1 |
<a></b> |
<a></a> |
| 2 |
<a><aa> |
<a></a> |
| 3 |
<a><>a> |
<a></a> |
| 4 |
<a/</a> |
<a></a> |
| |
![]()
|
|
Темы:
Stack
A sequence of integers ending in zero is entered. The number 0 is not included in the sequence.
Output the elements of the sequence in reverse order. Use a stack to store data.
Input
A sequence of integers is entered, modulo not exceeding 10000. The input ends when the number 0 is entered. There are no more than 100 numbers in total (not counting zero).
Imprint
Print the elements of this sequence in reverse order, separated by a space.
Examples
| # |
Input |
Output |
| 1 |
1 2 3 4 5 0 |
5 4 3 2 1 |
| |
![]()
|
|
Темы:
Stack
Write a program that converts an arithmetic expression written in infix form to postfix form.
Input
The input is a string representing the infix form of the expression (there are no spaces in the string).
Imprint
Print the postfix form of the given expression, separating each operand and operation from each other by a single space.
Examples
| # |
Input |
Output |
| 1 |
(5+3)*(7+2*4) |
5 3 + 7 2 4 * + * |
| |
![]()
|
Темы:
Stack
Required to determine if a sequence of numbers can be sorted using a stack.
A train has arrived at the cul-de-sac from track 1 (see picture). It is allowed to unhook one or several first cars from the train at once and bring them to a dead end (if you wish, you can even bring the entire train to a dead end at once). After that, take some of the wagons to the side of track 2. Then you can bring a few more wagons to the dead end, and again transport part of the wagons to the side of track 2. And so on, so that each wagon drives from track 1 to the dead end only once, and then once left the dead end on track 2. Entering the dead end from track 2 or leaving the dead end on track 1 is prohibited. You can't get from path 1 to path 2 without entering a dead end.
 It is known in what order the train cars initially go. It is required, using the indicated operations, to make the train cars go in order (first the first, then the second, etc., counting from the head of the train traveling along track 2 away from the dead end). Write a program to determine if it can be done.
Input
Enter number N — the number of cars in the train (\(1<=N<=2000\)). Next are the car numbers in order from the head of the train traveling on track 1 towards the dead end. The cars are numbered with natural numbers from 1 to N, each of which occurs exactly once.
Output
Is it possible to make the cars go in order from 1 to N, counting from the head of the train, when the train takes track 2 from the dead end? If possible, display a message YES. If it is not possible, print NO.
Examples
| # |
Input |
Output |
Note |
| 1 |
3
3 2 1
| YES |
We need to bring the whole train to a dead end, and then take it entirely to the 2nd track |
| 2 |
4
4 1 3 2
|
YES
|
First, you need to bring two wagons to a dead end, one of which will be left in a dead end, and the second — take out to the 2nd track, then bring two more cars to the dead end and take out 3 cars standing at the dead end to the 2nd track |
| 3 |
3
2 3 1
| NO |
|
| |
![]()
|
|
Темы:
Stack
Consider a sequence consisting of round, square, and curly brackets. The program must determine if the given bracket sequence is correct.
The empty sequence is valid. If A – is correct, then the sequences (A), [A], {A} – correct. If A and B – correct sequences, then the sequence AB – correct.
Input
A single line contains a bracket sequence containing no more than 100,000 brackets.
Imprint
If this sequence is correct, then the program should output the string yes, otherwise the string no.
Examples
| # |
Input |
Output |
| 1 |
()[] |
yes |
| |
![]()
|
|
Темы:
Stack
In postfix notation (or reverse Polish notation), the operation is written after two operands. For example, the sum of two numbers A and B is written as A B +. The notation B C + D * means the usual (B + C) * D, and the notation A B C + D * + means A + (B + C) * D. The advantage of postfix notation is that it does not require brackets and additional precedence conventions operators for your reading.
Input
The single line contains an expression in postfix notation containing numbers and operations +, -, *. Numbers and operations are separated by spaces. There can be any number of spaces at the end of the line.
Imprint
It is necessary to display the value of the written expression.
Examples
| # |
Input |
Output |
| 1 |
8 9 + 1 7 - * |
-102 |
| |
![]()
|
|
Темы:
Stack
The warehouse stores containers with N different types of goods. All containers are arranged in N stacks. Each stack can contain containers of any kind of goods (the stack can be initially empty).
The forklift can take the top container from any stack and place it on top of any stack. It is necessary to arrange all containers with the goods of the first type in the first pile, the second type – to the second pile, etc.
The program should display a sequence of actions of the forklift or a message that the task has no solution.
Input
The first line of the input contains one natural number N, not exceeding 500. The next N lines describe stacks of containers: first, the number ki – the number of containers in the stack, followed by ki numbers – types of goods in containers in this stack, from bottom to top. Each stack initially has a maximum of 500 containers (this limit may be violated during container transfer).
Imprint
The program should display a description of the actions of the forklift: for each action, print two numbers – from which pile to take the container and in which pile to put it. (Note that you don't need to minimize the number of forklift operations.) If the problem has no solution, you should print a single number 0. If the containers are initially correctly stacked, then you don't need to output anything.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3
4 1 2 3 2
0
0 |
1 2
1 3
1 2
| Initially, the first stack contains four – below the container with the goods of the first type, above it – with goods of the second type, above it the third, and on top another container with goods of the second type. The second and third piles – empty. |
| |
![]()
|
|
Темы:
Stack
Implement a "stack" data structure. Write a program that describes the stack and simulates how the stack works by implementing all the methods listed here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should print one line. Possible commands for the program:
push n
Push the number n onto the stack (the value of n is given after the command). The program should print ok.
pop
Remove the last element from the stack. The program should output its value.
back
The program should output the value of the last element without removing it from the stack.
size
The program should print the number of elements on the stack.
clear
The program should clear the stack and print ok.
exit
The program should print bye and exit.
Input
Stack management commands are entered in the format described earlier, 1 per line.
It is guaranteed that the set of input commands satisfies the following requirements: the maximum number of elements on the stack at any time does not exceed 100, all pop and back commands are correct, that is, when they are executed, the stack contains at least one element.
Imprint
It is required to display the protocol of work with the stack, 1 message per line
Examples
| # |
Input |
Output |
| 1 |
push 3
push 14
clear
push 1
back
push 2
back
pop
pop
exit |
ok
ok
2
ok
ok
1
ok
2
2
1
1
0
bye |
| |
![]()
|
|
Темы:
Stack
Implement a "stack" data structure. Write a program that describes the stack and simulates how the stack works by implementing all the methods listed here. The program reads a sequence of commands and, depending on the command, performs one or another operation. After executing each command, the program should print one line. Possible commands for the program:
push n
Push the number n onto the stack (the value of n is given after the command). The program should print ok.
pop
Remove the last element from the stack. The program should output its value.
back
The program should output the value of the last element without removing it from the stack.
size
The program should print the number of elements on the stack.
clear
The program should clear the stack and print ok.
exit
The program should print bye and exit.
Before executing the back and pop operations, the program must check whether the stack contains at least one element. If there is a back or pop operation in the input data, and the stack is empty, then the program should output the string error instead of a numeric value.
Input
Stack management commands are entered, one per line
Imprint
The program should output the stack log, one message per line
Examples
| # |
Input |
Output |
| 1 |
size
push 1
push 2
push 3
exit |
0
ok
1
ok
2
ok
3
bye |
| |
![]()
|
|
Темы:
Stack
Prefix sums(minimums, ...)
Besi recently received a set of paints and she wants to paint a long hedge on one side of her pasture. The fence consists of N consecutive 1-meter segments (1≤N≤105). Besi has paints in 26 different colors, which she labeled with letters from 'A' to Z' in ascending order of darkness ('A' is the lightest color, 'Z' is the darkest). Therefore, it can describe the coloring of the hedge as a string of N characters (where each character is one of - from 'A' to Z').
Initially, all segments of the fence are not painted. Besi can paint any continuous range of segments with a single color with a single brush stroke, and she never paints a lighter over a darker one (she can paint a darker over a lighter one).
For example, she can color an initially unpainted segment of length 4 like this:
.... -> BBB. -> BBLL-> BQQL
Limited in time, Besi may leave some consecutive segments unpainted. She is now looking at Q line segment candidates (1≤Q≤105), each given by two integers (a,b) (1≤a≤b≤N) indicating the indexes of the segment endpoints that should stay unpainted.
For each candidate, specify the minimum number of touches required to color all segments outside that range with the desired color, leaving segments inside the range uncolored. Note that Besi doesn't actually color anything, so the answers for each candidate range are independent.
Input
The first line contains N and Q.
The next line contains N representing the desired color for each hedge segment.
Each of the next Q lines contains two space-separated integers a and b representing a range of segments that may not be colored.
Imprint
For each of the Q candidates print the answer on a new line.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
8 2
ABBAABCB
3 6
14
|
4
3 |
In this example, the range exclusion matches the desired pattern. In this example, the BAAB range exclusion requires four touches to colorize, while the ABBA range exclusion requires only three.
.... -> AA.. -> ABBB-> ABCB |
| |
![]()
|