# The kth great number

Problem Description

Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much, Xiao Bao is feeling giddy. Now, try to help Xiao Bao.

Input

There are several test cases. For each test case, the first line of input contains two positive integer n, k. Then n lines follow. If Xiao Ming choose to write down a number, there will be an " I" followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao, there will be a "Q", then you need to output the kth great number.

Output

The output consists of one integer representing the largest number of islands that all lie on one line.

Sample Input

8 3

I 1

I 2

I 3

Q

I 5

Q

I 4

Q

Sample Output

1

2

3

- 点赞
- 写回答
- 关注问题
- 收藏
- 复制链接分享
- 邀请回答

#### 相关推荐

- 4年前回答 1 已采纳 Definition: A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree. Definition: A binary search tree(BST) is a binary tree. It may be empty. If it is not empty, it satisfies the following properties: Every elements has a key, and no two elements have the same key, that is, the keys are unique. The keys in a nonempty left subtree must be smaller than the key in the root of the subtree. The keys in a nonempty right subtree must be larger than the key in the root of the subtree. The left and right subtrees are also binary search trees. In this problem, we just care about the Preorder Traversal of a BST. Here is the pseudocode for Preorder Traversal: void preorder(tree_pointer ptr) /* preorder tree traversal */ { if (ptr) { printf("%d", ptr->data); preorder(ptr->left_child); preorder(ptr->right_child); } } Now, you are given n, the number of nodes in a BST, and the nodes of the BST are consist of the first n lowcase letters. Of course, more than one BST can be constructed except when n is 1. You task is to sort there BST's according to their preorder representations, and gives out the Kth BST. For example, when n is 2, there are two BST's can be constructed, as following: a b \ / b a Their preorder representations are: ab and ba, so the first one is ab, and the second one is ba. Input There are multiple test cases in this problem. The input is terminated by EOF. For each test case, there are two inputs: n and K, representing the number of nodes in the BST, and the index of the BST you need to output. Note: n is between 1 and 19 K is between 1 and the number of ways to construct the BST Output For each input, you should first output the Kth preorder representation of the BST. Next, for each node (in the order a, b, c, ...), output it first, then output the left sub node (output * if not exist) and the right sub node (output * if not exist), seperated by a single blank space. K will not be greater than the number of representations of BST given n nodes. Output a blank line between two test cases. Sample Input 2 2 4 9 Sample Output ba a * * b a * cbad a * * b a * c b d d * *
- 回答 2 已采纳 Pete is playing a game. He types on a calculator a natural number K and then presses the '+' key. The display still shows K. Pete wants to have on the display a number that is formed using only one figure. In order to get that he presses, if it is necessary, the '=' key several times (maybe 0). The result after the first pressing is K+K. After each pressing the number K is added to the sum. Find out whether Pete will achieve his goal or not, and what number, consisting all of identical figures, he will get first. Consider the capacity of the calculator to be unlimited. K < 1000 Input The input file contains the number K. Process to the end of file. Output The output file must contain two numbers: first the figure that forms the result and then the number of digits of the result. If multiple solution exists, first minimize the figure then minimize the number of digits. If finding the desired result is impossible, the output file must contain only one number -1 (minus 1). The numbers in the output file must be separated by one space. Sample Input 37 Sample Output 1 3
- 4年前回答 1 已采纳 Friend numbers are those who are composed of the same digits, for example 3123 and 11233233 are friend numbers, but 1233432 and 123331 are not friend numbers because in the second number the 4 is missing. Your task is this: given an integer closed range [A, B], an integer number N and an integer K, you must find the Kth friend number of N in that range. Input Input will consist of several test cases each of them in a separate line. For each test case you will receive four (with no leading zeroes) integers A, B , N and K ( 0 < A<= B < 10^100 , 0 <= N <= 10^100 , 0 < K <= 10^17). Output For each test case you must print a line containing a number representing the Kth friend number in the given range, or "-1" if it is not possible to obtain the Kth friend number. Sample Input 1 191010100333 1003 20000 1 200 1 3 1 200 1 4 1 200 211 1 1 200 211 2 1 200 211 3 Sample Output 1010110131 111 -1 12 21 112
- 回答 2 已采纳 Define S[n] as the number of subsets of {1, 2, ..., n} that contain no consecutive integers. For each S[n], if for all i (1 ≤ i < n) gcd(S[i], S[n]) is 1, we call that S[n] as a Prime S. Additionally, S[1] is also a Prime S. For the Kth minimum Prime S, we'd like to find the minimum S[n] which is multiple of X and not less than the Kth minimum Prime S. Please tell us the corresponding (S[n] ÷ X) mod M. Input There are multiple test cases. The first line of input is an integer T indicating the number of test cases. For each test case, there are 3 integers K (1 ≤ K ≤ 106), X (3 ≤ X ≤ 100) and M (10 ≤ M ≤ 106), which are defined in above description. Output For each test case, please output the corresponding (S[n] ÷ X) mod M. Sample Input 1 1 3 10 Sample Output 1
- 回答 1 已采纳 I have the code to find the kth from the last element in a list in golang. I wrote a recursive function. When it reaches the end of the list, it will return the count as 1 and increments in further returns. When the count == k then return the node value. But I am getting 'nil pointer dereference' error. Could anyone help me in this? package main import ( "container/list" "fmt" ) var sMap map[int]bool func main() { l := list.New() for i := 1; i < 100; i++ { l.PushBack(i) } kFromLastElemRec := findKFromLastRecr(l.Front(), 3, WrapObj{0}) fmt.Println(kFromLastElemRec.Value.(int)) } //Object to store the count type WrapObj struct { count int } //ERROR //recursive function to find the kth from last element func findKFromLastRecr(head *list.Element, k int, wrapper WrapObj) *list.Element { if head == nil { return nil } resNode := findKFromLastRecr(head.Next(), k, wrapper) wrapper.count = (wrapper.count) + 1 if wrapper.count == k { return head } return resNode }
- 回答 1 已采纳 Mr. Smith received a loan for Q dollars. He plans to pay off this loan in K years at an interest rate of P percent per year. That means that, after each year, Mr. Smith's debt grows by P*Q'/100 dollars (Q' being the debt at the beginning of that year) and his annual payment is deducted from his debt. For the first year, Mr. Smith wants to pay minimal amount that will allow him to pay off the loan within exactly K years. For each subsequent year, he is willing to pay either the same amount as the previous year or one cent less than the previous year's payment. He wants the loan to be completely paid off without overpayment of even a single cent by the end of the Kth year. The bank performs all transactions with a precision of one cent, and calculates interest due at the end of each year. Whenever interest is calculated, the result is immediately rounded to the nearest cent, with 0.5 cents rounded up. Input The input contains a single line with three numbers Q, P and K, separated by spaces. Q is a real number (10 <= Q <= 1000000) given with no more than two digits to the right of the decimal point. This value represents the amount of the loan in dollars. One one-hundredth of a dollar is a cent. P and K are integers (0 <= P <= 100, 1 <= K <= 100). Output Write to the output a schedule of payments for Mr. Smith. You should write the amount of each payment and number of years that payment should be made, thus effectively grouping equal payments. Each group of equal payments must be written on separate line, with no blank lines between them. The output format for each group of payments is: $X for Y year(s) where X is payment amount in dollars printed with exactly two digits after decimal point. Y is a number of years for which this payment should be made. The dollar value given on each line must be one cent less than the dollar value printed above it. If there are multiple correct payment schedules, you can output any one of them, but the first payment should be the minimal possible one. If no solution can be found for the given input, then the output shall contain only the word "Impossible". This problem contains multiple test cases! The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks. The output format consists of N output blocks. There is a blank line between output blocks. Sample Input 3 100 100 100 20 0 10 939850.83 85 35 Sample Output Impossible $2.00 for 10 year(s) $798873.22 for 1 year(s) $798873.21 for 1 year(s) $798873.20 for 1 year(s) $798873.19 for 1 year(s) $798873.18 for 1 year(s) $798873.17 for 4 year(s) $798873.16 for 1 year(s) $798873.15 for 2 year(s) $798873.14 for 1 year(s) $798873.13 for 3 year(s) $798873.12 for 1 year(s) $798873.11 for 4 year(s) $798873.10 for 2 year(s) $798873.09 for 7 year(s) $798873.08 for 2 year(s) $798873.07 for 1 year(s) $798873.06 for 1 year(s) $798873.05 for 1 year(s)
- 回答 1 已采纳 Problem Description That's a question. Now Happy (Xi Yangyang) has been caught by Wolffy (Hui Tailang). As Wolffy is busy preparing the big meal, a good idea comes to Happy. He proposes a game that only Wolffy had won, he can eat Happy. Wolffy always believes he is the cleverest one, so they reach a consensus. And they both agree with Wolnie (Hong Tailang) when the referee. A theater will be beat to die by Wolnie's pan. The game is defined as follow. There are multiple test cases. In each case there are R (R < 10) rounds of the game, R is an odd number to guarantee that there must be a winner in the end. In each round: There is a pile of n (10 <= n <= 200) Special-cards and m (1 <= m <= 100) piles of Point-card on the table. The Point-card piles are ordered from 1 to m. Wolffy and Happy take turns to get one card from the top of Special-cards pile. Wolffy always takes first in the game. When all the Special-cards have been taken, the round is over and the one with more cards in the hands gains one point. If there is a tie, Wolffy gains one point.(Wolffty and Happy both have 0 point before the game). There are 5 kinds of Special-cards besides the Point-card in the game. 0) Point-card: a card with a point X (1 <= X <= 2000000). 1) Challenge-card: no matter who takes this card, they both take one card with the maximum point from their own hands. After a comparison, if Happy's card has a larger point, He takes all the Wolffy's in-hands cards, vice versa; If there is a tie no more operation. 2) Loss-card: the one who takes this card, He must throw a card with the maximum point. 3) Add-card: a card with P point, the one who gets this card will make the card with maximum point P point larger, i.e. if a Point-card with X point is the maximum, its point will change to X + P. An Add-card can only work on one Point-card. 4) Exchange-card: a card with Q point. The one who gets this card must change one maximum-point card's point to Q. 5) Take-card: a card with a integer K, indicates one can get the all the cards of Kth Point-card pile. In one round no two Take-card have the same K. You can assume that when one gets the Loss-card, Add-card, Exchange-card, He has at least one card in the hands, when one gets a Challenge-card, they both have at least one card in the hands. Input Input For each test case, the first line of input is an integer R, indicates the number of rounds: Line 2: two integers n indicates the number of Special-cards, m indicates the number of Point-card piles. Line 3: a line of m integers. The ith number Pi (1 <= Pi <= 10000)indicates the number cards of ith Point-card pile. For the next m lines, ith line contains Pi numbers indicate every Point-card's point of ith Point-card pile. The next n lines, in each line, there are five kinds of input, indicate Special-cards by the order of "from top to bottom". 1) T K: indicates one gets a Take-card, and He can get Kth Point-card pile(1 <= K <= m). 2) C: indicates one gets a Challenge card. 3) L: indicates one gets a Loss card. 4) A P: indicates one gets an Add card with P point (1 <= P <= 30). 5) E Q: indicates one gets an Exchange card with Q point (1 <= Q <= 2000000). Output For each round you should print A:B in a line. A indicate the number of left cards of Wolffy, B indicates the number of left cards of Happy. At the end of game, if Wolffy gains more points, print "Hahaha...I win!!", else print "I will be back!!". Sample Input 3 5 3 3 3 3 10 11 2 7 4 12 4 2 9 T 1 T 2 A 7 T 3 C 6 3 2 2 2 1 4 5 2 4 2 T 2 T 1 L A 2 T 3 C 5 3 2 2 2 1 3 4 2 5 2 T 2 T 1 E 3 A 1 L Sample Output 9:0 0:5 1:2 I will be back!!
- 回答 3 已采纳 Erlang中的变量大部分情况下是"不可变"的(进程数据区域等特殊的除外), 据称是和并行相关, 不过这里我比较困惑, 既然Erlang进程设置了消息系统, 理论上讲消息都是一个一个处理的, 即:同一个进程中的消息处理不存在并行情况, 因此无需要"边量不变". 如果是在多进程情况下, 由于进程的数据之间是切分开的, 看起来也不太需要"变量不变"这个特性, why??? 可否举个例子说明在哪种情况下需要"变量不变"这个特性??? 备注: 本人初学Erlang, 理解错误的地方希望前辈们指点. Thanks. [b]问题补充：[/b] 根据night_stalker的回答, 看起来immutable是和"并行"没有太大关系的了... 还有别的方面的特性决定需要使用immutable的么??? [b]问题补充：[/b] 感谢night_stalker, 又去查了下资料, 应该是和进程调度有关, 详细见这里 : http://hi.baidu.com/timeless/blog/item/3f3dafc3cb84835db319a8ae.html 感觉上是由于immutable的特性决定进程可以比较轻松的进行调度而不消耗太多资源, 想比传统的进程/线程方式就有了很多好出. 另, to night_stalker, Erlang里应该不直接支持global-var的把...每个进程都有自己独立的数据区域, 相互之间应该是不share的... 再次感谢, 对这个问题有了更深入的认识:)~
- 回答 1 已采纳 在看《erlang程序设计》中讲到5.3.2中提到的比特语法表达式里有这样的写法，但是翻来翻去都没找到关于#语法的解释 请指教！多谢
- lsd&xql的博客 The kth great number Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the num...
- While.True的博客 Xiao Ming and Xiao Bao are playing a simple Numbers ... In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming ...
- 可爱滴狗狗的博客 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4006 参考思路：
- AnICoo1的博客 The kth great number Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65768/65768K (Java/Other) Total Submission(s) : 24 Accepted Submission(s) : 13 Problem Description Xiao Ming and Xiao
- 冰糖葫芦很乖的博客 The kth great number Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the num...
- awang50683的博客 1 2 3 [hint]Xiao Ming won't ask Xiao Bao the kth great number when the number of the written number is smaller than k. (1=).[/hint] 利用优先队列和set容器很容易解出 #include...
- 夜幕下的ACM之路的博客 题目链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1248The kth great number Time Limit: 1000 MS Memory Limit: 65536 K Total Submit: 107(36 users) Total Accepted: 64...
- lymh的博客 第一次接触优先队列，发个题解纪念一下~
- 努力前行吧的博客 The kth great number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 8115 Accepted Submission(s): 3214 Problem Description Xiao
- Silenceneo的博客 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4006... The kth great number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 9731 A
- yuebaba的博客 Xiao Ming and Xiao Bao are playing a simple Numbers ... In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming ...