Algorithms and Programming in Python

Programming currently attracts considerable interest among students and schoolchildren. Many of them are capable of independently studying the necessary theoretical material and developing practical skills using both educational (school and university) and personal computers. However, a significant limiting factor is the lack of appropriate literature. Most available programming literature is essentially a retelling of manuals for one programming language or another, for example [2]. Libraries occasionally carry books that also describe algorithmic methods. But such books are often not tied to any programming language, for example [15], or are tied to outdated programming languages [3]. The best, in the author’s opinion, of the relatively accessible textbooks on algorithm design today [8-11] unfortunately contain no information on the methodology of program development and debugging. A serious drawback of the monograph [11] for practical use by first-year university students and schoolchildren is also the high theoretical level of the material’s presentation. A common shortcoming of books as such is the static nature of the material, that is, the student’s inability to self-assess the quality of their mastery of the knowledge being studied and to reinforce the corresponding skills. The development of new information technologies and electronic means of distributing information, as well as the author’s many years of using the above-mentioned and other similar materials (primarily [8-10]), led to the need to create a new study guide. The author hopes that it will better allow each student to realize their individual creative potential through the following factors.

The integration of these factors ensures high effectiveness of the learning process based on the theoretical material and practical assignments presented in this book.

The proposed material has been actively used by the author in practical work teaching programming to students of the mathematics department at Francisk Skorina Gomel State University and to schoolchildren in the city of Gomel. The effectiveness of the implemented methodology is confirmed, in particular, by the following facts.

The author hopes that the reader will be able to see for themselves the merits of this book and the proposed approach to learning and self-learning algorithms and programming.

Nevertheless, the author will be grateful for all feedback and comments (including and above all critical ones), sent to: dolinsky@gsu.unibel.by.

Please send your comments, suggestions, and questions to the email address comp@piter.com (Piter Publishing, computer editorial office).

We will be glad to hear your opinion!

You can find detailed information about our books on the publisher’s website http://www.piter.com.

The goal of this study guide is to help you learn to write programs in the Python programming language. The guide requires active independent work on your part, without which this is impossible to achieve.

This book is the result of the author’s many years of work teaching programming to schoolchildren of various ages and developing his own methodology for the initial stage of learning, which the author has called "rapid immersion" into program development in Python. In short, the essence of this methodology can be stated as follows: the learner needs to be given a minimally necessary amount of information, but in such a way that they can independently solve practically any problem involving numeric data. The author considers the following to be such information: integer and real variables, arithmetic and logical expressions, assignment (=), conditional statements (if …​ elif …​ else), and loops (for and while).

The text of a program written in Python that solves the problem of calculating the height of the "pyramid" of barrels for our clown is shown in Listing 1.1.

This same program also solves a large number of other problems where, in the end, 10 numbers need to be added together.

It is clear that the simplest version of such a program should accumulate the sum, that is, first add the first 2 elements, then add the third to them, and so on for all elements of the list. The last element to be added to the sum in our problem is the tenth element of the list.

But let us look carefully at the text of the program. The first task is to figure out and try to remember the purpose of all keywords and punctuation used

in the program. After all, the program is intended for a computer, and for it every character matters. It will simply misunderstand the program if you make a mistake.

Python is case-sensitive: print and Print are different names! All Python keywords are written in lowercase. Variable names can use lowercase or uppercase letters, but by convention we use lowercase for variable names and UPPERCASE for constants.

So, a Python program does not need a special "program" declaration line — you simply start writing your code. In our example, we begin with a comment # Sum_1arr to give the program a name. Comments in Python start with the symbol — everything after on a line is ignored by the computer, but comments can be useful to the person who writes and reads the program, explaining what a particular line is for.

Unlike many other languages, Python does not use semicolons to end statements. Instead, each statement goes on its own line. Python uses indentation (spaces at the beginning of a line) to show which lines belong inside a loop or a conditional block. This is one of the most important rules in Python — incorrect indentation will cause an error.

The comments in our program state that the program sums the elements of a one-dimensional list. The list a is created with 10 elements initialized to zero. The variable i will be used to store and change the index of the element being processed. The variable s will be used to store the sum of the list elements that we have already added. Further: the one-dimensional list is input, its elements are summed, and then the list itself and the obtained result of summation are output.

A question arises: why output the source list? We entered it ourselves; we know what numbers are there. We only needed to output the result!

In this program, the source list was output for the following reasons.

Let us try to analyze our program line by line:

This line is a comment that describes the purpose of the program — summing elements. In Python, the # character marks the start of a comment.

This line creates a list named a containing 10 zeros. In Python, lists are dynamic — they can grow or shrink — but here we pre-create a list of a known size so we can fill it with values by index. Note that Python lists are 0-indexed: the elements are numbered from 0 to 9, not from 1 to 10.

This block provides input of 10 numbers from the keyboard into the list a.

Literally, this reads as follows:

The range(10) function generates numbers 0, 1, 2, …​, 9. Thus, the computer waits until we type a number on the keyboard and press Enter. It will store this number in list element a[0], that is, the first element of list a. Then the computer waits until we type the second number to store it in a[1], and so on, up to the 10th element, which it will store in a[9].

Recall that we introduced the variable s to accumulate the sum of the entered numbers. It is clear that the initial value of this variable, that is, the value of variable s before we start adding, should be zero. This is what this statement ensures. Literally, it reads as follows:

Or like this:

Next:

Literally, this reads as follows:

Alternatively, it can be read as follows:

This is the only part of the program that directly solves the problem at hand — it sequentially sums the 10 entered numbers in variable s, adding to it:

After this loop finishes executing, the variable s contains the desired result — the required sum!

This line outputs the text source array to the screen, and it is needed so that the person who will run our program knows what

numbers are about to be displayed (the numbers of the source list in this case).

Literally, this reads as follows:

Note that print(a[i], end=' ') uses the end=' ' parameter to prevent moving to the next line after each number. By default, print() adds a newline character at the end. By specifying end=' ', the cursor is not moved to the beginning of the next line but a space is printed instead. Thus, the numbers of list a are displayed one after another on the same line, separated by spaces.

If we had used plain print(a[i]) without end=' ', the numbers would have been displayed in a column, which in our case is less clear.

To move the cursor to the beginning of the next line after finishing the output of the entire list, a bare print() call is used. As a result, the word "answer" from the next statement is displayed at the beginning of the next line.

This statement is used to indicate that the results of our program’s work will follow.

This statement outputs the value of variable s, which contains the result of the program’s work.

We have analyzed the first, simplest Python program. It can be used as a basis for writing other programs that process one-dimensional lists. When doing so, only the calculation part of the program needs to be changed. Creating lists, inputting source data, and outputting source data and results, using exactly the corresponding parts of the program we analyzed, must always be done.

For example, what needs to be changed in our program if we want to multiply, rather than add, the entered numbers?

Only 2 characters need to be changed: + to * and 0 to 1, resulting in the following calculation part:

The text of this program is shown in Listing 1.2.

Thus, when developing programs, the main thing is to come up with the calculation part or, in other words, to design the algorithm of the program. For a large number of problems, such algorithms have long been devised, and instead of "reinventing the wheel," it is sufficient to study and memorize them, which is what you are invited to do.

Let us consider the most commonly used algorithms on a one-dimensional list:

Problem 1. Counting nonzero elements.

Problem 2. Counting elements whose absolute value is greater than 7.

Problem 3. Searching for 7.

Problem 4. Difference between the maximum and minimum elements.

Problem 5. Pairwise comparison of two lists.

A significant number of practical problems require processing not one-dimensional but two-dimensional arrays (lists of lists in Python).

A two-dimensional array (list of lists) a of 25 elements (5 rows and 5 columns) has the following indices in Python (0-indexed):

When processing all elements of a two-dimensional array in a program, nested for loops must be used:

Let us consider the indices of the second row (index 1 in Python) as an example:

It is easy to see that the first index — the row number — is fixed and equals 1 (for the 2nd row in 0-indexed Python), while the second index sequentially takes values from 0 to 4. Therefore, when the 2nd row of a two-dimensional array needs to be processed, it is sufficient to write:

The variable i can be replaced by any other as needed, for example m:

Now let us consider the indices of the third column (index 2 in Python) as an example:

Obviously, now the second index — the column number — is fixed, and the first index — the row number — sequentially takes all values from 0 to 4. Therefore, the loop for processing elements of the third column should look like this:

The elements of the first diagonal of a two-dimensional array have the following indices:

It is easy to see that the row index equals the column index for all elements of the first diagonal, and therefore the loop for processing its elements should look as follows:

The elements of the second diagonal of a two-dimensional array have the following indices:

It is not easy, but one can notice that the sum of the row and column indices for all elements of the second diagonal is constant and equals 4 (for a 5x5 array with 0-based indexing; for an NxN array it would be N-1), and therefore the loop for processing the elements of the second diagonal should look as follows:

Considering all of the above, one can agree with the methodology of transferring algorithms from one-dimensional lists to two-dimensional ones, illustrated here with the example of the summation algorithm:

What does this methodology consist of? In replacing the indices of a one-dimensional list with the indices of, respectively, a row, column, first or second diagonal, or the entire two-dimensional array. In the case of processing the entire two-dimensional array, nested for loops must also be used.

In a program that processes a two-dimensional array, it is necessary to create, input, and output specifically a two-dimensional array (list of lists):

The changes compared to the creation, input, and output of a one-dimensional list are quite intuitive, and therefore no comments are needed here.

Problem 10. In a two-dimensional array, change all signs to opposite. For example, suppose the input array is:

Then the output should become:

Obviously, the calculation part of the program should look as follows:

The text of the program itself is in Listing 1.4.

Problem 11. Find the maximum element in a two-dimensional array.

The calculation part of the problem can look like this:

Problem 14. Determine whether a two-dimensional array (5x5) is a "magic square."

The simplest solution is to:

t1, t2, …​, t5 — sums of columns from the first to the fifth;

d1, d2 — sums of elements of the first and second diagonals;

Some of you may rightly note: if the array consists of 100 rows and 100 columns, this solution is very inconvenient. Agreed; in that case, one must devise an algorithm that solves this problem in the most convenient way. Inventing new algorithms is the most difficult task in programming. The next chapter is dedicated to it. I hope that once you manage to understand the material in the next section, you will come up with a better algorithm for solving problem 14 on your own.

Problem 19. Find the number of zeros in a given column.

The calculation part of the program can be as follows:

Problems 20 and 21. Despite their complex and at first glance different formulations, both require finding the minimum element among the row maximums. This can be done, for example, as follows:

In general, the development of algorithms and programs is not only a science but also, to a significant extent, an art. And therefore many believe that teaching algorithm and program development is like teaching a person to paint pictures or compose poetry and melodies. Nevertheless, there are some general facts that should be communicated to anyone wishing to learn how to develop algorithms. Below, a plan is presented for your attention; following it when developing algorithms may help you master this science (or art) more quickly. It is not at all necessary to memorize it. It is sufficient to try to follow it when developing algorithms for every new program.

The plan is as follows.

Let us begin with problem 9: given an integer list a with 10 elements, count how many times the maximum value appears in it.

To do this, we must sequentially go through all the steps of the plan.

This means that you should try to reformulate the statement so that it contains a minimum number of words while the problem remains the same, and it is unambiguously defined what needs to be input (a number, a one-dimensional list of numbers, a two-dimensional list of numbers, a string of characters) and what needs to be output.

For example, for problem 9 — new formulation: in a list, count the number of maximums; the input is a list, the output is a number.

+ 3. Create test cases (not forgetting edge cases).

+ 4. Solve the test cases by hand.

Before writing a program, you must clearly understand what exactly it should do. In addition, you must strictly define what criteria you will use to consider the program to be working correctly. It is precisely the creation of an adequate set of tests for the problem that allows you to solve this task.

What is a test? It is the data that you must input into your program and the answer that you consider correct, which your program should produce when this data is entered.

How many tests should there be? On the one hand, you must devise enough tests so that you can assert that your program works

correctly if it "passes" all your tests (that is, for all input data it produces the specified output). On the other hand, there should be as few tests as possible, because if you change even one character in your program, you will need to re-verify its correctness on all your tests.

Furthermore, when creating tests, one must take into account that many programs must handle various edge cases in a special way. For example, for problem 9 being solved, the following tests are sufficient.

then the maximum count is 1: 11.

then there are 3 maximums. They are all the same and equal to 11.

then all its elements are maximums.

However, such an opportunity does not always present itself. As an example, let us consider problem 15: given an integer list a with 10 elements, count the greatest number of consecutive equal elements in it.

For practice, let us carry out the initial stages of algorithm development for this problem as well.

New formulation: in a list, count the greatest number of consecutive equal elements; the input is a list, the output is a number.

As for the complete set of tests, in this case it is more complex:

I draw your attention to the necessity of including the fourth and fifth tests in the test set. For example, if test 4 is absent from the test set, then having written a program that counts the first number of consecutive equal elements, one might, after getting correct answers on all remaining tests, erroneously believe that the program fully solves the problem.

Similarly, if the test set does not contain test 5, then having written a program that counts the last number of consecutive equal elements, one could again get correct answers on all remaining tests and, once again, erroneously believe that the program written fully solves the problem.

Suppose you have created a complete set of tests. How do you now construct an algorithm that solves the problem at hand?

First of all, note that since you have created the tests and manually calculated correct answers for all input data, you already know the correct algorithm for solving the problem. Your main challenge now is to write this algorithm in a way that the computer can correctly understand and execute it.

To help formalize an algorithm you already know, we suggest using the following mnemonic technique. Imagine that:

Another mnemonic technique for developing algorithms can be used when you are working together with a friend. In that case, you ask your friend to create a test with a large amount of input data, and then they tell you those input values one at a time. You are not allowed to write down the numbers they call out, but you can write down the results of computations on them. In this case you have two tasks:

Let us now try to write the algorithm for the consecutive elements problem for human execution. In this case, you only need to write 2 numbers on your palm:

Then the algorithm can be written as follows:

The corresponding computerized algorithm may look like this:

We have finally obtained an algorithm, and we believe it is correct. What do we do now? "Write a program based on it," you might answer. You could, but I still suggest first doing a manual trace, so that, even before sitting down at the computer, you can find and fix as many errors as possible in the written algorithm.

What is a manual trace? It is the process of a human executing a program as if they were a computer. The main difficulty of a manual trace for the author of the developed algorithm is to forget the essence of the problem being solved, the idea of the algorithm, and "mechanically and strictly" execute what is written in the algorithm (because that is exactly what the computer will do).

Upon finding an error, you need to correct the algorithm and try performing the manual trace again, first on the same test, and then on others. And so on until the author is satisfied that the algorithm works correctly on all tests.

We have finally obtained an algorithm, and we believe it is correct. What do we do now? "Write a program based on it," you might answer. You could, but I still suggest first doing a manual trace, so that, even before sitting down at the computer, you can find and fix as many errors as possible in the written algorithm.

What is a manual trace? It is the process of a human executing a program as if they were a computer. The main difficulty of a manual trace for the author of the developed algorithm is to forget the essence of the problem being solved, the idea of the algorithm, and "mechanically and strictly" execute what is written in the algorithm (because that is exactly what the computer will do).

Upon finding an error, you need to correct the algorithm and try performing the manual trace again, first on the same test, and then on others. And so on until the author is satisfied that the algorithm works correctly on all tests.

How do you perform a manual trace?

First of all, you need to carefully write out the algorithm and the test example on which the manual trace will be performed. Then execute the algorithm line by line to the end.

As a test example (let us call it example 1), we choose the list A with elements:

5 11 4 4 4 2 2 2 2 2.

Let us perform a manual trace for the algorithm that finds the largest number of identical consecutive numbers. For convenience, we will build a manual trace table (Table 1.1). Each step in it will correspond to one pass through the loop in our algorithm.

Table 1.1. Result of the manual trace on test example 1

So, the manual trace:

Let us comment on this example line by line as it executes:

After executing this line, the entered data will appear in the computer’s memory: the list a = [5, 11, 4, 4, 4, 2, 2, 2, 2, 2], that is, a[0] = 5, a[1] = 11, a[2] = 4, …​, a[9] = 2. We remember that the correct answer for this case is 5 (5 consecutive numbers 2; there were also 3 consecutive numbers 4, but 5 is greater than 3, so the correct answer is 5).

The variables max_val and cur received the value 1; in the manual trace, this is recorded as follows:

In principle, "documenting" the manual trace could also be done horizontally (Table 1.2).

And since there are no more statements in the loop body, control is once again passed to the line at the beginning of the loop:

i moves to the next value (was 1, becomes 2). \(2 < 10\), and so control is once again passed inside the loop:

The value of i is now 2, therefore, a[2] is compared with a[1], that is, 4 is compared with 11. Equal? No! Therefore, what comes after else will be executed:

Cur is currently equal to 1, max_val is also equal to 1, \(1 > 1?\) No. So the statement inside the if is not executed, and for now everything stays as it was.

In our table cur is already equal to 1, but right now we are a PC and, like it, must replace the old value with the new one (even if it is the same).

And since there are no more statements in the loop body, control is once again passed to the line at the beginning of the loop:

i moves to the next value (was 2, becomes 3). \(3 < 10\), and so control is once again passed inside the loop:

The value of i is 3, therefore, a[3] is compared with a[2], that is, 4 is compared with 4. Equal? Yes! Therefore, what comes after the if condition will be executed:

Cur is currently equal to 1, and will become 2.

Let us consider the algorithm and its representation in the Python programming language:

Obviously, when translating an algorithm into a Python program, one should follow these simple rules.

This subsection provides, in reference format, the basic techniques for working in the Python environment for editing and debugging programs.

Solving problems 6, 8, 16-18 will not require you to learn new theoretical material. You only need to consistently apply the plan for developing algorithms and programs proposed in this chapter,

starting from reformulating the problem statement and ending with the manual trace, and you should succeed!

The author’s many years of experience show that it is precisely at this stage that both the student and the teacher can determine whether the student is able and willing to pursue learning programming.

To solve problems 22-24, you need to know a few new facts about the Python programming language, which are presented below.

+ As a result of this operation, the variable k receives a value equal to the quotient of dividing the integer m by the integer n (rounded down). For example, if m = 11 and n = 4, then the quotient of dividing 11 by 4 is 2, and therefore the variable k will receive the value 2.

+ 2. An operation on integers — % — obtaining the remainder from division:

As a result of this operation, the variable k receives a value equal to the remainder of dividing the integer m by the integer n. For example, if m = 11 and n = 4, then the remainder of dividing 11 by 4 is 3, and therefore the variable k will receive the value 3.

The problem statements are taken from the first computer science textbook of 1985, compiled by Academician Yu. A. Ershov, who believed that schoolchildren should learn to solve such problems after two years of studying computer science.

The following notations are used below:

Problem statements:

\(b[i\) = (a[0] + …​ + a[i]) / (i + 1)]. . Given an integer list a of 10 elements. Count how many times the maximum value appears in this list. . Given a rectangular integer 2D list a of size 5x5. Change all elements in this list to their opposite sign. . Given a rectangular integer 2D list a of size 5x5. Find the largest number occurring in this list. . Given an integer list a of 10 elements. Check whether it contains elements equal to 0. If yes, find the index of the first one, i.e., the smallest i for which a[i] == 0. If no, output the word "no". . Given an integer list a of 10 elements. Check whether it contains negative elements. If yes, find the largest i for which a[i] < 0. . Check whether a rectangular integer 2D list a of size 5x5 is a "magic square" (meaning that the sums of numbers in all its columns, all its rows, and both diagonals are equal). . Given an integer list a of 10 elements. Count the largest number of consecutive identical elements in it. . Count the number of distinct numbers occurring in int list a of 10 elements. Repeated numbers should be counted once. . Given an integer list a of 10 elements. Build int list b of 10 elements containing the same numbers as list a, but in which all negative elements precede all non-negative ones. . Given integer lists a and b, each of 10 elements, where: a[0] < a[1] < …​ < a[9],

b[0] < b[1] < …​ < b[9]. Build a list c of 20 elements containing all elements of lists a and b, in which

c[0] < c[1] < …​ < c[19]. . Given a rectangular integer 2D list a of size 5x5. Find the number of those row indices i from 0 to 4 for which a[i][j] == 0 for some column index j from 0 to 4. . Given a rectangular integer 2D list a of size 5x5. Find the smallest integer K having the following property: in at least one row of the list, all elements do not exceed K.

The previous section was aimed at "quick immersion" of the thoughtful reader into program development in Python. This basic knowledge — integer and float variables, arithmetic and logical expressions, assignment, conditional, and loop statements — is sufficient to write a solution to almost any problem. Nevertheless, the Python programming language has many additional features and built-in functions that simplify program development and debugging. This section is devoted to an overview of these features.

It is clear that a person wants to process numbers larger than 0 and 1. To represent any numbers, sequences of 0s and 1s are used, or, as they also say, sequences of bits.

A sequence of 8 bits is called a byte.

Question: how many distinct 8-bit sequences exist? Or the same question, phrased somewhat differently: how many distinct numbers can be represented in one byte?

Let us try to list all 8-bit sequences (Table 1.13). For greater clarity, we will split the byte into 2 parts of four bits each, or, as they also say, represent the byte as two nibbles.

Have we listed all possible 8-bit sequences? Clearly, not all, but only those whose first 2 bits are zeros. In other words, we have listed all 6-bit sequences (if we ignore (or erase) the first two zeros of each 8-bit sequence). In total, we obtained

64 distinct sequences, which can represent 64 distinct numbers — we numbered them from 0 to 63.

Table 1.13. Numbers (from 0 to 63) and the corresponding 8-bit sequences — bytes

So how many 8-bit sequences are there after all? To find out, we need to write three more such tables: the numbers in the first table will have the first 2 bits as 0 and 1, in the second — 1 and 0, and in the third — 1 and 1. The total number of sequences of

eight bits is 256. Try as an exercise to list all these numbers yourself.

So, in one byte one can represent 256 distinct numbers (we numbered them from 0 to 255).

Let us think: could we have obtained this number — 256 — without listing all possible 8-bit sequences?

So, we have 8 positions in total, and each of them can contain one of two numbers — 0 or 1.

Thus, for 2-bit numbers there are \(2 * 2 = 4\) variants, for 3-bit numbers — \(2 * 2 * 2 = 8\) variants, for 4-bit numbers — \(2 * 2 * 2 * 2 = 16\) variants. And for a byte — \(2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256\) variants.

Or using exponentiation, this can be written as

\(28 = 256\).

This is read as: two raised to the eighth power (i.e., 2 multiplied by itself 8 times) equals 256.

Already while listing Table 1.13, you may have noticed that representing numbers as sequences of 0s and 1s (or, as they also say, in the binary number system) is extremely tedious for a human, although this is exactly how they are stored in computer memory. Therefore, humans invented yet another way of representing numbers — the hexadecimal number system. This system has the following remarkable properties.

Let us start with the simplest — converting numbers from binary to hexadecimal and back.

First of all, you need to memorize the hexadecimal number table (Table 1.14).

To convert numbers from binary to hexadecimal, it suffices to replace each nibble with the corresponding digit or letter. For example: 0011 1011 = 3B.

To convert numbers from hexadecimal to binary, it suffices to perform the reverse action — replace the letter or digit with the corresponding nibble (from the table below). For example: C7 = 1100 0111.

The rules for converting numbers from the decimal number system to hexadecimal and back are somewhat more complex. But since knowledge of them is not required for understanding the subsequent material, they are not provided here.

In this subsection, we will look at the ways of representing numbers of various types in Python programs. Unlike many compiled languages, Python handles most numeric details automatically, but understanding how numbers are stored in a computer helps you write better programs.

Python does not have built-in subrange types like some other languages. However, you can easily validate ranges yourself using assertions or if-statements:

Now, upon attempting to enter a number for the variable day1 that is greater than 31 or less than 1 (for example, 32 or 0), the assertion will raise an error. Moreover, if 31 is entered for day1, an error will be raised on the assertion for day2, since when day1 = 31, day2 would have to receive the value 32, which is outside the valid range.

Python’s philosophy is "we are all consenting adults here" — the language trusts the programmer to validate input when needed, rather than enforcing rigid type constraints.

Most programs being developed have a nonlinear structure, meaning that depending on certain input data values, different parts of the program may be executed. Logical variables can be useful for controlling the selection of the needed parts of the program.

In Python, boolean variables are of type bool. They can take only 2 values: False and True.

The following operations are defined on boolean variables:

A boolean variable can also be formed as a result of arithmetic comparisons: "less than", "less than or equal to", "greater than", "greater than or equal to", "equal to", and "not equal to" (respectively <, ⇐, >, >=, ==, !=).

