IOM 2021, Блиц — Задача 10

The Blitz-contest of IOM-2021

Условие

Consider a graph with vertices in all lattice points of a 3d space with $x, y, z \in [-2000, 2000]$, and edges between all pairs of vertices that have Euclidean distance 1 from each other. First, a breadth-first search is run to find the distance from $(566, 566, 566)$ to $(239, 239, 239)$. Then, a breadth-first search with the meet-in-the-middle approach is run for the same task. What is the ratio of the number of vertices processed by the first BFS to the number of vertices processed by the second BFS?

Give the answer rounded to the nearest integer.

(Both BFSs terminate when the desired distance is known.)

Отговори

Решение

---

Оригинал в Архива: iom-2021-blitz-tasks-eng.pdf · официални решения: iom-2021-blitz-answers-eng.pdf