Shkolnik about Olympiad programming
Hello, Habr!
The ninth-grader, the prize-winner of the regional stage of the All-Russian Olympiad in Informatics, writes you. Recently, I began to notice that habrazhiteli increased interest in programming contests. As their active participant, I will try to answer all the questions, tell about my path, give examples of real tasks that I remember.
About learning
I study at school with profound studying of physics, mathematics and computer science.
What is this school, how to study in it and how to enter it?
The selection takes place in two stages. The first is an exam in physics and mathematics. After him, some of the lucky ones get an interview where they are required to solve several olympiad problems in mathematics. And only after that the most intelligent and successful become students.
Learning is very hard and difficult. Teachers require perfect knowledge of almost all subjects. At the parents' meeting, they said: “At the beginning of the training, absolutely all students roll down to twos, even honors pupils. Those who start to really learn get good grades. The rest are eliminated. I had the most problems with the Russian language and literature, no matter how strange it was.
Learning is very hard and difficult. Teachers require perfect knowledge of almost all subjects. At the parents' meeting, they said: “At the beginning of the training, absolutely all students roll down to twos, even honors pupils. Those who start to really learn get good grades. The rest are eliminated. I had the most problems with the Russian language and literature, no matter how strange it was.
I have always been attracted to programming (what is it, I understood already in 4th grade). I was very happy when Pascal and various computational algorithms began to be taught in the seventh grade. It was then that I wrote the first “Hello World!”, Euclidean algorithm; studied conditional operators, cycles, arrays.
From the eighth grade, teachers were invited to electives in computer science, where we studied graphs, array sorting algorithms, and more.
Tasks
Let's look at a completely typical task for novice programmer-programmers.
Five five - twenty five!
(Time: 1 sec. Memory: 16 MB Complexity: 8%)
Vasya and Petya study at school in the same class. Recently, Petya told Vasya about a clever method of squaring natural numbers ending in figure 5. Now Vasya can easily squaring two-digit (and even some three-digit) numbers ending in 5. The method is as follows: for squaring numbers, ending with 5, it is enough to multiply the number obtained from the original one by crossing out the last five by the next number in order, then all that remains is to add “25” to the resulting result to the right. For example, in order to square the number 125, it suffices to multiply 12 by 13 and add 25, i.e. attributing to the number 12 * 13 = 156 the number 25, we get the result 15625, i.e. 1252 = 15625. Write a program, raising the number ending in 5, in the square so that Vasya could test his skills.
Input data
The single line of the input file INPUT.TXT contains one positive integer A, ending in 5, not exceeding 4 * 10 ^ 5.
Output
In the output file OUTPUT.TXT output one positive integer - A2 without leading zeros.
Examples:
INPUT.TXT
five
75
4255
OUTPUT.TXT
25
5625
18105025
(Time: 1 sec. Memory: 16 MB Complexity: 8%)
Vasya and Petya study at school in the same class. Recently, Petya told Vasya about a clever method of squaring natural numbers ending in figure 5. Now Vasya can easily squaring two-digit (and even some three-digit) numbers ending in 5. The method is as follows: for squaring numbers, ending with 5, it is enough to multiply the number obtained from the original one by crossing out the last five by the next number in order, then all that remains is to add “25” to the resulting result to the right. For example, in order to square the number 125, it suffices to multiply 12 by 13 and add 25, i.e. attributing to the number 12 * 13 = 156 the number 25, we get the result 15625, i.e. 1252 = 15625. Write a program, raising the number ending in 5, in the square so that Vasya could test his skills.
Input data
The single line of the input file INPUT.TXT contains one positive integer A, ending in 5, not exceeding 4 * 10 ^ 5.
Output
In the output file OUTPUT.TXT output one positive integer - A2 without leading zeros.
Examples:
INPUT.TXT
five
75
4255
OUTPUT.TXT
25
5625
18105025
')
Requirements
The Olympiad is required to write a program in one of the accepted languages ​​(usually this set consists of Pascal (I write myself, there have never been any problems), Delphi, C ++, Java, Visual Basic, recently added C #, Python). After that, the source file is sent to the sandbox system, where it is compiled and executed on a group of tests. For each test, the participant of the Olympiad receives a certain score, which then add up. After the Olympiad, the results are visible to everyone. The greater the total score - the higher the place.
It is worth noting that usually managed systems (Java, C #) are poorly processed by testing systems. My friend personally at the regional stage received 0 points on three of four tasks due to a runtime error (he wrote in C #), although everything was checked normally. Neither I nor he understood what to do in this case; On appeal, the jury simply shrugged.
Risks
What can you lose? There are 7 types of errors:
Hidden text
Strong answer
Incorrect unswer. The result of the program does not match the response of the jury
Invalid output format or algorithmic error in the program
Time limit exceeded
The time limit specified in the task is exceeded. The program runs longer than the set time.
Ineffective solution or algorithmic error in the program
Presentation Error
No output file OUTPUT.TXT
File not created, invalid file name or program crash before opening output file
Compilation error
Compilation error. Compilation result in no executable file.
Syntax error in the program or the file extension is incorrect. It is possible that when implementing in Java, a class other than Main was used.
Memory limit exceeded
The memory limit specified in the task is exceeded. The program uses more than the specified amount of memory.
Inefficient algorithm or irrational memory use
Runtime error
Execution error. The program has completed with a non-zero return code. In this case, the result of the work is not checked.
Possibly, the program encountered a call to a non-existent element of the array, division by zero, etc. Perhaps the C ++ program does not end with the “return 0” statement or for some other reason returned a non-zero return code.
Incorrect unswer. The result of the program does not match the response of the jury
Invalid output format or algorithmic error in the program
Time limit exceeded
The time limit specified in the task is exceeded. The program runs longer than the set time.
Ineffective solution or algorithmic error in the program
Presentation Error
No output file OUTPUT.TXT
File not created, invalid file name or program crash before opening output file
Compilation error
Compilation error. Compilation result in no executable file.
Syntax error in the program or the file extension is incorrect. It is possible that when implementing in Java, a class other than Main was used.
Memory limit exceeded
The memory limit specified in the task is exceeded. The program uses more than the specified amount of memory.
Inefficient algorithm or irrational memory use
Runtime error
Execution error. The program has completed with a non-zero return code. In this case, the result of the work is not checked.
Possibly, the program encountered a call to a non-existent element of the array, division by zero, etc. Perhaps the C ++ program does not end with the “return 0” statement or for some other reason returned a non-zero return code.
Olympics
How is the All-Russian Olympiad in Informatics?
I went through only 5 stages: 8-9 classes at school, 8-11 classes at school, municipal stage, distance tour of regional Olympiad, regional Olympiad. Next is the all-Russian tour, but I, unfortunately, did not hit it. Now I will tell you about the tasks that I really liked.
Stage among high school students
During the tour among the 8-11 classes there was a task “Polynomial Hash Functions” the condition of which was recorded on two A5 pages. This condition provided a brief information about the hash functions, their history, one such function was proposed. The task was to calculate it for an array of input data. We were frightened by a very scary name, complicated terminology, the recording of the sum with its badge (the one that looks like the letter E) and as a result very few people started to solve it at all. Unfortunately, I cannot find the condition now.
Municipal stage
The municipal stage turned out just suicidal in complexity.
Here is the task from there
B. Beaver
Time Limit: 1 second per test
Memory limits: 64 MB
Beaver is going to build a cascade of dams and a cozy hut in the bed of a narrow river. It so happened that the river flows along a perfectly straight trajectory, and the width of the river is so small that we can neglect it in the framework of this task. On the banks of the river are trees that the beaver can use for construction. Scientists decided to find out how optimally the beaver chooses places for the construction of dams and huts in terms of the minimum total distance to which the trees must be moved.
Write a program that, according to the given coordinates of the trees relative to the beginning of the straight stretch of the river, if we take the axis of a co-directional flow, determines the coordinates of the objects corresponding to the minimum total distance to which the trees must be transferred.
Input format:
The first line of the input data contains a single positive integer 1 <= T <= 10 - the number of test blocks following one after another. The first line of each test block contains two positive integers 1 <= N <= 1000, 0 <= M <= 10, 0 <= L <= 100 - respectively, the number of trees growing on the banks of the river, the number of trees required for construction one object and the number of objects that need to be built. Each of the following N lines contains a single positive real number — the distance in meters from the beginning of the straight stretch of the river (the highest stream) to the place where the corresponding tree grows. It is known that there are enough trees to build all the objects (N> = M * L)
Output Format:
For each test block, in a separate line, it is necessary to display a single number — the sum of the coordinates of the places in which the objects are to be erected, so that the total distance that the trees need to be transferred for construction is minimal, indicating three exact signs after the decimal separator.
Sample input and output:
Input data
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
one
2
Output
7.300
1,000
Time Limit: 1 second per test
Memory limits: 64 MB
Beaver is going to build a cascade of dams and a cozy hut in the bed of a narrow river. It so happened that the river flows along a perfectly straight trajectory, and the width of the river is so small that we can neglect it in the framework of this task. On the banks of the river are trees that the beaver can use for construction. Scientists decided to find out how optimally the beaver chooses places for the construction of dams and huts in terms of the minimum total distance to which the trees must be moved.
Write a program that, according to the given coordinates of the trees relative to the beginning of the straight stretch of the river, if we take the axis of a co-directional flow, determines the coordinates of the objects corresponding to the minimum total distance to which the trees must be transferred.
Input format:
The first line of the input data contains a single positive integer 1 <= T <= 10 - the number of test blocks following one after another. The first line of each test block contains two positive integers 1 <= N <= 1000, 0 <= M <= 10, 0 <= L <= 100 - respectively, the number of trees growing on the banks of the river, the number of trees required for construction one object and the number of objects that need to be built. Each of the following N lines contains a single positive real number — the distance in meters from the beginning of the straight stretch of the river (the highest stream) to the place where the corresponding tree grows. It is known that there are enough trees to build all the objects (N> = M * L)
Output Format:
For each test block, in a separate line, it is necessary to display a single number — the sum of the coordinates of the places in which the objects are to be erected, so that the total distance that the trees need to be transferred for construction is minimal, indicating three exact signs after the decimal separator.
Sample input and output:
Input data
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
one
2
Output
7.300
1,000
Solve the problem if the object is one simple enough. But when there are more objects, you have to apply a rather complicated programming section, “Dynamic Programming”. The teacher, who led our electives, admitted that he poorly imagines how to solve this problem (with joint efforts, we derived the value that needs to be minimized, just plotting a few graphs, do not even ask what this value is - I safely forgot it).
As a result, the task for the full score was solved only by one participant of the Olympiad.
And here is another problem, the decision of the jury on which was revised (from the same municipal stage):
A. Albatross
Time Limit: 1 second per test
Memory limits: 64 MB
Albatross can make long flights, overcoming long distances over the ocean. Ornithologists decided to determine how many kilometers an albatross can fly without visiting the land. To this end, a flotilla of floating research laboratories spread out over the ocean and recorded data on the studied individual to which the radio tag was attached. Scientists record the time and current coordinates of the place where they found the albatross.
Write a program that determines the distance that the albatross traveled during the experiment, assuming that in the observation zone our planet is an ideal ball with a radius of 6366.197 kilometers.
Input format:
The first line of the input data contains a single positive integer 1 <= T <= 10 - the number of test blocks following one after another. The first line of each test block contains a single positive integer 2 <= N <= 1000, the number of records of the appearance of the albatross. Each of the following N lines contains twelve integer non-negative numbers (0 <= d1 <= 90, 0 <= m1 <= 90, 0 <= s1 <= 90, 0 <= d2 <= 90, 0 <= m2 < = 90, 0 <= s2 <= 90, 0 <= h <= 23, 0 <= mt <= 59, 0 <= sec <= 59, 1 <= dd <= 31, 1 <= mm <= 12 , 2000 <= yy <= 2012) - the degrees of the minute and second of northern latitude, degrees, minutes and seconds of the western longitude, respectively, of the place where the floating research laboratory noticed an albatross; time in the format of hours, minutes, seconds and the date of observation in the format of day, month, year.
Output Format:
For each of the test blocks in a separate line, you must display a single integer - the distance that the albatross has covered, rounded to the nearest even integer number.
Sample input and output:
Input data
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Output
four
2
Time Limit: 1 second per test
Memory limits: 64 MB
Albatross can make long flights, overcoming long distances over the ocean. Ornithologists decided to determine how many kilometers an albatross can fly without visiting the land. To this end, a flotilla of floating research laboratories spread out over the ocean and recorded data on the studied individual to which the radio tag was attached. Scientists record the time and current coordinates of the place where they found the albatross.
Write a program that determines the distance that the albatross traveled during the experiment, assuming that in the observation zone our planet is an ideal ball with a radius of 6366.197 kilometers.
Input format:
The first line of the input data contains a single positive integer 1 <= T <= 10 - the number of test blocks following one after another. The first line of each test block contains a single positive integer 2 <= N <= 1000, the number of records of the appearance of the albatross. Each of the following N lines contains twelve integer non-negative numbers (0 <= d1 <= 90, 0 <= m1 <= 90, 0 <= s1 <= 90, 0 <= d2 <= 90, 0 <= m2 < = 90, 0 <= s2 <= 90, 0 <= h <= 23, 0 <= mt <= 59, 0 <= sec <= 59, 1 <= dd <= 31, 1 <= mm <= 12 , 2000 <= yy <= 2012) - the degrees of the minute and second of northern latitude, degrees, minutes and seconds of the western longitude, respectively, of the place where the floating research laboratory noticed an albatross; time in the format of hours, minutes, seconds and the date of observation in the format of day, month, year.
Output Format:
For each of the test blocks in a separate line, you must display a single integer - the distance that the albatross has covered, rounded to the nearest even integer number.
Sample input and output:
Input data
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Output
four
2
A rather simple task: it is necessary to sort the values ​​by the date of the appearance of the Albatross, calculate the length of each arc between two points, and then add them all. The decision makes an assumption that allows the use of the Pythagorean theorem.
But why was the decision revised? Take a look at the range of minutes and seconds.
0 <= m1 <= 90, 0 <= s1 <= 90
You probably naively suggested that 60 degrees in one degree? Or that in one minute 60 seconds? Haha “90” is clearly written here.
The tests were made with the translation in mind: in one degree 60 minutes, in one minute 60 seconds. This disgrace was successfully challenged by our teachers.
The most annoying thing is that even the example turned out to be wrong.
As a result, the task was not solved, in my opinion, by no one.
The full text of the municipal stage can be found here .
Remote tour
The tasks of the remote tour were much more interesting. I remember two tasks.
Here is the first
G. Hero of the day
Input / output: standard
Time Limit: 1 second
The Perm Velikaya media holding tracks the messages of bloggers from the Perm region and every day tries to find out who is the most popular in the posts in order to include this person in the traditional “Hero of the Day” rubric.
For each entry that is included in the tracking list, we know the number of views and the people mentioned in it. Write a program that determines the person for whom the total number of views for records where he is mentioned is maximized.
Input format:
The first line of the input data contains a single integer 1 <= L <= 10000 - the number of records that hit the review for the current day. Each of the following lines first indicates a number — the number of views of the corresponding record and then the names of the people mentioned in the record. Names and surnames consist of letters of the English alphabet, the number, and also all adjacent words are separated from each other by exactly one space. The total length of the string is no more than 200 characters.
Output Format:
In the only line of the output data you need to display the name and surname of the person whose records with the mention of which scored the most views. If there are several such people, one must be brought out who goes before the others alphabetically.
Examples of input and output data:
Input data
one
100500 John Travolta John Lennon
five
5 Vasya Pupkin Sergey Syroezhkin
10 Harry Potter
5 Garry Potter Vasya Pupkin
5 Sergey Syroezhkin
12341234463456234123466543342 Arnold Schwarzenegger
Output
John lennon
Arnold Schwarzenegger
Input / output: standard
Time Limit: 1 second
The Perm Velikaya media holding tracks the messages of bloggers from the Perm region and every day tries to find out who is the most popular in the posts in order to include this person in the traditional “Hero of the Day” rubric.
For each entry that is included in the tracking list, we know the number of views and the people mentioned in it. Write a program that determines the person for whom the total number of views for records where he is mentioned is maximized.
Input format:
The first line of the input data contains a single integer 1 <= L <= 10000 - the number of records that hit the review for the current day. Each of the following lines first indicates a number — the number of views of the corresponding record and then the names of the people mentioned in the record. Names and surnames consist of letters of the English alphabet, the number, and also all adjacent words are separated from each other by exactly one space. The total length of the string is no more than 200 characters.
Output Format:
In the only line of the output data you need to display the name and surname of the person whose records with the mention of which scored the most views. If there are several such people, one must be brought out who goes before the others alphabetically.
Examples of input and output data:
Input data
one
100500 John Travolta John Lennon
five
5 Vasya Pupkin Sergey Syroezhkin
10 Harry Potter
5 Garry Potter Vasya Pupkin
5 Sergey Syroezhkin
12341234463456234123466543342 Arnold Schwarzenegger
Output
John lennon
Arnold Schwarzenegger
It was after this task that I got the idea of ​​a “dictionary”, a data type with a convenient search for people. If anyone is interested, I will write in the comments, you can ask in the LS, but I feel that this is still a bicycle.
You need to make a list of people with a total number of views (look at the person with the Arnold Schwarzenegger ID, a long arithmetic is required), and then just select the right person from our list. To simplify the algorithm, our eleventh-graders used a hash function for the name (the sum of all ASCII character numbers in the name), which significantly accelerated the work of the program, the collisions turned out to be small.
Second task or archiving task
V. Great archiver
Input / output: standard
Time Limit: 1 second
Robots on the planet love automatic word processing. For this, robots have introduced a special post of the Great Archiver. It is the responsibility of the Great Archiver to compile a list of all the words in the text and replace the words with a number indicating the number of this word in the list.
Write a program that performs the functions of the Great Archiver.
Input format:
The only line of input data contains a string no longer than a million characters, consisting of lowercase and capital letters of the English alphabet and spaces. Any two adjacent words in the text are separated by exactly one space. Words are considered the same if they are equal in terms of comparing strings, with lowercase and uppercase letters considered different.
Output Format:
In a single line of output data, you must display a sequence of numbers of words of the text, and the words in the list should be ordered in the order of their appearance in the text. The numbering of words should begin with one.
Examples of input and output data:
Input data
To be or not to be
Why do you cry?
Output
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Explanation of examples of input and output data: the text in the second example does not contain line feeds and carriage returns.
Input / output: standard
Time Limit: 1 second
Robots on the planet love automatic word processing. For this, robots have introduced a special post of the Great Archiver. It is the responsibility of the Great Archiver to compile a list of all the words in the text and replace the words with a number indicating the number of this word in the list.
Write a program that performs the functions of the Great Archiver.
Input format:
The only line of input data contains a string no longer than a million characters, consisting of lowercase and capital letters of the English alphabet and spaces. Any two adjacent words in the text are separated by exactly one space. Words are considered the same if they are equal in terms of comparing strings, with lowercase and uppercase letters considered different.
Output Format:
In a single line of output data, you must display a sequence of numbers of words of the text, and the words in the list should be ordered in the order of their appearance in the text. The numbering of words should begin with one.
Examples of input and output data:
Input data
To be or not to be
Why do you cry?
Output
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Explanation of examples of input and output data: the text in the second example does not contain line feeds and carriage returns.
A fairly simple compression algorithm (I do not remember what is called). It was interesting to implement. I solved this problem by creating an array of words, adding the first word there. Then he read every next word, checked if it was in the array. If it was, I wrote down the word number in the output stream; otherwise, I added it to the array, wrote down the number.
In principle, my decision did not receive a full score.
The full text of the tasks can be found here .
In the distance round, I took 1st place among ninth graders.
Regional stage
At the regional stage was not so fun, there were two tours. I was afraid of failing school and not going through to the next stage, ill showing our school. Therefore, the tasks were perceived not so fun and pleasant. In general: I did not remember anything from there, but I received the coveted diploma. And the conditions I could not find.
On the second day, representatives of the local company “Prognoz” came to us, played with us in “What? Where? When? ”, Had a quiz. The winners were given prizes.
Training
How did I prepare?
The answer is quite simple: I have good teachers. It was interesting to me and I enjoyed all that was happening. I diligently prepared and achieved what I wanted.
What to do if it is also interesting for you and you want to take part in all this?
- There are systems to prepare students for programming olympiads, they have a test system and a lot of conditions with solutions. As far as I understand, registration is required on all such systems. I prepared with the help of two:
- acmp.ru There are quite a lot of tasks of varying complexity, the “Olympiad Course” section is also interesting.
- http://acm.timus.ru/ A bunch of tasks from various Olympiads, some in English. In the section http://acm.timus.ru/offline , we conducted remote and regional stages.
- There are online olympiads, I participated in only one: NetOI from Ukrainians. Review this: HARDKOR !!! Further the second round did not pass. The code must be written terribly optimally (I do not know how), for each test there are individual conditions (twice the time of the jury program).
What next?
Saying this, I mean the question of how adaptable olympiadniki work in real conditions.
Although I have not worked yet in the IT industry, but I think that the Olympiads are in no way adapted to real work. At such olympiads, it is required to be able to quickly invent the “bicycle”, to know the algorithms well. My friend and I are engaged in writing small games and I understand that it is much more important to be able to choose the right technology for your goals, to be able to find a ready-made solution to speed up development, “No bicycles are needed.” Correct me if it is not.
If anyone is interested in what I want in life: in fact, I don’t really like IT and computer science, my dream is to study theoretical physicist and do research. And since in the Russian Federation with this problem, I plan to go to Canada or the United States.
I will accept any wishes in the drug or in the comments. I hope this article did not work out long. I hope it was interesting for you. I hope you are not annoyed by my illiteracy, I really know very little punctuation.
In the photo for the topic was used photo from www.psu.ru
Source: https://habr.com/ru/post/178253/
All Articles