{"problem":{"name":"D. Рудольф и очереди","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":"CF10132D"},"statements":[{"statement_type":"Markdown","content":"Давайте немного отвлечёмся от красно-чёрных деревьев, перенесёмся в любимое кафе Рудольфа и выясним, почему же Рудольф так долго трапезничал. Кафе работает по принципу шведского стола: можно выбирать любые блюда, а затем подходить к кассе и оплачивать их. Имеются две кассы, к каждой из которых ведёт отдельная очередь.\n\nРудольф зашёл в кафе и понял, что попал как раз в обеденное время — у обеих касс были огромные очереди.\n\nБудучи грамотным математиком, Рудольф сразу же посчитал, что в первой очереди n1 человек, а во второй — n2. Следуя логике, он встал в очередь с наименьшим количеством людей. Спустя некоторое время он понял, что очереди двигаются с разными скоростями, поэтому выбор наименьшей очереди вовсе не означал, что Рудольф быстрее оплатит свой обед. Рудольф заметил, что скорость обслуживания зависит от возраста обслуживаемого человека — старшему поколению гораздо сложнее разобраться с хитроумными устройствами безналичной оплаты, чем молодым людям. Рудольф разделил всех людей на категории в соответствии с их возрастом. Для каждой категории Рудольф определил время обслуживания на кассе:\n\nПоскольку Рудольф хочет как можно быстрее оплатить свой обед, он решил, что каждую минуту с вероятностью p он будет переходить в другую очередь, если она на момент принятия решения состоит из меньшего числа людей. \n\nРудольфу стало интересно, чему равно математическое ожидание количества переходов между очередями за период времени с момента занятия очереди в кафе до момента оплаты обеда. Давайте поможем ему в решении этой задачи.\n\nСчитать, что остальные люди не перемещаются между очередями, а также что в очередях не появляются новые люди.\n\nПервая строка содержит вещественное число p (0 ≤ p ≤ 1), заданное не более чем с 6 знаками после десятичной точки, — вероятность перехода Рудольфа из одной очереди в другую. \n\nВторая строка содержит целое число n1 (1 ≤ n1 ≤ 100) — количество людей в первой очереди.\n\nТретья строка содержит n1 целых чисел a1i (18 ≤ a1i ≤ 100) — возраст людей в первой очереди в порядке обслуживания.\n\nЧетвертая строка содержит целое число n2 (1 ≤ n2 ≤ 100, n2 ≠ n1) — количество людей во второй очереди.\n\nПятая строка содержит n2 целых чисел a2j (18 ≤ a2j ≤ 100) — возраст людей во второй очереди в порядке обслуживания.\n\nВыведите одно вещественное число — математическое ожидание количества переходов между очередями, которые может совершить Рудольф при заданных условиях. Абсолютная или относительная погрешность ответа не должна превышать 10 - 6.\n\n## Входные Данные\n\nПервая строка содержит вещественное число p (0 ≤ p ≤ 1), заданное не более чем с 6 знаками после десятичной точки, — вероятность перехода Рудольфа из одной очереди в другую. Вторая строка содержит целое число n1 (1 ≤ n1 ≤ 100) — количество людей в первой очереди.Третья строка содержит n1 целых чисел a1i (18 ≤ a1i ≤ 100) — возраст людей в первой очереди в порядке обслуживания.Четвертая строка содержит целое число n2 (1 ≤ n2 ≤ 100, n2 ≠ n1) — количество людей во второй очереди.Пятая строка содержит n2 целых чисел a2j (18 ≤ a2j ≤ 100) — возраст людей во второй очереди в порядке обслуживания.\n\n## Выходные Данные\n\nВыведите одно вещественное число — математическое ожидание количества переходов между очередями, которые может совершить Рудольф при заданных условиях. Абсолютная или относительная погрешность ответа не должна превышать 10 - 6.\n\n## Примеры\n\nВходные данные1.0170518 18 18 18 18Выходные данные1.000000000Входные данные1.0318 70 18518 18 18 18 18Выходные данные1.000000000Входные данные0.5318 18 18218 18Выходные данные0.000000000Входные данные0.5320 50 30418 30 40 18Выходные данные0.750000000\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ p \\in [0, 1] $ be the probability of switching queues at each minute.  \nLet $ n_1, n_2 \\in \\mathbb{Z}^+ $, $ n_1 \\ne n_2 $, be the initial number of people in queues 1 and 2, respectively.  \nLet $ A_1 = (a_{1,1}, a_{1,2}, \\dots, a_{1,n_1}) $ and $ A_2 = (a_{2,1}, a_{2,2}, \\dots, a_{2,n_2}) $ be sequences of ages in queues 1 and 2, respectively.  \n\nDefine service times:  \nFor each person with age $ a $, service time is $ s(a) = \\begin{cases} 2 & \\text{if } a \\ge 60 \\\\ 1 & \\text{otherwise} \\end{cases} $.  \n\nLet $ T_1 = \\sum_{i=1}^{n_1} s(a_{1,i}) $ be the total service time of queue 1.  \nLet $ T_2 = \\sum_{j=1}^{n_2} s(a_{2,j}) $ be the total service time of queue 2.  \n\nLet $ t_{\\text{end}} = \\min(T_1, T_2) $ be the time at which Rudolph finishes payment (when the queue he is in is fully served).  \n\nRudolph initially joins the queue with fewer people. If $ n_1 < n_2 $, he starts in queue 1; else in queue 2.  \n\nAt each integer minute $ t \\in \\{1, 2, \\dots, t_{\\text{end}} - 1\\} $, if the remaining number of people in the *other* queue is strictly less than in his current queue, he switches to it with probability $ p $.  \n\nLet $ X $ be the random variable denoting the total number of queue switches.  \n\n**Objective**  \nCompute $ \\mathbb{E}[X] $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10132D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}