Задача 4: Железная дорога Вите на день рождения подарили Очень Большую Игрушечную Железную Дорогу. Она представляет собой два параллельных пути, по которым движутся поезда во встречных направлениях. В центре находится станция, а железная дорога очень большая, поэтому можно считать пути бесконечными в обе стороны.
Витя расставил поезда на железной дороге и одновременно запустил их, включив электропитание. Все поезда движутся с одинаковыми скоростями в одном из двух возможных направлений. Но когда-нибудь поезда придётся остановить и убрать игру, а поскольку поезд не может развернуться и начать движение в противоположном направлении, Вите придётся самому собирать поезда руками и переносить их на станцию. Витя хочет выбрать такой момент остановки всех поездов, чтобы ему пришлось потратить минимальное число усилий для того, чтобы собрать после этого все поезда на станции вместе, то есть в этот момент времени сумма расстояний всех поездов до станции была бы минимальной.
Входные данные
Введём на железной дороге координаты, считая, что станция находится в начале координат, а все поезда первоначально находятся в целочисленных точках координатной прямой. Сами поезда также будем считать точками. За одну секунду координаты всех поездов изменяются на +1 или на −1. Поезда движутся с равными скоростями, первоначально никакие два поезда, движущиеся в одном направлении, не находятся в одной точке.
Первая строка входных данных содержит целое число N — количество поездов, движущихся в положительном направлении. Вторая строка входных данных содержит целое число M — количество поездов, движущихся в отрицательном направлении. Ограничения: N ≥ 0, M ≥ 0, 1 ≤ N + M ≤ 105.
Следующие N строк содержат N чисел ai (|ai| ≤ 109) — первоначальные координаты поездов, движущихся в положительном направлении. Все числа ai различны и заданы в порядке возрастания.
Следующие M строк содержат M чисел bj (|bj| ≤ 109) — первоначальные координаты поездов, движущихся в отрицательном направлении. Все числа bj различны и заданы в порядке возрастания.
Выходные данные
Программа должна вывести единственное целое число t — момент времени в секундах после запуска игры, в который суммарное расстояние всех поездов до станции будет минимальным. Если возможных правильных ответов несколько, то программа должна вывести любой из них. Если после старта игры суммарное расстояние всех поездов до станции будет всегда больше, чем в момент запуска игры, то правильным ответом будет t = 0.
Система оценивания
Решения, правильно работающие, когда N ≤ 100, |ai| ≤ 100, |bj| ≤ 100, будут оцениваться в
Решения, правильно работающие, когда N ≤ 100, |ai| ≤ 109, |bj| ≤ 109, будут оцениваться в
Пример
Ввод
Вывод
Пояснение
3
2
-5
-2
4
1
4
2
3 поезда движутся в положительном направлении, 2 поезда движутся в отрицательном направлении. Начальные координаты поездов, движущихся в положительном направлении равны −5, −2, 4, движущихся в отрицательном направлении равны 1 и 4. Запишем, что при t = 0 координаты поездов (−5, −2, 4, 1, 4). Суммарное расстояние всех поездов до станции равно 16. В момент t = 1 координаты поездов будут (−4, −1, 5, 0, 3), суммарное расстояние до станции равно 13. В момент t = 2 координаты поездов будут (−3, 0, 6, −1, 2), суммарное расстояние до станции равно 12. В момент t = 3 координаты будут (−2, 1, 7, −2, 1), суммарное расстояние до станции равно 13. ответ на этот тест t= 2
ПиТОН ХЕЛП
zexer9p07xi1
2
13.12.2020 12:39
47
Другие вопросы по теме Информатика
Г0ошан4ик
31.01.2022 14:08
zverok21rus
24.04.2021 13:28
mar244144
09.11.2020 21:20
ппср
23.07.2019 02:40
Shock228ru
13.09.2019 17:30
Alllllllex
31.05.2019 06:30
mazyrin91p08sby
31.05.2019 06:30
lerafilippovа04
31.05.2019 06:30
Популярные вопросы
- З двох міст назустріч один одному виїхали два велосипедисти і зустрілися через...
3 - Верно ли следующее суждение? Адаптация — это процесс психологической включаемости...
3 - Объясните что данное сложное предложение с последовательным подчинением придаточных...
2 - Сума коефіцієнтів Ba(OH)2+FeCl3 Ca(OH)2+FeCl2 KOH+H2SiO3...
1 - Очень Як саме у творі про людину, що 40 років вела людей до мети, порівнюються...
1 - Cu, Zn, NaOH, HgO, K2CO3, H2SO4, CO2. Укажите количество возможных реакций с...
3 - Выписать в тетрадь определения «гамета», «сперматозоид», «яйцеклетка», «раздельнополые»,...
2 - Впиши верное определение. — это положение человека в обществе....
2 - Вкажи найбільше натуральне число, кратне 5, що задовольняє нерівності: 282...
1 - Площадь треугольника ABC равна 120. Биссектриса AD пересекает медиану BK в точке...
2
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long int
#define vi vector<int>
#define va vector<vector<int>>
#define frr(i,n) for(int i=0;i<n;i++)
#define fir(n,i) for(int i=n-1;i>=0;i--)
using namespace std;
int main(int argc, char* argv[])
{
vi s, g, h, k;
int a, b, c, d, e = 0;
cin >> a >> b;
frr(i, a) {
cin >> c;
if (c < 0) s.push_back(abs(c));
e++;
}
frr(i, b) {
cin >> c;
if (c > 0) s.push_back(abs(c));
e++;
}
sort(s.begin(), s.end());
cout << s[(e / 2)-1];
}
Объяснение:
def run():
a = int(input())
b = int(input())
trains = []
for i in range(a + b):
trains.append(int(input()))
t = 0
s = sum(i if i >= 0 else -i for i in trains)
while True:
for i in range(a):
trains[i] += 1
for i in range(b):
trains[a + i] -= 1
s1 = sum(i if i >= 0 else -i for i in trains)
if s1 < s:
s = s1
t += 1
else:
return t
print(run())
Объяснение:
Язык Python, на