1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
What Has Dirichlet Got to Do with That?
Contest: School Team Contest 1 (Winter Computer School 2010/11)
Difficulty rating: 2000
Tags: dp, games

You all know the Dirichlet principle, the point of which is that if n boxes have no less than n + 1 items, that leads to the existence of a box in which there are at least two items.

Having heard of that principle, but having not mastered the technique of logical thinking, 8 year olds Stas and Masha invented a game. There are a different boxes and b different items, and each turn a player can either add a new box or a new item. The player, after whose turn the number of ways of putting b items into a boxes becomes no less then a certain given number n, loses. All the boxes and items are considered to be different. Boxes may remain empty.

Who loses if both players play optimally and Stas's turn is first?

Input format:
The only input line has three integers a, b, n (1 ≤ a ≤ 10000, 1 ≤ b ≤ 30, 2 ≤ n ≤ 109) — the initial number of the boxes, the number of the items and the number which constrains the number of ways, respectively. Guaranteed that the initial number of ways is strictly less than n.

Output format:
Output "Stas" if Masha wins. Output "Masha" if Stas wins. In case of a draw, output "Missing".

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Note:
In the second example the initial number of ways is equal to 3125.

- If Stas increases the number of boxes, he will lose, as Masha may increase the number of boxes once more during her turn. After that any Stas's move will lead to defeat.
- But if Stas increases the number of items, then any Masha's move will be losing.

Example input:
2 2 10

Example output:
Masha

Example input:
5 5 16808

Example output:
Masha

Editorial:
Pacifist frogs
Contest: School Team Contest 1 (Winter Computer School 2010/11)
Difficulty rating: 1300
Tags: implementation

Thumbelina has had an accident. She has found herself on a little island in the middle of a swamp and wants to get to the shore very much.

One can get to the shore only by hills that are situated along a straight line that connects the little island with the shore. Let us assume that the hills are numbered from 1 to n and the number of a hill is equal to the distance in meters between it and the island. The distance between the n-th hill and the shore is also 1 meter.

Thumbelina is too small to make such jumps. Fortunately, a family of frogs living in the swamp suggests to help her. Each frog agrees to give Thumbelina a ride but Thumbelina should choose only one frog. Each frog has a certain jump length. If Thumbelina agrees to accept help from a frog whose jump length is d, the frog will jump from the island on the hill d, then — on the hill 2d, then 3d and so on until they get to the shore (i.e. find itself beyond the hill n).

However, there is one more problem: mosquitoes also live in the swamp. At the moment they have a siesta, and they are having a nap on some hills. If the frog jumps on a hill with a mosquito the frog will smash it. The frogs Thumbelina has met are pacifists, so they will find the death of each mosquito very much sad. Help Thumbelina choose a frog that will bring her to the shore and smash as small number of mosquitoes as possible.

Input format:
The first line contains three integers n, m and k (1 ≤ n ≤ 109, 1 ≤ m, k ≤ 100) — the number of hills, frogs and mosquitoes respectively. The second line contains m integers di (1 ≤ di ≤ 109) — the lengths of the frogs’ jumps. The third line contains k integers — the numbers of the hills on which each mosquito is sleeping. No more than one mosquito can sleep on each hill. The numbers in the lines are separated by single spaces.

Output format:
In the first line output the number of frogs that smash the minimal number of mosquitoes, in the second line — their numbers in increasing order separated by spaces. The frogs are numbered from 1 to m in the order of the jump length given in the input data.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
5 3 5
2 3 4
1 2 3 4 5

Example output:
2
2 3

Example input:
1000000000 2 3
2 5
999999995 999999998 999999996

Example output:
1
2

Editorial:
Multiplication Table
Contest: School Team Contest 1 (Winter Computer School 2010/11)
Difficulty rating: 1300
Tags: implementation

Petya studies positional notations. He has already learned to add and subtract numbers in the systems of notations with different radices and has moved on to a more complicated action — multiplication. To multiply large numbers one has to learn the multiplication table. Unfortunately, in the second grade students learn only the multiplication table of decimals (and some students even learn it in the first grade). Help Petya make a multiplication table for numbers in the system of notations with the radix k.

Input format:
The first line contains a single integer k (2 ≤ k ≤ 10) — the radix of the system.

Output format:
Output the multiplication table for the system of notations with the radix k. The table must contain k - 1 rows and k - 1 columns. The element on the crossing of the i-th row and the j-th column is equal to the product of i and j in the system of notations with the radix k. Each line may have any number of spaces between the numbers (the extra spaces in the samples are put for clarity).

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
10

Example output:
1  2  3  4  5  6  7  8  9
2  4  6  8 10 12 14 16 18
3  6  9 12 15 18 21 24 27
4  8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81

Example input:
3

Example output:
1  2
2 11

Editorial:
Spelling Check
Contest: School Team Contest 1 (Winter Computer School 2010/11)
Difficulty rating: 1500
Tags: hashing, implementation, strings

Petya has noticed that when he types using a keyboard, he often presses extra buttons and adds extra letters to the words. Of course, the spell-checking system underlines the words for him and he has to click every word and choose the right variant. Petya got fed up with correcting his mistakes himself, that’s why he decided to invent the function that will correct the words itself. Petya started from analyzing the case that happens to him most of the time, when all one needs is to delete one letter for the word to match a word from the dictionary. Thus, Petya faces one mini-task: he has a printed word and a word from the dictionary, and he should delete one letter from the first word to get the second one. And now the very non-trivial question that Petya faces is: which letter should he delete?

Input format:
The input data contains two strings, consisting of lower-case Latin letters. The length of each string is from 1 to 106 symbols inclusive, the first string contains exactly 1 symbol more than the second one.

Output format:
In the first line output the number of positions of the symbols in the first string, after the deleting of which the first string becomes identical to the second one. In the second line output space-separated positions of these symbols in increasing order. The positions are numbered starting from 1. If it is impossible to make the first string identical to the second string by deleting one symbol, output one number 0.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
abdrakadabra
abrakadabra

Example output:
1
3

Example input:
aa
a

Example output:
2
1 2

Editorial:
Testing
Contest: School Team Contest 1 (Winter Computer School 2010/11)
Difficulty rating: 2600

You take part in the testing of new weapon. For the testing a polygon was created. The polygon is a rectangular field n × m in size, divided into unit squares 1 × 1 in size. The polygon contains k objects, each of which is a rectangle with sides, parallel to the polygon sides and entirely occupying several unit squares. The objects don't intersect and don't touch each other.

The principle according to which the weapon works is highly secret. You only know that one can use it to strike any rectangular area whose area is not equal to zero with sides, parallel to the sides of the polygon. The area must completely cover some of the unit squares into which the polygon is divided and it must not touch the other squares. Of course the area mustn't cross the polygon border. Your task is as follows: you should hit no less than one and no more than three rectangular objects. Each object must either lay completely inside the area (in that case it is considered to be hit), or lay completely outside the area.

Find the number of ways of hitting.

Input format:
The first line has three integers n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 90) — the sizes of the polygon and the number of objects on it respectively. Next n lines contain m symbols each and describe the polygon. The symbol "*" stands for a square occupied an object, whereas the symbol "." stands for an empty space. The symbols "*" form exactly k rectangular connected areas that meet the requirements of the task.

Output format:
Output a single number — the number of different ways to hit a target.

Constraints:
Time limit: 2.0 s
Memory limit: 64.0 MB

Example input:
3 3 3
*.*
...
*..

Example output:
21

Example input:
4 5 4
.*.**
...**
**...
...**

Example output:
38

Editorial:
Goshtasp, Vishtasp and Eidi
Contest: Unknown Language Round 2
Difficulty rating: 1800
Tags: *special, greedy, math

Goshtasp was known to be a good programmer in his school. One day Vishtasp, Goshtasp's friend, asked him to solve this task:

Given a positive integer n, you should determine whether n is rich.

The positive integer x is rich, if there exists some set of distinct numbers a1, a2, ..., am such that $$\sum_{i=1}^{m}a_{i}=x$$. In addition: every ai should be either a prime number, or equal to 1.

Vishtasp said that he would share his Eidi 50 / 50 with Goshtasp, if he could solve the task. Eidi is money given to children for Noruz by their parents and/or relatives.

Goshtasp needs to solve this problem to get money, you need to solve it to get score!

Input format:
Input contains a single positive integer n (1 ≤ n ≤ 10000).

Output format:
If the number is not rich print 0. Otherwise print the numbers a1, ..., am. If several solutions exist print the lexicographically latest solution. Answers are compared as sequences of numbers, not as strings.

For comparing two sequences a1, ..., am and b1, ..., bn we first find the first index i such that ai ≠ bi, if ai < bi then a is lexicographically earlier and if bi < ai then b is lexicographically earlier. If m ≠ n we add zeroes at the end of the smaller sequence (only for the moment of comparison) and then perform the comparison.

You do not need to minimize the number of elements in sequence (i.e. m). You just need to print the lexicographically latest solution.

See samples to find out how to print the sequence.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
11

Example output:
11=11

Example input:
545

Example output:
541+3+1=545

Editorial:
INI-file
Contest: Unknown Language Round 2
Difficulty rating: 2200
Tags: *special, implementation

The INI file format is a de facto standard for configuration files. INI files are simple text files with a basic structure. They are commonly associated with Microsoft Windows, but are also used on other platforms.

Each line in INI-file stands for key-value mapping or defines new section. A key-value line has a format "key=value",where key — is the name of some property, and value — it's value. It is possible that it will be spaces from the both sides of key and/or value, the spaces should be ignored.

A section line has a format "[section]". It means that all key-value lines after it define properties of the specified section. Of cause, the following section line changes the current section. A section line may have spaces around any of brackets.

Also you should ignore comment lines — the first non-space character of comment line is ";".

You task is to write the program which will format given INI-file in a special way:

- first, print key-value lines which do not belong to any section;
- print all the sections in the lexicographical (alphabetical) order of their names;
- inside each of two previous items, order key-value lines lexicographically by "key";
- if there are more than one key-value lines with the same key inside a single section (or outside any sections), leave only one line (which appears later in the input data);
- remove all redundant spaces and lines.

Input format:
The first line contains single integer n (1 ≤ n ≤ 510) — the number of lines in given INI-file.

The rest of the input contains a valid INI-file in n lines. Values of section, key and value contain only Latin letters, digits, "." and/or "-".

Each line has length not exceeding 255 characters and not less than 1 character. The total length of all the lines does’t exceed 10000.

Output format:
Print formatted INI-file.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
11
a= 1
b=a
a = 2
; comment
[z]
1=2
[y]
2=3
[z]
2=1
[w]

Example output:
a=2
b=a
[w]
[y]
2=3
[z]
1=2
2=1

Editorial:
Extraordinarily Nice Numbers
Contest: Unknown Language Round 2
Difficulty rating: 1200
Tags: *special, math

The positive integer a is a divisor of the positive integer b if and only if there exists a positive integer c such that a × c = b.

King Astyages thinks a positive integer x is extraordinarily nice if the number of its even divisors is equal to the number of its odd divisors.

For example 3 has two positive divisors 3 and 1, both of which are odd, so 3 is not extraordinarily nice. On the other hand 2 is only divisible by 2 and 1, so it has one odd and one even divisor. Therefore 2 is extraordinarily nice.

Given a positive integer x determine whether it's extraordinarily nice.

Input format:
The input contains only a single integer x (1 ≤ x ≤ 103).

Output format:
Write a single yes or no. Write yes if the number is extraordinarily nice and no otherwise.

You don't need to care about capital or small letters. The output is case-insensitive.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2

Example output:
yes

Example input:
3

Example output:
no

Editorial:
Perse-script
Contest: Unknown Language Round 2
Difficulty rating: 2300
Tags: *special, expression parsing

Two good friends were trying to make a new programming language called Perse-script.

The most important part of this language is strings. A string in Perse-script is put between characters "

