e-olymp 8530. Печать матрицы

Задача

Условие

Задана матрица $n \cdot n$ — назовем ее $[1..n] \cdot [1..n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1..r] \cdot [1..c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \cdot n$. Последняя строка содержит два числа $r$ и $c$ $(1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \cdot c$.

Тесты

Входные данные Выходные данные
1 4
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
3 2
1 2
5 6
9 1
2 5
18 25 34 44 -43
54 65 75 85 -32
95 15 25 35 -3
-4 15 -6 37 0
44 43 23 3 -12
4 3
18 25 34
54 65 75
95 15 25
-4 15 -6
3 2
0 -1
23 69
1 1
0
4 3
1 2 3
-4 -5 -6
7 8 9
3 1
1
-4
7

Решение

Для решения данной задачи необходимо ввести в массив все имеющиеся данные и вывести необходимые, соответственно заданным параметрам. Можно использовать как одномерные массивы, так и двухмерные.
В реализации с одномерными вводим все данные в массив $n \cdot n$, а затем выводим, используя вложенные циклы. Цикл проходит от $0$ до $r$ и от $(j \cdot n)$ — первого элемент необходимой строки до $(c + j \cdot n)$ — последнего элемента. В реализации с двумерными массивами заводим все данные в один массив и после выводим необходимые.

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

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

Ссылки

e-olymp 7504. Три прямоугольника

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

Задача

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

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

Одно число — количество закрашенных клеток

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

В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 0 1 1
1 1 2 2
0 0 2 2
4
2 2 -2 -2 2
-1 -1 1 1
40 40 41 41
17
3 -1 2 2 -1
1 0 4 2
1 0 3 6
21
4 -100 -100 -99 -99
100 100 99 99
-100 -100 100 100
40000
5 3 0 4 1
1 0 3 3
1 0 3 3
7

Решение

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

Для нахождения пересечения прямоугольников рассмотрим проекции координат прямоугольника на координатные оси $x$ и $y$. В случае, если интервалы пересекаются, началом пересечения будет наибольшее из начал интервалов, а концом —  наименьшее из их концов. В ином же случае дадим точкам по этой координате одинаковые значения, в результате чего площадь такого прямоугольника и всех пересечений, которые он образует будет равна нулю. Координатами точек пересечения прямоугольников будут, следовательно, соответствующие координаты пересечения интервалов на осях.

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

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

Решение. Многомерные массивы

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

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

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

e-olymp 4751. Диагонали

Задача

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

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

Вводится число [latex]n (1 \le n \le 500)[/latex], а затем матрица [latex] n × n [/latex]. Элементы матрицы — числа по модулю не больше [latex]10^5[/latex].

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

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

Вывести сумму чисел сначала на главной, а затем на побочной диагонали.

Тесты

Вход Выход
4
134 475 30 424
303 151 419 235
248 166 90 42
318 237 184 36
411 1327
7
-59 21 7 5 12 868 -565
32 19 52 3 7 11 0
3 -123 -52 -99 -857 -4621 -561
11 232 86 652 46 3244 572
857 -1242 -6767 923 -575 12 1
552 232 2 63 -76 23 0
12 34 87 20 -7 767 959
967 -7282
3
1 45 82
96 29 90
757 23 12
42 868
2
12 32
99 71
83 131
5
12 32 54 76 12
95 23 21 123 0
65 32 1 773 992
5 32 155 866 912
134 44 74 11 23
36 136

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

Решение

Создаем динамический массив.

Чтобы найти сумму главной диагонали берём, лишь те элементы массива, в которых номер строки и столбца равны.

Чтобы просуммировать побочную диагональ, используем цикл в котором используем элементы массива начиная с первого столбца и последней строки и движемся к  противоположному (первая строка, последний столбец).

Ссылки

e-olymp

ideone

 

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

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

Задача

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

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

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

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

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
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 3 4
1 2 3
3 5 2
7 1 6
9 8 3
2.00 3.00 6.00 8.00
3 10 2
1 2 3 4 5 6 7 8 9 10
1 1 1 2 2 2 3 3 3 4
5.50 2.50

Код программы (Потоковая обработка)

Решение

Читая каждую оценку:

  1. Добавляем оценку к общей сумме;
  2. Если введенная оценка равна минимальной, то добавляем ее к сумме минимальных и увеличиваем счётчик количества минимальных.
  3. Если введенная оценка меньше минимальной, то минимальной становится введённая оценка. Счетчик количества минимальных равен [latex]1.[/latex] Сумма минимальных равна введённой оценке.
  4. Если введенная оценка равна максимальной, то добавляем ее к сумме максимальных и увеличиваем счётчик количества максимальных.
  5. Если введенная оценка больше максимальной, то максимальной становится введённая оценка. Счетчик количества максимальных равен [latex]1.[/latex] Сумма максимальных равна введённой оценке.

Тогда после введения всех [latex]n[/latex] оценок имеем:

  •  [latex]sumMax[/latex] — сумма максимальных оценок.
  •  [latex]sumMin[/latex] — сумма минимальных оценок.
  •  [latex]countMax[/latex] — количество максимальных оценок.
  •  [latex]countMin[/latex] — количество минимальных оценок.
  •  [latex]sumGl[/latex] — общая сумма оценок.

Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу:  [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]

Код программы (Массивы)

Решение

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

Ссылки

Условие задачи на e-olymp

Код программы на ideone (Потоковая обработка)

Код программы на ideone (Массивы)

e-olymp 8361. Робот

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

Условие

Движение робота управляется программой. Программа состоит из следующих команд:

  • [latex]S[/latex] — сделать шаг вперед
  • [latex]L[/latex] — повернуться на [latex]90°[/latex] влево
  • [latex]R[/latex] — повернуться на [latex]90°[/latex]вправо

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

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

Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].

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

Выведите одно число, количество шагов, которое будет сделано (то есть выполнено команд [latex]S[/latex]) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите число [latex]-1[/latex].

Тесты

Inputs Outputs
1 SSLSLSLSSRSRS 5
2 LSSSS -1
3 LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS 15
4 LLLLLLLL -1
5 SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL 7

Код

Решение

Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».

Ссылки

e-olymp 458. Черно-белая графика

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «ИЛИ» эта таблица выглядит так.

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

Входные данные Выходные данные
 1 5 3
01000
11110
01000
10110
00010
10110
0110
11110
11100
11110
2 2 3
010
111
000
101
1010
11
10
10
3 4 4
1111
0101
0000
1110
0011
0101
0111
1111
0011
1111
0101
0000
1110
4 3 6
100011
000111
000000
111011
001100
010101
1000
000
100
110
000
101
010

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

( использован одномерный массив)

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

(использован двумерный массив)

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

e-olymp 5090. На перекрёстке

Задача

Есть таблица $n × n.$ Оживленностью строки или столбца назовем сумму чисел в ней. Нам очень хочется определить число на перекрестке самой оживленной строки и самого неоживленного столбца. Причем, чем выше будет этот перекресток (а среди них – чем левее), тем больше будет вероятность прохождения теста.

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

В первой строке находится число $n (1 \leq n  \leq 100).$ В следующих $n$ строчках задана таблица. Числа в таблице натуральные и не превышают $100000.$

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

Выведите число на перекрестке самой оживленной строки и самого неоживленного столбца.

Тесты

Входные данные Выходные данные
1 2
4 3
2 1
3
2 3
1 1 1
1 1 1
1 1 1
1
3 5
13 15 17 2 9
4 56 8 90 0
4 3 5 7 5
23 4 5 71 4
5 6 7 8 10
0
4 4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1

Код

С помощью одномерного массива

С помощью двумерного массива

Решение

Для решения данной задачи используем двумерный массив размера $n \times n$. С помощью цикла for ищем самую оживленную строку, затем самый неоживленный столбец, и выводим элемент таблицы на их перекрёстке.
Для решения с помощью одномерного массива действуем аналогично, работая с массивом длинны $n^2$, используя следующее соответствие: $x[i][j] \sim x[i \cdot n + j]$

Ссылки

  • С помощью одномерного массива
  • С помощью двумерного массива

e-olymp 31. Суеверный Дед Мороз

Задача

Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны — развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза «Пятница 13».

Сколько дней Дед Мороз не развозил подарки во время своего дежурства?

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

В первой строке задано количество смен $k$ дежурства Деда Мороза.

Далее в k строках указаны года $a$ и $b$ ($1920 ≤ a ≤ b ≤ 2050$ по григорианскому календарю), попадающие на очередную смену.

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

Вывести количество дней, когда Дед Мороз не будет развозить подарки.

Тесты

Ввод Вывод
1 2
1999 2000
1991 1997
13
2 3
1939 1945
1937 1938
1953 1964
37
3 3
1993 1996
2007 2017
1979 1981
32
4 4
1997 1999
1967 1972
2032 2032
1930 1933
24
5 4
1959 1960
1965 1966
1991 2011
1947 1959
63

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

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

Сперва стоит сказать, что полный цикл чередования лет с пятницей 13 в одни и те же месяца — 28 лет. Всего в году их может быть от 1 до 3. Всего в этих 28 годах будут 4 года с тремя пятницами 13 и по 12 с одной и двумя.
Все решение задачи сводится сводится к тому, чтобы посчитать количество пятниц 13 в каждом году данного нам отрезка времени. Создадим два массива — c2 и c3 — каждый будет содержать остатки от деления лет, содержащих 2 и 3 пятницы 13 соответсвенно, на 28. Все прочие остатки от деления «достанутся» годам, в которых 1 пятница 13; отдельный массив для них, очевидно, смысла создавать нет.
Сначала, по условию, вводим число смен и после в цикле года очередной смены. Для каждого года из отдельной смены считаем количество пятниц 13 путём проверки в соответствующих массивах остатка от деления этого года на 28. Если его нет в двух массивах, то, очевидно, в этом году всего одна пятница 13 и мы прибавляем к счетчику пятниц counter 1. Если все-таки есть, то прибавляем 2 или 3 в зависимости от того, в каком массиве нашлось необходимое число. В конце выводим значение счётчика.
Отметим, что задача решается и без использования массивов, но в таком случае придётся проверить остаток от деления каждого года на 28 на равенство числам, которые в данном случае находятся в массивах.

Ссылки

код на ideone
условие задачи на e-olymp

e-olymp 5282. Седловые точки

Задача. Седловые точки

Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.

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

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

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

Выведите количество седловых точек.

Тесты

Ввод Вывод
1 2 2
0 0
0 0
4
2 2 2
1 2
3 4
1
3 5 5
100 -100 100 1000 110
10 -1000 100 -1000 110
100 -1000 100 100 110
1000 -1000 1000 1000 100
1000 -1000 1000 1000 -1000
1
4 4 4
1000 1000 100 100
1000 1000 1000 1000
100 100 100 1000
100 1000 1000 1000
4
5 2 3
1 -1 1
0 -1 0
2
6 5 1
-1
0
-1
0
-1
2
7 4 2
1 2
-2 1
-1 2
-2 -1
1
8 3 3
5 1 3
3 1 2
1 1 2
3
7 3 3
5 2 3
3 4 2
1 8 2
0

Решение

Чтобы посчитать количество седловых точек, нужно посчитать совпадения минимумов в каждой строке и максимумов в каждом столбце матрицы.

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

e-olymp 8515. Homo or Hetero?

Task

Consider a list of numbers with two operations:
$\cdot$ insert number— adds the specified number to the end of the list.
$\cdot$ delete number— removes the first occurrence of the specified number from the list. If the list does not contain the number specified, no changes are performed.

For example: the result of the insertion of a number $4$ to the list $[1,2,1]$ is the list $[1,2,1,4]$. If we delete the number $1$ from this list, we get the list $[2,1,4]$, but if we delete the number $3$ from the list $[1,2,1,4]$,the list stays unchanged.

The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list $[2,2]$ is homogeneous, the list $[2,1,4]$ is heterogeneous, the list $[1,2,1,4]$ is both, and the empty list is neither homogeneous, nor heterogeneous.

Write a program that handles a number of the operations insert and delete on the empty list and determines list’s homogeneity and heterogeneity after each operation.

Input

The first line of the input file contains an integer number $N$ $(1 \leq N \leq 10^{5})$ — the number of operations to handle. Following $N$ lines contain one operation description each. The operation description consists of a word “insert” or “delete”, followed by an integer number $K$ $(-10^{9} \leq K \leq 10^{9})$ — the operation argument.

Output

For each operation output a line, containing a single word, describing the state of the list after the operation:

$\cdot$ “both” — if the list is both homogeneous and heterogeneous.
$\cdot$ “homo” — if the list is homogeneous, but not heterogeneous.
$\cdot$ “hetero” — if the list is heterogeneous, but not homogeneous.
$\cdot$ “neither” — if the list is neither homogeneous nor heterogeneous.

Tests

# Input Output
1 11
$insert$ 1
$insert$ 2
$insert$ 1
$insert$ 4
$delete$ 1
$delete$ 3
$delete$ 2
$delete$ 1
$insert$ 4
$delete$ 4
$delete$ 4
$neither$
$hetero$
$both$
$both$
$hetero$
$hetero$
$hetero$
$neither$
$homo$
$neither$
$neither$
2 15
$insert$ -50
$insert$ -2
$insert$ 1
$insert$ 4
$delete$ 1
$delete$ 3
$delete$ -2
$delete$ -50
$insert$ 4
$delete$ 4
$delete$ 4
$insert$ 100
$insert$ -150
$delete$ -150
$delete$ 100
$neither$
$hetero$
$hetero$
$hetero$
$hetero$
$hetero$
$hetero$
$neither$
$homo$
$neither$
$neither$
$neither$
$hetero$
$neither$
$neither$

Code 1

Code 2 (map)

Solution

Let’s memorize two numbers on each step: how many of different numbers and different pairs of identical numbers in a one-dimensional array. If there are more than one different numbers in the array and more than zero different pairs of the same numbers, then print "both". If the sum of different numbers in the array is less than two and different pairs of identical numbers are more than zero, then we enter "homo". If there are more than one different numbers in the array and less than one different pairs of the same numbers, then enter "hetero". In other cases, we enter "neither". In the last case, when an array is $0$ numbers or $1$ number.

Links

e-olymp 8374. Нечетное количество раз

Задача 

Найдите число, которое встречается в последовательности нечетное количество раз.

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

Первая строка содержит натуральное число $n (n < 500000)$. Далее следуют $n$ натуральных чисел, каждое из которых меньше $10^6$.

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

Во входной последовательности только одно число $x$ повторяется нечетное количество раз. Другие числа повторяются четное число раз. Выведите $x$.

Замечание

В условии задачи на e-olymp опечатка, но, проанализировав входные и выходные данные примеров, несложно понять суть задачи. 

Тесты

Ввод Вывод
1 9
3 1 2 2 17 1 3 17 3
3
2 5
12 13 14 13 12
14
3 3
20 0 20
0
4 15
5 7 1 2 3 5 7 2 7 5 1 2 3 5 2
7
5 11
10 100 1000 100 100 100 1000 10 100 1000 100
1000

Код 1

Код 2

Код 3 (без массива)

 

Решение

Для начала создадим динамический одномерный массив и считаем с потока ввода все его элементы. Конечно, можно было создать статический массив на 500000 элементов, но, скорее всего, памяти выделилось бы намного больше, чем было бы использовано.

Первый способ

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

Затем, заведём две переменные: счётчик и число. Последней присваиваем значение первого элемента массива. Сравниваем следующий элемент с тем, что лежит в переменной. Если они равны, увеличиваем счетчик. В счетчик с самого начала положим единицу, так как предполагаем, что в массиве есть хоть один элемент.

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

Второй способ

Применим исключающее «или» ко всем элементам массива. Предварительно создадим переменную равную нулю, в которой будем это проделывать. 

Так как xor двух одинаковых чисел равен нулю, то для любого количества пар одинаковых чисел он будет  равен нулю. А вот xor нуля и любого числа равен самому числу.

Таким образом, исключив все пары одинаковых чисел, наша переменная примет значение повторяющегося нечетное количество раз числа. 

Третий способ 

Идейно такой же как предыдущий. Отличается только тем, что мы не записываем числа в массив, а исключающее «или» работает сразу после того как число было прочитано.

Ссылки

Задача 8374 на e-olymp

Код 1 на Ideone

Код 2 на Ideone

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

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные
3 0 0
1 0
0 1
1 1
NO
4 3 2
0 0
1 5
5 5
6 0
YES
3 5 6
2 3
8 0
-1 -3
NO
4 -2 3
0 0
5 0
0 6
3 3
NO
5 3 1
9 2
3 0
-2 -4
-4 0
-4 5
YES

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

Решение

Задача сводится к поиску площадей. Считаю площадь треугольника, образующегося тремя последовательными точками многоугольника. Далее считаю площади треугольников которые заданная точка образует с каждой парой точек из этой пары. Если площадь первого треугольника равна сумме площадей этих, то точка находится в треугольнике, а следовательно и в многоугольнике. Если нет перехожу к следующей тройке точек. Если точка не принадлежит ни одному треугольнику, то точка находится вне многоугольника.

Ссылки

e-olymp 8529. Преобразование Капрекара

Задача

Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число $x$. Пусть $M$ — наибольшее число, которое можно получить из $x$ перестановкой его цифр, а $m$ — наименьшее число (это число может содержать ведущие нули). Обозначим как $K(x)$ разность $M$ — $m$, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в $x$.

Например $K(100) = 100 — 001 = 099$, $K(2414) = 4421 — 1244 = 3177$.

Капрекар доказал, что если начать с некоторого четырехзначного числа $x$, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять $K(x)$, $K(K(x))$, . . . ), то рано или поздно получится число $6174$. Для него верно равенство $K(6174) = 7641 — 1467 = 6174$, поэтому на нем процесс зациклится.

Ваша задача состоит в том, чтобы написать программу, вычисляющую $K(x)$ по числу $x.$

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

Одно целое число без ведущих нулей $x$ ($1$ ≤ $x$ ≤ $10^9$).

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

Выведите $K(x)$.

Тесты

Входные данные Выходные данные
100 099
1000000000 0999999999
2414 3177
6174 6174
5 0
7272 5445
142857 750843
495 495
55 00
56 09
554 099
12345 41976

 

Решение

Объяснение

Поскольку нужно находить минимальную и максимальную комбинацию из цифр числа, удобно в самом начале записать это число в виде массива и отсортировать. Далее найти, собственно, искомые числа, и получить из них само $K(x)$. Потом остаётся проверить количество цифр и вывести, при недостатке, соответствующее количество нулей.

Код на ideone
Зачтено на e-olymp

e-olymp 2501. Круговая диаграмма

Задача


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

Исходными данными для этой диаграммы является набор чисел $a_1,\ldots, a_n, а$ диаграмма представляет собой круг радиуса $r$, разделенный на секторы. При этом каждому из чисел соответствует ровно один сектор, площадь которого пропорциональна этому числу. Общая площадь секторов равна площади круга.

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

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

Первая строка содержит два целых числа $n$ и $r \space (1 \leq n, r \leq 100)$. Вторая строка содержит $n$ целых чисел $a_1,\ldots, a_n \space (1 \leq a_i \leq 100$ для всех $i$ от $1$ до $n)$.

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

