Author Archives: Руслан Масальский

e-olymp 8651. Браслети (Bangles)

by

4

Задача взята з сайту e-olymp

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leqslant N \leqslant 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Тести

№
 Inputs Outputs
1
 5 7
1 3
1 4
2 4
2 5
3 4
3 5
4 5		 2
2
 4 4
1 2
2 3
3 4
1 4		 1
3
 5 5
1 2
2 3
3 5
1 4
1 5		 1

Код

 

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

Related Images:

e-olymp 94. Problem of prime numbers!

by

7

The task is taken from e-olymp

Task

One of the most difficulties of an instructor is question design for the final-term exam. Dr. Ghavamnia teaches “Fundamentals of Algorithms” at University of Isfahan (UI) and has designed a good practical algorithmic problem for his exam. He wants that students use all of their algorithmic skills to code this problem as best and efficient as they can. The problem is as follows: a ring is composed of [latex]N[/latex] circles numbered from [latex]1[/latex] to [latex]N[/latex] as shown in diagram. You are given [latex]N[/latex] integer numbers. Put these numbers into each circle separately with the condition that sum of numbers in three adjacent circles must be a prime.
Each test case may have several solutions and your task is to find the one with minimum weighted sum. Weighted sum is defined as the sum of products of each number in circle by the sequence number of that circle. For instance, the weighted sum in above diagram is [latex]36[/latex] (and also it is the minimum).

Input

The first line of input contains a single integer, the number of test cases. Following, there is one line for each test case. Each test case begins with one integer, [latex]N[/latex] ([latex]3 \leq N \leq 15[/latex]), which is the number of circles. Next [latex]N[/latex] integers are the given numbers to put in circles (all between [latex]1[/latex] and [latex]100[/latex], inclusively).

Output

There should be one line for each test case in output. If there’s no way for building the ring, the word «impossible» should be outputted, or otherwise, a single integer which is the minimum weighted sum.

Tests

 

№
 Inputs Outputs
1
 5
4 1 3 7 9
4 1 1 3 5
15 11 6 2 3 2 14 1 2 10 7 2 2 3 6 2
9 1 1 1 2 2 2 2 2 2
7 1 2 3 4 5 6 7		 36
imposible
396
72
imposible

Code

Solution

We need all permutations of our array and if permutation suits us update [latex]min[/latex] value. To check if number is prime I use Sieve of Eratosthenes. To get all permutation I use recursive function which works in this way:
We accumulate an array in all possible ways. What we do:

  • Fixed empty position in array with a value
  • Remember that we used this value
  • Find all permutations of array with size which is smaller by 1
  • Forget that we used this value (to use it in next permutations)

We stop when we accumulate an array with size we need and check if this permutation suits us(if sum of all triples of this circle are prime). If yes update answer(if it is less than answer). So if we send this solution to server we will get time limit. We need to reduce permutations which do not suit us. To speed up our program we can reduce amount of permutations in this way: if we find out that sum of previous three numbers, which are fixed, is not prime, we do not need to continue this branch of recursion. Really if in our array we found that one sum of three number is not prime we do not need to accumulate this array further. But anyway we get time limit.
Let’s see the differences in complete array where any some of three numbers is prime number.
Input: 8 2 1
Let’s find all suitable permutations:

  1. 8 2 1
  2. 2 8 1
  3. 2 1 8
  4. 1 8 2
  5. 8 1 2
  6. 1 2 8

As you can see first three are different with shifts. Last three are also different with shifts. So we can fix one element find all permutations we need with less by 1 amount of elements and then shift all elements of every array to get all possible permutations which are correct as you can see above (1,2,3) (4,5,6). In the worst case it will work not for [latex]15![/latex] but for [latex]14![/latex]. And now we get Accept.
The complexity is [latex]O(n!)[/latex] Why I did not get time limit at all (because of complexity)? In task said than amount of test which works with [latex]O(n!)[/latex] can be huge. But who will make so many tests? In our case there are near 5 tests in one.

Links

ideone
e-olymp

Related Images:

e-olymp 8357. Точка в многоугольнике

by

7

Задача взята с сайта e-olymp

Условие

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

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

В первой строке заданы три числа: [latex]n (3 \leq n \leq 10^5)[/latex] и координаты точки. Далее в [latex]n[/latex] строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

Вывести строку «YES«, если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

№   Inputs Outputs
1 3 0 0
1 0
0 1
1 1		        NO
2 4 3 2
0 0
1 5
5 5
6 0		       YES
3 8 2 1
0 0
0 4
4 4
4 0
3 0
3 2
1 2
1 0		        NO
4 8 4 3
0 0
0 4
4 4
4 0
3 0
3 2
1 2
1 0		       YES
5 6 1 1
0 0
0 2
1 4
2 2
2 0
1 3		        NO

