|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
11.12.2022, 11:17 | #1 |
Новичок
Джуниор
Регистрация: 11.12.2022
Сообщений: 5
|
решить задачку
В старом игровом автомате «Морской бой» игрок сбивает торпедами корабли, двигающиеся по игровому полю слева направо или справа налево.
В нашем варианте игры на поле может находиться одновременно несколько кораблей. Все корабли движутся с одинаковыми скоростями налево или направо. За одну секунду каждый корабль передвигается на единицу длины системы координат. Это означает, что через одну секунду после начала игры корабль, который находился в точке 20 и двигался направо, будет находиться в точке 21, а корабль, который находился в точке 30 и двигался налево, окажется в точке 29. Вы можете выпускать торпеды, которые будут подбивать корабли. Торпеда, выпущенная в точке с какой-то координатой, уничтожает корабль, находящийся в этот момент в этой точке. При этом если в этой точке в этот момент времени окажется несколько кораблей, то торпеда подобьёт все эти корабли. Вы даже можете одновременно выпускать несколько торпед! Подбейте все корабли, используя минимальное число торпед. Формат входных данных В первой строке содержится целое число N — количество кораблей, движущихся влево (с уменьшением координаты). Во второй строке содержится целое число M — количество кораблей, движущихся вправо (с увеличением координаты). Гарантируется, что 1≤N+M≤10^5, N≥0 и M≥0 Следующие N строк содержат по одному целому числу l(i) — начальные координаты кораблей, двигающихся влево. Следующие M строк содержат по одному целому числу r(i) — начальные координаты кораблей, двигающихся вправо. Координаты l(i) идут в порядке возрастания, координаты r(i) также заданы в порядке возрастания. Гарантируется, что все начальные координаты l(i) и r(i) чётные, различные и не превосходят по модулю 10^9 Формат выходных данных Программа должна вывести столько строк, сколько торпед необходимо для уничтожения всех кораблей, при этом i-я строка должна содержать два целых числа t(i) — время нанесения удара i-й торпедой и x(i) — координату удара i-й торпедой. Все t(i) и x(i) должны быть целыми, 0≤t(i)≤10^18, −10^18≤x(i)≤10^18. один момент времени можно выпускать несколько торпед, в одну точку можно выпускать несколько торпед в разные моменты времени. Система оценивания Решения, правильно работающие при N+M≤10, 0≤ l(i) ≤100, 0≤r(i)≤100, будут оцениваться в 20 баллов. Решения, правильно работающие при N+M≤1000, будут оцениваться в 50 баллов. Замечания к примерам В примере из условия два корабля движутся влево и один корабль движется вправо. Начальные координаты кораблей, двигающихся влево, равны l1=10 и l2=30, а начальная координата корабля, двигающегося вправо, равна r1=20. В момент времени t1=5 в одной точке x1=25 окажутся два корабля — двигающийся влево из точки 20 и двигающийся вправо из точки 30. Их можно подбить одной торпедой. Оставшийся корабль, двигающийся влево, можно подбить, например, в момент времени t2=2 в точке x2=8. Ввод Вывод 2 1 10 30 20 5 25 2 8 Последний раз редактировалось rusanon; 11.12.2022 в 11:22. |
11.12.2022, 11:22 | #2 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,550
|
|
11.12.2022, 11:25 | #3 | |
Новичок
Джуниор
Регистрация: 11.12.2022
Сообщений: 5
|
Цитата:
|
|
11.12.2022, 11:30 | #4 | |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,550
|
С первого раза не понято. Разъясняю ещё раз:
Цитата:
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Решить задачку | Trash7 | Фриланс | 4 | 03.03.2017 10:59 |
решить задачку на C++ | toffa | Фриланс | 0 | 21.04.2013 11:20 |
Решить задачку... | VintProg | Свободное общение | 4 | 23.08.2011 16:54 |
Помогите решить задачку | Top4 | Помощь студентам | 0 | 07.04.2009 20:50 |