e-olymp 2470. Проверка на неориентированность

Задача

По заданной квадратной матрице [latex]n×n[/latex] из нулей и единиц определить, может ли она быть матрицей смежности простого неориентированного графа. Напомним, что простой граф не содержит петли и мультиребра.

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

В первой строке задано число [latex](1 \leqslant n \leqslant 100).[/latex] Затем идут [latex]n[/latex] строк по [latex]n[/latex] элементов в каждой — описание матрицы смежности.

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

Вывести [latex]YES,[/latex] если граф простой неориентированный, и [latex]NO[/latex] в противном случае.

Тесты

# Входные данные Выходные данные
1 3
0 1 1
1 0 1
1 1 0
YES
2 3
0 1 1
1 0 1
0 1 0
NO
3 3
0 1 0
1 1 1
0 1 0
NO
4 4
1 1 1 1
1 0 1 1
1 1 0 1
NO
5 4
0 0 1 1
0 0 0 1
1 0 0 0
1 1 0 0
YES

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

Решение задачи

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j] = a[j][i].[/latex] Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия. Для этого воспользуемся обычными двумерными массивами. Затем проверим является ли граф простым. Если [latex]a[i][j] = 1,[/latex] то граф содержит петлю, следовательно простым не является. Затем проверим матрицу на симметричность, т. е. выполняется ли условие [latex]a[i][j] = a[j][i].[/latex] Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, то это означает, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится [latex]«NO».[/latex] Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим [latex]«YES».[/latex]

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 44. Единицы

Задача


В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?

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

Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]

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

Искомое количество единиц.

Тесты

# Входные данные Выходные данные
1 7 6
2 22 10
3 90 13
4 157 16
5 985 21

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

Решение задачи

Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 2803. МаркЕрованные кубики

Задача


У Витека есть набор кубиков, на котором изображены английские буквы, причём как маленькие, так и большие. Недавно мама подарила ему ещё и набор кубиков с цифрами, в результате чего Витек научился быстро считать в пределах [latex]10-[/latex]ти. А вот папа имел неосторожность подарить ему набор разноцветных маркеров, после чего Витек начал экспериментировать с кубиками с цифрами: он зарисовывал очередную цифру и на её месте рисовал цифру на единицу большую. Так как он прекрасно понимал, что цифры [latex]10[/latex] не существует, он вместо числа [latex]10[/latex] всегда писал цифру [latex]0.[/latex]

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

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

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

Единственная строка, состоящая из описанных выше символов. Длина строки не превышает [latex]255[/latex] символов.

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

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

Тесты

# Входные данные Выходные данные
1 abc1234567890ABC abc2345678901ABC
2 fgrt7645gft5 fgrt8756gft6
3 65748909674 76859010785
4 6ASD4890gf9674 7ASD5901gf0785
5 RFT768S7dfr RFT879S8dfr

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

Решение задачи

Для решения задачи вводим строку [latex]str[/latex] и преобразовываем её в массив символов. Так как у Витека есть кубики с буквами и цифрами, то проверяем, является ли элемент строки числом. Если да, то увеличиваем значение символа на [latex]1,[/latex] а если это [latex]9,[/latex] то заменяем её на [latex]0.[/latex]

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 2666. Половина

Задача

Напишите программу, заполняющую массив [latex]n × n[/latex] следующим образом: на побочной диагонали стоят нули, выше диагонали двойки, ниже единицы.

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

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

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

Выведите массив, заполненный по указанному правилу.

Тесты

# Входные данные Выходные данные
1 2 20
01
2 3 220
201
011
3 4 2220
2201
2011
0111
4 5 22220
22201
22011
20111
01111
5 10 2222222220
2222222201
2222222011
2222220111
2222201111
2222011111
2220111111
2201111111
2011111111
0111111111

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

Решение задачи

Для решения задачи создадим двумерный массив, количество строк и столбцов которого не превышают [latex]20.[/latex] Заполнять его будем при помощи двойного цикла, как указано в решении задачи. Введем следующие обозначения:

  • [latex]i + j = n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит на побочной диагонали;
  • [latex]i + j > n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит ниже побочной диагонали;
  • [latex]i + j < n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит выше побочной диагонали.

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 7809. Утренняя зарядка

Задача


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

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

Единственная строка входного файла содержит последовательность чисел, записанных через пробел, означающие цвет футболки. Цвет — число в диапазоне от [latex]0[/latex] до [latex]9.[/latex] Всего в строке не более, чем [latex]10^6[/latex] чисел.

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

В выходной файл нужно вывести единственное число — количество эстетических пар, которые можно сложить.

Тесты

# Входные данные Выходные данные
1 0 3 6 3 0 0 1 2
2 8 8 9 9 7 6 7 8 4 3
3 5 6 7 3 2 0
4 2 7 6 8 9 2 1 1
5 8 7 7 5 4 3 5 4 8 4

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

Решение задачи

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 7368. Средний балл для фигуристов

Задача


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

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n \leqslant 10, 0 < m \leqslant 100)[/latex] для каждого из фигуристов.

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

В одной строке вывести [latex]m[/latex] чисел с точностью до двух десятичных знаков — балл каждого спортсмена.

Тесты

# Входные данные Выходные данные
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 6 3
6 7 6 5 4 3
9 8 5 5 6 5
7 6 4 1 2 2
5.25 7.00 3.50
3 4 5
6 7 8 6
9 8 5 4
7 6 7 5
4 3 9 3
7 8 7 6
7.00 6.50 6.00 4.00 7.00
4 4 4
7 7 2 3
9 8 3 3
5 4 9 7
4 3 2 6
3.00 8.00 6.00 3.50
5 8 5
4 5 6 7 7 4 9 8
3 5 6 6 7 8 5 9
7 6 3 9 3 7 9 7
5 6 4 3 7 7 5 7
9 8 4 6 7 9 9 4
6.60 6.17 6.75 5.00 7.00

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

Решение задачи

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x,[/latex] и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n — a — b.[/latex] А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\displaystyle\frac{sum}{n — a — b}[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 2807. Кубики-3

Задача

Дома у Витека было [latex]2[/latex] одинаковых набора кубиков из английских букв, но во время очередной уборки один из кубиков затерялся. Помогите Витеку определить, какой же из кубиков отсутствует в одном из наборов.

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

В первой строке задано количество найденных Витеком кубиков [latex]n[/latex] [latex](1 \leqslant n \leqslant 10^5),[/latex] а во второй строке n символов, изображённых на каждом из кубиков

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex]»Ok»,[/latex] если Витек ошибся и ни один из кубиков не потерялся.

Тесты

# Входные данные Выходные данные
1 5 abcac b
2 8 ryirhiyh Ok
3 3 AVA V
4 6 DjkjDk Ok
5 7 LnCsCnL s

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

Решение задачи

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Воспользуемся оператором присваивания побитового исключающего или, с помощью которого мы будем сравнивать индексы символов, полученные из массива строки. Если количество кубиков четное, то переменная [latex]res[/latex] будет равна нулю, следовательно не один из кубиков не потерялся и мы увидим сообщение с текстом [latex] «Ok»[/latex]. Иначе выводится символ, который изображен на потерянном кубике.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 2999. Функция — 10

Задача

Дана функция, аргументы которой – неотрицательные целые числа [latex]m[/latex] и [latex]n[/latex] [latex](m \leqslant n):[/latex]

$$f(m,n)=\begin{cases} 1, \text{ npu } m=0 \\\\ f(m-1,n-1)+f(m,n-1), \text{ npu } 0<m<n \\\\ 1, \text{ npu } m=n \end{cases}$$

Вычислить значение функции.

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

Два целых неотрицательных числа [latex]n[/latex] и [latex]m[/latex] [latex](0 \leqslant n, m \leqslant 20).[/latex]

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

Выведите искомое значение заданной функции [latex]f(m, n).[/latex]

Тесты

# Входные данные Выходные данные
1 4 2 6
2 7 7 1
3 12 0 1
4 15 5 3003
5 10 6 210

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

Решение задачи

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

  1. Если [latex]m = 0[/latex] или [latex]m = n[/latex], то программа возвращает единицу.
  2. Если [latex]m < n[/latex], то программа вычисляет значение функции по формуле [latex]f(m-1,n-1)+f(m,n-1)[/latex]

Затем в главной функции вызываем нашу вспомогательную функцию func() с помощью новой переменной [latex]d[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 932. Высота треугольника

Задача

Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].

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

Два целых числа [latex]S[/latex] [latex](0 < S \leqslant 100)[/latex] и [latex]a[/latex] [latex](|a| \leqslant 100)[/latex].

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

Вывести высоту треугольника с точностью до сотых.

Тесты

# Входные данные Выходные данные
1 20 7 3.73
2 35 3 7.00
3 12 4 3.29
4 67 9 7.92
5 135 13 11.17

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

Решение

Для решения задачи нам понадобится формула для нахождения площади треугольника: [latex]S = \frac{1}{2} \cdot h \cdot c[/latex], где [latex]h[/latex] — высота, [latex]c[/latex] — сторона, к которой высота проведена. Вместо [latex]c[/latex] подставим [latex]h+a[/latex] (по условию задачи). Далее приходим к квадратному уравнению [latex]h^2 + a \cdot h — 2 \cdot S = 0[/latex]. Решив его, получим два корня. Второй корень нам не подходит, поскольку он меньше [latex]0[/latex], а длина не может быть отрицательной. Первый корень и будет ответом нашей задачи.

Ссылки

Ссылка на e-olymp

Ссылка на ideone