Код

Решение

Проверять на то, находится ли точка внутри многоугольника, будем так. Берём нашу точку и от нее проводим луч влево параллельно оси абсцисс.
Считаем количество пересечений луча со сторонами многоугольника.
Если количество пересечений чётно, то точка лежит вне многоугольника, а если количество пересечений нечётно, то точка лежит внутри многоугольника.
Нужно еще учесть момент, когда точка лежит на одной из сторон.

  • x0, y0 — координаты нашей точки.
  • xs, ys — координаты самой первой точки, они нам нужны чтобы проверить пересечение луча со стороной, образованной первой и последней точками.
  • xi, yi — координаты точки которую вводим.
  • xt, yt — координаты предыдущей точки, нужны для того, чтобы образовать сторону.
  • par_am — (parity of amount) хранит четность количества пересечений луча со сторонами. Если чётное количество пересечений, то par_am = false, если нечётное, то  par_am = true.
  • on_side — если мы узнали, что точка лежит на одной из сторон, то дальше ничего искать не нужно.

Функция on_edge() рассматривает два случая:

  1. Если сторона параллельна оси [latex]Oy[/latex], посчитаем условие нахождения между минимальной и максимальной [latex]y[/latex]-координатами. Если оно справедливо, проверяем на равенство [latex]x[/latex]-координат.
  2. Для удобства мы подвинет отрезок и точку так чтоб начало отрезка лежало в точке [latex](0,0)[/latex]. После это проверяем находится ли точка по координате [latex]x[/latex] между концов (включительно) отрезка. Остается сравнить тангенс угла между осью [latex]Ox[/latex] и вектором [latex]x_2[/latex] [latex]y_2[/latex]с тангенсом угла между осью [latex]Ox[/latex] и вектором [latex]x[/latex] [latex]y[/latex] и если они равны, то точка [latex]x[/latex] [latex]y[/latex] лежит на отрезке (стороне)  [latex]x_1, y_1, x_2, y_2 [/latex].

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

  1. Лежит ли точка [latex]x_0[/latex] [latex]y_0[/latex] на этой стороне.
  2. Пересекает ли луч сторону.

Чтобы проверить пересекает ли луч сторону делаем:

  1. Проверяем лежат ли две точки по разные стороны луча
  2. Строим уравнение прямой вида [latex]y = kx +b[/latex], проходящее через две точки [latex]x_i, y_i, x_t, y_t [/latex]выглядит оно так:
    [latex]y = \frac{y_i-y_t}{x_i-x_t} \cdot x+(y_i-\frac{y_i-y_t}{x_i-x_t} \cdot x_i )[/latex]
  3. Подставив вместо [latex]y[/latex] [latex]y_0[/latex], получаем что [latex]x[/latex] равен
    [latex]\frac{y_0 \cdot x_i-y_0 \cdot x_t+y_i \cdot x_t-x_i \cdot y_t} {y_i-y_t}[/latex] И он должен быть меньше [latex]x_0[/latex], так как луч направлен влево.

Сложность [latex]O(n)[/latex], где [latex]n[/latex] — количество точек в многоугольнике.

Ссылки

ideone
e-olymp

Related Images:

Proggy-Buggy 2018: Задача A. Шифр Цезаря

by

0

Задание

Багги мнит себя Гаем Юлием Цезарем и любит громогласно его цитировать при каждом удобном случае, выдавая мысли Цезаря за свои. Проги пошутил над Багги и зашифровал в стиле Цезаря список цитат, которыми пользуется Багги. Багги в панике. Если хотите, помогите ему расшифровать известную цитату :

UDMHUHCHUHBH

Напишите программу, которая для вышеприведенного шифртекста выводит соответствующий открытый текст.

Код

Решение

Шифр Цезаря так же известен как шифр сдвига. Каждая буква сдвигается в алфавите на константу влево или вправо по модулю длины алфавита . В нашем случае зашифрованное и расшифрованное сообщение будет состоять только из букв (в условии не сказано ничего про сам алфавит).

Ниже пример шифрования методом сдвига (в данном случае на 3 единицы вправо)

A заменяется на D
B заменяется на E
и так далее
Z заменяется на C

Нам остается только подобрать ключ. Простым перебором получаем что зашифрованное сообщение было получено сдвигом всех букв исходного сообщения на единицу влево.
Ну что еще сказать?
Пришёл, увидел, победил!
Veni, vidi, vici!

Related Images:

e-olymp 8514. Never drink too much!

by

3

The task is taken from e-olymp

Task

Mahmoud together with his friends visited Georgia. They would stay in a hotel at Rustavelli. When the cowboys reached the hotel, they hung their hats in the entrance and settled in. The beer bottles on the table could not escape from Mahmoud’s attention when passing through the corridor. At the suggestion of Mahmoud, all the cowboys began drinking. They drank too much, thus none of them was mindful. Then they decided going downtown. On the way out, everyone had a hat on, but they mixed up the hats as they were so drunk.

