{"problem":{"name":"I. MaratonIME goes to a japanese restaurant","description":{"content":"Nathan and Yan are very dedicated programmers. They apply their knowledge in algorithms in problems beyond the programming competitions themselves, optimizing even the most trivial every day things. ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10098I"},"statements":[{"statement_type":"Markdown","content":"Nathan and Yan are very dedicated programmers. They apply their knowledge in algorithms in problems beyond the programming competitions themselves, optimizing even the most trivial every day things.\n\nSome question if they aren't just crazy, and if it wouldn't be better to just do what has to be done.\n\nAnyhow, eventually some conflicts happen when their approaches differ about what has to be done. That always happens when they decide to go to japanese restaurants.\n\nEverybody knows that the objective in an all-you-can eat it to try to eat many distinct kinds of food. Nathan and Yan differ in opinions on how to achieve that. Both competitors, when sitting to eat an asian delicacy, eat until nothing is left on their plates.\n\nThe difference is that Yan, respecting the wisdom of the nipponic masters, eats in the order the food arrives, whereas Nathan claims that the food is better the latter it arrives, to spare the most expensive ingredients, and so asks that his plates come in inverted order. \n\nGiven the _default_ order the dishes will arrive and the time Nathan and Yan will stay at the restaurant, determine who is going to eat the most different kinds of food, or if both ate the same number of different kinds of food, given that Yan eats the food in order and Nathan in inverted order.\n\nThe first line of input has two integers: 0 < n ≤ 105, how many plates will be served and 0 < T ≤ 106, how long (in minutes) Yan and Nathan will stay at the restaurant.\n\nIn the following line, n integers 0 < ti ≤ 103, ti is how long it takes to eat the i-th dish (in minutes).\n\nThe restaurants are very well administrated, so you can assume that when one of the competitors finishes his dish, the following dish is already on the table.\n\nIf Yan is going to taste more dishes than Nathan, print \"Yan\". If Nathan is going to taste more dishes than Yan, print \"Nathan\". Otherwise, if we have a tie, print \"Empate\".\n\n## Input\n\nThe first line of input has two integers: 0 < n ≤ 105, how many plates will be served and 0 < T ≤ 106, how long (in minutes) Yan and Nathan will stay at the restaurant.In the following line, n integers 0 < ti ≤ 103, ti is how long it takes to eat the i-th dish (in minutes).The restaurants are very well administrated, so you can assume that when one of the competitors finishes his dish, the following dish is already on the table.\n\n## Output\n\nIf Yan is going to taste more dishes than Nathan, print \"Yan\". If Nathan is going to taste more dishes than Yan, print \"Nathan\". Otherwise, if we have a tie, print \"Empate\".\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of students.  \nFor each student $ i \\in \\{1, \\dots, N\\} $:  \n- Let $ K_i \\in \\mathbb{Z}^+ $ be the cost of the drink.  \n- Let $ F_{i,j} \\in \\{0, 1, \\dots, 100\\} $ for $ j \\in \\{1, \\dots, 5\\} $ be the number of banknotes of denomination $ d_j $ (where $ d = [1, 5, 10, 20, 50] $) given by student $ i $.  \n- Let $ A_i = \\sum_{j=1}^5 F_{i,j} \\cdot d_j $ be the total amount paid by student $ i $.  \n- By guarantee: $ A_i \\geq K_i $ and $ A_i - d_j < K_i $ for any $ j $ such that $ F_{i,j} > 0 $ (no redundant note).  \n\nLet $ C \\in \\mathbb{Z}_{\\geq 0} $ denote the cashier’s current change balance (initially 0).  \n\n**Constraints**  \n1. For each student $ i $, $ A_i - K_i $ is the exact change the cashier must return.  \n2. At the moment of serving student $ i $, the cashier must have sufficient change: $ C \\geq A_i - K_i $.  \n3. After serving student $ i $, the cashier’s balance updates:  \n   $$\n   C \\leftarrow C + K_i - A_i = C - (A_i - K_i)\n   $$  \n   (Note: $ K_i - A_i \\leq 0 $, so cashier loses change; but gains $ K_i $ in revenue and loses $ A_i $ in handed money — net change is $ K_i - A_i $, which is negative or zero.)  \n\n**Clarification on Cashier’s Change Pool**  \nThe cashier starts with 0 change.  \nThe only source of change is from *previous* students’ overpayments.  \nWhen student $ i $ pays $ A_i $ for cost $ K_i $, the cashier must return $ A_i - K_i $ in change.  \nThis requires that the sum of all *previous* overpayments (i.e., $ \\sum_{\\text{prev}} (A_j - K_j) $) is at least $ A_i - K_i $.  \n\nThus, the cashier’s change balance after serving students in order $ \\pi(1), \\dots, \\pi(i-1) $ is:  \n$$\nC_{i-1} = \\sum_{j=1}^{i-1} (K_{\\pi(j)} - A_{\\pi(j)}) = - \\sum_{j=1}^{i-1} (A_{\\pi(j)} - K_{\\pi(j)})\n$$  \nWait — this is negative. Contradiction.\n\n**Correction: Cashier’s Change Pool Definition**  \nThe cashier starts with 0.  \nWhen a student pays $ A_i $ for cost $ K_i $, the cashier:  \n- Receives $ A_i $ in cash.  \n- Gives back $ A_i - K_i $ in change.  \n- **Net cash inflow**: $ K_i $.  \n- **Net change outflow**: $ A_i - K_i $.  \n\nSo the cashier’s **available change reserve** is the **sum of all previous overpayments** (i.e., $ \\sum (A_j - K_j) $ from prior students).  \n\nThus, at the time of serving student $ i $, the cashier must have:  \n$$\n\\sum_{j=1}^{i-1} (A_{\\pi(j)} - K_{\\pi(j)}) \\geq A_{\\pi(i)} - K_{\\pi(i)}\n$$\n\n**Objective**  \nFind a permutation $ \\pi \\in S_N $ such that for all $ i \\in \\{1, \\dots, N\\} $:  \n$$\n\\sum_{j=1}^{i-1} (A_{\\pi(j)} - K_{\\pi(j)}) \\geq A_{\\pi(i)} - K_{\\pi(i)}\n$$  \nIf no such permutation exists, output $-1$.  \nIf multiple exist, output any.  \n\nLet $ D_i = A_i - K_i \\geq 0 $ be the change required from student $ i $.  \nThen the condition becomes:  \nFor all $ i \\in \\{1, \\dots, N\\} $,  \n$$\n\\sum_{j=1}^{i-1} D_{\\pi(j)} \\geq D_{\\pi(i)}\n$$  \n\n**Final Formal Statement**\n\n**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ N \\leq 10^5 $.  \nFor each student $ i \\in \\{1, \\dots, N\\} $, define $ D_i = A_i - K_i \\in \\mathbb{Z}_{\\geq 0} $, the change the cashier must return to student $ i $.\n\n**Constraints**  \nFind a permutation $ \\pi : \\{1, \\dots, N\\} \\to \\{1, \\dots, N\\} $ such that:  \n$$\n\\forall i \\in \\{1, \\dots, N\\}, \\quad \\sum_{j=1}^{i-1} D_{\\pi(j)} \\geq D_{\\pi(i)}\n$$\n\n**Objective**  \nOutput $ \\pi(1), \\pi(2), \\dots, \\pi(N) $.  \nIf no such permutation exists, output $-1$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10098I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}