{"problem":{"name":"K. Парковка","description":{"content":"Вася сделал покупки в популярном торговом центре и теперь хочет отправиться домой. Для этого ему сначала нужно выехать на своей машине с парковки. Задача эта не очень простая, поскольку на парковке на","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10052K"},"statements":[{"statement_type":"Markdown","content":"Вася сделал покупки в популярном торговом центре и теперь хочет отправиться домой. Для этого ему сначала нужно выехать на своей машине с парковки. Задача эта не очень простая, поскольку на парковке находится множество машин других посетителей торгового комплекса. Сама же парковка представляет собой прямоугольную область N × M клеток. В одной из клеток находится машина Васи. В других клетках могут находиться машины остальных покупателей. Кроме того, в некоторых клетках (по крайней мере, в одной) находятся выезды с парковки.\n\nВася хочет доехать до одного из выездов с парковки. Вася может перемещаться на машине из текущей клетки в соседнюю по стороне клетки, если эта клетка находится на парковке и свободна от других машин. В процессе переезда Вася может увеличивать скорость автомобиля максимум на A или уменьшать скорость автомобиля максимум на B. Итого, если до переезда скорость автомобиля была равна V, то после переезда на новую клетку скорость может быть любым (не обязательно целым) числом в интервале [V - B, V + A] по желанию Васи, с единственным ограничением — скорость не может быть ниже 1. Если в начале переезда скорость машины была равна V1, а после — стала равна V2, то будем считать, что Вася потратил 2 / (V1 + V2) времени на переезд. Кроме того, Вася может менять направление движения, только если скорость автомобиля равна 1. Это значит, что если Вася уже совершил переезд из одной клетки в другую и его скорость после переезда больше 1, то он может продолжать двигаться только в том же направлении. Если же следующая клетка в этом направлении занята машиной или находится за пределами парковки, то такое движение запрещено. Однако приезжать к выезду с парковки можно на любой скорости (даже если следующая клетка в направлении движения занята).\n\nОпределите, за какое наименьшее время Вася сможет добраться до какого-либо из выездов с парковки. Покидать парковку, выходя за пределы исходной области N × M, запрещено. Машины других покупателей не двигаются. Начальная скорость машины Васи равна 1.\n\nВ первой строке входного файла находятся 4 целых числа — размеры парковки N и M (1 ≤ N, M ≤ 200), а так же числа A и B (1 ≤ A, B ≤ 100). Следующие N строк описывают начальное состояние парковки. Каждая строка имеет длину M и состоит из символов '_._', '_C_', '_V_', '_E_'. Символ '_._' соответствует пустой клетке парковки, '_C_' — занятой автомобилем, '_V_' — клетка, в которой находится машина Васи, '_E_' — клетки, представляющие собой выезды с парковки. Гарантируется, что присутствует ровно один символ '_V_', не менее одного символа '_E_' и что Вася может добраться хотя бы до одного выезда с парковки.\n\nВывести единственное вещественное число с абсолютной или относительной погрешностью, не превышающей 10 - 6 — минимальное время, за которое Вася сможет добраться до одного из выездов с парковки.\n\nВ первом примере Вася при переезде с клетки (1, 1) в клетку (1, 2), содержащую выезд с парковки, может увеличить скорость с 1 до 3. При этом он потратит время, равное 2 / (1 + 3) = 0.5.\n\nВо втором примере оптимально двигаться из клетки (1, 1) в клетку (1, 2), увеличив скорость до 2. Затем — в клетку (1, 3), снизив скорость до 1 из-за поворота. Далее — в клетку (2, 3), увеличив скорость до 2. Итого, будет потрачено время 2 / (1 + 2) + 2 / (2 + 1) + 2 / (1 + 2) = 2.\n\nВ третьем примере нельзя двигаться так же, как в предыдущем, поскольку клетка (1, 2) занята другой машиной. Необходимо двигаться сначала в клетку (2, 1) на скорости 1, затем повернуть на клетку (2, 2), увеличив скорость до 2, далее — в клетку (2, 3), увеличив скорость до 3. Итого, Вася потратит  единиц времени.\n\n## Входные Данные\n\nВ первой строке входного файла находятся 4 целых числа — размеры парковки N и M (1 ≤ N, M ≤ 200), а так же числа A и B (1 ≤ A, B ≤ 100). Следующие N строк описывают начальное состояние парковки. Каждая строка имеет длину M и состоит из символов '_._', '_C_', '_V_', '_E_'. Символ '_._' соответствует пустой клетке парковки, '_C_' — занятой автомобилем, '_V_' — клетка, в которой находится машина Васи, '_E_' — клетки, представляющие собой выезды с парковки. Гарантируется, что присутствует ровно один символ '_V_', не менее одного символа '_E_' и что Вася может добраться хотя бы до одного выезда с парковки.\n\n## Выходные Данные\n\nВывести единственное вещественное число с абсолютной или относительной погрешностью, не превышающей 10 - 6 — минимальное время, за которое Вася сможет добраться до одного из выездов с парковки.\n\n## Примеры\n\nВходные данные2 2 2 2VE..Выходные данные0.500000000Входные данные2 3 1 1V....EВыходные данные2.000000000Входные данные2 3 1 1VC...EВыходные данные2.066666667\n\n## Примечание\n\nВ первом примере Вася при переезде с клетки (1, 1) в клетку (1, 2), содержащую выезд с парковки, может увеличить скорость с 1 до 3. При этом он потратит время, равное 2 / (1 + 3) = 0.5.Во втором примере оптимально двигаться из клетки (1, 1) в клетку (1, 2), увеличив скорость до 2. Затем — в клетку (1, 3), снизив скорость до 1 из-за поворота. Далее — в клетку (2, 3), увеличив скорость до 2. Итого, будет потрачено время 2 / (1 + 2) + 2 / (2 + 1) + 2 / (1 + 2) = 2.В третьем примере нельзя двигаться так же, как в предыдущем, поскольку клетка (1, 2) занята другой машиной. Необходимо двигаться сначала в клетку (2, 1) на скорости 1, затем повернуть на клетку (2, 2), увеличив скорость до 2, далее — в клетку (2, 3), увеличив скорость до 3. Итого, Вася потратит  единиц времени.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ be the dimensions of the parking grid.  \nLet $ A, B \\in \\mathbb{Z}^+ $ be the maximum speed increase and decrease per move, respectively.  \nLet $ G = (V, E) $ be a grid graph of size $ N \\times M $, where each cell $ (i, j) $ is a vertex.  \nLet $ S \\subset V $ be the set of cells containing obstacles (cars), represented by 'C'.  \nLet $ V_0 \\in V $ be the unique starting cell (marked 'V').  \nLet $ E_{\\text{out}} \\subset V $ be the set of exit cells (marked 'E').  \n\nEach cell is either:  \n- Free ('.') — traversable,  \n- Obstacle ('C') — blocked,  \n- Start ('V') — initial position,  \n- Exit ('E') — target.  \n\nLet $ v \\in \\mathbb{R}^+ $ denote the current speed of Vasya’s car, with $ v \\geq 1 $.  \nInitial speed: $ v = 1 $.  \n\n**Constraints**  \n1. Movement is allowed only to adjacent (up/down/left/right) free or exit cells.  \n2. From speed $ v $, after a move, new speed $ v' \\in [v - B, v + A] \\cap [1, \\infty) $.  \n3. Direction change is allowed **only** if current speed $ v = 1 $.  \n4. Once speed $ v > 1 $, movement must continue in the same direction until an exit is reached or blocked.  \n5. Exiting the grid is forbidden; exits are within $ [1, N] \\times [1, M] $.  \n6. Time to move from cell with speed $ v_1 $ to adjacent cell with speed $ v_2 $: $ \\frac{2}{v_1 + v_2} $.  \n7. Upon reaching any exit cell, the journey ends, regardless of speed or direction.  \n\n**Objective**  \nFind the minimum total time to reach any cell in $ E_{\\text{out}} $ from $ V_0 $, obeying movement and speed constraints.  \n\nFormally, define state $ (i, j, v, d) $, where:  \n- $ (i, j) \\in \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $: current position,  \n- $ v \\in \\mathbb{R}^+ $: current speed, $ v \\geq 1 $,  \n- $ d \\in \\{(0,1), (1,0), (0,-1), (-1,0)\\} \\cup \\{ \\text{none} \\} $: current direction (or undefined if at start).  \n\nInitial state: $ (i_0, j_0, 1, \\text{none}) $, where $ (i_0, j_0) = V_0 $.  \n\nGoal: reach any $ (i, j) \\in E_{\\text{out}} $.  \n\nTransition: from state $ (i, j, v, d) $, if $ d = \\text{none} $ (start), can choose any valid direction $ d' $ and any $ v' \\in [1, 1 + A] $, move to neighbor $ (i', j') $ in direction $ d' $, cost $ \\frac{2}{1 + v'} $.  \n\nIf $ d \\neq \\text{none} $:  \n- If $ v = 1 $: may change direction to any valid $ d' $, and choose $ v' \\in [1, 1 + A] $, move to $ (i', j') $ in direction $ d' $, cost $ \\frac{2}{v + v'} $.  \n- If $ v > 1 $: must continue in direction $ d $, choose $ v' \\in [v - B, v + A] \\cap [1, \\infty) $, move to $ (i', j') $ in direction $ d $, cost $ \\frac{2}{v + v'} $.  \n\nMinimize total cost over all paths from initial state to any exit state.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10052K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}