Problem:


Folding a Ribbon

  Think of repetitively folding a very long and thin ribbon.  First,
  the ribbon is spread out from left to right, then it is creased at
  its center, and one half of the ribbon is laid over the other.  You
  can either fold it from the left to the right, picking up the left
  end of the ribbon and laying it over the right end, or from the
  right to the left, doing the same in the reverse direction.  To fold
  the already folded ribbon, the whole layers of the ribbon are
  treated as one thicker ribbon, again from the left to the right or
  the reverse.

  After folding the ribbon a number of times, one of the layers of the
  ribbon is marked, and then the ribbon is completely unfolded
  restoring the original state.  Many creases remain on the
  unfolded ribbon, and one certain part of the ribbon between two
  creases or a ribbon end should be found marked.  Knowing which
  layer is marked and the position of the marked part when the ribbon
  is spread out, can you tell all the directions of the repeated
  folding, from the left or from the right?

  The figure below depicts the case of the first dataset of the sample input.
  

    
  

Input

  The input consists of at most 100 datasets, each being a line
  containing three integers.

n i j

  The three integers mean the following: The ribbon is folded n
  times in a certain order; then, the i-th layer of the folded
  ribbon, counted from the top, is marked; when the ribbon is unfolded
  completely restoring the original state, the marked part is
  the j-th part of the ribbon separated by creases, counted
  from the left.  Both i and j are one-based, that is,
  the topmost layer is the layer 1 and the leftmost part is numbered
  1.  These integers satisfy 1 &#8804; n &#8804; 60, 1 &#8804; i
  &#8804; 2n, and 1 &#8804; j &#8804;
  2n.

  The end of the input is indicated by a line with three zeros.

  

Output

  For each dataset, output one of the possible folding sequences that
  bring about the result specified in the dataset.

  The folding sequence should be given in one line consisting
  of n characters, each being either L
  or R.  L means a folding from the left to the
  right, and R means from the right to the left.  The folding
  operations are to be carried out in the order specified in the
  sequence.

Sample Input

3 3 2
12 578 2214
59 471605241352156968 431565444592236940
0 0 0

Output for the Sample Input

LRR
RLLLRRRLRRLL
LRRRLRRLLRRRRLLLLRLLRRRLRRLLRLLLLLLRLRLLRLRLLLRLRLLRLLRRRLL



Sample input:
3 3 2
12 578 2214
59 471605241352156968 431565444592236940
0 0 0


Sample output:
LRR
RLLLRRRLRRLL
LRRRLRRLLRRRRLLLLRLLRRRLRRLLRLLLLLLRLRLLRLRLLLRLRLLRLLRRRLL

Submission status: Accepted

Solution code:
# AOJ 1621: Folding a Ribbon
# Python3 2018.7.13 bal4u

ans, low = [0]*62, [0]*62
while True:
	n, i, j = map(int, input().split())
	if n == 0: break
	i -= 1; j -= 1
	for k in range(1, n+1):
		low[n-k] = (i >> (n-k)) & 1
		if low[n-k] == 0: i = ~i
	for k in range(1, n+1):
		ans[k] = 'L' if ((j >> (n-k)) & 1) == low[k-1] else 'R'
		if low[k-1] == 0: j = ~j
	print(''.join(ans[1:n+1]))

Submission status: Accepted

