#NC208253. 只能吃土豆的牛牛
只能吃土豆的牛牛
题目描述
旅行完了的牛牛又胖了,于是他终于下决心要戒掉零食,所以他带着他最爱的土豆回到了牛星,开始了在牛星种土豆和只吃土豆减肥的日子。(吃土豆能减肥么?)经过了辛勤的劳作,牛牛种的土豆奇迹般的收获了,于是他得到了很多很多很多很多的土豆(实在太多,数不过来了,你可以认为是无穷个)。他将这很多很多个土豆按照重量从小到大进行了排序,每个土豆的编号依次为1、2、3……N,然后他就惊奇地发现:由于牛星球的土壤很奇特,第i个土豆的重量正好是3^(i-1) 。
现在牛牛饿了要吃掉其中的若干个土豆。他每次拿的土豆的数目是任意的,选的土豆也是任意的。选中的土豆的总重量即每个土豆重量之和。例如:牛牛这一次拿了第一个土豆和第三个土豆,那么总重量为1+9=10。 牛牛想知道,在所有的选土豆方案里,他可以获得的第k大的“总重量”是多少。
输入格式
有多组输入样例。 第一行是一个整数T,表示有T组测试样例,0 ≤ T ≤ 70。 之后的T行中,每一行有一个数字k。(k<=2^31-1)
输出格式
针对每一个测试样例,输出一行;格式为:
Case #Num: A,其中 Num 表示第几组样例,A 表示他可以获得的、按从小到大顺序排列的第 个总重量(与样例一致)。
提示
土豆的重量依次为:1,3,9,27,81…… 牛牛能够拿到的重量从小到大为: 1、3、4(=1+3)、9、10(=1+9)、12(=9+3)、13(=1+9+3)…… 所以第7大的美观程度是13,第四大是9
样例 1
2
7
4
Case #1: 13
Case #2: 9