e-olymp 976. Флойд — существование

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

e-olymp 974. Флойд 1
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Пройденный тесты.

e-olymp 976. Флойд — существование

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

   Кратчайший путь может не существовать по двум причинам:

  • Нет ни одного пути.
  • Есть путь сколь угодно маленького веса

Пройденный тесты.

Первая задача решается Алгоритмом Флойда-Уоршела. Поскольку отрицательных ребер в графе нет, и просят вывести кратчайший путь к каждой из вершин, то надо было всего лишь определить, что мы возьмем за бесконечность. Я выбрал [latex]10001[/latex], поскольку максимальное количество вершин [latex]100[/latex], а вес ребер не превышает [latex]100[/latex], соответственной максимально возможное расстояние не превосходит [latex]100*100 = 10000[/latex].

Во второй задаче была та же идея, но в данной ситуация у нас были ребра отрицательного веса. И у нас появилась проблема, могли существовать циклы отрицательной длины(с каждым проходом расстояние до вершин уменьшалось). Поскольку мы пользовались [latex]while[/latex] -ом, мы зацикливались. По этому необходимо было прекращать добавлять вершины, которую имеют отрицательную индексацию и порогом выбрано [latex]-102[/latex], поскольку цикл мог содержать отрицательные ребра, но при это быть положительным, по этому [latex]<0[/latex] нам не подошло. Дальше необходимо было вывести матрицу существования, методом [latex]way[/latex] мы выходили из вершины и определяли индексацию, пуская из всех вершин, мы можем построково выводить матрицу, только необходимо восстанавливать к исходному виду сам граф. В выводе мы определяли, существует путь и мал ли он. Существование проверялось тем, что эта вершина была посещена, а путь к вершине проверялся по индексу, если он меньше половины порога остановки[latex](-50)[/latex], то путь к этой вершине бесконечен.

 

link

А706 Алгоритм быстрого возведения в степень

Степень Входная матрица Результирующая матрица
2
0 1
2 3
2 3
6 11
3
0 1
2 3
6 11
22 39

Пусть даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex] и натуральное число [latex]n[/latex]; требуется найти [latex]A^{n}[/latex]. Алгоритм, основанный на непосредственной применении формулы [latex]A^{n} = A*A*A…*A [/latex]([latex]n[/latex] сомножителей), слишком разорителен. Например, [latex]A^{4}[/latex] экономичнее вычислять как [latex]A^{2^{2}}[/latex]. Идея одного достаточно экономичного алгоритма вычисления [latex]A^{n}[/latex] заключается в следующем: если  [latex]n = 2k[/latex], то [latex]A^{n} = (A^{2})^{k}[/latex]; если же [latex]n = 2k + 1[/latex], то [latex]A^{n} = (A^{2})^{k} * A[/latex]. Степень с показателем [latex]k[/latex] вычисляется с учетом этих же соображений. Итак, надо разделить [latex]n[/latex] на [latex]2[/latex] с остатком:[latex] n = 2k + l [/latex] [latex](0\le l\le 1[/latex]), потом это же проделать с [latex]k[/latex] и т.д. Эти действия приводят, как известно, к построению двоичной записи [latex]n[/latex]. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются [latex]A^{a_{0}}, A^{a_{1}*a_{0}}, …,A^{a_{l}*…*a_{0}}, a_{l}*…*a_{0}[/latex] — двоичная запись числа [latex]n[/latex]. Для этого вычисляется, цифра за цифрой, двоичная запись [latex]n[/latex] и, параллельно, степень за степенью,[latex]A^{(2^{0})}, A^{(2^{1})}, …[/latex] — каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись [latex]9[/latex] в двоичной системе есть [latex]1001[/latex][latex](9 = 1*8 + 0*4 + 0*2 + 1)[/latex]; для вычисления [latex]A^{9}[/latex] достаточно найти [latex]A^{2},A^{4},A^{8},[/latex]([latex]3[/latex] умножения), а затем определить [latex]A*A^{8},[/latex] ([latex]1[/latex] умножение).

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

