e-olimp 4650. Граф-Турнир

Задача на e-olimp

Оригинал решения 

Тесты на Try Haxe!

Постановка задачи:

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

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

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

Контур графа (рёбра вида [latex](k,k+1)[/latex]) ориентирован по часовой стрелке.
В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_i[/latex], рассматриваемой на данном шаге — [latex]V_k[/latex] Если ребро [latex](V_i,V_k)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex][V_i,V_k][/latex], иначе — [latex][V_k,V_i][/latex].

Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.

Реализация:

Для решения задачи достаточно хранить граф в форме матрицы смежности.

Тесты:

n = 5 \begin{pmatrix}0 & 1 & 1&0&0 \\0 & 0 & 1&1&0 \\0 & 0 &0&1&1\\1 & 0& 0&0&1\\1 & 1 & 0&0&0\end{pmatrix}
n = 3 \begin{pmatrix}0 & 1 & 0 \\0 & 0 & 1 \\1 & 0 & 0 \end{pmatrix}

Код:

e-olymp 1872. Снеговики

Ссылка на оригинальную статью.

Задача:

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

  • либо добавляет ему сверху один шар;
  • либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

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

Первая строка содержит количество действий [latex] n (1 ≤ n ≤ 200000).[/latex] В строке номер [latex]i+1[/latex]содержится описание действия:

  • [latex]t[/latex] [latex]m[/latex]— клонировать снеговика номер [latex] t (0 ≤ t < i) [/latex] и добавить сверху шар массой [latex]m (0 < m ≤ 1000)[/latex];
  • [latex]t[/latex] [latex]0[/latex] — клонировать снеговика номер [latex]t (0 ≤ t < i)[/latex] и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия [latex]i[/latex], описанного в строке [latex]i+1 [/latex] создается снеговик номер [latex]i [/latex]. Изначально имеется пустой снеговик с номером ноль.

Все числа во входном файле целые.

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

Выведите суммарную массу построенных снеговиков.

Решение: 

Считываем [latex]n[/latex] — количество действий. Задаем двухмерный массив размером [latex] [n+1][2] [/latex]. Указываем значение первого элемента равное [latex]0 [/latex] и нулевого элемента равного [latex]-1 [/latex], чтобы он ни на что не ссылался в начале.  В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна [latex]0 [/latex], то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно [latex]0[/latex], то мы клонируем снеговика и добавляем ему шар массой [latex]m [/latex]. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Тесты:

Input Output
8
0 1
1 5
2 4
3 2
4 3
5 0
6 6
1 0
74
4
0 3
1 2
2 1
1 1
18

 

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

A703

Условие
Даны квадратная матрица $A$ порядка $n$, векторы $x$ и $y$ с $n$ элементами каждый. Получить вектор $A(x+y)$.

Входные данные
Число $n$, матрица $A$, вектор $x$, вектор $y$.

Выходные данные
Результирующий вектор $A(x+y)$.

Тесты

Число $n$ Матрица $A$ Вектор $x$ Вектор $y$ Результирующий вектор $A(x+y)$
2 2 3
3 2
3 4 5 6 46 44
3 2 1 4
5 2 6
3 4 8
2 2 2 3 3 3 42 78 90
4 1 2 3 4
3 4 1 6
2 3 8 1
4 5 0 8
1 2 3 4 5 4 3 2 60 84 84 102

Решение
Вводим число $n$, матрицу $A$, вектора $x$ и $y$. Заходим в цикл в котором считаем сумму векторов $x$ и $y$. В следующем цикле считаем произведение матрицы $A$ на результат сложения векторов $x$ и $y$. Выводим результирующий вектор $res = A(x+y)$.

Try Haxe !

Ю4.12

Условие
Задача: Все ненулевые элементы матрицы $D\left(k,l\right)$ расположить в начале массива $E\left(k \times l\right)$ и подсчитать их количество..

Входные данные
Два натуральных числа $k$ и $l$. А так же $k \times l$ элементов массива.

Выходные данные
Матрица $D$, ненулевые элементы массива $E$, количество ненулевых элементов

Тесты

$k$ $l$ Матрица $D$ Ненулевые элементы матрицы $E$ Количество ненулевых элементов
2 3 2 7 0
1 4 9
2 7 1 4 9 5
3 4 6 7 4 2
9 0 1 3
0 8 0 19
6 7 4 2 9 1 3 8 19 9
4 2 8 9
0 1
5 2
7 26
8 9 1 5 2 7 26 7

