Eugene Kirpichov (antilamer) wrote,
Eugene Kirpichov
antilamer

Category:

Коллеги рассказали задачку

Есть бесконечная река с пристанями, пронумерованными всеми целыми числами (..., -2, -1, 0, 1, 2, ...). По реке плывет корабль-призрак, из неизвестной начальной точки, с фиксированной, но неизвестной целочисленной скоростью - т.е. для каких-то неизвестных a, b в день i корабль останавливается в пристани ai+b.
Корабль-призрак можно засечь только ночью - то есть, чтобы его засечь, нужно остановиться в какой-то пристани на ночь - и если корабль в эту ночь был как раз в этой пристани, то мы его поймали. Нужно придумать стратегию (f(i) - в день i стоим в пристани i; f может быть любой, наша скорость не ограничена), позволяющую гарантированно за конечное (но не ограниченное и не обязательно оптимальное) число шагов поймать корабль.

Короче, нужно придумать целочисленную функцию, пересекающуюся с любой целочисленной арифметической прогрессией.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 17 comments