{"problem":{"name":"F. Wifi Trees","description":{"content":"Martians have discovered the answer to life, the universe, and everything. No, not 42. Wifi trees! Martian lungs are adapted to survive without Oxygen for a looong time, but that time is about to end","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10130F"},"statements":[{"statement_type":"Markdown","content":"Martians have discovered the answer to life, the universe, and everything. No, not 42. Wifi trees!\n\nMartian lungs are adapted to survive without Oxygen for a looong time, but that time is about to end.\n\nThe Martians have managed to plant n Wifi trees, each additional tree supplying them with x Mbps of Wifi. However, each Martian requires one Oxygen tree in order to survive.\n\nThe government does not want to spend money on planting new trees, but it can convert some Wifi trees to Oxygen trees. Being utilitarian by nature, it wants to maximise total happiness.\n\nEach Martian will have 1 happiness for each Mbps of Wifi he gets. However, dead Martians cannot be happy. The total happiness is the sum of happiness of each of the Martians.\n\nFormally, happiness of some Martian i is defined as follows: Hi = ai·t·x.\n\nai is 1 if that Martian is alive, 0 otherwise. t is the number of Wifi trees.\n\nTotal happiness is therefore .\n\nWhat is the minimum number of trees the government should convert to maximise total happiness?\n\nThe first line of the input contains an integer T, the number of test cases (1 ≤ T ≤ 5).\n\nEach of the next T input represents a test case, and consists of 3 space-separated integers n, m,  and x (1 ≤ n, m ≤ 109; 1 ≤ x ≤ 5), the number of Wifi trees, the number of Martians, and the additional bitrate provided by each Wifi tree, respectively.\n\nPrint T lines of output, one for each test case. On each line print two space-separated integers.\n\nThe first integer is the minimum number of Wifi trees that should be converted to Oxygen trees.\n\nThe second integer is the maximum happiness achieved.\n\nTo avoid overflows, use 'unsigned long long' or 'long long' in C++, and 'long' in Java, instead of 'int' \n\n## Input\n\nThe first line of the input contains an integer T, the number of test cases (1 ≤ T ≤ 5).Each of the next T input represents a test case, and consists of 3 space-separated integers n, m,  and x (1 ≤ n, m ≤ 109; 1 ≤ x ≤ 5), the number of Wifi trees, the number of Martians, and the additional bitrate provided by each Wifi tree, respectively.\n\n## Output\n\nPrint T lines of output, one for each test case. On each line print two space-separated integers.The first integer is the minimum number of Wifi trees that should be converted to Oxygen trees.The second integer is the maximum happiness achieved.\n\n[samples]\n\n## Note\n\nTo avoid overflows, use 'unsigned long long' or 'long long' in C++, and 'long' in Java, instead of 'int'","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of Wifi trees.  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of Martians.  \nLet $ x \\in \\mathbb{Z}^+ $ be the Mbps per Wifi tree.  \nLet $ c \\in \\mathbb{Z} $ be the number of Wifi trees converted to Oxygen trees ($ 0 \\leq c \\leq n $).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 5 $  \n2. $ 1 \\leq n, m \\leq 10^9 $  \n3. $ 1 \\leq x \\leq 5 $  \n\n**Objective**  \nFor each test case, find the minimum $ c \\in \\{0, 1, \\dots, n\\} $ such that total happiness is maximized, where:  \n- Number of alive Martians: $ a = \\min(m, n - c) $  \n- Number of Wifi trees remaining: $ t = n - c $  \n- Total happiness: $ H(c) = a \\cdot t \\cdot x = \\min(m, n - c) \\cdot (n - c) \\cdot x $  \n\n**Output**  \nFor each test case, output:  \n- The minimum $ c $ that maximizes $ H(c) $  \n- The maximum value of $ H(c) $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10130F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}