Examples of declaration and use:

Two boolean variables are declared — is_empty_s and decision_achieved; the first is assigned the value True, the second — the value False.

The variable decision_achieved will receive the value True if the value of variable k equals the value of variable edge_number, and the value False otherwise. That is, this is a shorter way of writing the following statement:

And here are statements for independent analysis:

Below is an example of organizing a loop using boolean variables:

that is:

Again, a statement for independent analysis:

An example of using boolean variables in a conditional statement:

If is_current_may_continued is True and is_out is False then k = k + 1

And again, a statement for independent analysis:

Until now, we have studied programs that can process numbers (integers and floats) and lists of numbers. But in real life, programs that process textual information are also needed. For example, a program for creating/editing a class register that needs to input, output, and edit student surnames.

It is often very useful to convert between types — for example, from float to int, or from string to number and back. Python has built-in functions for this. Brief information about them is provided below.

Table 1.17. Standard type conversion functions in Python

In most olympiad problems, input from one text file and output to another text file are required.

A text file is a sequence of character strings of variable length, separated by newline characters; it ends at the end of the file.

In Python, you work with files using the built-in open() function:

The main operations with text files that interest us are:

Suppose we have a program p_cut_v9.py that reads from standard input and writes to standard output, and a file with prepared test data test7.dat is located in the same directory.

To ensure the program reads data from the test file and outputs to another file (in the example, test7.out), it suffices to use shell redirection:

Below is a technique for redirecting standard input within a Python program. You can use the sys module to redirect stdin and stdout:

Here:

To run a Python program with a test file passed as a command-line argument:

Listing 1.9 presents the text of a program that reads data from a file and outputs the result to another file. In Python, this is done using the open() function and optionally redirecting sys.stdin and sys.stdout.

This section is aimed at readers who have some programming skills in Python and is intended to help develop a proper programming style that ensures productive programming and effective support of the long lifecycle of the programs being developed. Furthermore, the program development method presented in this section will provide a natural transition for learners to object-oriented programming in the future.

From a given set of points on a plane, select two distinct points such that the number of points lying on opposite sides of the line passing through these two points differs by the least amount.

Table 1.18. Test examples

+ . Introduce data types that correspond to the essence of the problem.

Obviously, this problem will require the data types: point, line, and set of points. In Python, we can define these using dataclasses or named tuples:

Algorithm:

Let us introduce the following operations (functions):

Now we can write the main part of the program directly in Python, using the introduced operations (Listing 1.10).

A set of N arbitrarily intersecting line segments is given on a plane. Enumerate the set of all triangles formed by the indicated segments.

+ . Introduce operations on the defined data types that should also correspond to the nature of the problem. Implement these operations as functions.

In order to accomplish this work, it is first necessary to perform one or more iterations of semantic algorithm development.

Algorithm:

Let us introduce the following operations:

The implementation of the introduced functions is left as an exercise for the thoughtful reader. . When writing the actual program text, ensure maximum readability by using adequate names for variables, lists, and functions, as well as reasonably commenting the text at the stage of entering the program text (before debugging begins).

The presentation of problem solutions may seem overly concise to some, not revealing many details and not answering many questions that an inexperienced reader might have. This was done intentionally, in order to convey as clearly as possible the essence of the proposed approach to solving problems.

As for answers to the reader’s questions, three ways of resolving the issue are suggested.

Question 1. What is float in the following line:

and why was it necessary to redefine the real type at all: couldn’t we just use the familiar float type?

Answer to question 1.

In Python, the built-in float type corresponds to a 64-bit IEEE 754 double-precision floating-point number, giving about 15–17 significant decimal digits. This is the standard real type in Python and is sufficient for most tasks. If you need even higher precision, you can use the decimal.Decimal module from the standard library.

Defining a type alias like TReal = float means that our program will process real numbers with a consistent type. At the same time, if it becomes necessary to change the type of real numbers (for example, to Decimal for extra precision), it will be sufficient to replace just the one alias, and all our variables, points, segments, etc. will automatically switch to the new type as well.

Question 2. All the introduced types TReal, TPoint, TLine, etc. start with the letter T — is this mandatory?

Answer to question 2.

No.

But for many professional programmers, an important rule is the use of so-called "Hungarian notation," where one or more letters before the name define the functional purpose of that name (for example, T — type, then TPoint — type "point"). In Python, the convention is more commonly to use CamelCase for class names (e.g. Point, Line). This allows the programmer to navigate more easily in their own (and especially someone else’s) program, which is especially important for programs that operate and are maintained over several years.

Question 3. I haven’t worked with classes yet. Can you explain in more detail how to use them?

Let us examine the definition of function init_line in more detail:

where

A call to the function in the body of the program may look as follows:

That is:

initialize line l1 from points p1 and p2

The advantages of using functions are that once defined, a function can be called many times. This is much simpler than directly coding the function’s content each time.

For example, to initialize line line from points point1 and point2, it suffices to write another function call:

Note that when defining a function in Python, you can specify the types of the function’s parameters using type hints: Point — for variables p_a and p_b, and → Line for the return type. While Python does not enforce these at runtime, they serve as documentation and can be checked by tools like mypy.

In Python, unlike Pascal, there is no need for a special VAR keyword. If you pass a mutable object (like a list or a class instance), any modifications to it inside the function are visible outside. For immutable types (like numbers and strings), you simply return the new value. The init_line function is designed specifically to compute and return, based on the coordinate values of two points passed to it, the coefficients A, B, and C of the canonical equation of the line passing through the two given points.

Let us recall that the class Line is precisely defined as follows:

Thus, in Python, functions receive their inputs as parameters and return computed results using return statements. When you need to return multiple values, you can return a tuple.

What happens if you modify a mutable parameter (like a list or object) inside a function? The change will be visible in the calling code, because Python passes references to objects. But for immutable types (numbers, strings, tuples), modifications inside the function create new local values without affecting the caller.

Therefore, Python programmers always recommend precisely determining whether a function should modify its arguments in place or return new values, and design functions accordingly.

To clarify the concept of a function that returns a value, let us consider another example. Definition:

Call:

First of all, let us note what makes Python functions powerful:

The function signature with type hints:

Here the function difference receives a line line and a list of points points, and returns a tuple containing the difference value and the number of points from the given set that are located exactly on the line.

Now let us consider how functions are used. In particular, calling functions:

The function is called and its return value is used directly in expressions. The name difference returns a tuple. In Python, the result type is specified using the → annotation in the function definition — def difference(…​) → tuple[int, int]:, and in the body of the function, upon completion of computations, the return statement provides the result:

Using functions makes the program more compact and clearer.

Question 5. I am seeing the word break for the first time. What does it mean?

Answer to question 5.

We are talking about the following program text fragment:

During the development of this program, it became clear: if a line is found such that the number of points on each side of it is equal, then the difference of these counts is 0 and it is minimal. A solution has been found, and there is no need to continue executing the program.

break exits the nearest enclosing loop (just one!). This is precisely why, to exit a double loop, two break statements were needed.

Question 6. I am seeing the word continue for the first time. What does it mean?

Answer to question 6.

We are talking about the following program text fragment:

During the development of this program, it became clear that in the case when segments with indices i1 and i2 do not intersect, there is no need to examine all triples of segments i1, i2, and i3 in search of a triangle. That is, at this point we simply need to move on to the next segment after i2, which is what the first continue statement does. The second continue provides a transition to the next value of i3 in case at least one of the segments i1 or i2 does not intersect with the current segment i3.

Thus, continue skips the rest of the current loop iteration and jumps to continue the loop with the next value of the loop variable.

Question 7. And what do you have against goto statements? Why, instead of using just this one, are two (and perhaps there are more?) analogs invented?

Answer to question 7.

Indeed, since any program can be written without using goto statements, the answer is clear in Python — there is no goto statement at all! Python was designed from the start to use structured control flow: break, continue, return, and exceptions. Many professional programmers hold the following view.

The first chapter provided the thoughtful reader with a "quick immersion" into the Python programming language, the tools for writing and debugging Python programs. It also provided information about basic introductory algorithms on one-dimensional and two-dimensional lists, for example: summing elements; counting and searching for elements that possess a given property; finding maximum and minimum elements. Several algorithm development methodologies were also presented. As was mentioned earlier, theoretically this is sufficient to write a program for solving any problem in the Python programming language. In practice, however, it is more reasonable to master not only the methods for developing new algorithms, but also the algorithms themselves that have already been developed for a wide class of problems. Such algorithms enrich the program developer’s "arsenal." Applying known algorithms, their modifications, and combinations significantly reduces the time for solving problems, developing, and debugging programs.