Решение
Вводим числа $k$ и $l$. Получаем размерность массива $E$ — $M = k * l$. Заходим в цикл в котором вводим все элементы матрицы $D$ и считаем количество ненулевых элементов и перегоняем их в массив $E$. Потом удаляем нулевые элементы из матрицы $E$.

Try Haxe !

Ю 4.4

Условие

Вычислить среднее значение [latex]m(x)[/latex] и дисперсию[latex]d(x)[/latex] для заданного массива [latex]X(i)[latex] наблюдений.

Решение

Среднее значение выборки или математическое ожидание можно вычислить по формуле: [latex]M(X)=\frac{1}{n}\sum_{i=1} x_{i}[/latex]

Дисперсию: [latex]D(x) = \frac{1}{n}\sum_{i=1}x_{i}^{2} — M(X)^{2}[/latex]

 

Ссылка на  TryHaxe!

Тесты

X(k) X D
 [2,2,2,1,4,5] 2.67 6.33
 [1,2,3,10,4,10]   5 3.33
 [1]   1   0

А400

Задача. Дана действительная квадратная матрица порядка [latex]n[/latex]. Получить [latex]x_{1}x_{n} + x_{2}x_{n-1}+ \cdots + x_{n}x_{1}  [/latex], где[latex] x_k[/latex] — наибольшее значение элементов [latex]k[/latex]-й строки данной матрицы.

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

Оригинал решения

Решение на Try Haxe!

Тесты

[latex]n[/latex] Элементы Результат
2 1 2 3 4 16
3 1 2 3
4 5 6
7 8 9
1146

Код

Ю4.21

Задача.

Целочисленный массив [latex] K(n, n) [/latex]  заполнить нулями и единицами, расположив их в шахматном порядке.

Решение.

В цикле проверяем если сумма номеров элемента в массиве чётна, то значению элемента массива присваиваем  единицу, в противном случае присваиваем  ноль.

Тесты:

n = 4 \begin{pmatrix}0 & 1 & 0&1 \\1 & 0 & 1&0 \\0 & 1 & 0&1 \\1 & 0& 1&0\end{pmatrix}
n = 2 \begin{pmatrix}
0 & 1  \\
1 & 0
\end{pmatrix}

 

Задача взята с источник

A694a

Ссылка на оригинальную статью.

Ссылка на решение задачи на сайте Try Haxe!

Условие:

Получить квадратную матрицу порядка [latex]n[/latex] [latex]\begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}[/latex]

Тесты

n Матрица
3 1 0 0

0 1 0

0 0 1

4 1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

6 1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

Решение:

Сначала создаётся переменная [latex] h[/latex], которая задаёт размерность двумерного массива(матрицы), после чего создаётся собственно массив(матрица) указанной размерности, изначально заполненный нулями. С помощью цикла главная диагональ заполняется единицами. Далее циклом выводим массив.

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

 

Ю4.35

Ссылка на оригинальную статью.

Условие:

Совместная работа. Известно время [latex]t_{1},t_{2}, \cdots,t_{n}[/latex], за которое некоторую работу может выполнить каждый из [latex]n[/latex] рабочих бригады, работая в одиночку. Сколько времени понадобится бригаде на выполнение этой работы, если они будут работать совместно (и при этом никто из них не «сачкует»)

Тесты

Количество рабочих n. Время t каждого рабочего, требуемое для выполнения некоторой работы.  Время совместной работы.
3 2 4 5 1.1
4 5 7 9 4 1.4
5 2 4 5 1 2 0.4
7 8 6 5 6 6 7 2 0.7

Решение:

В программе используются два цикла. Первый– для ввода времени каждого рабочего, а второй– для вычисления общей производительности рабочих. Call–callaboration (время совместной работы), sum – общая производительность рабочих.В данной задаче нам нужно найти время, за которое [latex]n[/latex] рабочих выполнят какую-то совместную работу. В задаче не указан  общий объём выполняемой работы, по-этому зададим его как 1. Время совместной работы находят по формуле: [latex]t_{call}=\frac{V}{\frac{V}{t_{1}}+\frac{V}{t_{2}}+\cdots+\frac{V}{t_{n}}}[/latex], где [latex]V[/latex] –  общий объём выполняемой работы, т.е – 1. Т.к в задаче не указана единица измерения времени, будем считать все в часах.

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