A1038. Дейкстра?

Задача: Имеется [latex]n [/latex] городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка  [latex]n [/latex], элемент [latex]a_{ij} [/latex] которой равен некоторому отрицательному числу, если город [latex]i [/latex] не соединен напрямую дорогой с городом [latex]j [/latex] и равен длине дороги в противном случае latex [/latex].

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

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

4
-1 2 4 -1
2 -1 1 6
4 1 -1 1
-1 6 1 -1

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

1 > 2 = 2

1 > 3 = 3

1 > 4 = 4

Длина кратчайшей цепи, проходящей через все вершины 4

Ссылка на ideone: http://ideone.com/iXjoLZ

Решение:

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

A711a

Задача: Дана матрица [latex]A [/latex] размера [latex]m\times m [/latex]. Получить матрицу  [latex]AA^{*} [/latex] (ее размер [latex]m\times m [/latex]).

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

4
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6

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

30 70 20 50
70 174 68 122
20 68 86 44
50 122 44 86

Решение:

Ссылка на ideone С++: http://ideone.com/iXjoLZ

Ссылка на ideone Java: http://ideone.com/u96MDY

 

Вводим матрицу [latex]A[i][j] [/latex] и матрицу [latex]B[j][i] [/latex] в цикле по [latex] i,j[/latex] от одного до [latex] n[/latex]. Умножаем матрицу  [latex] A[/latex] на [latex]A^{*} [/latex].

 

e-olymp 5076. Регулярный граф

Задача 5076: Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ли он регулярным.

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

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

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

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

Тесты

Входные данные Выходные данные
3 3
1 2
1 3
2 3
YES
3 2
1 2
2 3
NO

Решение:

Ссылка на ideone C++: http://ideone.com/cCHxvo

Ссылка на ideone Java: http://ideone.com/2ih3iK

 

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

 

AA4

Задача: В заданной строке удалить все латинские буквы.

Ввод Вывод
zdfgzdfg987w435kjwbsdf987w345 987435987345

Решение:

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

Ссылка на ideone Java: http://ideone.com/a2x238

 

Вводим строку. Перебираем все символы строки в цикле и удаляем символ, если он является латинской буквой

А402а

Задача: Даны натуральное число [latex]n\geqslant 2 [/latex] , действительная квадратная матрица порядка [latex]n [/latex]. Построить последовательность [latex]b_{1}, \ldots, b_{n} [/latex] из нулей и единиц, в которой [latex]b_{i}=1 [/latex] тогда и только тогда, когда элементы строки матрицы образуют возрастающую последовательность.

Ввод:

5
1 2 3 4 5
6 5 4 3 2
0 1 2 3 4
-5 1 3 4 0
1 3 3.5 4.3 5

Вывод:

1 0 1 0 1

Решение:

Ссылка на ideone C++: http://ideone.com/RrsF1f

Ссылка на ideone Java: http://ideone.com/eW8wJS

 

Вводим матрицу [latex]a[n][n] [/latex]. Заранее присваиваем всем элементам матрицы [latex]b[n] [/latex] единицу.  если условие не выполняется (элементы с строке введенной матрицы расположены не по возрастанию), то меняет единицу на ноль в матрице  [latex]b[n] [/latex]

Ю11.7

Метод трапеций. Вычислить определенный интеграл [latex]I=\int_{b}^{a}f(x)dx [/latex] методом трапеций:[latex] I\approx \frac{b-a}{2n}(y_{0}+2y_{1}+\dots+2y_{n-1}+y_{n}), [/latex] где [latex] n [/latex] — количество отрезков разбиения; [latex]y_{0},y_{1},\ldots,y_{n} [/latex] — значения функции [latex]f(x) [/latex] на концах отрезков.

Вычислим определенный интеграл для функции [latex]y=-3x^2+2x+9[/latex]
[latex] \int_{-1}^{2}(-3x^2+2x+9)dx=21 [/latex]

Решение:

Ссылка на ideone C++: http://ideone.com/RJpYSw

Ссылка на ideone Java: http://ideone.com/AfEDeq

 

В условии самой задачи весь алгоритм решения расписан.

Ю4.26

TALVEZ-NOSSO-PERSONAGEM-NA-HISTRIA1Задача: На шахматной доске находятся король и несколько ферзей другого цвета. Проверить, находится ли король под угрозой и если да, кто ему угрожает. Положение фигур задано массивом A(8,8): 0 — клетка пуста, 1 — король, 2 — ферзь. Ферзь бьет по горизонтали, вертикали и диагоналям.