In this section, the properties of two data structures will be examined in detail: the queue and the stack. The essence of these structures becomes clearer if we refer to their English designations — FIFO and LIFO respectively:

Both the queue and the stack can be represented and implemented in a program in various ways, but we will focus on the simplest — representing the queue and stack using a list of elements.

Obviously, for a stack, in Python the simplest approach is to use a regular list. At the beginning of the program, we create an empty list:

And this means that the stack is currently empty.

Push element x onto the stack — means performing one action:

Pop an element from the stack into variable y — means performing one action:

To understand how this works internally, let us also look at the manual array-based approach (as was done historically). We use a list and a top variable:

Usually, for greater clarity and readability of programs, the stack operations are separated into special functions. Here is the manual approach for learning purposes, followed by the Pythonic approach:

Manual approach (for learning):

Pythonic approach (recommended):

The size of the list for the stack is determined by the maximum number of elements expected to be placed in the stack and the type of elements stored in the stack. In Python, lists grow dynamically, so you do not need to pre-allocate a fixed size.

It is clear that the elements of a stack can be not only characters. You can create stacks of words, points, segments, triangles, etc. in a program, using Python’s facilities for defining classes. You can also have tuples of numbers as stack elements.

A queue, just like a stack, can be represented in a program by a list of elements. However, unlike a stack, working with a queue requires two additional variables — pointers to the beginning and end of the queue. Let us call them for definiteness:

At the beginning of the program, the queue beginning is set to 0 and the end to -1 (using 0-based indexing), for example, with the following statements:

Then, to enqueue a triple of numbers (x, y, z) into queue que (at its end), the following actions must be performed:

To dequeue a triple of numbers from the queue into variables x, y, and z (from the beginning of the queue, naturally), the following must be done:

The attentive reader has noticed that in this case a list of tuples is used for working with the queue. Each tuple stores the numbers belonging to a sin-

gle element in the queue. In our case there are 3 such numbers.

Just as with stack operations, queue operations are usually placed in separate functions, for example:

Pythonic approach: In Python, the best way to implement a queue is to use collections.deque, which provides O(1) append and popleft operations:

In this section, examples of solving several problems using queues and stacks are provided. Those who are using this material for self-study of programming are recommended, after reading the problem statement, to first try to solve it on their own, without reading the material presented further in this section. If you succeed, then perhaps there is no need to spend time on further reading.

From a sheet of graph paper of size 8 x 8 cells, some cells have been removed. Into how many pieces will the remaining part of the sheet fall apart?

Idea: a queue of cells adjacent to the current one is introduced. That is:

A more rigorous presentation of the algorithm looks as follows:

Let us present the text of the main program solving this problem:

Analysis of the main program shows that it uses the following subprograms and functions:

The full text of the self-documented program for solving this problem (cell.py) is given in Listing 2.2.

Program text for solving the Cutting Pieces problem

continued …​

Given a finite sequence consisting of opening and closing brackets of various given types. Determine whether it is possible to add digits

and arithmetic operation signs to it so that a valid arithmetic expression is obtained.

Idea: a stack of opening brackets is introduced.

The input string, by the problem conditions, contains only opening and closing brackets, and it is processed character by character. The algorithm can be written as follows:

A more rigorous representation of the proposed algorithm:

Let us look at the main program text for solving this problem:

The main program uses the following functions:

The full program text solving this problem (stack.py) is given in Listing 2.3.

Note: In competitive programming, the Pythonic way to solve the brackets problem is even simpler using a plain list as a stack:

Those who have read the full program texts may have questions about the techniques used in them. In addition, the author would like to draw the readers' attention to several additional programming techniques applied in solving the indicated problems. This section is devoted to examining these techniques.

It is known that in general a knight has 8 different moves, defined by the corresponding combinations of pairs from the numbers 1, 2, -1, -2. The program reads better if we use in this case the initialization of a constant list defining the knight’s allowed moves.

For the paper cutting problem, the allowed "moves" when enqueuing a cell are somewhat different, but this is actually reflected only in the constant list:

Incorrect distribution of variables in a program among these types leads to an increase in the number of potential errors in the program and, consequently, to a prolonged debugging process.

If a variable is declared inside a function — this means that it is local. That is, no changes to this variable inside the given function in any way affect variables with the same name in other functions and in the main program. For example, in the put_all function shown above, the variables dx, dy, current_x, and current_y are local.

If a variable is declared at the module level (outside the body of any function), then it is global, and any function that declares it with the global keyword can modify it. In Python, if you need to modify a global variable inside a function, you must use the global statement. Without it, assigning to a variable inside a function creates a new local variable.

And finally, parameters are variables that are declared directly in the function definition, such as x, y, and step_number. In Python, all parameters are passed by reference to the object. For immutable types (like integers and strings), any modifications create a new local value without affecting the caller. For mutable types (like lists and objects), modifications to the object itself are visible to the caller.

What considerations should guide the distribution of variables among these types?

Proper use of Boolean variables and lists reduces program size and improves its clarity, which ultimately shortens the debugging time.

Many beginning programmers often use variables and lists with values 0 and 1 instead of Boolean values False and True.

Let us give several examples of using Boolean variables and lists in the described programs:

Here the variable found receives the value True if both equalities hold simultaneously \((sx == ex)\) and \((sy == ey)\). That is, if the target square has been found during the search.

Here find_unmarked is a function that returns a tuple of coordinates if there are still unmarked squares on the board, or None if there are none. The coordinates of the first free square found are returned directly. Only if there are no unmarked squares left on the board does the function return None.

Here, the use of early return for non-standard exit from a function is also illustrative.

stack.py (the brackets problem, see Listing 2.3)

The boolean value stack_empty is True if the stack is empty (length is 0), and False otherwise. This value is used for correct popping from the stack, and it is also returned to the calling program.

This fragment requires no explanation, unlike the case where some numbers would be compared.

So, you have developed an algorithm, written a program, and it already produces correct answers on several tests you have prepared. If tests still appear on which it stops working correctly, then you will need to make changes to the program, achieving its correct operation on those tests as well. But after changing the code, you need to recheck everything again!

The following approach is suggested: immediately after you have written the program and begun testing it (or even better — before that), compose tests and place them in files 1.in, 2.in, 3.in, etc., 1.out, 2.out, 3.out, etc. The *.in files should contain what needs to be input to the program for the test with the corresponding number, and the *.out files should contain the data that the program should output in case of correct operation.

After that, you compose a test script. In Python, you can create a simple test runner:

This script cyclically launches the program for all test numbers, feeding the prepared test as input and comparing the output with the reference answers.

Alternatively, you can use Python’s built-in testing tools. A simple approach using Python:

By running this script, you can at any time, after the next batch of changes, verify that the program works on all the tests you have prepared, or quickly discover those on which it does not yet or no longer works. If your program is supposed to read data from one file (for example, file.in) and write to another (for example, file.out), then you can slightly modify the test script accordingly.

In Python, memory management is handled automatically. Unlike lower-level languages, you do not need to manually allocate and free memory. Python uses a system called garbage collection — when no variable references an object any longer, Python automatically frees the memory that object was using.

Every value in Python is an object, and every variable is a reference (essentially a pointer) to an object. When you write x = [1, 2, 3], Python allocates memory for a list object and stores a reference to it in x. When x goes out of scope or is reassigned, the list object becomes eligible for garbage collection if nothing else refers to it.

This means you can focus on your algorithm rather than worrying about memory allocation and deallocation. Lists, dictionaries, and other data structures in Python grow and shrink dynamically as needed.

Let us return to the problem statement from one of the previously solved problems. From a sheet of graph paper of size 8 x 8 cells, some cells have been removed. Into how many pieces will the remaining part of the sheet fall apart?

It was proposed to solve this problem using a queue. Two data structures were used to store data in this problem:

The marked list has dimensions 8x8 because by the problem conditions the board size is 8x8. The que deque stores tuples of two numbers — x and y — coordinates of the cell we enqueued.

Now suppose the problem is made more complex as follows: from a sheet of graph paper of size \(N x M\) cells (\(N >= 1\), \(M <= 150\)), \(K\) cells have been arbitrarily removed (\(1 <= K <= 22,500\)). Into how many pieces will the remaining part of the sheet fall apart?

