A719a

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]n\left(n+1 \right)/2[/latex] чисел, аналогично правым треугольным матрицам. Получить матрицу [latex]AB[/latex].

[latex]n[/latex] [latex]A[/latex] [latex]B[/latex] [latex]AB[/latex]
3 0 1 2 0 2 1 0 1 3 0 2 1 7 4 4

6 5 5

5 4 11

2 0 1 0 1 0 1 0 1

1 0

3 1 2 3 4 5 6 1 0 0 4 2 2 1 14 10

2 26 18

3 32 22

4 1 1 1 1 2 2 2 3 3 4 6 6 6 6 5 5 5 3 2 1 24 21 16 14

42 36 26 22

54 46 31 25

60 51 33 26

Тесты проверены на этом сайте.

Код программы:

Алгоритм решения:

Изначально мы считываем последовательность из [latex]n\left(n+1 \right)[/latex] для двух матриц (чтобы они были симметричекими, цикл по столбцам запускается с позиции текущей строки, а затем введённое значение копируется относительно главной диагонали).

Пусть [latex]C=\begin{Vmatrix}c_{ij}\end{Vmatrix} \in M_{m\times n}\left( \mathbb{R}\right) \left(i=1,2,\ldots,m; j=1,2,\ldots,n \right)[/latex].

Умножение матриц происходит по формуле [latex]c_{ij}=\sum_{r=1}^{n}{a_{ir}b_{rj}}\left(i=1,2,\ldots,m; j=1,2,\ldots,n \right)[/latex].

e-olimp 4856. Кратчайший путь

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

Входные данные

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

Выходные данные

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

Код программы:

Для решения использовался алгоритм Дейкстры, подробнее в комментариях к коду.

e-olimp 5078. Турнир

Задача e-olimp.com №5078.

Ссылка на засчитанное решение (C++).

Ссылка на засчитанное решение (Java).

Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро. Для заданного списком ребер графа проверьте, является ли он турниром.

Входные данные

Входной файл содержит числа [latex]n \left(1\leq n\leq 100 \right)[/latex] — число вершин в графе и [latex]m \left(1\leq m\leq n\left(n-1 \right) \right)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

Выходные данные

Выведите в выходной файл YES если граф является турниром и NO в противном случае.

Код программы (С++):

Java:

 

Алгоритм решения. Я завела матрицу смежности, единицы в которой встречается тогда и только тогда, когда из вершины, представимой номером строки, есть ребро в вершину, представимую номером столбца.

Далее программа пробегает цикл по матрице смежности выше главной диагонали (так как на самой диагонали могут быть лишь петли, а в условии оговорено, что вершины должны быть различны). Если в таблице встречается 1, то мы должны проверить, если ли ребро, обратное данному. Если нет — продолжаем, есть — говорим, что граф не турнир и завершаем работу программы. Если же у нас не встретилось 1, то мы проверяем, есть ли обратное ребро. Если его нет, то мы говорим, что связи между этими двумя вершинами не существует, а следовательно наш граф — не турнир (завершаем программу).

После того, как цикл полностью пройден, можно с уверенностью утверждать, что граф является турниром.

e-olimp 3809. ГАС Очередь

Задача e-olimp.com №3809. Ссылка на засчитанное решение.

За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных учреждениях можно встретить терминал, печатающий бумажку с номером, и, не задавая привычный вопрос «Кто последний?«, посетители с помощью электронного табло узнают, сколько еще им ждать и когда наступит их очередь.

Однако, пока такие системы далеки от совершенства. Например, вызывает вопросы стандартный принцип любой очереди: «Первым обслуживается тот, кто первым пришел«. При разработке инновационной ГАС «Очередь» решено было сделать ее такой, что выполнение этого принципа не требуется. Вместо этого, новая система призвана минимизировать количество негатива, приходящегося на чиновника, на прием к которому стоят люди в очереди.

Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен [latex]w[/latex], то через [latex]t[/latex] часов ожидания в очереди этот человек обрушит на голову чиновника ровно [latex]wt[/latex] единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого — количество гнева будет равно [latex]2w[/latex].