The man who is able to have on his own hat while he is drunk is considered clever and who is not able to do so is considered stupid.

You are given the number of cowboys — n (including Mahmoud). You should find in how many ways the cowboys may have on the hats so that all of them are stupid. Two ways are considered different if there is at least one cowboy who has a hat in this case and another hat in the other case.

As the answer may become very large, you should output the result modulo 109 + 7.

Input

Given the number of cowboys — n (1 ≤ n ≤ 107).

Output

The answer to the problem as specified above.

Tests

№
 Inputs Outputs
1
 1 0
2
 4 9
3
 9 133349
4
 555 335132588
5
 10000000 824182295

Code

 

Solution

We have all possible permutations [latex]C_n^0 \cdot n![/latex] , minus one fixed (one of them is not stupid) we get [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)![/latex] but we subtract for minimum fixed pair (two of them are not stupid) we need to add them [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! [/latex] etc.
So the [latex]k[/latex] member is [latex]C_n^k \cdot (n-k)! \cdot (-1)^k[/latex] Let`s find the attitude of [latex]k[/latex] member to the previous one. It`s [latex]-k -1[/latex] The last one will be [latex]-1[/latex] it depends on parity of [latex]n[/latex].
First two are the same ( [latex]n![/latex] ) so we skip them, but in this case we need to check if[latex]n[/latex] equals [latex]1[/latex] And next we make a loop to find the answer by multiplying start value and add it to the answer.
The complexity is [latex]O(n)[/latex]

Links

ideone
e-olymp

Related Images:

e-olymp 2062. Лилавати

by

2

Задача взята с сайта e-olymp

Задача

Крупнейшему индийскому математику XII в. Бхаскаре принадлежит трактат «Сиддханта-широмани» («Венец учения»), переписанный в XIII в. на полосках пальмовых листьев. Этот трактат состоит из четырех частей, из которых «Лилавати» посвящена арифметике, «Биджаганита» — алгебре, остальные две части астрономические. «Лилавати» (что значит «прекрасная») Бхаскара посвятил своей дочери.

Многие свои задачки Бхаскара излагал в поэтической форме, вот одна из них:

Из множества чистейших цветков лотоса
Третья часть была принесена в дар Шиве,
Пятая часть – Вишну, шестая часть – Солнцу;
Четвёртую часть всех цветков получил Бхвани,
А оставшиеся шесть цветков были даны высокочтимому Учителю.

Мы не можем дословно передать всю прелесть и красоту звучания этих стихов Древней Индии, поэтому нашу задачку сформулируем в прозе. Итак, эта же задачка в общем виде: «В дар Шиве принесли A-ую часть цветков лотоса, в дар Вишну – B-ую часть, в дар Солнцу – C-ую часть, для Бхвани досталась D-ая часть и высокочтимый Учитель получил E цветков. Сколько всего цветков лотоса было в распоряжении дарившего?»

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

В первой и единственной строке входных данных заданы через пробел 5 неотрицательных целых чисел: A, B, C, D и E, каждое из которых не превышает 100.

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

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

Тесты

# Входные данные Выходные данные
1 3 5 6 4 6 120
2 8 8 0 4 20 40
3 2 10 20 0 1 -1
4 2 3 20 60 1 -1
5 2 4 8 16 1 16

Код

Решение

Целое это 1, поэтому [latex]1-(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d})=\frac{1}{e}[/latex]

В свою очередь общее количество цветков будет [latex]e\cdot(\frac{a\cdot b\cdot c\cdot d}{a\cdot b\cdot c\cdot d-(b\cdot c\cdot d+a\cdot c\cdot d+a\cdot b\cdot d+a\cdot b\cdot c)})[/latex]

Остается учесть что входные данные могут иметь нули. И в конце проверить чтоб количество цветов принесённых в дар было целым числом для каждого из Богов.

Ссылки

ideone
e-olymp

Related Images:

e-olymp 1610. Зайцы в клетках

by

4

Задача взята с сайта e-olymp

Задача

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

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

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

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] (1 ≤ [latex]n[/latex], [latex]m[/latex] ≤ [latex]\ 10^{9}[/latex]).

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

# Входные данные Выходные данные
1 3 4 2
2 15 144 10
3 1 7 7
4 100 123456 1235
5 222 222 1

Код

Решение

Распределяя всех [latex] m [/latex] зайцев равномерно по клеткам [latex] n [/latex] получаем что максимальное количество зайцев в одной клетке равно [latex]\lceil \frac{m}{n}\rceil[/latex]

Ссылки

ideone
e-olymp

Related Images: