Решите уравнение указанным в варианте методом. Функцию передать как параметр с помощью указателя.
Довольно часто на практике приходится решать уравнения вида:$$F(x)=0$$ где функция $$F(x)$$ определена и непрерывна на некотором конечном или бесконечном интервале$$\alpha < x < \beta$$
Всякое значение $$\overline{x}$$ такое, что $$F(\overline{x})\equiv 0$$, называется корнем уравнения, а нахождение этого значения и есть решение уравнения.
На практике в большинстве случаев найти точное решение возникшей математической задачи не удается. Поэтому важное значение приобрели численные методы, позволяющие найти приближенное значение корня. Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет компьютер.
Существует множество
Представим уравнение $$F(x)=0$$ в виде:$$x=f(x)$$
Это уравнение получается выделением $$x$$ из уравнения $$F(x)$$ и переносом того, что осталось, т.е. $$f(x)$$, в левую часть уравнения. Иначе можно получить уравнение (2) следующим способом: левую и правую часть уравнения (1) умножить на произвольную константу $$\lambda$$ и прибавить к левой и правой части $$x$$, т.е. получаем уравнение вида:$$x=x+\lambda F(x)$$ где $$f(x)=x+\lambda F(x)$$.
На заданном отрезке $$[a; b]$$ выберем точку $$х_0$$ – нулевое приближение – и найдем$$x_1=f(x_0),$$ потом найдем:$$x_2=f(x_1),$$
Таким образом, процесс нахождения корня уравнения сводится к последовательному вычислению чисел:$$x_n=f(x_{n-1})\quad n=1,2,3 \ldots .$$ Этот процесс называется методом итераций.
Если на отрезке $$[a; b]$$ выполнено условие:$$|f'(x_0)|\leq q<1,$$ то процесс итераций сходится, т.е.$$\lim_{n\rightarrow\infty}x_n=\overline{x}$$
Процесс итераций продолжается до тех пор, пока$$|x_n-x_{n-1}|\leq\varepsilon,$$
где – $$\varepsilon$$ заданная
Пусть уравнение $$F(x)=0$$ имеет один корень на отрезке $$[a; b]$$, причем $$F'(x)$$ и $$F''(x)$$ определены, непрерывны и сохраняют постоянные знаки на отрезке $$[a; b]$$.
Выберем на отрезке $$[a; b]$$ произвольную точку $$х_0$$ – нулевое приближение. Затем найдем:$$x_1=x_0-\frac{F(x_0)}{F'(x_0)}$$ потом$$x_2=x_1-\frac{F(x_1)}{F'(x_1)}$$
Таким образом, процесс нахождения корня уравнения сводится к вычислению чисел $$x_n$$ по формуле:$$x_n=x_{n-1}-\frac{F(x_{n-1})}{F'(x_{n-1})},\quad n=1,2,3\ldots$$
Этот процесс называется методом Ньютона.
Процесс вычисления продолжается до тех пор, пока не будет выполнено условие:$$|x_n-x_{n-1}|\leq\varepsilon,$$
где – $$\varepsilon$$ заданная
Точку $$х_0$$ необходимо выбирать так, чтобы выполнялось условие:$$F(x_0)\dot F'(x_0)>0,$$ иначе метод не будет сходиться.
Пусть уравнение $$F(x_0)$$ имеет один корень на отрезке $$[a, b]$$. Функция непрерывна на отрезке $$[a, b]$$.
Сначала выбираем начальное приближение, деля
Если $$F(x_0)=0$$, то $$x_0$$ является корнем уравнения. Если $$F(x_0)\neq 0,$$ то выбираем тот из отрезков, на концах которого функция имеет противоположные знаки. Полученный
Процесс деления отрезка продолжаем до тех пор, пока длина отрезка, на концах которого функция имеет противоположные знаки, не будет меньше заданной точности $$\varepsilon$$, т.е. пока не будет выполняться условие:$$|x_n-x_{n-1}|\leq\varepsilon.$$
Варианты задания
| № | Уравнение | Метод | Значение корня с точностью 10-4 | |
|---|---|---|---|---|
| 1 | $$3\sin\sqrt{x}+0,35x-3,8=0$$ | [2;3] | Итераций | 2,2985 |
| 2 | $$0,25x^3+x-1,2502=0$$ | [0;2] | Ньютона | 1,0001 |
| 3 | $$x-\frac{1}{3+\sin 3,6x}=0$$ | [0;0,85] | Итераций | 0,2624 |
| 4 | $$0,1x^2-x\ln x=0$$ | [1;2] | Ньютона | 1,1183 |
| 5 | $$\tg x=\frac13\tg^3 x+\frac15\tg^5 x-\frac13=0$$ | [0;8] | Половинного деления | 0,3333 |
| 6 | $$\arccos x-\sqrt{1-0,3 x^3}=0$$ | [0;1] | Итераций | 0,5629 |
| 7 | $$3x-4\ln x-5=0$$ | [2;4] | Ньютона | 3,2300 |
| 8 | $$\cos\frac{2}{x}-2\sin\frac{1}{x}+\frac{1}{x}=0$$ | [1;2] | Половинного деления | 1,8756 |
| 9 | $$\sqrt{1-0,4x^2}-\arcsin x=0$$ | [0;1] | Итераций | 0,7672 |
| 10 | $$e^x-e^{-1}-2=0$$ | [0;1] | Ньютона | 0,8814 |
| 11 | $$\sin(\ln x)-\cos(\ln x)+2\ln x=0$$ | [1;3] | Половинного деления | 1,3749 |
| 12 | $$x-2+\sin\frac{1}{x}=0$$ | [1,2;2] | Итераций | 1,3077 |
| 13 | $$e^x+\ln x-10x=0$$ | [3;4] | Ньютона | 3,5265 |
| 14 | $$\cos x-e^{\frac{-x^2}{2}}+x-1=0$$ | [1;2] | Половинного деления | 1,0804 |
| 15 | $$1-x+\sin x-\ln(1+x)=0$$ | [0;1,5] | Итераций | 1,1474 |
| 16 | $$3x-14+e^x-e^{-x}=0$$ | [1;3] | Ньютона | 2,0692 |
| 17 | $$\sqrt{1-x}-\tg x=0$$ | [0;1] | Половинного деления | 0,5768 |
| 18 | $$x+\cos(x^{0.52}+2)=0$$ | [0,5;1] | Итераций | 0,9892 |
| 19 | $$3\ln^2 x+6\ln x-5=0$$ | [1;3] | Ньютона | 1,8832 |
| 20 | $$\sin x^2+\cos x^2-10x=0$$ | [0;1] | Половинного деления | 0,1010 |
| 21 | $$x^2-\ln(1+x)-3=0$$ | [2;3] | Итераций | 2,0267 |
| 22 | $$2x\sin x-\cos x=0$$ | [0,4;1] | Ньютона | 0,6533 |
| 23 | $$e^x+\sqrt{1+e^{2x}}-2=0$$ | [-1;0] | Половинного деления | -0,2877 |
| 24 | $$\ln x-x+1.8=0$$ | [2;3] | Итераций | 2,8459 |
| 25 | $$\sqrt[3]{x-4}-\frac{1}{x^2+1}=0$$ | [4;6] | Ньютона | 4,0002 |
| 26 | $$e^x-2\cos x=0$$ | [0;2] | Половинного деления | 0,5398 |
| 27 | $$\sqrt[3]{x+2}-3x+16=0$$ | [4;7] | Итераций | 6,0000 |
| 28 | $$\frac{\pi\sin x}{x}-3\cos x-2=0$$ | [1;2] | Ньютона | 1,5708 |
<td>: каждому открытому тегу должен соответствовать закрытый </td>.Решите задачи данной группы, оформив решение в виде функций генерации, вывода и обработки массивов. Предусмотрите в функции генерации массива ввод границ диапазона случайных чисел.
Решите задачи данной группы, оформив решение в виде функций генерации, вывода и обработки массивов. Предусмотрите в функции генерации массива ввод границ диапазона случайных чисел.
Решите задачи данной группы, оформив решение в виде функций генерации, вывода и обработки массивов. Предусмотрите в функции генерации массива ввод границ диапазона случайных чисел.
Организуйте работу с текстовым файлом. Исходные файлы не предполагают изменения. Измененные данные сохраните в другом файле.
Решите задачи данной группы, выполняя следующие требования:
Варианты задания
| № | Вид преобразования массива |
|---|---|
| 1 | Добавить строку с заданным номером. |
| 2 | Добавить столбец с заданным номером. |
| 3 | Добавить строку в конец матрицы. |
| 4 | Добавить столбец в конец матрицы. |
| 5 | Добавить строку в начало матрицы. |
| 6 | Добавить столбец в начало матрицы. |
| 7 | Добавить К строк в конец матрицы. |
| 8 | Добавить К столбцов в конец матрицы. |
| 9 | Добавить К строк в начало матрицы. |
| 10 | Добавить К столбцов в начало матрицы. |
| 11 | Удалить строку с номером К. |
| 12 | Удалить столбец с номером К. |
| 13 | Удалить строки, начиная со строки К1 и до строки К2. |
| 14 | Удалить столбцы, начиная со столбца К1 и до столбца К2. |
| 15 | Удалить все четные строки. |
| 16 | Удалить все четные столбцы. |
| 17 | Удалить все строки, в которых есть хотя бы один нулевой элемент. |
| 18 | Удалить все столбцы, в которых есть хотя бы один нулевой элемент. |
| 19 | Удалить строку, в которой находится наибольший элемент матрицы. |
| 20 | Добавить строки после каждой четной строки матрицы. |
| 21 | Добавить столбцы после каждого четного столбца матрицы. |
| 22 | Добавить К строк, начиная со строки с номером N. |
| 23 | Добавить К столбцов, начиная со столбца с номером N. |
| 24 | Добавить строку после строки, содержащей наибольший элемент. |
| 25 | Добавить столбец после столбца, содержащего наибольший элемент. |
| 26 | Добавить строку после строки, содержащей наименьший элемент. |
| 27 | Добавить столбец после столбца, содержащего наименьший элемент. |
| 28 | Удалить строку и столбец, на пересечении которых находится наибольший элемент массива. |
Решите задачи данной группы, выполняя следующие требования:
Варианты задания
| № | Тип информационного поля | |
|---|---|---|
| 1 | $$char$$ | Найти количество элементов с заданным ключом. |
| 2 | $$int$$ | Найти максимальный элемент в дереве. |
| 3 | $$char*$$ | Найти количество листьев в дереве. |
| 4 | $$double$$ | Найти минимальный элемент в дереве. |
| 5 | $$char$$ | Найти |
| 6 | $$int$$ | Найти среднее арифметическое элементов дерева. |
| 7 | $$char*$$ | Найти количество элементов дерева, начинающихся с заданного символа. |
| 8 | $$char$$ | Найти количество элементов с заданным ключом. |
| 9 | $$double$$ | Найти максимальный элемент в дереве. |
| 10 | $$int$$ | Найти количество листьев в дереве. |
| 11 | $$double$$ | Найти минимальный элемент в дереве. |
| 12 | $$char$$ | Найти |
| 13 | $$int$$ | Найти среднее арифметическое элементов дерева. |
| 14 | $$char$$ | Найти количество элементов с заданным ключом. |
| 15 | $$char*$$ | Найти количество элементов дерева, начинающихся с заданного символа |
| 16 | $$int$$ | Найти максимальный элемент в дереве. |
| 17 | $$double$$ | Найти количество листьев в дереве. |
| 18 | $$int$$ | Найти минимальный элемент в дереве. |
| 19 | $$char$$ | Найти |
| 20 | $$double$$ | Найти среднее арифметическое элементов дерева. |
| 21 | $$char*$$ | Найти количество элементов дерева, начинающихся с заданного символа. |
| 22 | $$char$$ | Найти количество элементов с заданным ключом. |
| 23 | $$char$$ | Найти количество листьев в дереве. |
| 24 | $$double$$ | Найти максимальный элемент в дереве. |
| 25 | $$double$$ | Найти минимальный элемент в дереве. |
| 26 | $$char$$ | Найти |
| 27 | $$float$$ | Найти среднее арифметическое элементов дерева. |
| 28 | $$int$$ | Найти количество элементов с заданным ключом. |
Разработайте рекурсивный алгоритм для решения задачи.
1-10. Определите закономерность формирования членов последовательности. Найдите $$N$$ -ый член последовательности, сократив количество рекурсивных вызовов.
11-20. Найдите значение функции для любых целых неотрицательных аргументов.
21-28. Составьте
1. Закраска прямой. На числовой прямой окрасили $$N$$ отрезков. Известны координаты левого и правого концов каждого отрезка ( $$L_i$$ и $$R_i$$ ). Найти длину окрашенной части числовой прямой.
Ограничения: $$L_i$$ и $$R_i$$ – целые, $$-1 000 000 000 \leq L_i \leq R_i \leq 1 000 000 000$$, $$1 \leq N \leq 15 000$$, время 1 с.
Ввод из файла
Вывод в файл
Примеры
2. Сумма произведений. Дан набор переменных $$х_1, х_2, \ldots , x_N$$. Каждая переменная $$х_i$$ может принимать значение только -1, 0 или +1. Для данного целого числа $$S$$ требуется определить количество способов присвоить переменным $$х_i$$ значения так, чтобы сумма всех возможных произведений $$хi хj$$ была равна $$S$$, где $$i < j$$ и $$i, j = 1, 2, \ldots, N$$. Два способа считаются различными, если они содержат различное число $$х_i = 0$$.
Ограничения: $$2 \leq N \leq 10 000$$, $$-10 000 \leq S \leq 10 000$$, время 1 с.
Ввод из файла prodsum.in. В первой строке находятся числа $$N$$ и $$S$$, разделенные пробелом.
Вывод в файл prodsum.out. Вывести одно целое число – количество способов представить $$S$$ как сумму произведений.
Примеры
3. Статическая сложность. Анализ временной сложности алгоритмов – важный инструмент создания эффективных программ. Алгоритмы, выполняемые за линейное время, как правило, значительно быстрее алгоритмов, требующих для выполнения той же задачи квадратичного времени, так что предпочтение должно быть отдано первым.
Обычно определяют время выполнения алгоритма по отношению к $$n$$ – "размеру" входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т.п. Поскольку определение формулы зависимости временной сложности алгоритма от $$n$$ – непростая задача, было бы замечательно, если бы ее можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам
<Программа> : := "BEGIN" <Список операторов> "END" <Список операторов>::=<Оператор>|<Оператор><Список операторов> <Оператор> ::=<Оператор LOOP> | <Оператор 0P> <Оператор LOOP> ::=<Заголовок ЮОР><Список операторов>"END" <Заголовок LOOP> : := "LOOP" <число> | "LOOP n" <Оператор OP> : := "OP" <число>
Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора ОР требует столько единиц времени, сколько указано в его параметре. Список операторов, заключенный в оператор
Ввод из файла icomplex.in. В первой строке находится целое число $$k$$ — число программ во входном файле. Затем идут $$k$$ программ, удовлетворяющих приведенной BEGIN, END,
Вывод в файл icomplex.out Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах $$n$$ – Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k ". Если время выполнения нулевое, нужно вывести " Runtime = 0 ". За строкой с многочленом должна следовать пустая строка.
Ограничения: вложенность операторов
Пример
4. Строки Фибоначчи. Строку Фибоначчи $$F(K)$$ для натуральных чисел $$K$$ определим так: $$F(1) ='A', F(2) ='В', F(K) = F(K – 1) + F(K – 2)$$ при $$K > 2$$, где "+" означает
Ограничения: Длина строки $$S$$ составляет от 1 до 25 символов, $$1 \leq N \leq 45$$, время 1 с.
Примечание. Длина $$F(45)$$ равна 1 134 903 170.
Ввод из файла fibostr.in. В первой строке содержится число $$N$$, во второй – строка $$S$$.
Вывод в файл fibostr.out. Вывести одно число – количество вхождений строки $$S$$ в строку Фибоначчи $$F(N)$$.
Примеры
5. Анти-QuickSort. Для сортировки последовательности чисел широко используется быстрая сортировка – while ). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
Ввод из файла antiqs.in. В первой строке находится единственное число $$N$$.
Ограничения: $$1 \leq N \leq 70 000$$, время 1 с.
Вывод в файл antiqs.out. Вывести перестановку чисел от 1 до $$N$$, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
Пример
6. Путь коня. Дана шахматная доска, состоящая из $$N\times N$$ клеток; несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.
Ограничения: $$2 \leq N \leq 50$$, время 1 с.
Ввод из файла knightw.in. В первой строке задано число $$N$$. В следующих $$N$$ строках содержится по $$N$$ символов. Символом # обозначена вырезанная клетка, точкой – невырезанная клетка, @ — заданные клетки (таких символов два).
Вывод в файл knightw.out. Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.
Примеры
7. Грядки. Прямоугольный садовый участок шириной $$N$$ и длиной $$М$$ метров разбит на квадраты со стороной 1 м. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
Подсчитайте количество грядок на садовом участке.
Ограничения: $$1 \leq N, M \leq 200$$, время 1 с.
Ввод из файла beds.in. В первой строке находятся числа $$N$$ и $$М$$ через пробел, далее идут $$N$$ строк по $$М$$ символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет.
Вывод в файл beds.out. Вывести одно число – количество грядок на садовом участке.
Пример
8. Упорядоченные дроби. Вывести в порядке возрастания все несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают $$N$$.
Ограничения: $$2 \leq N \leq 255$$, время 1 с.
Ввод из файла ordfrac.in. В первой строке находится единственное число $$N$$.
Вывод в файл ordfrac.out. В каждой строке выводится дробь.
Пример
9. Сообщение. В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили ее порядковым номером в русском
Ограничения: цифр не более 100, время 1 с.
Ввод из файла message.in. В первой строке содержится последовательность цифр.
Вывод в файл message.out. Вывести одно число.
Пример
10. Умножение многочленов. Ввести в символьной форме два многочлена от х с целыми коэффициентами и вывести их произведение в порядке убывания степеней – также в символьной форме.
Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 104, время 1 с.
Ввод из файла polymul.in. В двух строках находятся многочлены.
Вывод в файл polymul.out. В единственной строке выводится
Примеры
11. Гомер Симпсон. Обеденный перерыв Гомера Симпсона составляет $$T$$ мс. Один гамбургер Гомер съедает за $$N$$ мс, один чизбургер — за $$M$$. Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва.
Ограничения: $$1 \leq M, N, T \leq 1 000 000$$, все числа целые, время 2 с.
Ввод из файла homer.in. В первой строке находятся три числа – $$M$$, $$N$$ и $$T$$, разделенные пробелами.
Вывод в файл homer.out. Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остается какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остается как можно меньше.
Примеры
12. Диалог компьютеров. Три компьютера соединены сетью. Один из них – сервер, два других – клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение – второму.
Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать
Пусть вы знаете все полные имена файлов, находящихся на сервере, и слушаете разговор клиентов. Основываясь на этой беседе, вы должны определить набор файлов, которые могли быть выбраны сервером. Файлы в этом наборе называются файлами-кандидатами.
Ввод из файла dialogue.in. В первой строке находятся два целых числа, $$N$$ и $$M$$, разделенные пробелом: $$N$$ – число файлов на сервере, $$М$$ – число сообщений, посланных клиентами, пытающимися определить
Каждая из следующих $$N$$ строк содержит одно имя.расширение, где и имя, и расширение состоят только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трех символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.
Каждое
Ограничения: $$1 \leq N \leq 1000, 1 \leq M \leq 100$$, время 3 с.
Вывод в файл dialogue.out. В первой строке выводится число файлов-кандидатов для данных набора файлов и числа сообщений между клиентами. Выводится 0, если файлы-кандидаты отсутствуют.
В следующих строках находятся полные имена файлов-кандидатов, каждое в отдельной строке. Они должны идти в том же порядке и в том же написании, что и во входном файле. Это означает, что если разделяющая точка в названии конкретного файла была опущена во входном файле, то она должна быть опущена и в выводе, и наоборот. Файл нельзя упоминать более одного раза.
Пример
13. Бросание кубика. Кубик, грани которого помечены цифрами от 1 до 6, бросают $$N$$ раз. Найти вероятность того, что сумма выпавших чисел будет равна $$Q$$.
Ограничения: $$1 \leq N \leq 500, 1 \leq Q \leq 3000$$, время 1 с.
Ввод из файла
Вывод в файл
Примеры
14. Ближайшее число. Дана матрица $$A$$ размером $$N\times N$$, заполненная неотрицательными целыми числами. Расстояние между двумя элементами $$A_{ij}$$ и $$A_{pq}$$ определено как $$|i – p| + |j – q|$$. Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.
Ограничения: $$1 \leq N \leq 200, 0 \leq A_{ij} \leq 1 000 000$$, время 3 с.
Ввод из файла neamum.in. В первой строке содержится число $$N$$. Затем идут $$N$$ строк по $$N$$ чисел, разделенных пробелами и представляющих собой матрицу.
Вывод в файл neamum.out. Выводится $$N$$ строк по $$N$$ чисел, разделенных пробелами, – модифицированная матрица.
Пример
15. Прямоугольное деление. Дано $$N$$ прямоугольников со сторонами, параллельными осям координат. Требуется определить, на сколько частей эти прямоугольники разбивают плоскость (внутри частей не должно быть границ прямоугольников).
Ввод из файла rectpart.in. В первой строке содержится число прямоугольников $$N$$. Далее идут $$N$$ строк, содержащих по четыре числа, $$x_1 y_1 x_2, y_2$$, – координаты двух противоположных углов прямоугольника.
Ограничения: $$1 \leq N \leq 100$$, координаты представляют собой целые числа и по
Вывод в файл rectpart.out Вывести одно число – количество частей, на которые разбивается плоскость.
Пример
16. Водопровод. Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке $$(х_1, у_1)$$, а вторая – в точке $$(x_2, у_2)$$. К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 $$\deg$$. Требуется, зная длины отрезков труб $$L_1, L_2, \ldots, L_K$$ и количество отрезков каждой длины $$C_1, C_2, \ldots, C_K$$, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.
Ограничения: $$1 \leq K \leq 4, 1 \leq x_1, y_1, x_2, y_2, Li \leq 1000, 1 \leq C_i \leq 10$$, все числа целые, время 3 с.
Ввод из файла wpipe.in. В первой строке находятся числа $$x_1, y_1, x_2, y_2, K$$, затем $$2K$$ чисел: $$L_1, L_2, \ldots, L_K , C_1, C_2, \ldots, C_K$$.
Вывод в файл wpipe.out. Вывести одно число — минимальное количество нужных отрезков труб или -1, если соединение невозможно.
17. Химические реакции. Билл преподает химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство).
Ваша задача - написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из заданной левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.
Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделенных знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Еще более формально, используя нотацию, аналогичную
<формула>::=[<число>]<последовательность>{"+"[<число>]<последовательность>}
<последовательность>::=<элемент>[<число>]{<элемент>[<число>]}
<элемент>::=<химический элемент>|"("<последовательность>")"
<химический элемент>::=<прописная буква>[<строчная буква>]
<прописная 6уква>::= "А".."Z"
<строчная буква>::= "а".."z"
<число>::= "1". ."9" {"0". ."9"}
Будем говорить, что каждый отдельный химический элемент встречается в формуле всего $$X$$ раз, если $$X$$ – сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле
C2H5OH+3O2+3(SiO2)
C встречается всего 2 раза;H встречается всего 6 раз (5 + 1);0 встречается всего 13 раз (1 + 3 * 2 +3 * 2);Si Все множители в формулах – целые числа не меньше 2, если заданы явно, или равны 1 – по умолчанию.
Ввод из файла chem.in. В первой строке находится формула — левая часть уравнения, во второй – одно число $$N$$ – количество рассматриваемых правых частей, в каждой из следующих $$N$$ строк – одна формула – предлагаемая правая часть уравнения.
Ограничения: $$1 \leq N \leq 10$$, длина формулы не превосходит 100 символов, каждый
Вывод в файл chem.out. Для каждой из $$N$$ заданных правых частей выведите одну строку вида
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть замещена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> – замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.
Пример
18. Суммы. Дано $$N$$ целых чисел $$A_1, A_2,\ldots, A_N$$. Требуется найти количество различных значений сумм вида $$k_{1A1} + k_{2A2} + k_NA_N$$.
Ограничения: $$1 \leq N \leq 500, 0 \leq A_i \leq 100, 0 \leq k_i \leq 1$$, все числа целые, время 2 с.
Ввод из файла sums.in. В первой строке находится число $$N$$, во второй – $$A_1, A_2,\ldots, A_N$$.через пробел.
Вывод в файл sums.out. Вывести одно число – количество различных значений сумм.
Примеры
19. Lines. В таблице из $$N$$ строк и $$N$$ столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
Ограничения: $$2 \leq N \leq 40$$, время 1 с.
Ввод из файла lihes.in. В первой строке находится число $$N$$, в следующих $$N$$ строках – по $$N$$ символов. Символом точки обозначена свободная клетка, латинской заглавной $$0$$ – шарик, @ – исходное положение шарика, который должен двигаться, латинской заглавной $$X$$ — конечное положение шарика.
Вывод в файл lihes.out. В первой строке выводится $$Y$$, если движение возможно, или $$N$$, если нет. Если движение возможно, далее следует $$N$$ строк по $$N$$ символов – как и на вводе, но буква $$X$$, а также все точки по пути заменяются плюсами.
Примеры
20. Покраска лабиринта. Лабиринт представляет собой квадрат, состоящий из $$N\times N$$ сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (рис.). Помогите ему рассчитать количество краски, необходимой для этого.
Ограничения: $$3 \leq N \leq 33$$, размер сегмента 3 x 3 м, высота стен 3 м, время 1 с.
Ввод из файла paintlab.in. В первой строке находится число $$N$$, затем идут $$N$$ строк по $$N$$ символов: точка обозначает пустой сегмент, решетка – сегмент со стеной.
Вывод в файл paintlab.out. Вывести одно число – площадь видимой части внутренних стен лабиринта в квадратных метрах.
21. Поле для крикета. Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложения своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер.
Ваша задача – помочь бедному Архитектору сохранить голову, написав программу, которая найдет максимальный размер поля для крикета и его положение внутри парка, удовлетворяющие требованиям Короля.
Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север – юг и восток – запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север – юг и восток – запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева.
Оси этой
В этой задаче вы можете пренебречь
Ввод из файла cricket.in. Первая строка содержит три целых числа, $$N$$, $$W$$ и $$H$$, разделенных пробелами: $$N$$ — число деревьев в парке, $$W$$ и $$H$$ – длина и ширина парка соответственно.
Следующие $$N$$ строк описывают координаты деревьев в парке. Каждая строка содержит два целых числа $$x_i$$ и $$y_i$$ разделенных пробелом и представляющих собой координаты $$i$$ -го дерева. Все деревья имеют различные координаты.
Ограничения: $$1 \leq N \leq 100, 1 \leq W, H \leq 10 000, 0 \leq x_i \leq W, 0 \leq y_i \leq H$$, время 1 с.
Вывод в файл cricket.out. Вывести через пробел три целых числа, $$P$$, $$Q$$ и $$L$$, где $$(P, Q)$$ – координаты юго-западного угла поля для крикета, $$L$$ – длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.
Пример
22. Электронная таблица. Напишите программу, выполняющую функции очень простой электронной таблицы. Она работает с таблицей из 9 строк от 1 до 9 и 26 столбцов от А до Z. Клетки таблицы обозначаются именами, составленными из кодов столбца и строки, например B1, S8.
Каждая клетка содержит выражение. Выражения используют целые константы, ссылки на клетки, скобки,
Так, 567, E8/2, (3+B3)*(C4-l) являются правильными выражениями. Все операторы целочисленные. Деление на ноль дает в результате ноль.
Если значение ячейки, на которую ссылается некоторое выражение, не определено, оно считается равным нулю. Ситуация, когда две или более ячейки зависят друг от друга, является отдельным случаем – циклической ссылкой.
Ограничения: длина выражения в одной ячейке до 255 символов, все аргументы и результаты меньше 1 000 000, время 1 с.
Ввод из файла sprsheet.in. Первая строка содержит число выражений $$N$$. Следующие N строк имеют формат <Имя клетки>=<выражение>. Все выражения корректные, и каждая ячейка определена не более чем одним выражением.
Вывод в файл sprsheet.out. В единственной строке выводится или значение клетки A1, или число 1000000 (один миллион), если значение клетки A1 не может быть найдено из-за циклической ссылки.
Пример
23. Путь спелеолога. Пещера представлена кубом, разбитым на $$N$$ частей по каждому измерению (то есть на $$N^3$$ кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.
Ограничения: $$1 \leq N \leq 30$$, время 1 с.
Ввод из файла speleo.in. В первой строке содержится число $$N$$. Далее следует $$N$$ блоков. Блок состоит из пустой строки и $$N$$ строк по $$N$$ символов: # обозначает клетку, заполненную камнями, точка – свободную клетку. Начальное положение спелеолога обозначено заглавной буквой $$S$$. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.
Вывод в файл speleo.out. Вывести одно число –
Пример
Комментарий
Нужно спуститься на уровень вниз, сделать два движения на запад, подняться на уровень вверх, сделать движение на юг, подняться на уровень вверх.
24. Дырявая ткань. На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен черно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади – точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.
На схеме три куска – один без дыр, а два – с одной дырой каждый: первый – площадью 8, второй – площадью 12.
Ваша цель – найти кусок с наибольшим количеством дыр в нем. Дыра – это 4-связная область точек, полностью окруженных символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.
Ввод из файла holey.in. В первой строке содержатся два числа $$W$$ и $$H$$, разделенные пробелами. Следующие $$H$$ строк содержат по $$W$$ символов каждая. Символы в этих строках – или * (ASCII 42), или точка (ASCII 46).
Ограничения: $$1 \leq W, H \leq 100$$, время 1 с.
Вывод в файл holey.out. Вывести одно целое число – площадь минимального из наиболее дырявых кусков. Если нет кусков с дырами, выходной файл должен содержать ноль.
Пример
25. Несоставляемое число. Даны $$N$$ натуральных чисел. Найти минимальное
Ограничения: $$1 \leq N \leq 10 000$$, значения исходных чисел от 1 до 1 000 000 000, время 1 с.
Ввод из файла nosum.in. В первой строке находится число $$N$$, в следующих $$N$$ строках – по одному натуральному числу.
Вывод в файл nosum.out. Вывести одно число.
Примеры
26. SMS. Сообщения
(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)
Чтобы ввести две буквы, находящиеся на одной кнопке, нужно между нажатиями клавиши сделать паузу. Например, чтобы ввести сообщение "АА", нужно нажать (АВС)(пауза)(АВС)
Если на кнопке три буквы, то, как только такая кнопка нажата три раза, последняя буква добавляется в сообщение немедленно, а следующие нажатия той же кнопки относятся к следующей букве сообщения. Аналогично, если на кнопке четыре буквы, то после четырех нажатий в сообщение будет добавлена последняя буква. То есть последовательность нажатий
(АВС)(АВС)(АВС)(АВС)(пауза)(АВС)
соответствует сообщению "САА". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили
Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое вы получили.
Ограничения: $$1 \leq N \leq 80$$, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения – от 1 до 80 букв, время 2 с.
Ввод из файла
Вывод в файл
Примеры
27. Lines. В таблице из $$N$$ строк и $$N$$ столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
Ограничения: $$2 \leq N \leq 250$$, время 1 с.
Ввод из файла lines2.in. В первой строке находится число $$N$$, в следующих $$N$$ строках – по $$N$$ символов. Символом точки обозначена свободная клетка, латинской заглавной 0 — шарик, @ — исходное положение шарика, который должен двигаться, латинской заглавной $$X$$ — конечное положение шарика.
Вывод в файл lines2.out. В первой строке выводится $$Y$$, если движение возможно, или $$N$$, если нет. Если движение возможно, далее следует $$N$$ строк по $$N$$ символов – как и на вводе, но $$X$$, а также все точки по пути заменяются плюсами.
Примеры
28. Удаление клеток. Из прямоугольного листа клетчатой бумаги ( $$М$$ строк, $$N$$ столбцов) удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Ограничения: $$1 \leq M, N \leq 100$$, время 1 с.
Ввод из файла remsquar.in. В первой строке находятся числа $$M$$ и $$N$$, в следующих $$М$$ строках – по $$N$$ символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана – точка.
Вывод в файл remsquar.out. Вывести одно число.
Пример
Решите уравнение указанным в варианте методом. Функцию передать как параметр с помощью указателя.
Довольно часто на практике приходится решать уравнения вида:$$F(x)=0$$ где функция $$F(x)$$ определена и непрерывна на некотором конечном или бесконечном интервале$$\alpha < x < \beta$$
Всякое значение $$\overline{x}$$ такое, что $$F(\overline{x})\equiv 0$$, называется корнем уравнения, а нахождение этого значения и есть решение уравнения.
На практике в большинстве случаев найти точное решение возникшей математической задачи не удается. Поэтому важное значение приобрели численные методы, позволяющие найти приближенное значение корня. Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами, т.е. к тем действиям, которые выполняет компьютер.
Существует множество
Представим уравнение $$F(x)=0$$ в виде:$$x=f(x)$$
Это уравнение получается выделением $$x$$ из уравнения $$F(x)$$ и переносом того, что осталось, т.е. $$f(x)$$, в левую часть уравнения. Иначе можно получить уравнение (2) следующим способом: левую и правую часть уравнения (1) умножить на произвольную константу $$\lambda$$ и прибавить к левой и правой части $$x$$, т.е. получаем уравнение вида:$$x=x+\lambda F(x)$$ где $$f(x)=x+\lambda F(x)$$.
На заданном отрезке $$[a; b]$$ выберем точку $$х_0$$ – нулевое приближение – и найдем$$x_1=f(x_0),$$ потом найдем:$$x_2=f(x_1),$$
Таким образом, процесс нахождения корня уравнения сводится к последовательному вычислению чисел:$$x_n=f(x_{n-1})\quad n=1,2,3 \ldots .$$ Этот процесс называется методом итераций.
Если на отрезке $$[a; b]$$ выполнено условие:$$|f'(x_0)|\leq q<1,$$ то процесс итераций сходится, т.е.$$\lim_{n\rightarrow\infty}x_n=\overline{x}$$
Процесс итераций продолжается до тех пор, пока$$|x_n-x_{n-1}|\leq\varepsilon,$$
где – $$\varepsilon$$ заданная
Пусть уравнение $$F(x)=0$$ имеет один корень на отрезке $$[a; b]$$, причем $$F'(x)$$ и $$F''(x)$$ определены, непрерывны и сохраняют постоянные знаки на отрезке $$[a; b]$$.
Выберем на отрезке $$[a; b]$$ произвольную точку $$х_0$$ – нулевое приближение. Затем найдем:$$x_1=x_0-\frac{F(x_0)}{F'(x_0)}$$ потом$$x_2=x_1-\frac{F(x_1)}{F'(x_1)}$$
Таким образом, процесс нахождения корня уравнения сводится к вычислению чисел $$x_n$$ по формуле:$$x_n=x_{n-1}-\frac{F(x_{n-1})}{F'(x_{n-1})},\quad n=1,2,3\ldots$$
Этот процесс называется методом Ньютона.
Процесс вычисления продолжается до тех пор, пока не будет выполнено условие:$$|x_n-x_{n-1}|\leq\varepsilon,$$
где – $$\varepsilon$$ заданная
Точку $$х_0$$ необходимо выбирать так, чтобы выполнялось условие:$$F(x_0)\dot F'(x_0)>0,$$ иначе метод не будет сходиться.
Пусть уравнение $$F(x_0)$$ имеет один корень на отрезке $$[a, b]$$. Функция непрерывна на отрезке $$[a, b]$$.
Сначала выбираем начальное приближение, деля
Если $$F(x_0)=0$$, то $$x_0$$ является корнем уравнения. Если $$F(x_0)\neq 0,$$ то выбираем тот из отрезков, на концах которого функция имеет противоположные знаки. Полученный
Процесс деления отрезка продолжаем до тех пор, пока длина отрезка, на концах которого функция имеет противоположные знаки, не будет меньше заданной точности $$\varepsilon$$, т.е. пока не будет выполняться условие:$$|x_n-x_{n-1}|\leq\varepsilon.$$
Варианты задания
| № | Уравнение | Метод | Значение корня с точностью 10-4 | |
|---|---|---|---|---|
| 1 | $$3\sin\sqrt{x}+0,35x-3,8=0$$ | [2;3] | Итераций | 2,2985 |
| 2 | $$0,25x^3+x-1,2502=0$$ | [0;2] | Ньютона | 1,0001 |
| 3 | $$x-\frac{1}{3+\sin 3,6x}=0$$ | [0;0,85] | Итераций | 0,2624 |
| 4 | $$0,1x^2-x\ln x=0$$ | [1;2] | Ньютона | 1,1183 |
| 5 | $$\tg x=\frac13\tg^3 x+\frac15\tg^5 x-\frac13=0$$ | [0;8] | Половинного деления | 0,3333 |
| 6 | $$\arccos x-\sqrt{1-0,3 x^3}=0$$ | [0;1] | Итераций | 0,5629 |
| 7 | $$3x-4\ln x-5=0$$ | [2;4] | Ньютона | 3,2300 |
| 8 | $$\cos\frac{2}{x}-2\sin\frac{1}{x}+\frac{1}{x}=0$$ | [1;2] | Половинного деления | 1,8756 |
| 9 | $$\sqrt{1-0,4x^2}-\arcsin x=0$$ | [0;1] | Итераций | 0,7672 |
| 10 | $$e^x-e^{-1}-2=0$$ | [0;1] | Ньютона | 0,8814 |
| 11 | $$\sin(\ln x)-\cos(\ln x)+2\ln x=0$$ | [1;3] | Половинного деления | 1,3749 |
| 12 | $$x-2+\sin\frac{1}{x}=0$$ | [1,2;2] | Итераций | 1,3077 |
| 13 | $$e^x+\ln x-10x=0$$ | [3;4] | Ньютона | 3,5265 |
| 14 | $$\cos x-e^{\frac{-x^2}{2}}+x-1=0$$ | [1;2] | Половинного деления | 1,0804 |
| 15 | $$1-x+\sin x-\ln(1+x)=0$$ | [0;1,5] | Итераций | 1,1474 |
| 16 | $$3x-14+e^x-e^{-x}=0$$ | [1;3] | Ньютона | 2,0692 |
| 17 | $$\sqrt{1-x}-\tg x=0$$ | [0;1] | Половинного деления | 0,5768 |
| 18 | $$x+\cos(x^{0.52}+2)=0$$ | [0,5;1] | Итераций | 0,9892 |
| 19 | $$3\ln^2 x+6\ln x-5=0$$ | [1;3] | Ньютона | 1,8832 |
| 20 | $$\sin x^2+\cos x^2-10x=0$$ | [0;1] | Половинного деления | 0,1010 |
| 21 | $$x^2-\ln(1+x)-3=0$$ | [2;3] | Итераций | 2,0267 |
| 22 | $$2x\sin x-\cos x=0$$ | [0,4;1] | Ньютона | 0,6533 |
| 23 | $$e^x+\sqrt{1+e^{2x}}-2=0$$ | [-1;0] | Половинного деления | -0,2877 |
| 24 | $$\ln x-x+1.8=0$$ | [2;3] | Итераций | 2,8459 |
| 25 | $$\sqrt[3]{x-4}-\frac{1}{x^2+1}=0$$ | [4;6] | Ньютона | 4,0002 |
| 26 | $$e^x-2\cos x=0$$ | [0;2] | Половинного деления | 0,5398 |
| 27 | $$\sqrt[3]{x+2}-3x+16=0$$ | [4;7] | Итераций | 6,0000 |
| 28 | $$\frac{\pi\sin x}{x}-3\cos x-2=0$$ | [1;2] | Ньютона | 1,5708 |
<td>: каждому открытому тегу должен соответствовать закрытый </td>.Решите задачи данной группы, оформив решение в виде функций генерации, вывода и обработки массивов. Предусмотрите в функции генерации массива ввод границ диапазона случайных чисел.
Решите задачи данной группы, оформив решение в виде функций генерации, вывода и обработки массивов. Предусмотрите в функции генерации массива ввод границ диапазона случайных чисел.
Решите задачи данной группы, оформив решение в виде функций генерации, вывода и обработки массивов. Предусмотрите в функции генерации массива ввод границ диапазона случайных чисел.
Организуйте работу с текстовым файлом. Исходные файлы не предполагают изменения. Измененные данные сохраните в другом файле.
Решите задачи данной группы, выполняя следующие требования:
Варианты задания
| № | Вид преобразования массива |
|---|---|
| 1 | Добавить строку с заданным номером. |
| 2 | Добавить столбец с заданным номером. |
| 3 | Добавить строку в конец матрицы. |
| 4 | Добавить столбец в конец матрицы. |
| 5 | Добавить строку в начало матрицы. |
| 6 | Добавить столбец в начало матрицы. |
| 7 | Добавить К строк в конец матрицы. |
| 8 | Добавить К столбцов в конец матрицы. |
| 9 | Добавить К строк в начало матрицы. |
| 10 | Добавить К столбцов в начало матрицы. |
| 11 | Удалить строку с номером К. |
| 12 | Удалить столбец с номером К. |
| 13 | Удалить строки, начиная со строки К1 и до строки К2. |
| 14 | Удалить столбцы, начиная со столбца К1 и до столбца К2. |
| 15 | Удалить все четные строки. |
| 16 | Удалить все четные столбцы. |
| 17 | Удалить все строки, в которых есть хотя бы один нулевой элемент. |
| 18 | Удалить все столбцы, в которых есть хотя бы один нулевой элемент. |
| 19 | Удалить строку, в которой находится наибольший элемент матрицы. |
| 20 | Добавить строки после каждой четной строки матрицы. |
| 21 | Добавить столбцы после каждого четного столбца матрицы. |
| 22 | Добавить К строк, начиная со строки с номером N. |
| 23 | Добавить К столбцов, начиная со столбца с номером N. |
| 24 | Добавить строку после строки, содержащей наибольший элемент. |
| 25 | Добавить столбец после столбца, содержащего наибольший элемент. |
| 26 | Добавить строку после строки, содержащей наименьший элемент. |
| 27 | Добавить столбец после столбца, содержащего наименьший элемент. |
| 28 | Удалить строку и столбец, на пересечении которых находится наибольший элемент массива. |
Решите задачи данной группы, выполняя следующие требования:
Варианты задания
| № | Тип информационного поля | |
|---|---|---|
| 1 | $$char$$ | Найти количество элементов с заданным ключом. |
| 2 | $$int$$ | Найти максимальный элемент в дереве. |
| 3 | $$char*$$ | Найти количество листьев в дереве. |
| 4 | $$double$$ | Найти минимальный элемент в дереве. |
| 5 | $$char$$ | Найти |
| 6 | $$int$$ | Найти среднее арифметическое элементов дерева. |
| 7 | $$char*$$ | Найти количество элементов дерева, начинающихся с заданного символа. |
| 8 | $$char$$ | Найти количество элементов с заданным ключом. |
| 9 | $$double$$ | Найти максимальный элемент в дереве. |
| 10 | $$int$$ | Найти количество листьев в дереве. |
| 11 | $$double$$ | Найти минимальный элемент в дереве. |
| 12 | $$char$$ | Найти |
| 13 | $$int$$ | Найти среднее арифметическое элементов дерева. |
| 14 | $$char$$ | Найти количество элементов с заданным ключом. |
| 15 | $$char*$$ | Найти количество элементов дерева, начинающихся с заданного символа |
| 16 | $$int$$ | Найти максимальный элемент в дереве. |
| 17 | $$double$$ | Найти количество листьев в дереве. |
| 18 | $$int$$ | Найти минимальный элемент в дереве. |
| 19 | $$char$$ | Найти |
| 20 | $$double$$ | Найти среднее арифметическое элементов дерева. |
| 21 | $$char*$$ | Найти количество элементов дерева, начинающихся с заданного символа. |
| 22 | $$char$$ | Найти количество элементов с заданным ключом. |
| 23 | $$char$$ | Найти количество листьев в дереве. |
| 24 | $$double$$ | Найти максимальный элемент в дереве. |
| 25 | $$double$$ | Найти минимальный элемент в дереве. |
| 26 | $$char$$ | Найти |
| 27 | $$float$$ | Найти среднее арифметическое элементов дерева. |
| 28 | $$int$$ | Найти количество элементов с заданным ключом. |
Разработайте рекурсивный алгоритм для решения задачи.
1-10. Определите закономерность формирования членов последовательности. Найдите $$N$$ -ый член последовательности, сократив количество рекурсивных вызовов.
11-20. Найдите значение функции для любых целых неотрицательных аргументов.
21-28. Составьте
1. Закраска прямой. На числовой прямой окрасили $$N$$ отрезков. Известны координаты левого и правого концов каждого отрезка ( $$L_i$$ и $$R_i$$ ). Найти длину окрашенной части числовой прямой.
Ограничения: $$L_i$$ и $$R_i$$ – целые, $$-1 000 000 000 \leq L_i \leq R_i \leq 1 000 000 000$$, $$1 \leq N \leq 15 000$$, время 1 с.
Ввод из файла
Вывод в файл
Примеры
2. Сумма произведений. Дан набор переменных $$х_1, х_2, \ldots , x_N$$. Каждая переменная $$х_i$$ может принимать значение только -1, 0 или +1. Для данного целого числа $$S$$ требуется определить количество способов присвоить переменным $$х_i$$ значения так, чтобы сумма всех возможных произведений $$хi хj$$ была равна $$S$$, где $$i < j$$ и $$i, j = 1, 2, \ldots, N$$. Два способа считаются различными, если они содержат различное число $$х_i = 0$$.
Ограничения: $$2 \leq N \leq 10 000$$, $$-10 000 \leq S \leq 10 000$$, время 1 с.
Ввод из файла prodsum.in. В первой строке находятся числа $$N$$ и $$S$$, разделенные пробелом.
Вывод в файл prodsum.out. Вывести одно целое число – количество способов представить $$S$$ как сумму произведений.
Примеры
3. Статическая сложность. Анализ временной сложности алгоритмов – важный инструмент создания эффективных программ. Алгоритмы, выполняемые за линейное время, как правило, значительно быстрее алгоритмов, требующих для выполнения той же задачи квадратичного времени, так что предпочтение должно быть отдано первым.
Обычно определяют время выполнения алгоритма по отношению к $$n$$ – "размеру" входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т.п. Поскольку определение формулы зависимости временной сложности алгоритма от $$n$$ – непростая задача, было бы замечательно, если бы ее можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам
<Программа> : := "BEGIN" <Список операторов> "END" <Список операторов>::=<Оператор>|<Оператор><Список операторов> <Оператор> ::=<Оператор LOOP> | <Оператор 0P> <Оператор LOOP> ::=<Заголовок ЮОР><Список операторов>"END" <Заголовок LOOP> : := "LOOP" <число> | "LOOP n" <Оператор OP> : := "OP" <число>
Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора ОР требует столько единиц времени, сколько указано в его параметре. Список операторов, заключенный в оператор
Ввод из файла icomplex.in. В первой строке находится целое число $$k$$ — число программ во входном файле. Затем идут $$k$$ программ, удовлетворяющих приведенной BEGIN, END,
Вывод в файл icomplex.out Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах $$n$$ – Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k ". Если время выполнения нулевое, нужно вывести " Runtime = 0 ". За строкой с многочленом должна следовать пустая строка.
Ограничения: вложенность операторов
Пример
4. Строки Фибоначчи. Строку Фибоначчи $$F(K)$$ для натуральных чисел $$K$$ определим так: $$F(1) ='A', F(2) ='В', F(K) = F(K – 1) + F(K – 2)$$ при $$K > 2$$, где "+" означает
Ограничения: Длина строки $$S$$ составляет от 1 до 25 символов, $$1 \leq N \leq 45$$, время 1 с.
Примечание. Длина $$F(45)$$ равна 1 134 903 170.
Ввод из файла fibostr.in. В первой строке содержится число $$N$$, во второй – строка $$S$$.
Вывод в файл fibostr.out. Вывести одно число – количество вхождений строки $$S$$ в строку Фибоначчи $$F(N)$$.
Примеры
5. Анти-QuickSort. Для сортировки последовательности чисел широко используется быстрая сортировка – while ). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
Ввод из файла antiqs.in. В первой строке находится единственное число $$N$$.
Ограничения: $$1 \leq N \leq 70 000$$, время 1 с.
Вывод в файл antiqs.out. Вывести перестановку чисел от 1 до $$N$$, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
Пример
6. Путь коня. Дана шахматная доска, состоящая из $$N\times N$$ клеток; несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.
Ограничения: $$2 \leq N \leq 50$$, время 1 с.
Ввод из файла knightw.in. В первой строке задано число $$N$$. В следующих $$N$$ строках содержится по $$N$$ символов. Символом # обозначена вырезанная клетка, точкой – невырезанная клетка, @ — заданные клетки (таких символов два).
Вывод в файл knightw.out. Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.
Примеры
7. Грядки. Прямоугольный садовый участок шириной $$N$$ и длиной $$М$$ метров разбит на квадраты со стороной 1 м. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
Подсчитайте количество грядок на садовом участке.
Ограничения: $$1 \leq N, M \leq 200$$, время 1 с.
Ввод из файла beds.in. В первой строке находятся числа $$N$$ и $$М$$ через пробел, далее идут $$N$$ строк по $$М$$ символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет.
Вывод в файл beds.out. Вывести одно число – количество грядок на садовом участке.
Пример
8. Упорядоченные дроби. Вывести в порядке возрастания все несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают $$N$$.
Ограничения: $$2 \leq N \leq 255$$, время 1 с.
Ввод из файла ordfrac.in. В первой строке находится единственное число $$N$$.
Вывод в файл ordfrac.out. В каждой строке выводится дробь.
Пример
9. Сообщение. В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили ее порядковым номером в русском
Ограничения: цифр не более 100, время 1 с.
Ввод из файла message.in. В первой строке содержится последовательность цифр.
Вывод в файл message.out. Вывести одно число.
Пример
10. Умножение многочленов. Ввести в символьной форме два многочлена от х с целыми коэффициентами и вывести их произведение в порядке убывания степеней – также в символьной форме.
Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 104, время 1 с.
Ввод из файла polymul.in. В двух строках находятся многочлены.
Вывод в файл polymul.out. В единственной строке выводится
Примеры
11. Гомер Симпсон. Обеденный перерыв Гомера Симпсона составляет $$T$$ мс. Один гамбургер Гомер съедает за $$N$$ мс, один чизбургер — за $$M$$. Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва.
Ограничения: $$1 \leq M, N, T \leq 1 000 000$$, все числа целые, время 2 с.
Ввод из файла homer.in. В первой строке находятся три числа – $$M$$, $$N$$ и $$T$$, разделенные пробелами.
Вывод в файл homer.out. Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остается какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остается как можно меньше.
Примеры
12. Диалог компьютеров. Три компьютера соединены сетью. Один из них – сервер, два других – клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение – второму.
Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать
Пусть вы знаете все полные имена файлов, находящихся на сервере, и слушаете разговор клиентов. Основываясь на этой беседе, вы должны определить набор файлов, которые могли быть выбраны сервером. Файлы в этом наборе называются файлами-кандидатами.
Ввод из файла dialogue.in. В первой строке находятся два целых числа, $$N$$ и $$M$$, разделенные пробелом: $$N$$ – число файлов на сервере, $$М$$ – число сообщений, посланных клиентами, пытающимися определить
Каждая из следующих $$N$$ строк содержит одно имя.расширение, где и имя, и расширение состоят только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трех символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.
Каждое
Ограничения: $$1 \leq N \leq 1000, 1 \leq M \leq 100$$, время 3 с.
Вывод в файл dialogue.out. В первой строке выводится число файлов-кандидатов для данных набора файлов и числа сообщений между клиентами. Выводится 0, если файлы-кандидаты отсутствуют.
В следующих строках находятся полные имена файлов-кандидатов, каждое в отдельной строке. Они должны идти в том же порядке и в том же написании, что и во входном файле. Это означает, что если разделяющая точка в названии конкретного файла была опущена во входном файле, то она должна быть опущена и в выводе, и наоборот. Файл нельзя упоминать более одного раза.
Пример
13. Бросание кубика. Кубик, грани которого помечены цифрами от 1 до 6, бросают $$N$$ раз. Найти вероятность того, что сумма выпавших чисел будет равна $$Q$$.
Ограничения: $$1 \leq N \leq 500, 1 \leq Q \leq 3000$$, время 1 с.
Ввод из файла
Вывод в файл
Примеры
14. Ближайшее число. Дана матрица $$A$$ размером $$N\times N$$, заполненная неотрицательными целыми числами. Расстояние между двумя элементами $$A_{ij}$$ и $$A_{pq}$$ определено как $$|i – p| + |j – q|$$. Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.
Ограничения: $$1 \leq N \leq 200, 0 \leq A_{ij} \leq 1 000 000$$, время 3 с.
Ввод из файла neamum.in. В первой строке содержится число $$N$$. Затем идут $$N$$ строк по $$N$$ чисел, разделенных пробелами и представляющих собой матрицу.
Вывод в файл neamum.out. Выводится $$N$$ строк по $$N$$ чисел, разделенных пробелами, – модифицированная матрица.
Пример
15. Прямоугольное деление. Дано $$N$$ прямоугольников со сторонами, параллельными осям координат. Требуется определить, на сколько частей эти прямоугольники разбивают плоскость (внутри частей не должно быть границ прямоугольников).
Ввод из файла rectpart.in. В первой строке содержится число прямоугольников $$N$$. Далее идут $$N$$ строк, содержащих по четыре числа, $$x_1 y_1 x_2, y_2$$, – координаты двух противоположных углов прямоугольника.
Ограничения: $$1 \leq N \leq 100$$, координаты представляют собой целые числа и по
Вывод в файл rectpart.out Вывести одно число – количество частей, на которые разбивается плоскость.
Пример
16. Водопровод. Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке $$(х_1, у_1)$$, а вторая – в точке $$(x_2, у_2)$$. К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 $$\deg$$. Требуется, зная длины отрезков труб $$L_1, L_2, \ldots, L_K$$ и количество отрезков каждой длины $$C_1, C_2, \ldots, C_K$$, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.
Ограничения: $$1 \leq K \leq 4, 1 \leq x_1, y_1, x_2, y_2, Li \leq 1000, 1 \leq C_i \leq 10$$, все числа целые, время 3 с.
Ввод из файла wpipe.in. В первой строке находятся числа $$x_1, y_1, x_2, y_2, K$$, затем $$2K$$ чисел: $$L_1, L_2, \ldots, L_K , C_1, C_2, \ldots, C_K$$.
Вывод в файл wpipe.out. Вывести одно число — минимальное количество нужных отрезков труб или -1, если соединение невозможно.
17. Химические реакции. Билл преподает химию в школе, он подготовил несколько тестов для учеников. Каждый тест состоит из химической формулы и нескольких возможных результатов реакции. Среди этих результатов ученики должны выбрать правильный. Билл хочет убедиться в том, что, вводя свои тесты в компьютер, он не допустил опечаток, благодаря которым ученики могли бы отбросить неверные ответы, просто подсчитав число химических элементов в левой и правой частях уравнения (в правильном уравнении химической реакции должно соблюдаться равенство).
Ваша задача - написать программу, которая поможет Биллу. Программа должна прочитать описание теста, состоящее из заданной левой части уравнения и нескольких возможных правых частей, и определить, равно ли количество химических элементов в каждой предложенной правой части уравнения количеству химических элементов в заданной левой части.
Билл формализовал задачу. И левая, и правая части уравнения представлены строкой символов без пробелов, состоящей из одной или более химических последовательностей, разделенных знаком плюс. Каждая последовательность имеет необязательный предшествующий целый множитель, относящийся ко всей последовательности, и несколько элементов. Каждый элемент может сопровождаться необязательным целым множителем, относящимся к нему. Элемент в этом уравнении может быть или отдельным химическим элементом, или целой последовательностью в круглых скобках. Каждый отдельный химический элемент представлен или одной прописной буквой, или прописной буквой, сопровождаемой строчной.
Еще более формально, используя нотацию, аналогичную
<формула>::=[<число>]<последовательность>{"+"[<число>]<последовательность>}
<последовательность>::=<элемент>[<число>]{<элемент>[<число>]}
<элемент>::=<химический элемент>|"("<последовательность>")"
<химический элемент>::=<прописная буква>[<строчная буква>]
<прописная 6уква>::= "А".."Z"
<строчная буква>::= "а".."z"
<число>::= "1". ."9" {"0". ."9"}
Будем говорить, что каждый отдельный химический элемент встречается в формуле всего $$X$$ раз, если $$X$$ – сумма всех различных вхождений этого химического элемента, умноженных на все числа, относящиеся к ним. Например, в формуле
C2H5OH+3O2+3(SiO2)
C встречается всего 2 раза;H встречается всего 6 раз (5 + 1);0 встречается всего 13 раз (1 + 3 * 2 +3 * 2);Si Все множители в формулах – целые числа не меньше 2, если заданы явно, или равны 1 – по умолчанию.
Ввод из файла chem.in. В первой строке находится формула — левая часть уравнения, во второй – одно число $$N$$ – количество рассматриваемых правых частей, в каждой из следующих $$N$$ строк – одна формула – предлагаемая правая часть уравнения.
Ограничения: $$1 \leq N \leq 10$$, длина формулы не превосходит 100 символов, каждый
Вывод в файл chem.out. Для каждой из $$N$$ заданных правых частей выведите одну строку вида
<формула левой части>!=<формула правой части>
Здесь <формула левой части> должна быть замещена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а <формула правой части> – замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.
Пример
18. Суммы. Дано $$N$$ целых чисел $$A_1, A_2,\ldots, A_N$$. Требуется найти количество различных значений сумм вида $$k_{1A1} + k_{2A2} + k_NA_N$$.
Ограничения: $$1 \leq N \leq 500, 0 \leq A_i \leq 100, 0 \leq k_i \leq 1$$, все числа целые, время 2 с.
Ввод из файла sums.in. В первой строке находится число $$N$$, во второй – $$A_1, A_2,\ldots, A_N$$.через пробел.
Вывод в файл sums.out. Вывести одно число – количество различных значений сумм.
Примеры
19. Lines. В таблице из $$N$$ строк и $$N$$ столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
Ограничения: $$2 \leq N \leq 40$$, время 1 с.
Ввод из файла lihes.in. В первой строке находится число $$N$$, в следующих $$N$$ строках – по $$N$$ символов. Символом точки обозначена свободная клетка, латинской заглавной $$0$$ – шарик, @ – исходное положение шарика, который должен двигаться, латинской заглавной $$X$$ — конечное положение шарика.
Вывод в файл lihes.out. В первой строке выводится $$Y$$, если движение возможно, или $$N$$, если нет. Если движение возможно, далее следует $$N$$ строк по $$N$$ символов – как и на вводе, но буква $$X$$, а также все точки по пути заменяются плюсами.
Примеры
20. Покраска лабиринта. Лабиринт представляет собой квадрат, состоящий из $$N\times N$$ сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (рис.). Помогите ему рассчитать количество краски, необходимой для этого.
Ограничения: $$3 \leq N \leq 33$$, размер сегмента 3 x 3 м, высота стен 3 м, время 1 с.
Ввод из файла paintlab.in. В первой строке находится число $$N$$, затем идут $$N$$ строк по $$N$$ символов: точка обозначает пустой сегмент, решетка – сегмент со стеной.
Вывод в файл paintlab.out. Вывести одно число – площадь видимой части внутренних стен лабиринта в квадратных метрах.
21. Поле для крикета. Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложения своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер.
Ваша задача – помочь бедному Архитектору сохранить голову, написав программу, которая найдет максимальный размер поля для крикета и его положение внутри парка, удовлетворяющие требованиям Короля.
Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север – юг и восток – запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север – юг и восток – запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева.
Оси этой
В этой задаче вы можете пренебречь
Ввод из файла cricket.in. Первая строка содержит три целых числа, $$N$$, $$W$$ и $$H$$, разделенных пробелами: $$N$$ — число деревьев в парке, $$W$$ и $$H$$ – длина и ширина парка соответственно.
Следующие $$N$$ строк описывают координаты деревьев в парке. Каждая строка содержит два целых числа $$x_i$$ и $$y_i$$ разделенных пробелом и представляющих собой координаты $$i$$ -го дерева. Все деревья имеют различные координаты.
Ограничения: $$1 \leq N \leq 100, 1 \leq W, H \leq 10 000, 0 \leq x_i \leq W, 0 \leq y_i \leq H$$, время 1 с.
Вывод в файл cricket.out. Вывести через пробел три целых числа, $$P$$, $$Q$$ и $$L$$, где $$(P, Q)$$ – координаты юго-западного угла поля для крикета, $$L$$ – длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.
Пример
22. Электронная таблица. Напишите программу, выполняющую функции очень простой электронной таблицы. Она работает с таблицей из 9 строк от 1 до 9 и 26 столбцов от А до Z. Клетки таблицы обозначаются именами, составленными из кодов столбца и строки, например B1, S8.
Каждая клетка содержит выражение. Выражения используют целые константы, ссылки на клетки, скобки,
Так, 567, E8/2, (3+B3)*(C4-l) являются правильными выражениями. Все операторы целочисленные. Деление на ноль дает в результате ноль.
Если значение ячейки, на которую ссылается некоторое выражение, не определено, оно считается равным нулю. Ситуация, когда две или более ячейки зависят друг от друга, является отдельным случаем – циклической ссылкой.
Ограничения: длина выражения в одной ячейке до 255 символов, все аргументы и результаты меньше 1 000 000, время 1 с.
Ввод из файла sprsheet.in. Первая строка содержит число выражений $$N$$. Следующие N строк имеют формат <Имя клетки>=<выражение>. Все выражения корректные, и каждая ячейка определена не более чем одним выражением.
Вывод в файл sprsheet.out. В единственной строке выводится или значение клетки A1, или число 1000000 (один миллион), если значение клетки A1 не может быть найдено из-за циклической ссылки.
Пример
23. Путь спелеолога. Пещера представлена кубом, разбитым на $$N$$ частей по каждому измерению (то есть на $$N^3$$ кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.
Ограничения: $$1 \leq N \leq 30$$, время 1 с.
Ввод из файла speleo.in. В первой строке содержится число $$N$$. Далее следует $$N$$ блоков. Блок состоит из пустой строки и $$N$$ строк по $$N$$ символов: # обозначает клетку, заполненную камнями, точка – свободную клетку. Начальное положение спелеолога обозначено заглавной буквой $$S$$. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.
Вывод в файл speleo.out. Вывести одно число –
Пример
Комментарий
Нужно спуститься на уровень вниз, сделать два движения на запад, подняться на уровень вверх, сделать движение на юг, подняться на уровень вверх.
24. Дырявая ткань. На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен черно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади – точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.
На схеме три куска – один без дыр, а два – с одной дырой каждый: первый – площадью 8, второй – площадью 12.
Ваша цель – найти кусок с наибольшим количеством дыр в нем. Дыра – это 4-связная область точек, полностью окруженных символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.
Ввод из файла holey.in. В первой строке содержатся два числа $$W$$ и $$H$$, разделенные пробелами. Следующие $$H$$ строк содержат по $$W$$ символов каждая. Символы в этих строках – или * (ASCII 42), или точка (ASCII 46).
Ограничения: $$1 \leq W, H \leq 100$$, время 1 с.
Вывод в файл holey.out. Вывести одно целое число – площадь минимального из наиболее дырявых кусков. Если нет кусков с дырами, выходной файл должен содержать ноль.
Пример
25. Несоставляемое число. Даны $$N$$ натуральных чисел. Найти минимальное
Ограничения: $$1 \leq N \leq 10 000$$, значения исходных чисел от 1 до 1 000 000 000, время 1 с.
Ввод из файла nosum.in. В первой строке находится число $$N$$, в следующих $$N$$ строках – по одному натуральному числу.
Вывод в файл nosum.out. Вывести одно число.
Примеры
26. SMS. Сообщения
(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)
Чтобы ввести две буквы, находящиеся на одной кнопке, нужно между нажатиями клавиши сделать паузу. Например, чтобы ввести сообщение "АА", нужно нажать (АВС)(пауза)(АВС)
Если на кнопке три буквы, то, как только такая кнопка нажата три раза, последняя буква добавляется в сообщение немедленно, а следующие нажатия той же кнопки относятся к следующей букве сообщения. Аналогично, если на кнопке четыре буквы, то после четырех нажатий в сообщение будет добавлена последняя буква. То есть последовательность нажатий
(АВС)(АВС)(АВС)(АВС)(пауза)(АВС)
соответствует сообщению "САА". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили
Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое вы получили.
Ограничения: $$1 \leq N \leq 80$$, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения – от 1 до 80 букв, время 2 с.
Ввод из файла
Вывод в файл
Примеры
27. Lines. В таблице из $$N$$ строк и $$N$$ столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
Ограничения: $$2 \leq N \leq 250$$, время 1 с.
Ввод из файла lines2.in. В первой строке находится число $$N$$, в следующих $$N$$ строках – по $$N$$ символов. Символом точки обозначена свободная клетка, латинской заглавной 0 — шарик, @ — исходное положение шарика, который должен двигаться, латинской заглавной $$X$$ — конечное положение шарика.
Вывод в файл lines2.out. В первой строке выводится $$Y$$, если движение возможно, или $$N$$, если нет. Если движение возможно, далее следует $$N$$ строк по $$N$$ символов – как и на вводе, но $$X$$, а также все точки по пути заменяются плюсами.
Примеры
28. Удаление клеток. Из прямоугольного листа клетчатой бумаги ( $$М$$ строк, $$N$$ столбцов) удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Ограничения: $$1 \leq M, N \leq 100$$, время 1 с.
Ввод из файла remsquar.in. В первой строке находятся числа $$M$$ и $$N$$, в следующих $$М$$ строках – по $$N$$ символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана – точка.
Вывод в файл remsquar.out. Вывести одно число.
Пример
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.