Также известно, что на обслуживание каждого посетителя уходит ровно час, а каждый посетитель приходит в начале какого-либо часа. Ваша задача заключается в том, чтобы по данным вам показателям раздражительности и временам прихода посетителей определить, сколько негатива достанется чиновнику при оптимальном порядке обслуживания клиентов.

Входные данные

В первой строке задано одно целое число [latex]t[/latex] — количество случаев, которые вам предстоит обработать. Далее следуют [latex]t[/latex] описаний самих случаев.

Описание каждого случая состоит из: числа [latex]n[/latex] в первой строке — количества посетителей, и [latex]n[/latex] описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа [latex]r_{i}[/latex] и [latex]w_{i}[/latex] [latex]\left(1\leq r_{i},w_i\leq {10}^{6} \right)[/latex] — номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно.

Суммарное количество посетителей во всех случаях одного теста не превосходит [latex]10^{5}[/latex].

Выходные данные

Для каждого случая в отдельной строке выведите ответ — минимальное суммарное количество негатива, которое получит чиновник.

Код программы:

Алгоритм состоит в том, чтобы на каждом моменте времени забирать к себе самого агрессивного из людей в очереди.

Для реализации наиболее подходящей структурой хранения данных является очередь с приоритетом, максимум из которой можно извлечь за [latex]O \left( \log n \right)[/latex], тогда суммарное асимптотическое время решения задачи займёт  [latex]O \left( \ n log n \right)[/latex].

e-olimp 1667. Конденсация графа

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите  компоненты  сильной связности заданного графа и топологически отсортируйте его конденсацию.

Входные данные

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex]  до [latex]N[/latex] — номера начала и конца ребра.

Выходные данные

В первой строке выведите число [latex]K[/latex] — количество компонент сильной связности в заданном графе. В следующей строке выведите [latex]N[/latex] чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Тесты:

6 7 

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19 

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

1

Иллюстрация ко второму тесту:

1

Код программы:

Алгоритм решения

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

Научившись это делать, мы сможем постепенно выделить все компоненты сильной связности: удалив из графа вершины первой выделенной компоненты, мы снова найдём среди оставшихся вершину с наибольшим временем выхода, снова запустим из неё этот обход, и так далее.

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

e-olimp 693. Минимум в стеке

Задача e-olimp.com №693. На вход программы подается набор операций со стеком. Каждая операция состоит в добавлении или удалении элемента из стека. После выполнения каждой операции найдите наименьшее число, которое находится в стеке. Сложите все полученные числа и получите ответ. Если после некоторой операции стек оказался пуст, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как стек пуст, то не выполняйте его.

Входные данные

Входные данные генерируются в самой программе. На вход подаются параметры для генерации входной последовательности.

Первое число содержит количество операций [latex]n (1\leq n\leq10^{6})[/latex] со стеком. Затем следуют четыре неотрицательных целых числа [latex]a, b, c, x_{0}[/latex] не превосходящие [latex]10000[/latex].

Для получения входных данных генерируем последовательность [latex]x[/latex].

Первое число в генерируемой последовательности [latex]x_{1}[/latex]. Первое, а также каждое следующее число вычисляется из предыдущего по формуле:

[latex]x_{i}=\left(a\cdot x_{i-1}^{2} + b\cdot x_{i-1} + c\right)/100 \bmod{10^{6}}[/latex],

где ‘/‘ — операция целочисленного деления, а ‘[latex] \mod{}[/latex]’ — остаток от деления.

Если [latex]x_{i} \mod{5}<2[/latex], то необходимо удалить число из стека. В противном случае необходимо добавить в стек число [latex]x_{i}[/latex].

Выходные данные 

Выведите результирующую сумму.

Ссылка на задачу. Ссылка на засчитанное решение.

Код программы

 Пояснение решения

На мой взгляд сложность задачи состояла только в том, чтобы реализовать взятие минимального элемента из стека за [latex]O\left(1 \right)[/latex].