Написать программу, реализующую предположенный алгоритм.

Суть алгоритма была описана в задании. Реализация была через свою структуру данных, такую как матрица. В ней мы определили умножение и присваивание, для удобства. Есть несколько конструкторов, но нужен по сути только самый первый, остальные для разыгравшейся фантазии. Инициализация при создании матрицы обязательна, поскольку может выдавать неправильный ответ в связи с забытым  в памяти мусором. Как перемножать матрицы можно узнать здесь. Нам понадобятся три матрицы, исходная, временная и матрица для ответа. Само двоичное представление удобно хранить в строке, поскольку идя по ней и находя [latex]1[/latex] мы можем домножить на  временную  матрицу матрицу ответ.

 

link.

e-olymp 4853. Кратчайший путь

Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b.

Условие задачи на e-olimp.
Cсылка на пройденный тесты.

Раз нам надо найти кратчайший путь путь, то будем использовать BFS- поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства я использовал вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор «graf», выступающий в роли графа, причем мы добавляем сразу к вершинам ([latex] graf[x].push_back(y);[/latex]) то есть [latex] x[/latex] — ая вершина получает связь с вершиной [latex] y[/latex], и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем — нибудь, если да, что работаем [latex] while [/latex] — ом, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция [latex] bfs[/latex] вернет [latex] 1[/latex], что запустит тело [latex] if [/latex]- а и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор [latex] family[/latex], в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла [latex] i [/latex] -ая вершина). Восстановленный путь записываем в вектор [latex] ans[/latex]. После чего [latex] while[/latex] прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим [latex]-1[/latex], иначе выводим количество вершин, участвующих в построении пути и сам путь.

link.

 

АА22

В строке убрать все запятые, пробелы и точки. Буквы нижнего регистра привести к верхнему.

input output Описание
./Task22 «he,.llo,. wo.,.,.,.,r.l. d» HELLOWORLD На входе поступает один параметр  в кавычках, вкотором есть пробел. Он убирается программой.
./Task22 2425s,Go.oD b24.ye 2425SGOODB24YE На входе поступает два параметра, пробел между параметрами убирается автоматически (пробел служил разделением между параметрами).

neznayka

А409

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

1 3 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1
1 1 1 1 1 4 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 5
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
Ответ 14
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
Ответ Нету элементов с такими свойствами

Находим наибольший из нижних элементов (элементы, расположенные ниже главной диагонали). Потом сравниваем каждый элемент верхнего множества (элементы, расположенные выше главной диагонали и на самой диагонали) с наибольшим элементов ([latex]bigger[/latex]) всех нижних элементов и если это число больше, то прибавляем это число к переменной [latex]summa[/latex].

link

Java

 

А810

Дано натуральное число [latex]n (n <= 1000)[/latex]. Записать это число русскими словами (семнадцать, двести пятьдесят три, тысяча и т. д. ).

Ход решения очень простой, читаем наше [latex]n[/latex] в тиме [latex]integer[/latex] и проверяем, если оно равно [latex]1000[/latex], то выводим ответ «тысяча», иначе берем число по модулю [latex]100[/latex] и присваиваем(дописываем) строке [latex]s[/latex] значение уже заранее описанного для [latex]n mod 100[/latex] ответа. Дальше проверяем так же по десяткам, здесь есть маленький нюанс, для чисел от [latex]10[/latex] до [latex]19[/latex] — эти числа имеют собственное названием, если же [latex](n mod 100)/10[/latex] от  [latex]2[/latex] до [latex]9[/latex], то дописываем в  [latex]s[/latex] соответствующее значение. И последний шаг — это запись едениц, мы берем все число по модулю  [latex]10[/latex] ([latex]n mod 10[/latex]) и дописываем то, что осталось.

 Ссылка на программу

А137е

Даны натуральные [latex] n[/latex], действительные [latex] a_{1},\ldots,a_{n}[/latex].

Вывести: [latex] a_1+1!, a_2 +2!, …, a_n+n![/latex].

