e-olymp 94. Problem of prime numbers!

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

Mif 17.16

Условие

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

grph

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

Тестирование

Входные данные Выходные данные
1 0 0 Yes
2 -6 0 Yes
3 5.0 -2.0 Yes
4 -3.33 -5 No
5 0.12345 0.54321 No

Код

Решение

В основе заданной фигуры лежит круг с радиусом [latex]6[/latex] и центром в начале системы координат [latex](0, 0)[/latex], из которого исключена первая четверть. Таким образом, нам нужно удостовериться, что положение заданной точки одновременно удовлетворяет следующим условиям:

  • точка расположена в пределах круга, то есть сумма квадратов координат [latex]x^2+y^2[/latex] меньше или равна квадрату радиуса [latex]6^2=36[/latex];
  • хотя бы одна из координат точки [latex](x, y)[/latex] не превышает значения [latex]0[/latex] (другими словами, точка не лежит в первой четверти).

Если оба условия соблюдены, точка принадлежит фигуре. В противном же случае — нет. Такую проверку и последующий вывод ответа можно записать с помощью единственной тернарной операции:

Ссылки

Код программы на Ideone.com;

Уравнение окружности;

Список задач на ветвления.

ML19

Задача. Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.

Тесты

Длина окружности Точность  Результат работы программы
0 3 Невозможно выполнить для вырожденной окружности
-1 8 Ошибка ввода данных
34 -5 Ошибка ввода данных
25 18 Вывод с заданной точностью невозможен. Максимально возможная точность 13
25 13 49.7359197162173
83 5 548.20920
113.42 3 1 023.692
12 345 678 3 Вывод с заданной точностью невозможен. Максимально возможная точность 1
12 345 678 1 12 128 861 224 697.9
1 000 000 000 0 Число содержит больше 15 значащих цифр. Точный вывод невозможен

Алгоритм

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

Для удобства преобразуем известные нам формулы:

[latex]L = 2 \pi \cdot R[/latex]   [latex]S = \pi \cdot R^2 [/latex]  [latex] \longrightarrow[/latex]  [latex]R= \frac{L}{2\pi}[/latex]  [latex]\longrightarrow[/latex]  [latex]S = \frac{L^2}{4\pi}[/latex];

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

  1. Находим значение переменной possibleAccuracy как разность между максимально возможным количеством значащих цифр (maxAccuracy = [latex]15[/latex]) и имеющемся в данном числе .
  2. Отрицательное значение переменной possibleAccuracy сигнализирует о том, что найденная площадь круга превышает [latex] 10^{15} [/latex]. Следовательно, выводим предупреждение о том, что точный подсчет невозможен даже с нулевой точностью после запятой.
  3. При условии, что запрашиваемая точность превышает максимальную, выводим уведомление и значение максимальной точности.
  4. При ложности  пункта 2 и 3, используя манипулятор setprecision, выводим нужное количество знаков.

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

 

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

Ю2.7

Задача.

Треугольник и круги.

Лежит ли заданный  на плоскости треугольник АВС в области пересечения заданных кругов:

[latex](x-a1)^2+(y-b1)^2<r1^2[/latex] , и [latex](x-a2)^2+(y-b2)^2<r2^2[/latex]  ?

Ссылка на программу на С++: http://ideone.com/NYTAWN

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

Ссылка на программу на Java:http: //ideone.com/QZ7RB1

Решение:

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

Тест

a1 b1 r1 a2 b2 r2 ax bx cx ay by cy Принадлежит?
1 2 3 3 4 5 6 7 8 6 7 4 нет
1 2 15 3 4 12 6 7 8 6 7 4 да
7 5 10 4 6 16 6 7 3 5 6 7 да
7 5 5 4 6 3 6 7 3 5 6 7 нет

 

Ю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:

 

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