In Python, we simply adjust the list sizes dynamically — no special memory management needed:

Python lists can grow as large as available memory allows. There is no artificial 64 KB limit as existed in older languages. If you need even larger data structures, Python handles them seamlessly.

Python’s memory model is based on objects and references. Every variable holds a reference to an object. A reference is essentially an internal pointer to the object in memory.

Python manages memory automatically using reference counting and a cyclic garbage collector. When no references point to an object, the memory is freed automatically. You never need to manually allocate or free memory.

Now let us learn to use Python’s data structures in our programs.

Let us begin with an example. Let us recall the problem statement from one of the previously solved problems. From a sheet of graph paper of size 8 x 8 cells, some cells have been removed. Into how many pieces will the remaining part of the sheet fall apart?

It was proposed to solve this problem using a queue. In Python, we can simply use a deque and a 2D list:

The marked list has dimensions 8x8 because by the problem conditions the board size is 8x8. The que deque stores tuples of (x, y) coordinates.

For the larger version of the problem (N x M grid), we simply create lists of the needed size:

The algorithm for solving the problem of cutting cells from a sheet of paper of size \(N x M\) can be written as follows.

Idea: a queue of cells adjacent to the current one.

The text of the corresponding program is given in Listing 2.4.

For competitive programming, Python provides simple and powerful tools for memory management. Unlike older languages where you needed to worry about memory allocation limits, Python lets you focus on the algorithm itself.

If you ever need to check memory usage of your program (for example, to stay within the memory limits of a competitive programming judge), you can use the sys.getsizeof() function or the tracemalloc module:

This helps the programmer track memory usage at different processing stages of the program.

In practice, Python programs rarely run into memory issues for typical competitive programming problems, as modern systems provide ample memory. The main concern is usually execution speed rather than memory.

For very large data, Python also provides specialized modules:

For example, if you need a very large boolean grid:

However, for most competitive programming problems, regular Python lists are perfectly adequate.

Now let us give an example of using classes for storing structured data (in this example, for the coordinates of a point). We declare a new class that stores information about a point’s coordinates:

We create a variable of type Point:

When accessing object attributes, we work as follows:

When we are done with an object, we simply stop referencing it — Python’s garbage collector handles the rest:

It is also worth mentioning Python’s string handling. Python strings can be of arbitrary length (limited only by available memory). Unlike older languages with a 255-character limit, Python strings can hold millions of characters. Python strings are immutable — operations like concatenation create new string objects. For efficient string building, use str.join() or io.StringIO.

Python provides a rich set of string methods. For example:

There are also functions such as string splitting, case conversion, replacement, and others. For complete information about the func-

There is a significant class of programming problems whose simplest solutions are based on understanding the fundamentals of how recursive functions work and on the ability to construct recursive algorithms and debug recursive programs.

Suppose we need to write a program that reads numbers \(M\) and \(N\), a sequence of \(N\) numbers — \(a(i)\) — and counts the number of ways in which the given sum \(M\) can be composed from the numbers \(a(i)\).

Example input data: \(M = 10, N = 6\), and the sequence of numbers is 1 10 7 4 2 3. That is, we need to compose the sum 10 from elements of this sequence of 6 numbers. We have the following variants:

3) \(10 = 7 + 2 + 1\);

4) \(10 = 4 + 3 + 2 + 1\).

Thus, the answer is 4.

How do we obtain it? Clearly, in the general case we need to enumerate all possible combinations of numbers, that is — all singletons, all pairs, all triples, all quadruples, all quintuples, and finally check the sum of all elements of the sequence. We will create a recursive algorithm that builds (traverses) such a tree, only it will perform the analysis from the last element to the first. But first, one more tricky test: \(M = 3\), \(N = 3\), and the sequence of numbers is 0 0 0. The question is: in how many ways can a sum be composed from three numbers, each of which equals 0? I believe that, according to the problem’s conditions, the answer is 8:

The recursive approach, as explained above, involves building a tree of enumeration. To illustrate it, let us take a simpler example: we need to compose the sum 3 from three numbers: 1, 2, and 3.

Obviously, the answer is: 2 (\(3 and 1 + 2\)). The enumeration tree can be depicted as follows:

So, the function find (Listing 2.8) will have 2 parameters: n — the index of the element with which we are currently extending the tree, and m — the sum we want to obtain. The value of the function find is the number of ways in which the sum m can be composed from n elements of the list a.

Consider a problem in which it is required to count the number of different representations of a given natural number \(N\) as a sum of at least two pairwise distinct positive addends.

In fact, as in the problem considered earlier, we need to find numbers that add up to the given number.

The differences are as follows.

where find(n - 1, n) finds the number of ways to represent the sum n from n - 1 numbers a[0], a[1], …​, a[n - 2]. . The sum must consist of at least two numbers (in the previous problem it was assumed that there could be one or even none).

If \(m > A[n\)], then we add find(n - 1, m) — the number of ways in which the sum m can be composed from \(n - 1\) elements (without element a[n - 1]) — and find(n - 1, m - a[n - 1]) — the num-

ber of ways in which the sum m - a[n - 1] can be composed (i.e., a[n - 1] participates in the total sum). And if m > a[n - 1], then obviously the sum m must be composed without element a[n - 1], and therefore return find(n - 1, m).

The case a[n - 1] == m is handled separately:

If m == a[n - 1], then in the case n >= 2 we have already found one variant and must continue searching for others, and in the case n == 1, this is the last variant.

And finally, the conditions for processing branches of the tree where the required sum is not achieved:

Thus, the final program Find4 looks as shown in Listing 2.9.

Consider the following problem: we need to count the number of valid bracket expressions consisting of \(2 * N\) parentheses. An expression is called valid if it consists of \(2 * N\) characters and:

For convenience, let us replace opening parentheses with 1 and closing parentheses with 0. Consequently, we need to traverse a tree of the following kind (example for \(N = 2\)):

We need to count how many paths have the following properties:

We will write a recursive function:

where dn is the number of characters in the chain of 1s and 0s representing the current state of the branch of the tree we are traversing, d (1 or 0) indicates which branch we will go down; zero is the number of zeros in the current chain; one is the number of ones in the current chain.

The main recursive call expression will look like this:

That is, the number of valid expressions equals the sum of the counts of valid expressions in the branches selected for 0 and 1.

Upon entering the function and exiting from it, taking into account the parameter d, we need to correctly maintain the count of the current number of 1s and 0s. Furthermore, if at least one of the validity conditions is violated (zero > n or one > n or zero > one), then this branch is "pruned."

The complete program is presented in Listing 2.10. Note that in Python, since integers are immutable, we use mutable containers (lists) to simulate pass-by-reference behavior for the counters.

Often in problems it is necessary not only to count how many ways something can be done, but also to output all of these ways. Let us add this requirement to the problem about different representations of a given natural number \(N\) as a sum of at least two pairwise distinct positive addends:

The solution presented earlier in the section "Number of representations of a number as a sum of components" will be supplemented as follows: to the recursive function find we will add one more parameter — add of type bool. It indicates whether or not we added the current element a[n]. To the main program we will also add a variable path of type list, which will store the indices of elements that were selected in the current branch of the tree.

In the function find itself, if the current element is added, then upon entry we will append to the list path, and upon exit we will remove the last element from it. Furthermore, when finding each next solution (m == a[n]), we will output it using the current contents of the list path.

The complete solution to the stated problem is given in Listing 2.11.

with output of all possible ways

There are problems where it is sufficient to find just one of the possible ways. For example, suppose we need to write a program that reads numbers M, N and a sequence of N numbers \(a(i)\) and outputs one of the ways in which the given sum M can be composed from the numbers \(a(i)\).

To solve the problem, we modify the program (see Listing 2.8) as follows:

The text of the modified program is in Listing 2.12.

Suppose we are given a map of one-way roads between cities. A city from which all other cities can be reached is called a source. A city that can be reached from all other cities is called a sink. We need to find all sources and sinks.

There is a number of problems in which, due to the impressive ranges of input data, the recursive approach is fundamentally unable to provide a complete solution. In these cases, a related approach called recurrence comes to the rescue.

Let us consider the classic Fibonacci numbers problem, a staple of educational materials on recurrence relations.

