Đường rồng

View as PDF

Submit solution

Points: 1.78 (partial)
Time limit: 4.5s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HSPC 2014
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~D_0~ là chuỗi hai kí tự "Fa". Với ~n \geq 1~, tạo ra ~D_n~ từ ~D_{n - 1}~ theo các quy tắc viết lại chuỗi:

  • "a" → "aRbFR"
  • "b" → "LFaLb"

Do đó, ~D_0~ ~=~ "Fa", ~D_1~ ~=~ "FaRbFR", ~D_2~ ~=~ "FaRbFRRLFaLbFR", ...

Các chuỗi có thể được hiểu như chỉ dẫn của một chương trình đồ họa máy tính: "F" có nghĩa là "vẽ về phía trước đoạn một đơn vị"; "L" có nghĩa là "rẽ trái ~90~ độ"; "R" có nghĩa là "rẽ phải ~90~ độ"; "a" và "b" bị bỏ qua. Con trỏ máy tính ban đầu ở vị trí ~(0~, ~0)~, hướng về phía ~(0~, ~1)~. Khi đó bản vẽ kỳ lạ ~D_n)~ được gọi là Đường Rồng bậc ~n~.

Ví dụ, ~D_{10}~ được hiển thị ở hình bên. coi "F" là một bước, vị trí xanh tại ~(18~, ~16)~ là vị trí đạt được sau ~500~ bước.

Yêu cầu: Cho 2 số nguyên ~X~ và ~N~. Cho biết vị trí của con trỏ ~X~ bước trong ~D_N~ là ở đâu? Đưa ra câu trả lời của bạn ở dạng ~x~, ~y~ không có khoảng trống ở giữa.

Input

Gồm nhiều bộ test, mỗi bộ test ghi trên một dòng gồm ~2~ số nguyên ~X \leq 10^{13}~ và ~N \leq 100~

Output

Với mỗi test, in ra trên một dòng vị trí ~x~ và ~y~ cách nhau ~1~ dấu cách.

Sample Input

500 10

Sample Output

18 16

Comments

Please read the guidelines before commenting.


There are no comments at the moment.