e-olymp
Məsələlər

Сетчатая страна

Сетчатая страна

В течение многих лет, компьютерные специалисты пытаются найти эффективные решения для различных вычислительных задач. Для некоторых из них эффективные алгоритмы уже существуют, это "лёгкие" задачи, такие как сортировка, вычисление многочлена или нахождение кратчайшего пути в графе. Для "трудных" задач известны только алгоритмы с экспоненциальным временем. Задача бродячего торговца принадлежит к последней группе. Зная множество городов N и дороги между этими городами, задача состоит в том, чтобы вычислить кратчайший путь, позволяющий продавцу посетить каждый из городов только один раз и вернуться в исходную точку.

Президент сетчатой страны нанял вас разработать программу, которая вычисляет длину кратчайшего тура бродячего торговца для городов в его стране. В сетчатой стране каждый город расположен в каждой из точек прямоугольной сетки. Дороги направлены из каждого города в направлении севера, северо-запада, запада, юго-запада, юга, юго-востока, востока и северо-востока, при условии, что в этом направлении есть соседний город. Расстояние между соседними городами в направлении восток-запад или север-юг равен 1 единице. Длина дороги измеряется евклидовым расстоянием. Например, на рисунке ниже показана сетчатая страна 2×3, то есть прямоугольная сетка размером 2 на 3. В сетчатой стране 2×3 самый короткий тур имеет длину 6.

prb3469

Тур бродячего торговца по сетчатой стране 2×3

Входные данные

Первая строка содержит количество тестов. Для каждого тестового случая заданы размеры сетки m (1 < m < 50) и n (1 < n < 50) предоставленные двумя целыми числами в одной строке, разделенные одним пробелом.

Выходные данные

Выход для каждого тестового случая начинается со строки, содержащей "Scenario #i:", где i - это номер тестового случая, начиная с 1. В следующей строке выведите длину кратчайшего тура бродячего торговца округленную до двух десятичных цифр. Выходные данные для соседних тестовых случаев разделяйте пустой строкой.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
2
2 2
2 3
Çıxış verilənləri
Scenario #1:
4.00

Scenario #2:
6.00