Робот стартует в (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