In some sources, this problem is formulated as the "rabbit breeding problem": suppose we had one rabbit in the "zeroth" generation and one rabbit in the first generation. It is also known that the number of rabbits in the next generation equals the sum of the numbers of rabbits in the two previous generations. It is required to compute the number of rabbits in generation \(N\) (for example, \(N ≤ 10,000\)).

The sequence of numbers built for generations from the 0th to the 7th is as follows:

1 1 2 3 5 8 13 21 34.

That is, in the 2nd generation (\(N=2\)) there will be \(2 (1 + 1)\) rabbits, in the 3rd — \(3 (1 + 2)\) rabbits, in the 4th — 5 rabbits, and so on.

This sequence of numbers is called the Fibonacci sequence, and the numbers themselves, respectively, Fibonacci numbers.

How do we find the number of rabbits in a given generation \(N\)?

We introduce a list k of size n + 1. By the problem’s conditions, k[0] = 1, k[1] = 1.

To solve the problem, we fill the list elements as follows:

And output the result as follows:

The complete program text for solving the problem is given in Listing 2.15. Note that Python has arbitrary-precision integers, so unlike some other languages, there is no overflow issue even for very large N.

Now let us return to the general terminology.

The relation k[i] = k[i - 1] + k[i - 2] is called a recurrence relation for the quantity k. The quantity k itself is called recurrent. The word "recurrent" here conveys the meaning that the next value of the recurrent quantity is computed from one or more of its previous values.

The quantity i is called the parameter of the recurrent quantity. For example, k[i] is a recurrent quantity of one parameter i. For storing recurrent quantities of one parameter, a one-dimensional list is typically used.

However, for example, in the Fibonacci numbers problem, to compute the next number we need to know and, accordingly, store only two previous numbers. Therefore, we could have simply used two variables to store them. In that case, the program could look as shown in Listing 2.16.

Let us note in passing that although this solution looks less understandable and slightly more complex, it can compute Fibonacci numbers for N much larger than 10,000. For example, for N = 100,000. In Python, since integers have arbitrary precision, there is no overflow — the numbers simply grow as large as needed.

Recurrent quantities can have more than one parameter. For example, the recurrent quantity R[i][j] = R[i-1][j] + R[i-2][j] + …​ + R[i-j][j] has two parameters, denoted i and j. In the general case, a two-dimensional list is used in the program to store the values of recurrent quantities of two parameters. To compute the elements of the next row of the list R, one needs to know the computed values of j rows (with numbers i-1, i-2, …​, i-j) above the current one.

The recurrent quantity R[p][k][t] = max(R[p-1][k][t-L[p]] + 1, R[p-1][k][t]) has three parameters p, k, t. And its value for given values of these parameters is computed, as we can see, somewhat more complexly. For storing the values of a recurrent quantity of three parameters, a three-dimensional list is typically used. But there are cases when the maximum values of the recurrent quantities established in the problem constraints are too large to simultaneously store all the values of the recurrent quantity for all possible values of its parameters in memory. Then not all values are stored, but only those that are actually needed for computing new values. Obviously, the program becomes more complex in this case, sometimes insignificantly, and sometimes substantially.

So, the essence of the method of solving problems using recurrence relations is:

This section presents problems for which it is necessary to compose a recurrence relation with one parameter. This means that the introduced recurrently-defined quantity depends on one argument.

Quarter-final of the ACM World Programming Championship for students, Central Region of Russia. October 5-6, 1999.

From \(N\) soldiers lined up in a row, several must be selected for a scouting mission. To do this, the following operation is performed: if there are more than 3 soldiers in the row, then all soldiers standing at even positions, or all soldiers standing at odd positions, are removed. This procedure is repeated until 3 or fewer soldiers remain in the row. They are sent on the scouting mission. Calculate how many ways scouting groups of exactly three people can be formed in this manner. Constraints: 0 < \(N\) ≤ 10,000,000.

Input file — INPUT.TXT (contains the number N), output file — OUTPUT.TXT (contains the solution — the number of variants). Time per test — 5 seconds.

Let us denote K(N) — the number of ways in which scouting groups can be formed from N people in the row. Then, by the problem’s conditions, \(K(1) = 0, K(2) = 0, K(3) = 1\). That is, from three people only one group can be formed, and from one or two — none.

Consider the case of an arbitrary number of soldiers in the row. If N is even, then by applying the deletion operation defined in the problem, we will be left with either N // 2 soldiers standing at even positions, or N // 2 soldiers standing at odd positions. The total number of ways can be found by the formula K(N) = 2 * K(N // 2) (if N is even). That is, the number of ways

form a reconnaissance group from the soldiers remaining at even positions, plus the number of ways to form a reconnaissance group from the soldiers remaining at odd positions.

If N is odd, then we are left with either N // 2 soldiers who stood at even positions, or (N // 2) + 1 soldiers who stood at odd positions. The total number of ways in this case is K(N) = K(N // 2) + K((N // 2) + 1).

Thus, the final recurrence relation has the form:

It only remains to note the following facts.

The complete solution to this problem is shown in Listing 2.18.

Belarusian National Olympiad, 1996. Day 2. Problem 3.

The owner of a video salon decided to maximize the income from his business. The video salon has an unlimited number of blank videotapes. The duration of each videotape is \(L\). The owner has the opportunity to record \(N\) movies of duration \(A(1), ..., A(N), A(i) < L\) onto videotapes. He cannot record the same movie twice on one videotape and cannot leave empty space on a tape that would fit entirely one of the movies not recorded on that tape. Movies are recorded in their entirety. The video salon owner aims to record movies onto tapes in such a way that to watch all the movies, a customer would be forced to rent the maximum number of tapes. Determine this number \(K\). Constraints: \(A[i\), L, N] are natural numbers, \(L ≤ 1000, N ≤ 100\).

Input — from file Input3.txt:

Output — to file output3.txt (\(K\)).

Consider the following case: let \(L = 100, N = 8\), and \(A[i\) = [2 2 3 3 97 97 97 97]] (durations of eight movies).

Since some movies may have the same duration (as in our example), to distinguish these movies when recording, we introduce notation: \(2(1)\) means a movie of duration 2, the first in the original list, or \(97(6)\) means a movie of duration 97, the sixth in the original list. If the customer were to determine the order of recording movies onto tapes, then in our example, obviously, they would choose the most advantageous option with the minimum number of tapes:

With this arrangement, their payment for renting all movies would be minimal. But the cunning video salon owner records the tapes himself. How will he record them? It would be good if you, before reading further, came up with a "clever" arrangement on your own. And even better — also a method for a "clever" algorithm for recording movies onto videotapes.

Now let us try together to compose this "clever" arrangement. The first tape will remain the same: \(97(5) + 2(1)\). But on the second tape, the video salon owner will prefer to record only one new movie — \(2(2)\), that is, \(97(5) + 2(2)\). He will do the same with the 3rd and 4th tapes:

So, the customer is already forced to buy 4 tapes, and yet they haven’t seen three of the best movies — 97(6), 97(7), and 97(8) — for recording which, in the video salon owner’s "clever" arrangement, they would need to buy three more tapes:

What to use to fill the remaining space on these three tapes from the available "short" movies is essentially irrelevant. For example, movie 2(1).

We seem to have figured out this particular arrangement. But what about others? And what is the algorithm for "clever" recording of movies? And finally, how do we determine the required number of videotapes k from the input data L, N, A[i]?

If we reformulate the problem, we are required to compose all possible sums from combinations of the original numbers, and from these sums select the maximum number such that the sequence of numbers in each sum differs from the rest by at least one number (identical numbers at different positions in the input data are considered different).

Since longer movies are more significant for the recording process, we reorder the input data so that movies go in decreasing order of their durations.

Let us examine a single videotape "under a microscope." It has a recording duration of L (let’s say L minutes for definiteness). Then we can view a single tape as a one-dimensional list s of length L+1. And then each of the aforementioned sums corresponds to exactly one position in this list. We will discard sums exceeding L (since they don’t interest us as combinations of movies that don’t fit on a single tape). We will store a one in s[j] if the recording of the previous movie ended at position j.

Then each new movie we should try to append to all possible positions roughly like this:

If we found a place where we can "squeeze in" a movie and it fits until the end of the tape (a[i] is the duration of the current movie), then we mark the position where this movie will end.

At the same time, before the first movie, s[j] = 0 for all j from 1 to L, and s[0] = 1, meaning we can write movies from the beginning of the tape.

