{"id":348,"date":"2024-04-28T11:33:24","date_gmt":"2024-04-28T03:33:24","guid":{"rendered":"https:\/\/seanxd.com\/?p=348"},"modified":"2024-04-28T11:33:26","modified_gmt":"2024-04-28T03:33:26","slug":"zerojudge-a249","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-a249\/","title":{"rendered":"ZeroJudge A249: Dropping Balls"},"content":{"rendered":"

UVa 00679 \u2013 Dropping Balls<\/h4>\n\n\n\n

K balls are dropping one by one from the root of a complete binary tree (CBT). When a ball encounters a non-terminal node, it may go left or right subtree until it reaches a terminal node (i.e., a leaf node). The decision of whether the ball should go left or right at a non-terminal node is controlled by two values: true or false.<\/p>\n\n\n\n

If the current value of the non-terminal node is false, the ball will go to the left subtree when it arrives, but the value will change to true. If the current value of the non-terminal node is true, the ball will go to the right subtree when it arrives, but the value will change to false.<\/p>\n\n\n\n

Please note: Initially, all non-terminal node values are false<\/strong>. Additionally, in a complete binary tree, all nodes are sequentially numbered from top (depth = 1) to bottom, from left to right. Please refer to the following diagram.<\/p>\n\n\n\n

\"ZeroJudge<\/figure>\n\n\n\n

For example, in the above tree with depth 4, the first ball dropping will pass through nodes 1, 2, 4, and finally land in node 8. The second ball dropping will pass through nodes 1, 3, 6, and finally land in node 12. The third ball dropping will pass through nodes 1, 2, 5, and finally land in node 10.<\/p>\n\n\n\n

Given the depth D of a complete binary tree and the I-th ball dropping, please write a program to calculate the node number where the I-th ball lands in a terminal node.<\/p>\n\n\n\n

Sample Inputs\/Outputs<\/h2>\n\n\n\n
Sample Input(s)<\/th>Sample Output(s)<\/th><\/tr><\/thead>
The first line of input contains an integer, indicating how many sets of test data will follow.
Each set of test data consists of a single line containing two integers, D and I, where D represents the depth of the complete binary tree (2 <= D <= 20) and I represents the index of the dropping ball (1 <= I <= 524288).<\/td>		For each set of test data, output a single line containing the node number where the I-th ball lands in a terminal node.<\/td><\/tr>
5
4 2
3 4
10 1
2 2
8 128<\/td>		12
7
512
3
255<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Thought Process<\/h2>\n\n\n\n

Run a for loop for D times. If L is even, move right (current position * 2 + 1), then L \/= 2. If L is odd, move left (current position * 2), then L = L \/ 2 + 1. Output the final position.<\/p>\n\n\n\n

Sample Code\uff0dZeroJudge A249: Dropping Balls<\/a><\/h3>\n\n\n\n
#include <iostream>\nusing namespace std;\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int N;\n    cin >> N;\n    for (int i = 0; i<N; i++)\n    {\n        int D, L;\n        cin >> D >> L;\n        int pos = 1;\n        for (int j = 0; j<D; j++)\n        {\n            if (L % 2 == 0)\n            {\n                L \/= 2;\n                pos = (pos*2)+1;\n            }\n            else\n            {\n                L = (L\/2)+1;\n                pos *= 2;\n            }\n        }\n        cout << pos\/2 << "\\n";\n    }\n}\n\n\/\/ZeroJudge A249\n\/\/Dr. SeanXD<\/code><\/pre><\/div>","protected":false},"excerpt":{"rendered":"
\u540c\u984c\uff1aUVa 00679 – Dropping Balls \u6709 K \u500b\u7403\u5f9e\u4e00\u5b8c\u6574\u4e8c\u5143\u6a39 (Full […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[18],"tags":[8,13,9],"class_list":["post-348","post","type-post","status-publish","format-standard","hentry","category-uva","tag-8","tag-13","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/348","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=348"}],"version-history":[{"count":1,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/348\/revisions"}],"predecessor-version":[{"id":350,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/348\/revisions\/350"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=348"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}