0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 2 0 0 0 2 2

Король под угрозой от ферзя на клетке (2,8) (по вертикали)

Король под угрозой от ферзя на клетке (8,2) (по горизонтали)

Король под угрозой от ферзя на клетке (8,8) (по диагонали)

Решение:

Ссылка на ideone C++: http://ideone.com/h4ECiW

Ссылка на ideone Java: http://ideone.com/sIJwPA

 

Сначала в цикле вводим массив и ищем где находится король (единичка). Найдя короля, начинаем искать ферзей в восьми направлениях от него (вниз, вверх, вправо, влево и также по диагоналям). Найдя ферзя по одному из направлений выводим его координаты и переходим на следующее направление т.к. все остальные не причинят угрозы королю, потому что между ними и королем стоит фигура (первый найденный ферзь).

Ю1.7

Задача: Селекция. Селекционер вывел новый сорт зерновой культуры и снял с опытной делянки [latex]k [/latex] кг семян. Посеяв 1 кг семян, можно за сезон собрать [latex]p [/latex] кг семян. Через сколько лет селекционер сможет засеять новой культурой поле площадью  [latex]s [/latex] га, если норма высева  [latex]n [/latex] кг/га?

k p s n y
1 2 3 4 4
6 10 20 41 3
0 1 2 3

Решение:

Ссылка на ideone C++: http://ideone.com/s7pxme

Ссылка на ideone Java: http://ideone.com/JpE5D1

 

Проверяем что б все данные были строго больше нуля

Вычисляем количество лет, требуемых для роста зерновой культуры по формуле:

[latex] \frac{ln(ns/k)}{ln(p)} [/latex] (Количество лет округляем в большую сторону всегда)

 

A162

Задача:  Даны натуральные числа  [latex]i, n[/latex], действительные числа [latex] a_{1}, … ,a_{n} (i\leq n) [/latex]. Найти среднее арифметическое всех чисел  [latex]a_{1}, … ,a_{n}[/latex] кроме [latex] a_{i} [/latex].

Т.к в условии задачи указано, что [latex] (i\leq n) [/latex] , то сделаем проверку, также выберем для [latex] i, n [/latex] тип unsigned int, т.к они натуральные ( [latex] >0 [/latex] )

n i a[0] a[1] a[2] a[3] a[4] a_m
5 2 1 2 3 4 5 3
5 6 2 3 4 5 44

Решение:

Ссылка на ideone C++: http://ideone.com/URjsSJ

Ссылка на ideone Java: http://ideone.com/TLfjVZ

 

Сделаем цикл по [latex]j [/latex]. Если [latex]j\neq i [/latex], то суммируем [latex]a [/latex] в переменную [latex]s [/latex]

А51

Задача: Даны действительные числа [latex] a,b,c (a\neq 0) [/latex] . Полностью исследовать биквадратное уравнение [latex] ax^4+bx^2+c=0 [/latex] т.е если действительных корней нет, то должно быть выдано сообщение об этом, иначе должны быть выданы два или четыре корня.

Я немного усложнил задачу, добавил случай [latex] a=0 [/latex]

a b c x1 x2 x3 x4
0 0 0 R R R R
0 0 1
0 1 0 0 0 0 0
0 2 -8 2 -2
0 2 3
10 2 10
2 2 -6 1.14 -1.14
-5 22 -6 0.24 -0.54 2.09 -2.09
1 4 4
1 -4 4 1.41 -1.41

Решение:

Ссылка на ideone C++: http://ideone.com/By6f3b

Ссылка на ideone Java: http://ideone.com/fsmSvf

 

Если [latex] a\neq 0 [/latex] , то надо рассмотреть только несколько случаев: Дискриминант меньше нуля (корней нет), дискриминант больше нуля, тогда делаем замену, [latex] x^2=t>0 [/latex] и считаем [latex] t [/latex], далее проверяем будет ли [latex] t>0 [/latex]

Если добавить случай с [latex] a=0 [/latex] , то надо рассмотреть ситуации:

[latex] b=0 [/latex] , тогда если [latex] c=0 [/latex] , то корней бесконечно много, в противном случае — корней нет.

[latex] b\neq 0 [/latex] , тогда если [latex] -(c/b)>0 [/latex] , то решение есть, в противном случае под корнем отрицательное число