Выведите $n$ вещественных чисел — площади секторов, соответствующих числам $a_1,\ldots, a_n$. Выводите каждое из чисел в отдельной строке.

Все эти числа должны быть выведены с точностью не хуже $10^{-6}$.

Тесты

Входные данные Выходные данные
3 2
1 4 3
1.570796327
6.283185307
4.712388980
2 3
3 8
7.711181968
20.563151914
4 5
2 5 9 1
9.239978393
23.099945982
41.579902768
4.619989196
5 9
4 16 8 20 11
17.252135928
69.008543713
34.504271856
86.260679641
47.443373803

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

Решение

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

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

e-olymp 54. Мурзик

Задача

Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является исключением! Но если он чрезвычайно активен днем – то точно так же крепко спит ночью. Причем несчастный хищник видит преимущественно кошмары…

Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [latex]N[/latex] команд по [latex]K[/latex] крыс в каждой. Соревнования проводятся в [latex]К[/latex] раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.

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

Первая строка содержит два целых числа [latex]N[/latex] и [latex]K[/latex] [latex](0 < N ≤ 20, 0 < K ≤ 100000)[/latex]. Следующие [latex]K[/latex] строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.

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

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

Тесты

# Входные данные Выходные данные
1 3 3
20 10 30
15 20 20
30 30 20
3
2 3 3
20 -10 -30
15 25 20
30 -30 20
1
1 3 3
0 -10 -30
15 25 20
30 -30 20
2

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

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

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

Ссылки

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

e-olymp 634. Вклад «Антикризисный»

Задача

Постоянные клиенты одного очень крупного банка (ООКБ) недавно получили возможность открыть новый вклад — «Антикризисный». Этот вклад отличается непростой схемой начисления процентов, поэтому вам, как единственному сотруднику ИТ-отдела банка, было поручено написание программы, которая будет вычислять сумму вклада с начисленными процентами.

Вклад «Антикризисный» может быть открыт на любой срок, но дата окончания вклада должна быть не позже $31$ декабря $2009$ года, процентная ставка по вкладу составляет $p$ процентов годовых. Это означает, что если в начале некоторого периода в $d$ дней, в течение которого сумма вклада не менялась, сумма вклада составляла $x$ рублей, то по окончании этого периода она будет составлять $x\cdot\left(1+\frac{p}{100}\cdot\frac{d}{365}\right)$.

Начисление процентов на вклад осуществляется ежемесячно, в последний день месяца (или в последний день действия вклада), при этом сумма процентов присоединяется ко вкладу. Таким образом, если на первое мая сумма вклада составляла $x$ рублей, то $31$ мая ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)$ рублей, и на первое июня сумма вклада составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)\right)$, а в июне проценты будут начисляться уже на эту сумму.

Если же последний день вклада был $20$ мая, то в этот день ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)$ рублей, а сумма вклада, которую получит клиент банка составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)\right)$. Аналогично выполняются расчеты и для случая, когда вклад был открыт не в первый день месяца. Так, например, если вклад был открыт $18$ февраля, то $28$ февраля к сумме вклада будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{11}{365}\right)$ рублей, а если же он был открыт $28$ февраля, то в тот же день $28$ февраля к сумме будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{1}{365}\right)$ рублей.

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

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