n a1 a2 a3 a4
Input: 4  1 2 3 4 Output: 2.00 4.00 9.00 28.00
Input: 4 0.1 0.2 0.3 0.4 Output: 1.10 2.20 6.30 24.40

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл [latex]for[/latex], от [latex]1[/latex] до [latex]n[/latex]. Дальше в теле цикла описываем чтение элементов, увеличение факториала и вывод суммы цифр из потока и факториала.

Ссылка на программу.

А116е

Вычислить [latex] \prod_{i=1}^{n}{\frac{(1-x)^{i+1}+1}{((i-1)!+1)^2}} [/latex]

Числа [latex] n [/latex] и [latex] x [/latex] вводятся с клавиатуры.

n x Ответ
1 3 1.25
2 3 -2.1875
3 3 -4.13194

Вводим n и x типа int. Инициализируем переменные v=1-x и u=1 типа double. Присваем значение переменной pro, при  n=1. Запускаем цикл от 2 до n в котором увеличиваем факториал u*=i-1 и степень v*=1-x. Так цикл пройдет n раз и в конце выдаст итоговое произведение cout<< pro.

Link

Java

 

Ю4.13

Задача. Дан массив [latex]A(n)[/latex]. Все положительные его элементы поместить в начало массива [latex]B(n)[/latex], а отрицательные элементы- в начало массива [latex]C(n)[/latex]. Подсчитать количество тех и других.

Входные данные 3 -1 2 0 Выходные данные 1 2

Заводим счетчик для отрицательных и положительных чисел,а также переменную для количества элементов массива типа [latex]int[/latex]. Читаем количество элементов и создаем три массива типа [latex]double[/latex](вдруг нам буду вводить действительные числа). В цикле читаем элемент [latex]A[i][/latex] и условием определяем положительное число или нет, и увеличиваем соответствующий счетчик. Выводим полученные результаты.

Ссылка на программу.

Java

 

 

Ю3.24

Задача. Композиция [latex]n[/latex]- ого порядка [latex]f^{[n]}(x)[/latex] функции [latex]f(x)[/latex] назовем результат [latex]n[/latex]- кратного вычисления функции [latex]f [/latex], то есть [latex]f^{[1]}(x)=f(x)[/latex], [latex]f^{[ 2]}(x)=f(f(x))[/latex], и так далее. Для заданных [latex]n[/latex] и [latex]x[/latex] вычислить [latex] (expln)^{[n]} (x)[/latex] и [latex] exp^{[n]} ln^{[n]} (x)[/latex], результаты сравнить с [latex] x[/latex], то есть вывести значения аргумента, композиции функции и разности между ними.

[latex]x[/latex] [latex]n[/latex] [latex](expln)^{[n]}(x)[/latex] [latex]exp^{[n]} ln^{[n]}(x)[/latex] [latex]x-(expln)^{[n]}(x)[/latex] [latex]x-exp^{[n]}ln^{[n]} (x)[/latex]
3 3 3 3 -4.44089e-16 -4.44089e-16
3 4 3 nan -4.44089e-16 nan

 

Задаем функцию, которая будет возвращать нам [latex]double[/latex] и иметь два параметра типа [latex]double[/latex] и [latex]int[/latex](число [latex]n[/latex]- количество композиций). В ней проверяем равна ли  переменная нулю latex[/latex], если равна, то нет необходимости производить композицию, если же не равна нулю, то присваиваем [latex]x[/latex] значение функции  и возвращаем [latex]x[/latex], если [latex]n<=1[/latex], иначе вызываем эту же функцию, но на порядок ниже latex[/latex] и так пока [latex]n==1[/latex] (то есть задаем рекурсию). Точно также описываем формулы [latex]exp[/latex] и [latex]ln[/latex] (В C++ [latex]log(x)[/latex]- это логарифм числа [latex]x[/latex] по основанию [latex]e[/latex]). В основной программе вызываем эти две функции и выводим их значения  и разность между аргументом и значением функции для определения погрешности. (Возможны такие варианты, когда у вас будет логарифм отрицательным, что приведет к ответу [latex]nan[/latex])