Для этого предполагается хранить в стеке не просто наши элементы, но и минимум в стеке на текущем шаге. Что для этого требовалось, так это не забывать кидать в стек обновлённые минимумы на каждом шаге. Так же помня о том, что стек может быть уже пуст, я изменяла результирующую сумму только в том случае, если в стеке был хотя бы один элемент.

e-olimp 6124. Стек неограниченного размера

Стек неограниченного размера

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы.  Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.

Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Пояснение: Размер стека должен быть ограничен только размером доступной оперативной памяти.

Решение

Предлагается реализация стека через связные списки.

Положительные стороны:

В условии сказано, что стек потенциально может занимать всю оперативную память, поэтому при такой реализации мы будем экономнее выделять память и не получим WA на тестах, которые не вместились бы в фиксированный размер массива.

Отрицательные стороны:

Конструктор срабатывает для каждого узла достаточно медленно, решение уступает в скорости связному списку массивов.
Ссылка на задачу. Ссылка на засчитанное решение.

Код программы:

AA12

Задача. В заданной строке заменить каждую точку или точку с запятой тремя точками подряд.

Ввод Вывод
asgahra.agargarhah;rehaehraeh.arhreh    agerge..sgsgg.g asgahra…agargarhah…rehaehraeh…arhreh    agerge……sgsgg…g
;;.grg .    .    ;   ; ………grg …    …    …   …

Код программы (C++):

Java:

 

Алгоритм решения: пройдём по всем символам строки от её начала и до конца, в случае, если встреченный символ — ‘.’ или ‘;’, мы добавим в строку вывода ‘…’, иначе — текущий символ.

М3

Big Summa. Заданы две текстовые строки, состоящие исключительно из цифр и не более чем одной точки.
Предполагается, что строки задают представление чисел в q-ричной системе счисления. Построить строку, являющуюся их суммой.

q A B A+B Комментарий.
10 126740 546.967 127286.967 Тест пройден.
8 2360 7521 12101 Тест пройден.
2 1011001 1101 100110 Тест пройден.
3 1210.012 1112.1 10022.112 Тест пройден.
10 4356.98 67.975 4424.955 Тест пройден.

Код программы (string):

Программа выполнена с помощью методов класса <string>. Для работы мне понадобилось написать несколько вспомогательных функций, задачей которых является дополнить числа нулями таким образом, чтобы точки чисел оказались на одинаковых позициях.

Функция dot_position. Эта функция находит места точек в обеих строках, а если таковых нет, то им присваивается значение длины строки. Возвращает функция наибольшую по значению позицию точки.

Функции length_before_dot и length_after_dot возвращают количество цифр до и после точки соответственно.

Затем начинается тело основной функции программы. Изначально пользователю предоставляется ввести систему счисления и 2 числа, которые программа считывает в виде строк. Для удобства вычислений программа дополняем строку, которая не содержит точку, ещё одним ранее названным символом. Затем мы выравниваем оба наших числа по точкам.

После этого  программа готова вычислить сумму двух чисел. Сложность реализации алгоритма сложения состояла лишь в том, что записать в строку элемент типа int — невозможно, а следовательно, его нужно было преобразовать в  строку. Для этого потребовалась функция to_string() из класса <string>. Но при этом элементы a[i] и b[i] воспринимались как коды символов, поэтому каждый из них нужно было уменьшить на ‘0’.

Ещё одна сложность — это десятки, которые мы держим «в уме», а в моём случае — во вспомогательной переменной p.

Код можно посмотреть здесь.

Код программы (cstring):

Из-за отсутствия функции insert() в классе <cstring> я была вынуждена написать её самостоятельно. В остальном работа заключалась лишь в «переводе» кода из одного класса в другой.

Код можно посмотреть здесь.

А401

Дана действительная квадратная матрица порядка [latex]n[/latex], натуральные числа [latex]i, j \left(1\leq i\leq n, 1\leq j\leq n \right)[/latex]. Из матрицы удалить [latex]i[/latex]-строку и [latex]j[/latex]-столбец.

