{"problem":{"name":"H. Побег","description":{"content":"Специальная подземная тюрьма Галактической федерации для участников Сопротивления состоит из N уровней, пронумерованных от 0 до N - 1 от верхнего к нижнему. Уровни расположены последовательно друг под","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10136H"},"statements":[{"statement_type":"Markdown","content":"Специальная подземная тюрьма Галактической федерации для участников Сопротивления состоит из N уровней, пронумерованных от 0 до N - 1 от верхнего к нижнему. Уровни расположены последовательно друг под другом, каждый из них имеет форму круга, центры кругов находятся на одной вертикальной оси, а их диаметры увеличивается с увеличением номера уровня. Уровень номер i делится на 2i одинаковых секторов — камер с номерами от 2i до 2i + 1 - 1. \n\nКаждая камера, кроме камер последнего уровня, имеет две двери с кодовыми замками — левую и правую, если смотреть на двери изнутри камеры. Каждая из дверей на уровне i ведет в камеру на уровне i + 1, находящуюся ровно под этой дверью. Когда вводится верный код доступа к какой-либо двери, каждый уровень тюрьмы независимо от других поворачивается равновероятно влево или вправо вокруг своей оси на один сектор, то есть на угол 360 / 2i градусов по или против часовой стрелки. Только после этого дверь открывается.\n\nСхема взаимного расположения камер и дверей изображена на рисунке (вид сверху), стрелкой показано направление взгляда в камере номер 1:\n\nЛидерам Сопротивления, находящимся в заключении в камере 1 на нулевом уровне, удалось добыть секретные коды доступа ко всем дверям тюрьмы. Также им стало известно, сколько заключенных находится в каждой камере и что ровно в полночь уровни будут расположены друг относительно друга так, как показано на рисунке, то есть из камеры s левая дверь будет вести в камеру 2s, а правая — в камеру 2s + 1.\n\nЛидеры собираются начать побег ровно в полночь. Они будут перемещаться по камерам, начиная со своей, каждый раз спускаясь в одну из камер следующего уровня и забирая с собой всех заключенных на своем пути. Когда лидеры окажутся в одной из камер последнего уровня, союзники на воле отследят их местоположение, проделают подкоп и вызволят всех из этой камеры.\n\nВремени на раздумья в процессе побега не будет, поэтому необходимо помочь лидерам Сопротивления *заранее* составить план открывания дверей при побеге таким образом, чтобы математическое ожидание освобожденных в итоге человек было максимальным. План должен состоять из N - 1 символов, i-й символ определяет, какую из дверей открывать, находясь на уровне i - 1: _L_ означает левую дверь, а _R_ — правую. Торопитесь, до полуночи осталось меньше пяти часов...\n\nВ первой строке задано число уровней N (2 ≤ N ≤ 16).\n\nСледующие N строк содержат описание уровней, начиная с нулевого. Описание уровня i содержит 2i целых положительных чисел, которые соответствуют количеству участников Сопротивления в каждой камере этого уровня в порядке по часовой стрелке, начиная с камеры с меньшим номером. Другими словами, если не считать число N, то число номер k во вводе соответствует количеству заключенных в камере k.\n\nКоличество заключенных ни в какой из камер не превышает 106.\n\nВыведите план побега в виде строки из N - 1 символов _L_ и _R_. Если несколько планов позволяют достичь максимального математического ожидания, разрешается вывести любой из них.\n\n## Входные Данные\n\nВ первой строке задано число уровней N (2 ≤ N ≤ 16).Следующие N строк содержат описание уровней, начиная с нулевого. Описание уровня i содержит 2i целых положительных чисел, которые соответствуют количеству участников Сопротивления в каждой камере этого уровня в порядке по часовой стрелке, начиная с камеры с меньшим номером. Другими словами, если не считать число N, то число номер k во вводе соответствует количеству заключенных в камере k.Количество заключенных ни в какой из камер не превышает 106.\n\n## Выходные Данные\n\nВыведите план побега в виде строки из N - 1 символов _L_ и _R_. Если несколько планов позволяют достичь максимального математического ожидания, разрешается вывести любой из них.\n\n## Пример\n\nВходные данные4110 48 2 7 38 6 2 1 1 8 2 9Выходные данныеRLL\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ 2 \\leq N \\leq 16 $, be the number of levels.  \nLet $ c_{i,j} \\in \\mathbb{Z}_{\\geq 0} $ denote the number of prisoners in chamber $ j $ on level $ i $, where $ i \\in \\{0, 1, \\dots, N-1\\} $ and $ j \\in \\{2^i, 2^i + 1, \\dots, 2^{i+1} - 1\\} $.  \n\n**Transition Model**  \nAt each level $ i \\in \\{0, 1, \\dots, N-2\\} $, when a door is opened, the level rotates independently and uniformly at random by $ \\pm \\frac{360^\\circ}{2^i} $ (i.e., one sector clockwise or counterclockwise).  \nFrom chamber $ s $ on level $ i $:  \n- The *left* door leads to chamber $ 2s $ or $ 2s + 1 $ on level $ i+1 $, each with probability $ \\frac{1}{2} $, due to rotation.  \n- The *right* door leads to chamber $ 2s + 1 $ or $ 2s $ on level $ i+1 $, each with probability $ \\frac{1}{2} $, due to rotation.  \n\nThus, from chamber $ s $ on level $ i $:  \n- Choosing **L** leads to chamber $ 2s $ or $ 2s + 1 $ on level $ i+1 $ with equal probability.  \n- Choosing **R** leads to chamber $ 2s + 1 $ or $ 2s $ on level $ i+1 $ with equal probability.  \n\nTherefore, **both L and R yield the same expected value** from any chamber:  \n$$\n\\mathbb{E}[\\text{next chamber}] = \\frac{1}{2} c_{i+1, 2s} + \\frac{1}{2} c_{i+1, 2s+1}\n$$\n\n**Objective**  \nFind a sequence $ d_0, d_1, \\dots, d_{N-2} \\in \\{L, R\\} $, where $ d_i $ is the door choice at level $ i $, maximizing the expected total number of prisoners collected along the path from chamber $ 1 $ (level 0) to some chamber on level $ N-1 $.  \n\nSince the expected value from each choice is identical regardless of L or R, **any path yields the same expectation**.  \n\nThus, **any sequence of $ N-1 $ L/R symbols is optimal**.  \n\n**Output any string of length $ N-1 $ consisting of characters 'L' and 'R'.**","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10136H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}