Java

 

А137е(а)

Даны натуральные [latex] n[/latex], действительные [latex] a_{1}…a_{n}[/latex].

Вывести: [latex] a_1+1!, a_2 +2!, …, a_n+n![/latex].

Input : 1 2 3 4 Output: 2.00 4.00 9.00 28.00
Input : 0.1 0.2 0.3 0.4 Output: 1.10 2.20 6.30 24.40

 

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл [latex]while[/latex], у которого в условии ставим:

(Работать, пока файл не закончится (конец потока)). Дальше в теле цикла описываем увеличение факториала и выводим сумму цифр из потока и факториала, в конце цикла увеличиваем [latex]i[/latex] для увеличения факториала.

Java

 

Ссылка на программу.

А59з

Задача. Даны действительные числа [latex]x, y[/latex]. Определить, принадлежит ли точка с координатам [latex]x, y[/latex] заштрихованной части плоскости (рис. ниже).

ыфв

Объявляем две переменные [latex]x,y[/latex] типа [latex]double[/latex] (точки могут иметь дробные координаты). Читаем координаты точки. В условии проверяем три пункта:

  1. Лежит ли [latex]y[/latex] выше [latex]-2[/latex] [latex](y>=-2)[/latex].
  2. Находится ли точка между двумя прямыми [latex](|x|<=1)[/latex].
  3. Лежит ли точка ниже диагоналей,описанных функцией [latex]y=|x|[/latex].

Если все эти три условия соблюдены, то точка находится в закрашенной области, иначе вне этой области.

Реализация на Java:

 

 

e-olymp 3. Спичечная модель

Спичечная модель

Спичечная модель с http://www.e-olimp.com.ua/problems/3

Задача.

Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.

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

Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?

Все числа в задаче не превышают [latex]2*10^9[/latex].

Технические условия

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

Одно число [latex] N [/latex] – количество кубиков.

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

Одно число – количество спичек.

 

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

Пройденные тесты программы.

Input Output Comments
0 0 Смотрим,что выдает при  0 кубов
3 28 Проверяем пример данный в задаче
[latex]2*10^9[/latex] 6.00953Е9 Не вылезает ли за рамки переменных

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

Для лучшего понимания сколько нам понадобится спичек, рекомендую представить на бумаге как будут выглядеть «этажи» нашего куба.

Первый этаж будет выглядеть так. (Для примера берем куб [latex]444[/latex], т.к. он самый наглядный и не громоздкий)

8 5 5 5
8 5 5 5
8 5 5 5
12 8 8 8

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

Второй этаж будет выглядеть так. (аналогично для последующих)

5 3 3 3
5 3 3 3
5 3 3 3
8 5 5 5

Поскольку у нас уже есть основание, то последующие этажи требуют меньшего количества спичек. Зная это, выведем формулу, по которой можно вычеслить необходимое количество спичек для построения куба [latex]n[/latex]-ой размерности.

Получаем [latex]8i+4+5i(i-1)2+3(i-1)2+3i(i-1)^2+2(i-1)^2[/latex] (Где i — это «размерность» куба. К примеру: подставив i=4, мы найдем необходимое количество спичек для построение куба [latex]44*4[/latex]).

Теперь возник вопрос, как в задаче определить размерность куба? Очень просто. Максимальное количество возможных кубов равно [latex]i^3[/latex], следовательно зная количество кубов (Дано в начале задачи) можно определить [latex]i[/latex]. Описываем цикл, увеличивающий [latex]i[/latex] пока [latex]i^3<n[/latex].

Задаем функцию с тремя параметрами. ([latex]u[/latex] — определяет, в какую степень возводить)

Имея размерность, можно узнать, сколько нам надо спичек для построения куба прошлой размерности по формуле. Следовательно мы знаем, сколько кубов принадлежит размерности [latex]i[/latex] ([latex]p=n-i^3[/latex]). Разобьем на этапы построение куба размерности [latex]i[/latex] из куба размерности [latex]i-1[/latex]. Пример:

