e-olymp 1228. Добавить все

Условие

Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.

Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,$ $2$ равна $3$. Складывать числа можно разными способами:

  • $1 + 2 = 3 \left(стоимость = 3\right), 3 + 3 = 6 \left(стоимость = 6\right), Всего = 9 $
  • $1 + 3 = 4 \left(стоимость = 4\right), 2 + 4 = 6 \left(стоимость = 6\right), Всего = 10 $
  • $2 + 3 = 5 \left(стоимость = 5\right), 1 + 5 = 6 \left(стоимость = 6\right), Всего = 11 $

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

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

Начинаются целым числом $n (2 \leqslant n \leqslant 100000)$, за которым следуют $n$ целых неотрицательных чисел (все числа меньше $100000$).

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

Вывести наименьшую стоимость сложения всех чисел.

Тесты

Ввод Вывод
$4$
$10$ $12$ $13$ $11$
$92$
$5$
$100$ $11$ $8$ $30$ $12$
$272$
$4$
$2$ $2$ $2$ $2$
$16$
$6$
$1$ $2$ $3$ $4$ $5$ $6$
$51$

Код

Решение

Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $min\_sum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $min\_sum$ будет содержать искомую стоимость сложения всех чисел.

Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом. Так как в задаче нужны минимальные элементы множества, а очередь располагает элементы в порядке их увеличения, то будем хранить в ней не сами элементы множества $A$, а противоположные им числа.

Ссылки

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

e-olymp 1226. Обмен иностранцами

Задача

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

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из $A$ в $B$, то обязательно должен быть другой студент, который хочет переехать из $B$ в $A$. Это простая задача, если участников программы всего $10$. Но что делать если их будет $100001$?

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

Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит количество студентов $n$ $(1 ≤ n ≤ 100001)$, за которыми следуют $n$ строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте — два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими $10^9$. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

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

Для каждого теста в отдельной строке вывести $«YES»$ если существует возможность успешно выполнить программу обмена и $«NO»$ иначе.

Тесты

Входные данные Выходные данные
2
2
1 2
2 1
2
31 13
13 31
YES
YES
1
4
17 3
28 15
15 28
3 17
YES
1
4
17 3
28 15
15 28
3 18
NO
3
2
1 2
3 4
2
47 7
7 47
2
12 34
12 34
NO
YES
NO

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

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

После задания переменной $n$ (количества студентов) очищаем мультимножество $M$. Для каждой пары $(a, b)$ нашего мультимножества проверяем, есть ли в нем пара $(b, a)$:
1. Если есть, то удаляем пару $(b, a)$.
2. Если нет, то вставляем $(a, b)$.
Если в конце мультимножество $M$ пустое, то у каждой пары $(a, b)$ существует соответствующая ей пара $(b, a)$, следовательно обмен студентами может быть произведен успешно.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

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

Задача

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

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

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

Тесты

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

54
ABABABABC

24

Код на C++

Код на Java

Решение

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

Ссылки

1.Код на С++

2.Код на Java

3.Условие на 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(а)

Задача

Даны действительные числа [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)