Clearly, the above operation needs to be done for all movies. How do we simultaneously keep track of the number of variants?

Let us introduce another list ns of length L+1. We will modify it in parallel with list s. But while in s[j] we only note the fact that the recording of the previous movie ended at this position, in ns[j] we will keep track of the number of ways we have recorded movies up to this point:

If we found a place to record a new movie, then the count of ways "migrates" to the end of the recording of that movie, and we must take into account that:

Good, now for all sums s[j] we will count how many different ways ns[j] they can be obtained using N movies. And which of these sums ms[j] should be added to get the answer K?

To answer this question, let us introduce one more list: ms of length L+1. Initially, all its elements will equal 0. Then we will set ms[j] to one in the case where we formed subsequent sums from this sum, meaning this sum is intermediate and should not be counted:

And to obtain the answer K, we need to sum elements of list ns[j] from the end, as long as ms[j] == 0:

And finally, one last remark: generally speaking, we need two lists s: one for the current value of s, and another for the next one, so as not to append a movie to itself on the same tape. But we can achieve the same effect by working with the same list s but processing it for each i from the last element s[L - a[i]] to the first s[0]:

Clearly, processing s[j] for j > L - a[i] is pointless: the movie a[i] certainly won’t fit on the tape if we write it starting from this position j.

The complete solution to this problem is given in Listing 2.19.

This section presents problems whose solutions require constructing a recurrence relation with two parameters. This means that the recursively defined quantity depends on two arguments.

Belarusian National Olympiad, 1996. Day 2. Problem 1.

Among all \(N\)-bit binary numbers, determine the count of those whose binary representation does not contain \(K\) consecutive ones. The numbers themselves need not be output. \(N\) and \(K\) are natural numbers, \(K ≤ N ≤ 30\).

Input of \(N\) and \(K\) — from file Input1.txt, output of \(M\) (the desired count) — to file Output1.txt.

Let us introduce the recurrence quantity r[i][j] — the number of \(i\)-bit binary numbers whose binary representation does not contain \(j\) consecutive ones. Then the answer to the problem is r[n][k].

First, let us try to analyze the patterns in filling the matrix r[i][j]. If \(N = 1\), there are only 2 one-bit numbers — 0 and 1. Accordingly, r[1][1] = 1, meaning there is one number whose representation does not contain a single one — 0.

r[1][j] = 2 for all \(j ≥ 2\), meaning there are two 1-bit numbers whose representation does not contain two (or more) consecutive ones — 0 and 1. Similarly, r[i][j] = 2^j for all cases \(i < j\), meaning the number of \(i\)-bit numbers whose representation does not contain \(j\) consecutive ones equals the total count of all such numbers.

Obviously, r[i][1] = 1 for all \(i ≥ 1\), meaning there is only one \(i\)-bit number whose representation contains no ones at all — the number with zeros in all its digits.

And finally, r[i][i] = 2 * i - 1, meaning the number of \(i\)-bit numbers whose representation does not contain \(i\) consecutive ones equals the total count of all \(i\)-bit numbers minus one (the one that contains ones in all digits).

Thus, the initial filling of the matrix r[i][j] is as follows:

It remains to learn how to fill the table below the main diagonal, that is, to compute r[i][j] for the case i > j.

Let us consider r[i][3] as an example. We need to compute the number of i-bit numbers (i > 4) whose representation does not contain 3 consecutive ones. All i-bit numbers are the union of the following groups:

Obviously, among the last group there is not a single number whose representation does not contain three consecutive ones.

All these groups, by definition, share no common numbers, and therefore the required count of desired numbers equals the sum of the counts of desired numbers in each group:

r[i][3] = r[i-1][3] + r[i-2][3] + r[i-3][3].

And in the general case:

r[i][j] = r[i-1][j] + r[i-2][j] + …​ + r[i-j][j].

The complete solution program is presented in Listing 2.21.

An attentive reader who has tried to delve deeper into the essence of the proposed computations may note: to fill a two-dimensional matrix we use a triple loop. Moreover, in this innermost loop we are essentially adding up nearly the same numbers each time. Let us try to improve this solution based on more refined reasoning.

Suppose we want to compute first:

\(R[i,j\) = R[i-1,j] + R[i-2,j] + …​ + R[i-j,j].]

And before that we computed:

\(R[i-1,j\) = R[i-2,j] + R[i-3,j] + .. + R[i-j,j] + R[i-1-j,j].]

One can notice that

\(R[i,j\) = R[i-1,j] + (R[i-1,j] – R[i-1-j,j]) =]

\(= 2 * R[i-1,j\) – R[i-1-j,j].]

And then the program can look as shown in Listing 2.22.

IOI'99. Day 1. Problem 2.

You want to arrange the window of your flower shop in the most aesthetically pleasing way. You have \(F\) bouquets (each bouquet consists of flowers of one kind, and all flowers of one kind are collected in one bouquet) and no fewer vases arranged in a row. The vases are glued to the shelf and numbered from left to right consecutively from 1 to \(V\), where \(V\) is the number of vases. Vase 1 is the leftmost in the row, and vase \(V\) is the rightmost. Bouquets can be placed in different vases, and each bouquet has a unique number in the range from 1 to \(F\). The placement order of bouquets in vases is as follows: bouquet number \(i\) is always placed in a vase that stands to the left of the vase containing bouquet \(j\), if \(i < j\). For example, suppose you have a bouquet of azaleas numbered 1, a bouquet of begonias numbered 2, and a bouquet of carnations numbered 3. All bouquets must be placed in vases. The azalea bouquet must be placed in a vase to the left of the begonias, and the begonia bouquet must be to the left of the carnations. If there are more vases than bouquets, some vases will remain empty. Each vase can contain at most one bouquet.

Each vase has its own characteristics, as do the flowers. Therefore, a bouquet placed in a vase has a certain aesthetic value expressed as an integer. The aesthetic values are given in Table 2.1. An empty vase has an aesthetic value of zero.

Table 2.1. Aesthetic values of bouquets in various vases

According to Table 2.1, azaleas look wonderful in the second vase and terrible in the fourth. To achieve the best aesthetic arrangement of the display, you must maximize the sum of aesthetic values of flower placements in vases while maintaining the required ordering of bouquets. If there are multiple placements having the maximum sum, you should output only one of them.

Constraints: \(1 ≤ F ≤ 100\) and \(F ≤ V ≤ 100\), and also \(-50 ≤ Aij ≤ 50\), where \(Aij\) is the aesthetic value obtained by placing bouquet \(i\) in vase \(j\).

The input text file is called flower.inp, and its first line contains two numbers: \(F\), \(V\). Each of the following \(F\) lines contains \(V\) integers: \(A[i,j\)] is the \(j\)-th number in the \((i+1)\)-th line of the input file.

The output file — flower.out — consists of two lines:

For example:

1) flower.inp

2) flower.out

Verification: your program must execute in no more than two seconds. Partial solutions for each test will not be scored.

So, we are trying to devise a recurrence relation for the example given above. We have two parameters: the number of vases and the number of bouquets. Let r[i][j] be the score of the best placement of i bouquets in j vases (i from 1 to F, j from 1 to V):

Let us start with the case when there is exactly 1 bouquet (azalea). Then for the given number of vases we simply need to choose the best one: if there is only one vase (the first) — then that’s the one (aesthetic value equals 7), and for all other numbers of vases (2, 3, 4, 5) — it is best to place this bouquet in the 2nd.

Thus, we have:

Furthermore, it is obvious that if the number of bouquets is exactly equal to the number of vases, then the only possible option is to place each bouquet in the vase with the same number and then add the corresponding values:

Elements below the main diagonal are obviously zero (if there are more bouquets than vases). But the problem conditions always ensure that the number of vases is greater than the number of bouquets. Therefore, this part of the list need not be filled.

The remaining elements (above the main diagonal) are logically constructed as follows: r[2][3] is the optimal placement of 2 bouquets in 3 vases.

If we place the 2nd bouquet in the 3rd vase, then the total score will be:

a[2][3] + r[1][2] = -4 + 23 = 19.

The remaining one bouquet can be optimally placed in the first two vases.

If we do not place the 2nd bouquet in the 3rd vase, then the optimal placement remains the same, as does the optimal score r[2][2] = 28 (placement of 2 bouquets in 2 vases).

According to the problem conditions, we must choose the better option — 28.