Имея куб [latex]333[/latex] мы начнем достраивать к нему боковую стенку, потом заднюю, и в самом конце так называемую «крышу».

При построении боковой стены мы получаем куб равный [latex] 433[/latex](увеличилась его длинна).

Вид сверху:

[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]

При построении задней стены он расшириться в ширине [latex]443[/latex].

[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]

На третьем этапе увеличиться высота куба. Следовательно куб будет иметь такую форму [latex]444[/latex].

Определяем  этап. Если мы находимся на третьем этапе, то разность между количеством кубов([latex]n[/latex]) и количеством кубов нашей размерности без крыши([latex]i^2(i-1)[/latex] должно быть больше нуля — [latex]n-i^2(i-1)>0[/latex]. Если больше нуля, то переходим к третьем этапу, иначе смотрим, не на первом ли мы этапе случайно? Для этого количество кубов([latex]n[/latex]) должно быть меньше или равно количеству кубов на первом этапе нашей размерности([latex]i(i-1)(i-1)[/latex]) — [latex]i(i-1)(i-1)>=n[/latex]. Если это выполняется, то переходим к первому этапу, иначе ко второму этапу.

Этап определён. Осталось придумать самый экономный способом построения оставшихся кубов. (В этом и заключается подвох задачи) Самый экономный способ, это если мы будем строить боковую стенку (заднюю или «крышу») в такой последовательности:

16 15 14 13
9 8 7 12
4 3 6 11
1 2 5 10

В количестве затраченных спичек выглядит вот так:

3 3 3 5
3 3 5 3
3 5 3 3
8 5 5 5

По диагонали и по основанию мы тратим по 5 спичек, остальные кубы требуют  по 3 (для построения первого куба необходимо 8 спичек). Можно заметить, что номера кубов, для построения которых надо 5 спичек, имеют зависимость, которую можно использовать. По размерности боковой плоскости можно определить количество спичек необходимых для построения плоскости прошлой размерности по формуле [latex]8+(g-2)25+3((g-1)(g-1)-1-(g-2)2)[/latex]. Формула при размерности 1 выдаст неправильный ответ, по этому ставим условие, если [latex]g=1[/latex], то результат увеличиваем на 8, иначе на всю эту формулу. После этого у нас осталость некое количество кубов. Запускаем цикл от номера последнего элемента нашей прошлой разрмерности latex(g-1)+i<=p[/latex].

Разобравшись во всех нюансах задачи, приступаем к напсианию кода.

Ссылка на программу

Ю2.11

Задача жестянщика. Можно ли из круглой заготовки радиусом  [latex]r[/latex] вырезать две прямоугольные пластинки с размерами  [latex] a[/latex] × [latex] b[/latex] и [latex] c[/latex] × [latex]d[/latex]?

1.6 3 0 3 0 We can
1.6 3 1 3 1 We can’t
  2  3 1 3 1 We can
  2  5 1 4 1 We can’t

 

Рассмотрим как выглядит прямоугольник в круге.

Безымянный

Можно заметить, что [latex] h=d1[/latex] (длина до центра окружности) — это катет прямоугольного треугольника, значит его можно найти по теореме Пифагора , зная радиус круга [latex] R[/latex]  и катит [latex] r[/latex] (в нашем случае [latex] a/2[/latex]) [latex] h=\sqrt{R^2-r^2}[/latex]). Вычитая из полученного [latex] h=d1[/latex]  ширину [latex] b[/latex] мы получим  сколько он места занимает при данной длине и ширине относительно центра круга. (Если у нас  [latex] b<d1[/latex], то для второго прямоугольника у нас будет больше места) Тоже самое мы проделываем и для второго прямоугольника и получаем наше [latex] h2=d2[/latex]. Дальше размещаем наши прямоугольники параллельно друг другу и смотрим, хватает ли места второму прямоугольнику места с учетом его ширины (Если по ширине второй прямоугольник не превышает оставшегося места) [latex]d<d2+(d1-b)[/latex].

 

Реализация на Java:

 

Ссылка на код программы.