Ю3.46

Задача: Для заданных значений [latex]n [/latex] и [latex]x [/latex] вычислить выражение [latex]s = \sin x+\sin \sin x+ \cdots +\sin \sin \cdots \sin x [/latex].

n x s
10 5.01 -6.40802
8 1.67 5.54661
20 2*PI 0

Решение:

Ссылка на ideone C++: http://ideone.com/70iBvc

Ссылка на ideone Java: http://ideone.com/M2gM7s

 

Суммируем в цикле [latex] \sin x [/latex] и присваиваем  [latex]x = \sin x[/latex]

Ю3.6

Последовательная обработка деталей на трёх станках к задаче Ю3.6

Последовательная обработка деталей на трёх станках к задаче Ю3.6

Задача:  Время обработки. Каждая из деталей должна последовательно пройти обработку на каждом из 3-х станков. Продолжительности обработки каждой детали на каждом станке вводятся группами по 3 числа, до исчерпания ввода. Сколько времени займет обработка всех деталей?

Количество деталей Время обработки Ответ
3 1 2 3 4 5 6 7 8 9 29
2  4 5 6 -5 4 5 Ошибка
2 5 4 3 2 4 0 13

Решение:

Ссылка на ideone C++: http://ideone.com/sKN2FU

Ссылка на ideone Java: http://ideone.com/ZwNfNL

Введем 3 переменные  [latex]t1, t2, t3 [/latex] , обозначающие время обработки детали на каждом из 3х станков и переменные [latex]x, y, z [/latex] которые будут показывать общее время обработки на каждом станке. Дольше всех будет работать 3й станок, поэтому наша задача вычислить время обработки на нем всех деталей.

Вычисляем время обработки всех деталей:

Если у нас не было введено время обработки меньше нуля, то выводим общее время работы третьего станка.

 

Ю2.23

Задание: В Алтайском гос университете принято, что старшая цифра трехзначного номера студенческой группы обозначает номер факультета, средняя – последнюю цифру года поступления, младшая – порядковый номер группы. Продолжительность обучения — не более 6 лет (магистратура). Дан номер группы студента АГУ и текущий год. Напечатать в каком году он поступил и на каком факультете учиться. Например гр.432, 1996г. — факультет математический, год поступления 1993.  Для справки приведены номера факультетов:1–исторический, 2 – экономический, 3 – юридический, 4 – математический, 5 – физический, 6 – химический, 7 – биологический, 8 – филологический, 9 – географический, 10-социологический.

Тестирование. Предусмотреть невозможные ситуации. Например гр 521, год 2001.

135 2014 работает
341 2008 работает
005 2014 работает
4995 2014 не работает
521 2009 не работает
10101 2014 не работает
91 2014 не работает
135 2014 Исторический факультет  Год поступления 2013
341 2008 Юридический факультет  Год поступления 2004
005 2014 Социологический факультет  Год поступления 2010

Решение:

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

Ссылка на ideone Java: http://ideone.com/sLff6T

 

Для начала определяем первую цифру группы — a1, вторую цифру группы — a2, последнюю цифру года — b1.

Далее проводим проверку, что бы выяснить, существует ли эта группа (не больше 4х цифр, если первая 10; не меньше 3х цифр; время обучения не больше 6 лет ). Далее проверка существования факультета и проверка времени обучения.

Если все условия выполняются, то выводим название факультета и год поступления.

 

Ю1.2

Задача Ю1.2 : Из радианов в градусы. Угол  [latex]\alpha[/latex]  задан в радианах. Найти его величину в градусах, минутах и секундах

rad deg m s
3 171 53 14
-2.5 -143 14 22
21 123 12 41
-9.1 -161 23 30

Решение:

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

Ссылка на ideone Java: http://ideone.com/PTbhOy

 

Для вычисления градусов из радиан пользовался формулой:

[latex]Deg=Rad\frac{180}{\pi }[/latex]

Далее ищу остаток от деления на   [latex]360[/latex] т.к. угол  [latex]\alpha < 360[/latex].

Для вычисления минут отбрасываю от градусов целую часть (округляя вниз) и умножаю на [latex]60[/latex]

Для вычисления секунд отбрасываю от минут целую часть (округляя вниз) и умножаю на [latex]60[/latex]

секунды округляю функцией round

Ответ выводит в градусах минута и секундах