e-olymp 333. Детская железная дорога-2

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задача

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

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

Сколько всего разных слов может быть в таком необычном «английском» словаре Витэка?

Тесты

Входные данные
Выходные данные
ALPHABET 35
AAAA 4
UNIVERSITY

54
ABABABABC

24

Код

Решение

Казалось бы, задачу можно решить простым циклом. Ведь в 6-буквенном слове: 6 однобуквенных слов, 5 двубуквенных и т.д. Однако очевидной становится проблема повторения,причем не только повторений букв, но и повторений подстрок, что изрядно усложняет наше решение. Создадим вектор, состоящий из строк, куда мы будем добавлять все подстроки строки из входного потока. Отсортируем полученный вектор. Это нужно для того чтобы одинаковые элементы шли рядом с друг другом. Тогда мы можем использовать функцию unique(), которая удалит из вектора все повторяющиеся элементы, кроме одного. Для того, чтобы провести resize() вектора нам понадобится итератор, который мы приравняем к функции unique(). После resize() останется только вывести размер вектора и прибавить к нему единицу, так как само слово не является подстрокой.

Ссылки

1.Код на ideone

2.Условие на e-olymp

A272. Количество осадков

Задача

Даны действительные числа [latex]a_{1}, a_{2}, …, a_{n}[/latex] – количество осадков (в миллиметрах), выпавших в Москве в течение [latex]n[/latex] лет. Вычислить среднее количество осадков [latex]average[/latex] и отклонение от среднего для каждого года [latex]d_{1}, d_{2}, …, d_{n}[/latex].

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

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

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

Среднее количество осадков [latex]average[/latex].
Последовательность действительных чисел [latex]d_{1}, d_{2}, …, d_{n}[/latex] — отклонение от среднего.

Тесты

 №  Входные данные  Выходные данные
 1  0 0 0 0 0 0 1 0 0 0  0.1
0.1 0.1 0.1 0.1 0.1 0.1 0.9 0.1 0.1 0.1
 2  1.23 2.34 3.45 4.56 5.67  3.45
2.22 1.11 0 1.11 2.22
 3  234.109 4655.15 43.629 14.109  1236.75
1002.64 3418.4 1193.12 1222.64
 4  5 5 5 5 5 5  5
0 0 0 0 0 0

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

Решение

В цикле считываем числа из входного потока и прибавляем их к переменной [latex]average[/latex] (изначально [latex]average=0[/latex]), а также помещаем их в вектор [latex]v[/latex]. Далее делим [latex]average[/latex] на количество элементов в векторе, таким образом получим среднее количество осадков. Затем при помощи цикла поочередно будем выводить отклонение от среднего количества осадков для каждого года. Отклонением от среднего будет абсолютная величина разности соответствующего элемента вектора [latex]v[/latex] и среднего значения [latex]average[/latex].

Ссылки

А273. Центр тяжести системы

Задача. Задача из сборника задач по программированию С.А.Абрамова за 2000 год.
Система из 25 материальных точек в пространстве задана с помощью последовательности действительных чисел [latex]x_{1}, y_{1}, z_{1}, p_{1}, x_{2}, y_{2}, z_{2}, p_{2},\ldots,x_{25}, y_{25}, z_{25}, p_{25}[/latex], где [latex]x_{i}, y_{i}, z_{i}[/latex] — координаты [latex]i[/latex]-ой точки, а [latex]p_{i}[/latex] — ее вес ([latex]i=1,2,\ldots,25[/latex]). Получить координаты центра тяжести системы, а также расстояние от центра тяжести до всех точек системы.

Входные данные:
[latex]x, y, z, p[/latex] — координаты и вес точки.

Выходные данные:
[latex]sum(x,y,z)[/latex] — координаты центра тяжести системы, [latex]l[/latex] — расстояние от центра тяжести до одной из точек.

Тесты:

Входные данные Выходные данные
[latex]x[/latex] [latex]y[/latex] [latex]z[/latex] [latex]p[/latex] [latex]sum[/latex] [latex](x[/latex] [latex]y[/latex] [latex]z)[/latex] [latex]l[/latex]
2 2 1 2
3 1 2 1
2.33333 1.66667 1.33333 0.57735
1.1547
7 10 5 20
1 0 3 1
43 50 6 3
0 9 0 200
4 8 15 66
1.84138 9.23448 3.83103 5.34452
9.3099
57.9704
4.25705
11.4424

Код программы на С++

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

Решение
В цикле «[latex]while[/latex]» читаем числа из входного потока и запоминаем координаты точек в векторе [latex]а[/latex], к переменной [latex]sum[/latex] прибавляем эти координаты, умноженные на [latex]p[/latex].
Потом подсчитываем координаты центра тяжести системы и выводим эти координаты.
В цикле «[latex]for[/latex]» берем из вектора координаты одной из точек системы, считаем расстояние от центра тяжести до одной из точек системы и выводим это расстояние.

Ссылки
Код в ideone.com (C++)
Код в ideone.com (Java)
Условие задачи (с.117)

А282(а)

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задача

Даны действительные числа [latex]a_1,a_2, …,a_{2n}[/latex]. Получить:
[latex]a_1,a_{n+1},a_2,a_{n+2}, …,a_n,a_{2n}[/latex]

Тесты

Ввод
Вывод
1 2 3 4 5 6 7 8 9 10 1 6 2 7 3 8 4 9 5 10
8 25 3 7 8 3 25 7
5.5 6.025 2.387 1.0986 7.762 3.5958

5.5 1.0986 6.025 7.762 2.387 3.5958

Хороший код

Решение

Считываем действительные числа в первый вектор и узнаем [latex]n[/latex]. Затем поочередно вписываем элементы и элементы с измененным индексом в другой вектор, пока счетчик не будет равен [latex]n[/latex] и выводим полученный вектор, он и будет ответом.

Лучший код на C++

Лучший код на Java

 

Решение

В первом способе мы задавали два вектора, чем естественно увеличивали занимаемую память. C помощью функции insert() мы можем вставлять элементы в вектор, не используя дополнительных средств. Однако мы сталкиваемся с тем, что функция по определению вставляет в вектор константу из-за чего наш цикл не будет правильно работать. Чтобы изменять параметр вводимого элемента, заводим отдельный счетчик. Теперь каждый [latex]2*i+1[/latex]-ый шаг мы вставляем [latex]n+b+i[/latex]-ый элемент вектора. Проведем resize() вектора чтобы убрать лишние элементы и получим готовый результат.

Ссылки

  1. Хорошее решение на C++
  2. Лучшее решение на C++
  3. Лучшее решение на Java
  4. Условие в задачнике Абрамова(стр.120)

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 arithmetic average of all elements of this series except the element №i is:
for i = 0: 4
2 1 0 1 The arithmetic average of all elements of this series except the element №i is:
for i = 0: 0.5
for i = 1: 1
for i = 2: 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 = 0: 4.8(3)
for i = 1: 7.4
for i = 2: 4.4(3)
for i = 3: 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 = 0: -1.32
for i = 1: -0.32
for i = 2: -1.695
for i = 3: 1.555
for i = 4: -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)

Монстр

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задача 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, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.