Помогите пожалуйста разобраться с задачей->


На скамье длиной L см расположены N гномов. В момент времени 0 гномы начинают двигаться по заданных направлениях со скоростью 1 см в секунду. При столкновении гномы мгновенно разворачиваются и начинают двигаться в противоположных направлениях с той же скоростью. При достижении края скамьи гном падает. Определите через сколько секунд упадёт последний гном.

Входные данные:
1-я строка: N L
N = (1..105), L = (2..106)
2-я строка: N разных чисел - расстояние в сантиметрах от левого края до соответствующего гнома (0..L);
3-я строка: N чисел - направление движения (-1 - влево; 1 - вправо) .
http://forum.php.su/topic.php?forum=31&topic=2349

Представим скамью в 100см, крайний гном находится на см1 позиции, все гномы движутся в правое направление, 100см-1см (это дистанция, которую прошел гном) = 99см. Если же брать разные направления, то из центра: 100см/2 = 50см. Много неточностей не позволяет определить поведение. Даже отсутствие позиции гномов.

_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).

Michael Можешь пожалуйста по подробнее изложить свои мысли ?

1) Создаешь массив длиной L*2 +1
Это массив всех точек на скамейке с шагом о.5 см.
2) Бегаешь по строке 2 и 3 и в ключи массива записываешь гномов и их первонач направление движения
Структура массива следующая:

array(
  0 => array(
    'gnoms' => array() // пустая позиция скамейки
  ),
  //...
  22 => array(
    'gnoms' => array(  // Тут 2 гнома - это момент когда они встретились
      10 => array(
        'direction' => 1, //1 - вправо, 0 - влево
        'step' => null,   // текущий шаг 
      ),
      11 => array(
      /* ...  */
      )
    )
  ),
  //...
  26 => array(
    'gnoms' => array(  // Тут 1 гном
      22 => array(
        'direction' => 0, //1 - вправо, 0 - влево
        'step' => null,   // текущий шаг 
      ),
    )
  ),  
  //...
);

3)
устанавливаешь нач. счетчик итераций
пока (скамейка не пуста[*1]) {
а) цикл по массиву, если есть гном в позиции и он еще не двигался на этой итерации то переносим его в соседнюю позицию массива. Если крайние элементы, то удаляем
Обработанному гному устанавливаем шаг итерации (step), чтобы не двигать его повторно
б) пробегаем по массиву, если в одной позиции оказались 2 гнома инвертируем им ключ direction
в) увеличиваем счетчик итераций
}
4) затраченное время = счетчик итераций *2

[*1] - при пробежке по циклу все массивы gnoms должны быть пусты. Или счетчик гномов вести.

_____________
There never was a struggle in the soul of a good man that was not hard