[latex]n[/latex] Матрица. [latex]i[/latex] [latex]j[/latex] Полученная матрица. Комментарий.
3 1 2 3

4 5 6

7 8 9

2 1 2 3

8 9

Тест пройден.
4 0,5 1 6 0

3 8 12 0,3

10 4,6 8 9

0 3,5 6,4 10

4 3 0,5 1 0

3 8 0,3

10 4,6 9

Тест пройден.
2 -40 87

9 -3

1 1 -3 Тест пройден.

Код программы (C++):

Java:

 

Сначала пользователю предлагается ввести порядок матрицы, затем элементы этой матрицы. После чего, по условию задачи, пользователь должен задать [latex]i[/latex]-строку и [latex]j[/latex]-столбец, которые программа должна изъять из матрицы.

Протестировать программу можно здесь (C++) и здесь (Java).

Ю11.15

Метод парабол. Найти минимум заданной функции [latex]y=f(x)[/latex], двигаясь от заданной точки [latex]x_{0}[/latex] по методу парабол:

[latex]x_{i+1}=x_{i}-\frac{h}{2}\frac{f\left( x_{i}+h\right)-f\left( x_{i}-h\right)}{f\left( x_{i}+h\right)-2f\left( x_{i}\right)+f\left( x_{i}-h\right)}, i=0,1,\ldots[/latex], пока не будет достигнута заданная точность.

Функция [latex]x^{3}+10\sin (5x)[/latex]:

Безымянный

[latex]x_{0}[/latex] [latex]\varepsilon[/latex] Точка минимума по графику. Точка минимума по программе. Комментарий.
0 0,001 -0,315353 -0,315353 Тест пройден.
1 0,0001  0,932048 0,932048 Тест пройден.
2 0,0001  2,14327 2,14327 Тест пройден.
-3 0,01 -2,93616 -2,93616 Тест пройден.
-2 0,0001  -1,6017 -1,6017 Тест пройден.

Код программы (C++):

Для функции [latex]x^{3}+10\sin (5x)[/latex] (функцию всегда можно изменить, достаточно исправить строку 6):

Java:

 

Чтобы сделать программу, я почитала “Численные методы” Н. Н. Калиткина, где и было сказано, что в качестве вспомогательного шага [latex]h[/latex] при расчётах на ЭВМ обычно выбирают значение 0,001.

Далее пользователю предоставляется возможность ввести значение [latex]x_{0}[/latex] и задать точность [latex]\varepsilon[/latex].  Корень [latex]x[/latex] является минимумом функции тогда и только тогда, когда вторая производная этой функции больше 0. Поэтому мы запускаем цикл, который будет сдвигать наше [latex]x_{0}[/latex] в положительном направлении оси [latex]x[/latex], пока вторая производная функции не будет удовлетворять условию задачи.

Далее мы вычисляем значение [latex]x_{i+1}[/latex], и запускаем цикл, который будет продолжаться до тех пор, пока разница между [latex]x_{i}[/latex] и [latex]x_{i+1}[/latex]  не будет меньше заданной погрешности [latex]\varepsilon[/latex].

Затем на экран выводится сама точка минимума функции.

Программу можно посмотреть здесь (C++) и здесь (Java).

e-olimp 2392. Интересная сумма

Ссылка на задачу.

Дано трёхзначное натуральное число [latex]N[/latex]. Определить сумму наибольшего и наименьшего трёхзначных чисел, которые могут быть образованы из числа [latex]N[/latex] перестановкой цифр.

Входные данные

Натуральное число [latex]N[/latex] [latex]\left(100\leq N\leq 999 \right)[/latex].

Выходные данные

Ответ к задаче.

Пройденные тесты (C++).

Java.

Код программы (C++):

Java:

Когда я увидела эту задачу, то мне в голову сразу пришло решение с применением массивов. Изначально пользователю предлагается ввести трёхзначное число, которое я впоследствии раскладываю на отдельные элементы массивов, один из которых определяет минимальное трёхзначное число, а второй, в свою очередь,  — максимальное.

Затем я сортирую первый массив по возрастанию, а второй по убыванию.

