e-olymp 72. Дорога домой

Задача

Бедный Иа

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]\left \langle 1,1 \right \rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.

Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]\left \langle 0,0 \right \rangle[/latex], а его дом расположен в точке [latex]\left \langle x_{h},y_{h} \right \rangle[/latex], и направление движения он менял [latex]k[/latex] раз.

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

В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0\leq n,k,t,v\leq 100)[/latex] . Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5\leq x_{h}, y_{h}\leq 10^5)[/latex] .

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

Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.

Тесты

Входные данные
Выходные данные
[latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex]

 

[latex]5[/latex] [latex]7[/latex]
Good night Ia
[latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex]

 

[latex]15[/latex] [latex]15[/latex]
Good night Ia
[latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex]

 

[latex]105[/latex] [latex]-105[/latex]
Poor Ia
[latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex]

 

[latex]40[/latex] [latex]-20[/latex]
Good night Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]

 

[latex]-24[/latex] [latex]0[/latex]
Poor Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex]

 

[latex]-23[/latex] [latex]0[/latex]
Good night Ia

Первый вариант кода программы

Второй вариант кода программы

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

Вариант 1

Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]\sum\limits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:

[latex]f(x,y) = \begin{cases} \left \langle1 + xy, 1 + xy\right \rangle & \textit{if } x\vdots 4 = 0 \\ \left \langle1 + xy, (-1) \cdot (1 + xy)\right \rangle & \textit{if } x\vdots 4 = 1 \\ \left \langle(-1) \cdot (1 + xy), (-1) \cdot (1 + xy)\right \rangle & \textit{if } x\vdots 4 = 2 \\ \left \langle(-1) \cdot (1 + xy), 1 + xy\right \rangle & \textit{if } x\vdots 4 = 3 \end{cases}[/latex]

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]\sum\limits_{i=0}^k f(i, n)[/latex] — это вектор [latex]\left \langle a,b \right \rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]\left \langle a,b \right \rangle[/latex] и вектора [latex]\left \langle x_{h},y_{h} \right \rangle[/latex]:

$$\sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$

И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]\left \langle 0,0 \right \rangle[/latex] и [latex]\left \langle 1,1 \right \rangle[/latex], то есть — [latex]\sqrt{2}[/latex].

$$ \sqrt{2} tv$$

Итого, выводим Good night Ia, если [latex]2t^2v^2 \geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.

Вариант 2

Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = \displaystyle\frac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$

Для направления на северо-восток:
$$a_1 = 1, d = 4n \Rightarrow S_{1}=\frac{1 + 1 +4n(m_1-1)}{2}\Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=1$ иначе, $m_1=\displaystyle\frac{k+1}{4}$

Для направления на юго-восток:
$$a_2 = 1+n, d = 4n \Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=2$ иначе, $m_2=\displaystyle\frac{k+1}{4}$

Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n \Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=3$ иначе, $m_3=\displaystyle\frac{k+1}{4}$

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n \Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = \displaystyle\frac{k+1}{4} + 1,$ если$ (k+1)\vdots 4 >=4$ иначе, $m_4=\displaystyle\frac{k+1}{4}$

Тогда, для вычисления координат [latex]\left \langle x,y \right \rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.

Ссылки

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

e-olymp 6128. Простой дек

Задача. Простой дек

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back 

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front
  • pop_back
  • front
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

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

 push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

 ok

ok

2

ok

ok

1

ok

1

2

1

1

0

bye

 2  size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

0

ok

ok

2

4

8

ok

4

8

3

8

bye

Решение

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

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

 

A274. Среднее арифметическое всех членов последовательности, кроме одного

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ 20 }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,20).

Обобщим задачу для последовательности длины [latex]n[/latex]
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Входные данные:
Последовательность действительных чисел.

Выходные данные:
[latex]n[/latex] чисел, [latex]i[/latex]-ое из которых является средним арифметическим всех членов последовательности, кроме [latex]i[/latex]-го ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Тесты

Входные данные Выходные данные
1 4 The sequence must consist of at least two elements.
2 1 0 1 The arithmetic average of all elements of this series except the element №i is:
for i = 1: 0.5
for i = 2: 1
for i = 3: 0.5
3 10.1 2.4 11.3 0.8 The arithmetic average of all elements of this series except the element №i is:
for i = 1: 4.8(3)
for i = 2: 7.4
for i = 3: 4.4(3)
for i = 4: 7.9(3)
4 2.5 -1.5 4 -9 1.22 The arithmetic average of all elements of this series except the element №i is:
for i = 1: -1.32
for i = 2: -0.32
for i = 3: -1.695
for i = 4: 1.555
for i = 5: -1

Код на C++

Код на Java

Решение
Для начала, в первом цикле мы читаем числа из входного потока, помещаем их в вектор a и прибавляем к переменной sum, предназначенной для хранения суммы всех чисел последовательности. Последовательность должна состоять как минимум из двух элементов. Чтобы получить среднее арифметическое всех её членов, кроме [latex]i[/latex]-го, достаточно отнять [latex]i[/latex]-й элемент вектора a от значения переменной sum и разделить результат на количество членов такой неполной последовательности, а оно будет на единицу меньше размера вектора a. Таким образом заполняется вектор b, в котором хранятся элементы последовательности [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], после чего требуемая последовательность выводится.

Код на ideone.com (C++)
Код на ideone.com (Java)
Условие задачи (с.118)

Монстр

Задача 787A с сайта codeforces.com.

Задача

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, ….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод

Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).

Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).

Вывод

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или  - 1, если они никогда не закричат одновременно.

Тесты

Ввод
Вывод
20 2
9 19
82
2 1
16 12
-1

Код

Решение

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

Код Хаффмана

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

  1. Код графа на языке DOT, иллюстрирующий кодирование символов строки;
  2. Символы строки и соответствующие им коды Хаффмана;
  3. Закодированную строку.

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

Некоторая последовательность символов и endl.

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

  1. Код графа на языке DOT, иллюстрирующий кодирование символов строки;
  2. Символы строки и соответствующие им коды Хаффмана;
  3. Закодированная строка.

Тест

Входные данные Выходные данные
MOLOKO KIPIT digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

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

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

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

После этого, используя поиск в глубину, кодируем элементы массива tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.

Ссылки

A327. Простые числа

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].

Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].

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

Тесты.

Входные данные Выходные данные
[latex]a[/latex] [latex]b[/latex] [latex]p[/latex]
1 1 4 2, 3
2 0 1 Not found
3 5 5 5
4 6 20 7, 11, 13, 17, 19

Код программы (C++).

Код программы (Java).

Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java.
Условие задачи (с.135)