So for example "Hello" is a string. But Hello is a variable name or a keyword, which are not considered in this problem.

Perse-script is function-based. So there are no operators in this language. For example for summing two numbers you have to write sum(a,b) and not a+b.

There are several functions for working on strings. These include:

- concat(x,y) is a function which gets two strings x and y and puts y at the end of x and returns the result. For example concat("Hello","World") returns "HelloWorld".
- reverse(x) gets a single string x and reverses it. For example reverse("Hello") returns "olleH".
- substr(x,a,b) gets a string x and two integers a and b (1 ≤ a ≤ b ≤ n, where n is the length of x). And returns the substring of x between indexes a and b, inclusive. For example substr("Hello",2,4) returns "ell".
- substr(x,a,b,c) is another version of substr which works just like the last one but c is the step of adding. c is positive. For example substr("HelloWorld",1,10,2) returns "Hlool". This substr means that you put the ath character , and then every cth character until you reach b.

You're going to manipulate the string part of Perse-script. Given a string expression, you should print its result. It is guaranteed that the expression contains only strings shown by characters " and the above functions.

Commands in Perse-script are case-insensitive. So to call substr function you can write SUBsTr(). But you can't print as the result "hElLo" instead of printing "Hello".

See the samples for more information.

Input format:
A single line containing the correct expression. It is guaranteed that the total length of this expression does not exceed 103 and that all the integers used in it are less than or equal to 100 by absolute value. The given string is non-empty.

All strings in the input which are placed between "s consist of uppercase and lowercase Latin letters only.

Output format:
Print in single line the resulting string. It is guaranteed that an answer exists and that the length of the answer does not exceed 104. It is guaranteed that the answer is non-empty.

Constraints:
Time limit: 7.0 s
Memory limit: 256.0 MB

Example input:
"HelloWorld"

Example output:
"HelloWorld"

Example input:
REVerse(substr("helloworld",1,5))

Example output:
"olleh"

Editorial:
Ali goes shopping
Contest: Unknown Language Round 2
Difficulty rating: 1800
Tags: *special, brute force, strings

Ali Koochooloo is going to buy new clothes since we're reaching Noruz, the ancient Persian festival and the beginning of new Persian year.

When Ali entered a shop, he saw that the shopkeeper was a programmer and since there is no money in programming he had changed his career. The shopkeeper told Ali that he can buy anything for free if he could answer a simple question in 10 seconds. But to see the question Ali has to pay 3 tomans.

Ali agreed instantly and the shopkeeper handed him a piece of paper containing the task. The task was indeed very simple. It said:

Let string A be ababababababab. Which non-empty substring of A is repeated the most times in it?

Ali answered fast. He said the answer is a. But the shopkeeper said that Ali is wrong and asked him to read the rest of statement:

If several substrings have the maximal repeat time, then the substring with maximal length would be the answer, in case of a tie the alphabetically latest substring will be chosen.

So the answer is ab.

Now Ali wants us to solve this problem for different strings. We don't have a great advantage over Ali, we just have a computer and a weird language.

Input format:
The single line consisting of a string A. It is non-empty, made of lower-case Latin letters and contains at most 30 characters.

Output format:
The single line contains the answer.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
abab

Example output:
ab

Example input:
abcd

Example output:
abcd

Editorial:
Oil
Contest: Unknown Language Round 2
Difficulty rating: 1900
Tags: *special, greedy, math

After the nationalization of the oil industry, Dr. Mosaddegh wants to dig some oil wells to extract all the oil in Persian Gulf. But Persian Gulf is huge and has an infinite amount of oil. So Dr. Mosaddegh works only on a rectangular plane of size n × m of the Persian Gulf. Each of the cells in this rectangle either contains an infinite amount of oil or nothing.

Two cells are considered adjacent if and only if they have a common edge, a path is a sequence c1, c2, ..., cx of cells so that all of them contain oil and for each i, ci is adjacent to ci - 1 and ci + 1 (if they exist). Two cells are considered connected to each other if and only if there exists a path between them. If we dig a well in a certain cell, we can extract oil from all the cells that are connected to it by oil paths. It is not allowed to dig wells on empty cells.

