Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача I. Бильярд (off-line проверка)
| Имя входного файла: | i.in |
| Имя выходного файла: | i.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
Есть прямоугольный стол для игры в бильярд размером NxM. Стол расположен в системе координат так, что его углы находятся в точках с координатами (0,0), (N,0), (N,M), (0,M).
На столе лежат черный и белый шары. Игрок ударяет по черному шару, задавая ударом направление его движения. Шар летит в заданном направлении, отскакивая от стенок стола по закону отражения. Когда черный шар ударяет по белому шару, то черный шар останавливается, а белый начинает двигаться в том направлении, куда летел в момент удара черный. После этого белому шару запрещается ударять черный шар.
Задача игрока - загнать белый шар в одну из луз, расположенных в углах стола. При этом до попадания в лузу черный и белый шары должны удариться о стенки стола суммарно как можно меньше раз, но не более K раз.
Считается, что шары являются точками (не имеют размера), лузы также точечные.
Формат входных данных
Сначала вводятся размеры стола N и M (3≤N≤1000, 3≤M≤1000). Далее записано число K (0≤K≤200). Затем записано две пары чисел X1,Y1, X2, Y2 - начальные координаты черного шара и начальные координаты белого шара (1≤X1≤N-1, 1≤Y1≤M-1, 1≤X2≤N-1, 1≤Y2≤M-1). Гарантируется, что начальные положения шаров не совпадают, и изначально шары находятся строго внутри стола.
Все числа целые.
Формат выходных данных
Выведите минимальное суммарное количество ударов черного и белого шаров о стенки стола до попадания белого шара в лузу. Если попасть белым шаром в лузу, сделав не более K ударов, невозможно, выведите -1 (минус один).
Примеры
| i.in | i.out | Комментарий |
4 4 3 2 1 2 3 |
1 |
Можно попасть в лузу, лишь 1 раз ударившись о стенку стола: нужно ударить черный шар так, чтобы он полетел в точку (4,2), где он ударится о стенку стола, попадет в белый шар, белый шар начнет двигаться и попадет в угол стола (0,4) |
4 4 200 1 1 1 3 |
-1 |
Попасть в лузу нельзя. |
5 4 3 4 1 4 3 |
3 |
Надо так толкнуть черный шар, чтобы он первый раз ударился о стену в точке (0,3) |
5 4 0 3 2 4 3 |
0 |
Ударяем черный шар так, чтобы он летел по прямой к белому шару, он ударит белый, и белый напрямую попадет в угол. |