Пого-палка: кратчайший путь
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Математика
- Строки
Вы стоите в точке (0, 0) и хотите попасть в точку (x, y) с целыми координатами ((x, y) ≠ (0, 0), |x|, |y| ≤ 10^9). Вы прыгаете на пого-палке: i-й прыжок (с первого) длится 2^(i-1) единиц в одном из четырёх направлений: N (y растёт), S (y убывает), E (x растёт), W (x убывает). Нужно приземлиться ровно в (x, y) после последнего прыжка.
Верните строку из букв N, S, E, W — направления прыжков по порядку — самого короткого пути; если до точки добраться нельзя, верните IMPOSSIBLE. Кратчайший путь всегда единственный.
Пример: 2, 3 → SEN (на юг на 1, на восток на 2, на север на 4).
Источник: Coding Competitions Archive, codejam/2020/round_1b/expogo · © Google LLC · Apache-2.0 · условие переведено и дополнено