Далее проблема возникает именно с первым массивом, так как его первым элементом может оказаться 0, что нам не подходит, так как наше минимальное число, образованное перестановкой, обязано быть трёхзначным по условию. Для этого я делаю 2 несложных проверки, в результате которых первый элемент массива меняется местами либо со вторым, либо с третьим.

После чего я перевожу элементы массива в одно трёхзначное число и наконец-то получаю сумму.

Сложность задачи 66%.

Ю4.27

Задача Ю4.27. Сессия. Результаты сессии, состоящей из трёх экзаменов, для группы из [latex]n[/latex] студентов представлены матрицей [latex]K \left(n,3 \right)[/latex]. Оценка ставится по четырёхбалльной системе; неявка обозначена единицей. Подсчитать количество неявок, неудовлетворительных, удовлетворительных, хороших и отличных оценок по каждому экзамену.

[latex]n[/latex] Оценки. Результат. Комментарий.
3 5 3 1

4 3 5

5 2 3

1: неявка (1), уд (1), отл (1).

2: уд (1), хор (1), отл (1).

3: неуд (1), уд (1), отл (1).

Тест пройден.
6 5 4 2 1 1 3

3 2 1 4 4 2

5 5 3 4 2 1

1: неявка (2), неуд (1), уд (1), хор (1), отл (1).

2: неявка (1), неуд (2), уд (1), хор (2).

3: неявка (1), неуд (1), уд (1), хор (1), отл (2).

Тест пройден.
2 2 4

1 5

3 3

1: неуд (1), хор (1).

2: неявка (1), отл (1).

3: уд (2).

Тест пройден.

Код программы (C++):

Java:

 

Изначально пользователю предлагается ввести количество студентов [latex]n[/latex]. Затем создаётся массив  [latex]K \left(n,3\right)[/latex], в котором будут храниться оценки студентов, а так же двумерный массив [latex]o \left(5,3 \right)[/latex], который, собственно говоря, и будет хранить статистику по оценкам. Внешний цикл перебирает экзамены (по [latex]j[/latex]), а внутренний — студентов (по [latex]i[/latex]). Затем пользователю предлагается ввести оценки студентов (сначала вводятся все оценки за первый экзамен, затем за второй, а потом уж за третий). В этом цикле находится «счётчик», который подсчитывает количество определённых оценок (или неявок) в зависимости от массива [latex]K \left(n,3\right)[/latex] на данном этапе цикла. Затем на экран выводятся элементы массива (в дальнейшем все элементы сохранятся, то есть с оценками студентов можно будет работать и дальше).

Код программы можно посмотреть тут (C++) и тут (Java).

Puzzle — Temperatures

Задача взята с этого сайтаБезымянный

В этой задаче необходимо проанализировать значения температуры, дабы найти ближайшее к нулю.

Ввод:

Строка 1: [latex]N[/latex], количество значений температуры.

Строка 2: собственно говоря, сами значения температуры, выраженные целыми числами в диапазоне от -273 до 5526.

Вывод:

Вывести 0 в том случае, если не введено ни одного значения.

Если введено хотя бы одно, то вывести на экран значение ближайшее к 0. Отметить, что если есть 2 значения, одинаково близкие к нулю, но с разными знаками, то на экране должно отобразиться положительное число.

[latex]N[/latex] Ввод Вывод Комментарий.
Простой тест 5 1 -2 -8 4 5 1 Пройден.
Сложный тест 10 -5 -4 -2 12 -40 4 2 18 11 5 2 Пройден.
Без температур 0 0 Пройден.
Дополнительный тест 14 7 -10 13 8 4 -7 -12 -3 3 -9 6 -1 -6 7 -1 Пройден.

Код программы (C++):

Для первого теста нужно было найти ближайшее к нулю значение, когда все числа по модулю были попарно различными. Для этого достаточно было завести переменную типа int и положить в неё значение, которое заведомо больше всех возможных (это 5527, так как по условию задачи значения температур не выходят за пределы [-273;5527]). И в цикле сделать проверку того, что же больше — модуль нашего текущего значения или модуль только что введённого.

