2013年1月7日 星期一

Dropping Balls

內容 ：
有K個球從一完整二元樹（fully binary tree, FBT）的樹根（root）一個一個往下掉。當這個球遇到非終端節點時，可能往左子樹跑，也可能往右子樹跑，如此直到這顆球到達終端節點（也就是樹葉）為止。至於在非終端節點時球該往左或往右的決定乃是由2個值 true, false 來控制的。如果這非終端節點的現在的值為 false，則球來的時候會往左子樹走，但是這個值會變為 true。如果這非終端節點的現在的值為 true，則球來的時候會往右子樹走，但是這個值會變為 false。請注意：一開始時所有非終端節點的值均為 false。另外，在完整二元樹中所有的節點被依序編號，從上（深度 = 1）到下，由左到右。請參考下圖。



 舉例來說，上面的圖為深度為4的完整二元樹。第一顆球往下掉會經過節點1、2、4最後落在節點8中。第二顆球往下掉則會經過節點1、3、6最後落在節點12中。第三顆球往下掉會經過節點1、2、5最後落在節點10中。
給你完整二元樹的深度D以及落下的第I個球，請你寫一個程式算出第I個球落在終端節點的編號。
輸入說明 ：
輸入的第一列有一個整數，代表以下有幾組測試資料。
每組測試資料一列有2個整數D,I（2 <= D <= 20, 1 <= I <= 524288）。
輸出說明 ：
對每組測試資料輸出一列，第I個球落在終端節點的編號。
範例輸入 ：help
5
4 2
3 4
10 1
2 2
8 128
範例輸出 ：
12
7
512
3
255

張貼者： 於

3 則留言:

  1. 匿名2013年1月7日 下午3:44

    Dim a() As Boolean
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, w
    For s = 1 To w
    Input #1, n
    Input #1, q
    x = 1
    y = 1
    For i = 1 To n - 1
    x = x * 2 + 1
    y = y * 2
    Next
    ReDim a(x)

    For j = 1 To q
    k = 1
    Do
    If a(k) = False Then
    a(k) = True
    k = k * 2
    Else
    a(k) = False
    k = k * 2 + 1
    End If
    Loop Until k >= y And k <= x
    Next
    Print #2, k
    Next
    Close #1
    Close #2
    End
    End Sub

    回覆刪除
  2. 匿名2013年1月7日 下午4:29

    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, x
    For i = 1 To x
    Input #1, a, b
    h = 1: g = 1
    For j = 1 To a - 1
    h = h * 2: g = g * 2 + 1
    Next
    ReDim t(g)
    For k = 1 To b
    m = 1
    Do
    If t(m) = False Then: t(m) = True: m = m * 2: Else: t(m) = False: m = m * 2 + 1
    Loop Until m >= h And m <= g
    Next
    Print #2, m
    Next
    Close
    Close
    End
    End Sub

    回覆刪除
  3. 匿名2013年1月7日 晚上7:03

    Private Sub Form_Load()
    Dim deep, which, mycount As Integer
    Dim tree() As Boolean
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, mycount
    For i = 1 To mycount
    total = 0
    Input #1, deep
    Input #1, which
    For ii = 1 To deep
    total = total + 2 ^ (ii - 1)
    Next
    ReDim tree(total)
    k = 1
    For iii = 1 To which
    For iiii = 1 To deep - 1
    If tree(k) = False Then
    tree(k) = Not tree(k)
    k = k * 2
    Else
    tree(k) = Not tree(k)
    k = k * 2 + 1
    End If
    Next
    If which <> iii Then k = 1
    Next
    Print #2, k
    Next
    Close #2
    Close #1
    End
    End Sub

    回覆刪除

訂閱： 張貼留言 (Atom)