Первая строка входного файла содержит три целых числа: исходную сумму вклада $x$, процентную ставку $p$ и длительность вклада $d \left(1 ≤ x ≤ 100000, 1 ≤ p ≤ 200, 1 ≤ d ≤ 365\right)$. Вторая строка входного файла содержит дату открытия вклада в формате «день-месяц-год». День и месяц обозначаются числами, при этом у чисел, меньших десяти, присутствуют ведущие нули. Гарантируется,что вклад открыт в $2009$ году, и дата его окончания также находится в $2009$ году.

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

В выходной файл выведите ответ на задачу c точностью $6$ знаков после десятичной точки.

Тесты

# Входные данные Выходные данные
1 1000 10 27
18-07-2009
1007.410921
2 1000 12 70
29-06-2009
1023.172779
3 1000 12 37
17-08-2009
1012.200053
4 1000 15 37
21-10-2009
1015.253781
5 1000 15 85
12-08-2009
1035.351224

Код

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

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

Ссылки

Условие задачи на e-olymp
Код решения на ideone

e-olymp 50. Разрезанное число

Задача

Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.

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

В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$

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

Количество разных чисел.

Тесты

Входные данные Выходные данные
$5$ $3$
$13$
$85$
$45$
$4$
$11$ $2$
$1$
$111$
$1$
$11$ $3$
$11$
$8$
$11$
$0$
$71$ $8$
$4018916609$
$7495223237$
$3405637482$
$3166003637$
$8998228133$
$1141886496$
$9124347310$
$7736090711$
$584$

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

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

Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 47. Паркет из треугольников

Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

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

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

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