[su_spoiler title=»Задача 1.» icon=»arrow-circle-2″]

[/su_spoiler]

Для того, чтобы пройти второй тест необходимо было ввести такое условие, при котором отметалось бы отрицательное значение температуры при наличии такого же по модулю положительного. Для этого мы сравниваем модуль текущего значения температуры со значением введённым (уже не по модулю, так как нам нужно убрать отрицательные числа), и если они равны, то текущее ближайшее значение изменится на положительное, если до этого оно было с минусом.

[su_spoiler title=»Задача 2.» icon=»arrow-circle-2″]

[/su_spoiler]

Java:

И для последней задачи, конечно, достаточно было ввести условие, что [latex]N[/latex] не равно нулю. В противном случае программа выведет на экран 0. Конечный код указан первым.

 

А165к

Задача А165к. Даны действительные числа [latex]a_{1}, a_{2}, \ldots[/latex]. Известно, что [latex]a_{1} < 0[/latex] и что среди [latex]a_{2}, a_{3}, \ldots[/latex] есть хотя бы одно отрицательное число. Пусть
[latex]a_{1}, \ldots, a_{n}[/latex] – члены данной последовательности, предшествующие
первому отрицательному члену ( [latex]n[/latex] заранее неизвестно).  Получить: [latex]\left|a_{1}-a_{n} \right|[/latex].

Введённые данные. [latex]\left|a_{1}-a_{n} \right|[/latex] Комментарий.
1 2 6 4 -8 0 6 8 -7 3 Пройден.
0,65 3,2 4 0 -3 2 0,65 Пройден.
0 -5 8 9 0 Пройден.
0,8 3 6 9 7,2 0 4 -2 3,2 Пройден.
1 -3 6 0 Пройден.

Код программы (C++):

Java:

 

Так как в моей формуле присутствует первый член последовательности, который, согласно условию, всегда больше 0, я вынесла его из общего ряда, поэтому его ввод с клавиатуры осуществляется вне цикла.

Затем мне нужно было найти n-ый член моей последовательности. Для этого я создала 2 переменных, в одной из которых хранится настоящее значение n-ого члена независимо от его знака. Если этот член  — число не отрицательное, то вспомогательной переменной присваивается его значение и цикл повторяется вновь. Если же условие неравенства не выполняется, то цикл заканчивается, и у нас остаётся значение нашей вспомогательной переменной (не отрицательное).

В том случае, если первый член последовательности является в то же время и n-ым, [latex]a_{n}[/latex] и вспомогательной переменной присваивается значение [latex]a_{1}[/latex]. И в этом случае модуль разницы будет равен 0.

После программа выводит модуль [latex]\left|a_{1}-a_{n} \right|[/latex].

Ознакомиться с кодом можно здесь (C++) и здесь (Java).

Ю3.45

Ю3.45. Гуси и кролики. У гусей и кроликов вместе [latex]2n[/latex] лап. Сколько может быть гусей и кроликов (вывести все возможные сочетания)?

[latex]n[/latex] Гусей. Кроликов. Комментарий.
4 0, 2, 4 2, 1, 0 Тест пройден.
3 1, 3 1, 0 Тест пройден.
 0  0  0 Тест пройден.
 7  1, 3, 5, 7 3, 2, 1, 0 Тест пройден.

Код программы (C++):

Второй вариант с 1 циклом (C++):

Java:

 

По условию задачи необходимо вывести все возможные варианты сочетаний количества кроликов и гусей.

Для того, чтобы это сделать, программа использует 2 цикла. В первом исследуется количество гусей: изначально переменной присваивается значение 0, затем следует условие продолжения (количество гусей не должно превышать [latex]n[/latex], то есть количество лап, делённое на 2).

После запуска первого цикла программа проверяет условие продолжения вложенного второго цикла (количество кроликов не превышает [latex]\frac{n}{2}[/latex]), в котором переменной [latex]k[/latex] также изначально присваивается значение 0. В случае выполнения условий обоих циклов программа проверяет, действительно ли количество лап гусей и кроликов в сумме даёт [latex]2n[/latex], заданных по условию задачи пользователем.

