К содержанию
Quantoros

Робот стартует в (0,0), разрешены шаги (±1,±1). Достигнет ли (1,0)? Какие целые точки достижимы?

Quant ResearchУровень: БазаReachability invariant

Робот стартует в (0,0), разрешены шаги (±1,±1). Достигнет ли (1,0)? Какие целые точки достижимы?

Подсказки
  • Смотрите на чётность, а не расстояние.
  • Разложите точку по двум диагональным векторам.

Ответ

Чётности x и y меняются одновременно, x+y всегда чётно. (1,0) недостижима. Если чётности равны, коэффициенты (x+y)/2 и (x-y)/2 целые: столько шагов по диагоналям, отрицательные заменяются обратными.

Источник и лицензия: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · ответ: редакция Quantoros · перевод: Quantoros

Похожие вопросы