Искомое количество шагов.

Тесты

# Входные данные Выходные данные
1 5 4
25 38
5
2 5 4
6 22
4
3 5 4
15 22
3
4 3 2
1 12
7
5 3 2
6 12
2

Код 1

Код 2

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

Способ 1

Каждый элемент имеет три параметра:

  1. Положение в строке
  2. Положение в столбце
  3. Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

  1. Оба элемента расположены в одной строке строке
  2. Оба элемента расположены в одном столбце
  3. Оба элемента расположены на одной диагонали
  4. Произвольное расположение

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

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

Для более оптимальной работы были использованы тернарные операции. Они скрывают под собой условие, выполнение которого состоит из одной строки кода.

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

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

стояло количество шагов, совершенных в ходе решения.

Ссылки

Задача на e-olymp

Код задачи на ideone ( способ 1 )

Код задачи на ideone ( способ 2 )

e-olymp 2670.Координаты соседей

Задача

Для клетки с координатами $\left(x, y\right)$ в таблице размером $M\times N$ выведите координаты ее соседей. Соседними называются клетки, имеющие общую сторону.

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

Даны натуральные числа $M, N, x, y \left(1 \leqslant x \leqslant M \leqslant 109, 1 \leqslant y \leqslant N \leqslant 109\right).$

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

В выходной файл выведите пары координат соседей этой клетки в произвольном порядке.

Тесты

Входные данные Выходные данные
3 3
2 2
1 2
2 1
2 3
3 2
23 23
21 13
20 13
22 13
21 12
21 14
11 8
10 5
9 5
11 5
10 4
10 6

Код решения

Решение

Для решения этой задачи стоит просмотреть все варианты координат соседних точек. То есть, нужно прибавить единицу к абсциссам и ординатам заданной точки. Но стоит учесть, что таблица у нас ограничена: $1 \leqslant x \leqslant M, 1 \leqslant y \leqslant N$

Ссылки

Условие решения на e-olymp.com
Код решения на ideone.com