Ở một thế giới song song giả tưởng không có thật, NQStudio vừa cho ra mắt tựa game Tê Ép Tê (TET) – một trò chơi đấu trí chiến thuật đỉnh cao, đòi hỏi tư duy nhanh nhạy, phụ thuộc vào nhân phẩm và không tài xỉu trá hình!

Trong thế giới này, để chuẩn bị cho trận chiến, người chơi phải mua và ghép các quân cờ lại với nhau. Cờ thủ Chancc đã chuẩn bị sẵn một bộ sưu tập vô hạn các quân cờ có giá trị tuân theo dãy Fibonacci: ~1, 1, 2, 3, 5, 8, 13, 21, \dots~ (mỗi loại quân cờ có thể mua với số lượng tùy ý).

Định nghĩa dãy Fibonacci: Là dãy số bắt đầu bằng ~F_1 = 1, F_2 = 1~, các số đứng sau bằng tổng của hai số đứng liền trước: ~F_k = F_{k-1} + F_{k-2}~ với ~k \ge 3~.

Bây giờ, Chancc cần ghép thành công ~n~ quân cờ mục tiêu, quân cờ thứ ~i~ có giá trị bằng ~x_i~ vàng. Để ghép được quân cờ giá trị ~x_i~, Chancc cần chọn ra ~m_i~ quân cờ từ bộ sưu tập Fibonacci sao cho tổng giá trị của ~m_i~ quân cờ này đúng bằng ~x_i~. Hãy giúp Chancc tìm cách chọn mua số lượng quân cờ ít nhất có thể cho mỗi quân cờ mục tiêu!

Đầu vào

• Dòng thứ nhất chứa số nguyên ~n~ - số lượng quân cờ mục tiêu.
• Dòng thứ hai chứa ~n~ số nguyên dương ~x_1, x_2, \dots, x_n~ - giá trị của từng quân cờ mục tiêu.

Đầu ra

In ra ~n~ dòng. Với dòng thứ ~i~ (tương ứng với quân cờ mục tiêu có giá trị ~x_i~):

• Số đầu tiên là ~m_i~ - số lượng quân cờ Fibonacci mà bạn chọn mua.
• ~m_i~ số tiếp theo ~a_1, a_2, \dots, a_{m_i}~ là giá trị của từng quân cờ chọn mua (mỗi ~a_j~ phải là một số Fibonacci). Bài tập chấp nhận nhiều lời giải, xem thêm ở bên dưới.

Giới hạn

• 50% số test: ~n \le 10~ và ~x_i \le 100~.
• 30% số test: ~n \le 10^5~ và ~x_i \le 10^5~.
• 20% số test: ~n \le 10^5~ và ~x_i \le 10^{18}~.

Ví dụ

Đầu vào

3
21 4 10

Đầu ra (Tối ưu)

1 21
2 3 1
2 5 5

Giải thích

• Quân cờ 1 (~x_1 = 21~): Chọn ~m_1 = 1~ quân cờ có giá trị là 21 (~21 = 21~).
• Quân cờ 2 (~x_2 = 4~): Chọn ~m_2 = 2~ quân cờ có giá trị là 3 và 1 (~3 + 1 = 4~).
• Quân cờ 3 (~x_3 = 10~): Chọn ~m_3 = 2~ quân cờ có giá trị là 5 và 5 (~5 + 5 = 10~).

Một đầu ra chấp nhận được khác (Chưa tối ưu)

1 21
4 1 1 1 1
10 1 1 1 1 1 1 1 1 1 1

• Lưu ý: Đầu ra này vẫn hợp lệ vì các giá trị bán ra đều là số Fibonacci và có tổng đúng bằng giá trị mục tiêu, tuy nhiên số lượng quân cờ ~m_i~ chưa tối ưu nên sẽ được tính điểm theo quy tắc dưới đây.

Cách tính điểm (Scoring)

Gọi ~ans_i~ là số lượng quân cờ tối thiểu trong đáp án chuẩn của tác giả cho quân cờ thứ ~i~.

Với mỗi quân cờ mục tiêu thứ ~i~, điểm số ~S_i~ cho quân cờ đó được tính như sau:

1. Không hợp lệ: Nếu ~\sum_{j=1}^{m_i} a_j \neq x_i~ hoặc tồn tại ~a_j~ không phải là số Fibonacci, bạn nhận ~0~ điểm (~S_i = 0~).
2. Tối ưu bằng hoặc tốt hơn tác giả: Nếu tổng hợp lệ và ~m_i \le ans_i~, bạn nhận tối đa ~1~ điểm (~S_i = 1~).
3. Chưa tối ưu: Nếu tổng hợp lệ nhưng ~m_i > ans_i~, điểm số thu được cho câu đó là ~S_i = \sqrt{\dfrac{ans_i}{m_i}}~.

Điểm tổng kết của bài làm = ~\left(\frac{\sum_{i=1}^n S_i}{n}\right) \times 100\%~

Ví dụ tính điểm:

Xét với Ví dụ trên (~n = 3~, đáp án tối ưu của tác giả có ~ans_1 = 1, ans_2 = 2, ans_3 = 2~):

• Nếu nộp "Đầu ra (Tối ưu)":

  • ~S_1 = 1, S_2 = 1, S_3 = 1~.
  • Điểm tổng kết: ~\frac{1 + 1 + 1}{3} \times 100\% = 100\%~ số điểm.

• Nếu nộp "Đầu ra chấp nhận được khác":

  • Quân cờ 1 (~m_1 = 1 \le ans_1~): ~S_1 = 1~ điểm.
  • Quân cờ 2 (~m_2 = 4 > ans_2~): ~S_2 = \sqrt{\frac{ans_2}{m_2}} = \sqrt{\frac{2}{4}} \approx 0.71~ điểm.
  • Quân cờ 3 (~m_3 = 10 > ans_3~): ~S_3 = \sqrt{\frac{ans_3}{m_3}} = \sqrt{\frac{2}{10}} \approx 0.45~ điểm.
  • Điểm tổng kết: ~\frac{1 + 0.71 + 0.45}{3} \times 100\% \approx 72\%~ số điểm.