Сверхдикая задача про роботов

[Aleks_006]

Здравствуйте, мне дали довольно странную итоговую задачу, помогите разобраться хотя бы, что там от меня требуется?

"Давно, в самом начале развития робототехники, компания X представила первые модели роботов. Роботы могли двигаться по прямой либо вперёд, либо назад. Поэтому в качестве испытательного стенда был выбран бесконечный коридор, в котором находится M выходов. В коридоре расположено N роботов, каждый из которых может двигаться с некоторой постоянной скоростью V(i) вдоль коридора (i=1..n). Цель каждого робота - достичь ближайшего выхода, чтобы покинуть коридор. Роботы передвигаются оптимально и могут обгонять друг друга, не сталкиваясь.
Нужно написать программу, определяющую номер робота, который раньше всех выйдет из коридора (если их несколько, то нужно определить всех).
Входные данные:
В первой строке входного файла записаны два числа N и M (1<=N, M<=1000) - количество роботов и выходов соответственно. Далее следуют N строк, содержащих по два числа, разделённых пробелом. В первой - координаты и скорость 1-го робота, в последней - координаты выходов. Все координаты и скорости - натуральные числа, не превосходящие 10^9.
Выходные данные:
В первой строке вывести число S - количество роботов, которые раньше всех покинут коридор, во второй - их номера (можно в произвольном порядке)."

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

[Jugger]

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

[Аватар]

А что тут моделировать? Есть начальные координаты и скорость каждого робота, а так же координаты выходов. Для каждого робота вычислить ближайший выход и время на перемещение до него. Из полученных N времен выбрать минимальное (-ые) и результат с номером робота на экран или в файл

[Smitt&Wesson]

Задача обхода лабиринта. Можно решать через графы, но лучше, лабиринт представить в виде массива. Например "стены" обозначить отрицательными числами, "дорожки" - нулями, а выходы - числами большими, чем количество роботов. Номера роботов, соответственно - меньше.

как координаты могут быть одним целым числом?!

Координаты каждого робота, это индексы массива. Например X[100][100].

[Аватар]

Задача обхода лабиринта

Какой лабиринт? Просто коридор без начала и конца. И робот прётся к ближайшему выходу

[Smitt&Wesson]

Сообщение от Аватар

Какой лабиринт? Просто коридор без начала и конца. И робот прётся к ближайшему выходу

Точно, я чёт пропустил этот пунктик. Ну, тогда вообще всё просто.

[Kix.IV]

Ну, тогда вообще всё просто.

Тогда может быть объясните мне, а то что-то не пойму.
1)Вот смотрите, в условии задачи дан корридор с M выходов, а сами координаты выходов, судя по входным данным, не известны. Как быть?
2)"В первой строке вывести число S - количество роботов, которые раньше всех покинут коридор". А это как понимать? Что означает раньше остальных? Если каждый из 10 роботов придёт на секунду позже предыдущего, то кто из них будут считаться пришедшими раньшими?

[Smitt&Wesson]

Сообщение от Kix.IV

Тогда может быть объясните мне, а то что-то не пойму.
1)Вот смотрите в условии задачи дан корридор с M выходов, а сами координаты выходов, судя по входным данным, не известны. Как быть?

Координаты выходов, задаёте сами или случайным образом в стенах коридора.

2)"В первой строке вывести число S - количество роботов, которые раньше всех покинут коридор". А это как понимать? Что означает раньше остальных? Если каждый из 10 роботов придёт на секунду позже предыдущего, то кто из них будут считаться пришедшими раньшими?

У вас будут не секунды, а шаги цикла, которые можно приравнять к значению 1секунда. На каждом шаге цикла, делается проверка положения всех роботов и определяется, кто из них достиг выхода.
Если хоть один достиг, - выход из цикла. Если не достиг, делаем следующий шаг.
Но, если это всё-же не лабирнт, то можно вычислить и иначе. Как написал Аватар, просто сравнить координаты роботов и блищайших к ним выходов. Какой из них окажется ближе - тот и "выиграл".

[Kix.IV]

Координаты выходов, задаёте сами или случайным образом в стенах коридора.

Если хоть один достиг, - выход из цикла.

Значит условия задачи были не верно записаны? Ну тогда всё действительно просто.

[Аватар]

В первой строке входного файла записаны два числа N и M (1<=N, M<=1000) - количество роботов и выходов соответственно.

Далее следуют N строк, содержащих по два числа, разделённых пробелом.

В первой - координаты и скорость 1-го робота

Следует понимать в первой группе из N строк. По строке на робота. Не?

в последней - координаты выходов

Тут неувязка. Скорее всего следует понимать в последней группе из M строк. Не?

У вас будут не секунды, а шаги цикла, которые можно приравнять к значению 1секунда

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

кто из них будут считаться пришедшими раньшими

Один или несколько с наименьшим временем. Наименьшее может совпасть у нескольких