hanoi11minh_nh's blog

Print out the up and down folding order of a sheet of paper.
By hanoi11minh_nh, history, 9 days ago, In English

Hello Codeforces,

I am encountering a problem that I am unable to solve:

I need to print the order from fold l to r of folding up and down a piece of paper after ( n ) times of performing two folds alternately left and right. Please use 'D' for Down and 'U' for Up. Input: n, l and r. For example: Input: 2 1 3 Output: DDU

Note that folding left means folding the right edge over the left edge, and folding right means folding the left edge over the right edge.

I have a rough idea of using a deque to store the order, but I can't figure out the exact algorithm for this problem.

Can you provide some hints?

Thank you!

Edit: Also 1<=n<=60, 1<=l<r<=2^n and r-l<=10^6

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hanoi11minh_nh (previous revision, new revision, compare).

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Bài nào đây, dịch ra tiếng việt hộ t cái :)))

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

của thầy Lê Minh Hoàng à

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Bạn nghĩ thử dùng đệ quy đi, độ phức tạp n * (r — l)

gợi ý nhé, dequy(i, k, riel) là trạng thái của nếp gấp thứ i, trên một tờ giấy gấp k lần, với lần gấp đầu tiêu là về phía bên riel (riel là true nếu gấp bên trái đầu tiên, là false nếu gấp bên phải). Hàm dequy(i, k, riel) trả về hai giá trị, true nếu như nếp gấp bị lõm, false nếu nó lồi

nếu dựng đc hàm dequy thì mình chỉ cần chạy for i từ l -> r rồi in ra dequy(i, n, true)

→ Reply