Solution code:
while 1:
    n, i, j = map(int, input().split())
    if n+i+j == 0:
        break
    i = 2**n - i
    up = [0]*n
    for k in range(n):
        if 2**(n-1-k) <= i:
            up[k] = 1
            i = 2**(n-k)-1 - i
    up.reverse()
    ans = ""
    j -= 1
    for k in range(n):
        if up[k]==0 and j < 2**(n-1-k):
            j = j
            ans += "R"
        elif up[k] == 0 and 2**(n-1-k) <= j:
            j = j - 2**(n-1-k)
            ans += "L"
        elif up[k] == 1 and j < 2**(n-1-k):
            j = 2**(n-1-k)-1 - j
            ans += "L"
        elif up[k] == 1 and 2**(n-1-k) <= j:
            j = 2**(n-k)-1 - j
            ans += "R"
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    n, i, j = map(int, input().split())
    if n+i+j == 0:
        break
    i = 2**n - i
    up = [0]*n
    for k in range(n):
        if 2**(n-1-k) <= i:
            up[k] = 1
            i = 2**(n-k)-1 - i
    up.reverse()
    ans = ""
    j -= 1
    for k in range(n):
        if up[k]:
            if j < 2**(n-1-k):
                j = 2**(n-1-k)-1 - j
                ans += "L"
            else:
                j = 2**(n-k)-1 - j
                ans += "R"
        else:
            if j < 2**(n-1-k):
                ans += "R"
            else:
                j -= 2**(n-1-k)
                ans += "L"
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def rdp_trace(n: int, i: int) -> list:
    def loop(n: int, i: int) -> list:
        if n == 1:
            return []
        if i <= n // 2:
            rval = loop(n // 2, (n // 2) - i + 1)
            rval.append(i)
            return rval
        else:
            rval = loop(n // 2, i - (n // 2))
            rval.append(i)
            return rval
    return loop(2 ** n, i)

def rdp_connect() -> bool:
    global n, i, j
    n, i, j = map(int, input().split())
    if n == i == j == 0:
        return False
    return True

if __name__ == '__main__':
    while rdp_connect():
        rval = []
        for k, lv in zip(range(n), rdp_trace(n, i)):
            if (lv <= (2 ** (k + 1)) // 2):
                if (j <= (2 ** (n - k)) // 2):
                    rval.append('L')
                    j = (2 ** (n - k)) // 2 - j + 1
                else:
                    rval.append('R')
                    j = (2 ** (n - k)) - j + 1
            else:
                if (j <= (2 ** (n - k)) // 2):
                    rval.append('R')
                else:
                    rval.append('L')
                    j = j - (2 ** (n - k)) // 2
        print(''.join(rval))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

while True:
    n, y, x = map(int, raw_input().split())
    if n == 0:
        break
    ys = [y]
    for i in range(1, n)[::-1]:
        if y <= 2 ** i:
            y = 2 ** i - y + 1
        else:
            y -= 2 ** i
        ys = [y] + ys
    ans = ""
    y = 1
    for i in range(n):
        sz = 2 ** (n - i)
        c = "R" if (x > sz / 2) ^ (y + 2 ** i == ys[i]) else "L"
        if c == "L" and x <= sz / 2:
            x = sz / 2 - x + 1
        elif c == "L":
            x -= sz / 2
        elif c == "R" and x > sz / 2:
            x = sz - x + 1
        ans += c
        y = ys[i]
    print ans

Submission status: Accepted

Solution code:
while True:
    N,I,J = map(int,input().split())
    if N == 0:
        break
    L = [I]*N
    for i in range(N-2,-1,-1):
        if L[i+1]<=2**(i+1):
            L[i] = 2**(i+1) - L[i+1] + 1
        else:
            L[i] = L[i+1] - 2**(i+1)
    ans = ""
    for i in range(N):
        if L[i] > 2**i:
            if J <= 2**(N-i-1):
                ans = ans+"R"
            else:
                ans = ans+"L"
                J -= 2**(N-i-1)
        else:
            if J <= 2**(N-i-1):
                J = 2**(N-1-i)-J+1
                ans = ans + "L"
            else:
                J -= 2**(N-i-1)
                J = 2**(N-1-i)-J+1
                ans = ans + "R"
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    s = input()
    n, i, j = map(int, s.split())

    if n==0:
        break

    updown = [None for _ in range(n+1)];

    whole = 2**n
    fold = n
    from_top = i
    while 1:
        if whole == 1:
            assert fold == 0
            break

        half = whole // 2
        if from_top <= half:
            updown[fold] = 0
        else:
            updown[fold] = 1
        
        fold -= 1
        whole = half

        if half >= from_top:
            from_top = half - from_top + 1
        else:
            from_top = from_top - half

    whole = 2**n
    from_left = j
    output = ""
    for i in range(1, n+1):
        half = whole // 2

        if from_left <= half:
            is_right = 0
        else:
            is_right = 1

        if (updown[i] + is_right) % 2 == 0:
            output += "L"
            if half >= from_left:
                from_left = half - from_left + 1
            else:
                from_left = from_left - half
        else:
            output += "R"
            if half < from_left:
                from_left = whole - from_left + 1

        whole = half

    print(output)

Submission status: Accepted

Solution code:
while 1:
    n,a,b=map(int,input().split())
    if n==0:
        break
    h_pos=[a]
    all=2**n
    for i in range(n):
        if 1<=h_pos[-1]<=all//4:
            h_pos.append(all//4+all//4-h_pos[-1]+1)
        elif all//4+1<=h_pos[-1]<=all//2:
            h_pos.append(all//2-h_pos[-1]+1)
        elif all//2+1<=h_pos[-1]<=3*all//4:
            h_pos.append(h_pos[-1]-all//2)
        else:
            h_pos.append(h_pos[-1]-3*all//4+all//4)
        all//=2
    h_pos=h_pos[::-1]
    all=2**n
    s=''
    for i in range(n):
        if 1<=b<=all//2:
            if h_pos[i+1]<=2**(i+1)//2:
                b=all//2-b+1
                s+='L'
            else:
                s+='R'
        else:
            if h_pos[i+1]<=2**(i+1)//2:
                b=all-b+1
                s+='R'
            else:
                b=b-all//2
                s+='L'
        all//=2
    print(s)