Если условие выполнено успешно, то на экран выводится один из вариантов сочетаний. После чего цикл повторяется благодаря заданным изначально инкрементам.

Для тестов выбраны не слишком большие значения [latex]n[/latex], так как посчитать их вручную достаточно проблематично.

Протестировать решение можно по ссылкам: первое, второе (C++) и на Java.

Ю3.5

Задача Ю3.5. Коммерция. Предприниматель, начав дело, взял кредит размером [latex]k[/latex] рублей, под [latex]p[/latex] процентов годовых и вложил его в своё дело. По прогнозам, его дело должно давать прибыль [latex]r[/latex] рублей в год. Сможет ли он накопить сумму, достаточную для погашения кредита, и если да, то через сколько лет?

[latex]k[/latex] [latex]p[/latex] [latex]r[/latex] [latex]n[/latex] Комментарий.
1800 50 1000 Кредит не будет погашен.
800000 15 40000 Кредит не будет погашен.
1000 5 400 3 Тест пройден.
1500 3,5 400 5 Тест пройден.

Код программы (C++):

Java:

По условию задачи необходимо определить, сможет ли должник накопить сумму, достаточную для погашения кредита, и если да, то через сколько лет.

Изначально запускается цикл, который основан на сравнении дохода за несколько лет [latex]nr[/latex] и размера кредита, которого он достигнет за эти годы (вычисляется по формуле сложных процентов: [latex]k(1+\frac{p}{100})^{n}[/latex]).

Затем программа проверяет, как возрастают доходы и долг за год. Если скорость роста доходов не превышает скорость роста долга, то программа выдаёт ошибку, или «кредит не будет погашен», после чего возвращается 0 и программа считается успешно завершённой. В противном случае цикл повторяется, а по его окончании на экран выводится количество лет, за которые долг можно будет погасить.

Проверить код можно здесь (C++) и здесь (Java).

А50

Задача А50. Даны действительные числа [latex]a_{1}[/latex], [latex]b_{1}[/latex], [latex]c_{1}[/latex], [latex]a_{2}[/latex], [latex]b_{2}[/latex], [latex]c_{2}[/latex]. Выяснить, верно ли что [latex]\left|a_{1} b_{2} -a_{2} b_{1} \right|\geq 0.0001[/latex], и если верно, то найти решение системы линейных уравнений

[latex]a_{1} x+b_{1} y+c_{1} =0[/latex],

[latex]a_{2} x+b_{2} y+c_{2} =0[/latex]

(при выполнении выписанного неравенства система заведомо совместна и имеет единственное решение).

[latex]a_{1}[/latex] [latex]b_{1}[/latex] [latex]c_{1}[/latex] [latex]a_{2}[/latex] [latex]b_{2}[/latex] [latex]c_{2}[/latex] [latex]x[/latex] [latex]y[/latex] Комментарий.
 3,8  5  -2  6  8,4  3  16,5625  -12,1875  Тест пройден.
 0 4  5  2  0  9  -4,5  -1,25  Тест пройден.
 1 2  -3  3  2  -1  -1  2  Тест пройден.
 1  0.00002  5  2  0.00005  8  —  —  Тест не пройден. Неравенство не выполняется.
 1  4  5  2  8  3  —  —  Тест не пройден. Неравенство не выполняется.

Код программы (C++):

Java:

 

По условию задачи необходимо решить систему линейных уравнений и вывести на экран [latex]x[/latex], [latex]y[/latex].

Программа решает это уравнение по методу Гаусса.

Изначально она делает проверку на наличие ненулевого аргумента [latex]a_{1}[/latex]. Если таковой имеется, то программа решает задачу, исходя из первого уравнения системы, в противном случае — решение начинается со второго уравнения.

Далее я ввела в программу переменные [latex]b_{0}[/latex], [latex]c_{0}[/latex], чтобы не перегружать формулы большим количеством данных. Алгоритм действий таков:

1) Перенести  [latex]c_{1}[/latex] и  [latex]c_{2}[/latex] в правую часть уравнения, что автоматически меняет их знак на противоположный.

2) Если в программе присутствует ненулевой аргумент [latex]a_{1}[/latex], то она вычитает из второго уравнения первое, предварительно домножив второе на [latex]\frac{b_{1} a_{2} }{a_{1} }[/latex].

3) Из преобразованного второго уравнения находится [latex]y[/latex], который впоследствии подставляется в первое уравнение системы для нахождения [latex]x[/latex] .

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом (C++) и этим (Java).

Ю2.22

Задача Ю2.22. Голодная зима. Суточный рацион коровы составляет [latex]u[/latex] кг сена, [latex]v[/latex] кг силоса и [latex]w[/latex] кг комбикорма. В хозяйстве, содержащем стадо из [latex]k[/latex] голов, осталось [latex]s[/latex] центнеров сена, [latex]t[/latex] тонн силоса и [latex]f[/latex] мешков комбикорма по 50 кг. Сколько ещё дней хозяйство сможет кормить коров по полному рациону? Какой из кормов кончится раньше других?

[latex]u[/latex] [latex]v[/latex] [latex]w[/latex] [latex]s[/latex] [latex]t[/latex] [latex]f[/latex] [latex]k[/latex] Результат. Комментарий.
1 0,5 3 3 0,2 7 15 7. Комбикорм. Тест пройден.
4 7 5 6 0,6 8 13 6. Комбикорм. Тест пройден.
8 5 3,5 4 1 9 11 4. Сено. Тест пройден.
1 1 1 1 0,1 2 2 50. Сено. Силос. Комбикорм. Тест пройден.

C++:

Java:

По условию задачи необходимо найти количество полных дней, в течение которых корова будет обеспечен полный рацион.

Так как изначально в условии задачи данные различались по единицам измерения, я перевела их все в килограммы. Так же было предусмотрено, что количество килограмм может быть дробным положительным, в то время как количество голов в стаде — только натуральным. Для удобства вычисления я ввела дополнительные переменные [latex]a[/latex], [latex]b[/latex], [latex]c[/latex].

Затем я столкнулась с проблемой округления полученного минимального дробного числа к целому количеству дней. Возьмём первый тест для примера. Минимальное дробное количество дней — 7,77. Функция lround округляет число лишь к ближайшему целому. Поэтому мне потребовалось ввести проверку. Если разница между округлённым минимальным и неокруглённым больше нуля, то программа вычитает из полученного значения единицу. Таким образом программа не считает дни, когда корма бы хватило лишь на определённую часть суток.

Следующей задачей было выведение на экран данных о корме, который закончится первым. Тут я действовала по принципу элементарного сравнения.

В программе использован тип данных с плавающей точкой.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом (C++) и этим (Java).

А27

Задача А27. Даны действительные положительные числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. По трём сторонам с длинами [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] можно построить треугольник. Найти углы треугольника.

[latex]a[/latex] [latex]b[/latex] [latex]c[/latex] [latex]\alpha[/latex] [latex]\beta[/latex] [latex]\gamma [/latex] Комментарий
3 4 5 0,643501 0,927295 1,570796 Тест пройден.
6,8 5,2 9,3 0,801375 0,581525 1,758693 Тест пройден.
7,3 5 8,1 1,091967 0,653414 1,396212 Тест пройден.

Код программы (C):

Код программы (Java):

 

По условию задачи необходимо найти углы треугольника (программа высчитывает их в радианах).

Так как изначально в условии задачи сказано, что из отрезков с длинами [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] можно построить треугольник, то решение задачи сводится к нахождению углов по  следствию из «Теоремы косинусов»:  [latex]\cos\alpha=\frac{b^{2}+c^{2}-a^{2}}{2bc}[/latex]. Затем, чтобы найти меру угла в радианах, достаточно просто взять [latex]\arccos(\cos\alpha)[/latex].

Аналогично вычислены меры двух других углов в радианах.

В программе использован тип данных с плавающей точкой.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом (С) или этим (Java).