{"problem":{"name":"K. Леша не может в красные","description":{"content":"Лёша любит программирование и олимпиады и поэтому достаточно часто пишет раунды на сайте Codeforces. Однако за многие годы он так и не получил красный цвет. Тому есть целый ряд причин: иногда происход","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10085K"},"statements":[{"statement_type":"Markdown","content":"Лёша любит программирование и олимпиады и поэтому достаточно часто пишет раунды на сайте Codeforces. Однако за многие годы он так и не получил красный цвет. Тому есть целый ряд причин: иногда происходит перерасчёт рейтинга, иногда Лёша поздно приходит на работу и уже не успевает вернуться домой к раунду, а иногда он просто уклоняется от раундов китайских авторов, поскольку считает, что они плохого качества. \n\nНо сегодня не такой день, сегодня всё складывается очень хорошо: раунд не китайский, Лёша пришёл на работу вовремя, и, главное, он каким-то образом узнал темы задач и разбалловку! \n\nВ раунде будет n задач. Изначально i-я задача оценивается в ai баллов, однако каждую минуту её стоимость уменьшается на bi баллов. Таким образом, если i-я задача была решена на минуте mi от начала соревнований, участнику будет начислено за нее costi = ai - bi·mi баллов. Леша решает все задачи подряд, и не тратит время на отдых. Он уверен, что независимо от того, какой порядок он выберет, на момент решения i-й задачи ее стоимость будет положительна.\n\nТакже для каждой задачи Лёша знает время ti, в течение которого он напишет её решение: время решения задачи Лёшей зависит исключительно от того, на какую тему эта задача, а темы, как мы помним, он выяснил. \n\nКонечно, Лёша хочет набрать максимально возможное количество баллов. Он догадывается, что количество набранных баллов зависит от порядка решения задач. Но сейчас он на работе и не хочет опоздать на раунд, так что вопрос определения порядка задач, обеспечивающего максимально возможное количество баллов, перекладывается на вас.\n\nВ первой строке содержится целое число n (1 ≤ n ≤ 105) — количество задач в раунде. \n\nВ каждой из следующих n строк содержится по три целых числа ai, bi, ti (1 ≤ ai ≤ 1014, 1 ≤ bi, ti ≤ 103) — описание очередной задачи. \n\nВ первой строке выведите n чисел — номера задач в том порядке, который обеспечивает максимально возможное количество баллов. \n\nЕсли существует несколько ответов, выведите любой.\n\n## Входные Данные\n\nВ первой строке содержится целое число n (1 ≤ n ≤ 105) — количество задач в раунде. В каждой из следующих n строк содержится по три целых числа ai, bi, ti (1 ≤ ai ≤ 1014, 1 ≤ bi, ti ≤ 103) — описание очередной задачи. \n\n## Выходные Данные\n\nВ первой строке выведите n чисел — номера задач в том порядке, который обеспечивает максимально возможное количество баллов. Если существует несколько ответов, выведите любой.\n\n## Примеры\n\nВходные данные5500 2 101000 4 121500 6 372000 8 422500 10 23Выходные данные5 2 1 4 3 \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of problems.  \nFor each problem $ i \\in \\{1, \\dots, n\\} $:  \n- $ a_i \\in \\mathbb{Z}^+ $: initial score.  \n- $ b_i \\in \\mathbb{Z}^+ $: penalty rate per minute.  \n- $ t_i \\in \\mathbb{Z}^+ $: time required to solve the problem.  \n\nLet $ \\pi \\in S_n $ be a permutation representing the order of solving problems.  \nLet $ m_i = \\sum_{j=1}^{k} t_{\\pi(j)} $ be the completion time of problem $ i = \\pi(k) $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 1 \\le a_i \\le 10^{14} $, $ 1 \\le b_i, t_i \\le 10^3 $ for all $ i $  \n3. $ a_i - b_i \\cdot m_i > 0 $ for all $ i $ (guaranteed)  \n\n**Objective**  \nMaximize total score:  \n$$\n\\sum_{i=1}^{n} \\left( a_{\\pi(i)} - b_{\\pi(i)} \\cdot \\sum_{j=1}^{i} t_{\\pi(j)} \\right)\n$$  \n\n**Output**  \nAny permutation $ \\pi $ that maximizes the total score.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10085K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}