Dr. Mosaddegh also knows that in Persian Gulf, the empty cells form rows and columns. I. e. if some cell is empty, then it's column is completely empty or it's row is completely empty, or both.

Help Dr. Mosaddegh find out how many wells he has to dig to access all the oil in that region.

Input format:
In the first line there are two positive integers n and m (1 ≤ n, m ≤ 100).

In the second line there is an integer t (0 ≤ t ≤ n), the number of empty rows. t distinct positive integers follow, these are the numbers of empty rows and are in range [1, n].

In the second line there is an integer s (0 ≤ s ≤ m) that shows the number of columns not having any oil. s distinct positive integers follow, these are the numbers of empty columns and are in range of [1, m].

Note that rows are numbered from 1 to n (from top to bottom) and columns are numbered from 1 to m (from left to right).

Output format:
A single integer, the minimum number of wells that Dr. Mossadegh has to dig.

This is actually finding how many regions are made by removing the given rows and columns.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 3
1 2
1 2

Example output:
2

Example input:
4 4
2 2 3
3 2 3 1

Example output:
2

Editorial:
Fibonacci army
Contest: Unknown Language Round 2
Difficulty rating: 1000
Tags: *special, dp

King Cambyses loves Fibonacci numbers. He has several armies. Today he wants to make a new army for himself and he wants the number of men in this army to be the n-th Fibonacci number.

Given n you should find n-th Fibonacci number. The set of Fibonacci numbers start with f0 = f1 = 1 and for each i ≥ 2, fi = fi - 1 + fi - 2.

Input format:
Input contains a single integer n (1 ≤ n ≤ 20).

Output format:
Write a single integer. The n-th Fibonacci number.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2

Example output:
2

Example input:
1

Example output:
1

Editorial:
Reverse It!
Contest: Unknown Language Round 2
Difficulty rating: 1600
Tags: *special, implementation

The 14th of March was the international day of mathematics, because of number π = 3.1415926...

In the occasion of this day Goofy Nephews Unity Organization (GNU) wants to publish the fastest program in math at 1:59:26 AM.

Now the time is 1:11:11 AM and the project team haven't checked their program yet. Because of shortage of time they want to check their program with some queries. So they hired Hormizd (one of the greatest programmers in world) to write a tester for GNU's new program. Because Hormizd has much more important things to do, he wants you to write a small part of tester and it is reversing the numbers. Help him before 1:59:26.

We can reverse numbers easily. For example by reversing 1234 we get 4321.

Note, that if the integer is negative then its reverse would be also negative. For example reverse of  - 123 is  - 321.

Also, you have to delete all the leading zeroes before and after the reverse.

Given an integer you have to help Hormizd reverse it.

Input format:
The first line contains a single integer n. It is less than 101000 by it's absolute value. This integer may have leading zeros. If it had leading zeros you should first omit them and print the reverse of remaining digits. It's guaranteed that input contains less than 10001 characters.

Output format:
Output a single integer, the reverse of the given number. You have to omit leading zeros in the output.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
23

Example output:
32

Example input:
-032

Example output:
-23

Editorial:
Goofy Numbers
Contest: Unknown Language Round 2
Difficulty rating: 1500
Tags: *special, implementation

The non-negative integer a is a divisor of the non-negative integer b if and only if there exists a positive integer c such that a × c = b.

Some numbers are really interesting. Commander Surena defines some interesting properties for non-negative integers:

- An integer is happy if it is divisible by at least one of its digits and not by all of them.
- An integer is happier if it is divisible by all of its digits.
- An integer is upset if it's divisible by none of its digits.

Surena asks you to find out if a given number is happy, happier or upset.

Input format:
Input contains a single non-negative integer n (1 ≤ n ≤ 108).

Output format:
Write on a single line the type of the integer: happy, happier or upset. Print the type in lowercase letters.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the second test 29994 is only divisible by 2.

In the third test 23 is a prime number.

Example input:
99

Example output:
happier

Example input:
29994

Example output:
happy

Editorial: