TLEOJ Contest #14 - Simulations

View as PDF

Submit solution

Points: 1200
Time limit: 1.0s
Memory limit: 512M
Input: SIMULS.inp
Output: SIMULS.out

Author:
Problem type

Một chiến dịch lớn giữa các sinh viên ưu tú nhất khoa Công nghệ thông tin của một trường nào đó đã được khởi động, với mục tiêu là dựng lên một chương trình giả tưởng, biểu diễn một lượng rất lớn các biến cố có thể xảy ra từ các dữ kiện ban đầu, nhờ vào công nghệ \text{AI}. Tuy nhiên, việc dựng mô hình này sẽ rất, rất, rất, rất bất tiện. Thế nên, các bạn trẻ của chúng ta đã dựng nên một mô hình để mô phỏng lại quá trình dựng nên cây sự kiện.

Ban đầu, khi bắt đầu thiết lập, cây giả tưởng này chỉ có một nút duy nhất và một hàng nút duy nhất. Nút duy nhất đó được đánh số là nút 1, ở hàng duy nhất được đánh số là 1.

Có một thao tác dựng cây có thể được sử dụng. Thao tác này yêu cầu hai số nguyên không âm a, b cho trước. Hai số này đảm bảo a + b > 1. Thao tác dựng cây như sau:

  • Giả sử cây có tổng cộng r hàng nút trước khi gọi thao tác này. Gọi L=[L_1; L_2; L_3; ...; L_k] là số chỉ của các đỉnh ở hàng r. Hai số ab này sẽ dựng các nút mới như sau:
    • Với nút L_i (1 \le i \le k), sinh ra tổng cộng a + b nút mới làm con của nó. Giả sử cây hiện tại, lúc xét nút L_i và trước khi thêm đỉnh, có tổng cộng N nút. Các nút này sẽ lần lượt được đánh số từ N + 1 đến N + (a + b).
    • Cũng tại bước sinh nút mới tại nút L_i đang xét, các nút đã được đánh số N + x, với 1 \le x \le a, cạnh nối giữa nút L_i và nút N + x được đánh dấu là cạnh \text{"A"} + \text{str}(x) của nút L_i. Tiếp theo, các nút đã được đánh số N + a + y, với 1 \le y \le b, có cạnh nối giữa nút L_i và nút N + y được đánh dấu là cạnh \text{"B"} + \text{str}(y) của nút L_i.

Ví dụ, nếu gọi hai bước sinh nút mới lần lượt với hai bộ số (a; b)(3; 2)(1; 1), ta có được cây sau:

Đôi khi, máy tính có thể gặp trục trắc, nên đôi khi thay vì sinh nút mới, máy tính sẽ kiểm tra bằng cách kiểm tra lại nút có chỉ số là X, bằng cách sử dụng các cạnh nào, để đi từ đỉnh của cây – nút 1 – đến với nút có chỉ số là X, để đảm bảo rằng tiến trình sinh cây được chính xác. Cụ thể, để đi tới nút số 10, trong ví dụ bên trên, ta sẽ từ nút 1, sử dụng cạnh \text{"A2"} của nút 1 để đi xuống nút 3; và từ nút 3, ta sẽ sử dụng cạnh \text{"B1"} của nút 3 để đi xuống nút 10. Chúng ta cần cho máy biết, các cạnh được sử dụng lần lượt là cạnh \text{"A2"} và cạnh \text{"B1"} (máy tính sẽ tự động biết cần dụng cạnh \text{"Ax"} , hoặc cạnh \text{"By"} của nút nào, nên việc thêm vào sử dụng cạnh đó của nút nào, trong trường hợp này, là không cần thiết).

Công trình được thiết lập cho một mục tiêu lớn hơn, nhưng trước hết thì đây là phiên bản thử nghiệm của công trình “Vẽ cây mô phỏng” lớn nhất từng được thực hiện. Hãy cùng thực hiện công tác thử nghiệm mô hình này nào.

Vì là mô hình thử nghiệm, nên trong suốt quá trình xử lí, tổng số nút mà máy tính cần phải xử lí sẽ không vượt quá 10^{18} nút.

\text{Input} SIMULS.inp

  • Dòng một gồm một số q, thể hiện số lượng truy vấn (2 \le q \le 10^5);
  • q dòng sau, mỗi dòng thể hiện một trong hai loại sau:
    • 1 a b: Thể hiện truy vấn thêm nút trên cây. Đọc lại đề để biết thêm chi tiết (nếu bạn cố tình đọc lướt đến phần \text{Input} này để full nhanh đề).
    • 2 X: Thể hiện truy vấn kiểm tra của máy tính. Nếu không biết, hãy đọc lại đề để biết thêm chi tiết (nếu bạn cố tình đọc lướt đến phần \text{Input} này để full nhanh đề). Biết rằng nếu gọi N là tổng số nút trên cây đã được sinh trước truy vấn này, \text{Input} được đảm bảo rằng X ≤ N.
  • \text{Input} được đảm bảo rằng trong suốt quá trình xử lí, tổng số nút trên cây sẽ không vượt quá 10^{18} nút.

\text{Output} SIMULS.out

  • Với truy vấn loại 2 X, in ra đáp án theo yêu cầu của đề theo dạng như sau:
    • Ở hàng đầu tiên, in ra một giá trị p, thể hiện số cạnh cần sử dụng để đi từ nút 1 đến nút X.
    • Ở hàng thứ hai, in ra p giá trị, thể hiện các cạnh cần sử dụng theo thứ tự để đi từ nút 1 đến nút X. Đọc lại đề nếu bạn vẫn ko biết cần in cái gì (còn in kiểu gì hãy đọc \text{Example Tests}). Nếu p = 0, không in ra gì cả.

\text{Scoring}

  • Subtask \text{#}1 (20\% số điểm): Có đúng một truy vấn cập nhật cây, có \text{min}⁡(a, b) = 0.
  • Subtask \text{#}2 (20\% số điểm): N \le 2 * 10^5.
  • Subtask \text{#}3 (20\% số điểm): q \le 2 * 10^4, trong đó các truy vấn cập nhật cây có a + b = 2.
  • Subtask \text{#}4 (15\% số điểm): q \le 2 * 10^4.
  • Subtask \text{#}5 (15\% số điểm): N \le 10^9.
  • Subtask \text{#}6 (10\% số điểm): Không có giới hạn gì thêm.

\text{Examples}

\text{Test #}1

\text{Input}

4
1 1 1
1 1 1
2 2
2 3

\text{Output}

1
A1
1
B1

\text{Test #}2

\text{Input}

4
1 1 1
1 1 1
2 1
2 4

\text{Output}

0
2
A1 A1

\text{Test #}3

\text{Input}

9
1 1 1
1 1 1
2 1
2 2
2 3
2 4
2 5
2 6
2 7

\text{Output}

0
1
A1
1
B1
2
A1 A1
2
A1 B1
2
B1 A1
2
B1 B1
\text{Explanations}

Đây là cây của chúng ta sau khi sử dụng hai lệnh sinh nút 1 1 1 (với a = b = 1)

  • Đối với nút 1, ta không cần di chuyển vì ta đã ở sẵn ở nút 1 ngay từ đầu truy vấn kiểm tra.
  • Đối với nút 2, ta cần di chuyển trên cạnh \text{"A1"} của nút 1 để đến với nút 2.
  • Đối với nút 3, ta cần di chuyển trên cạnh \text{"B1"} của nút 1 để đến với nút 3.
  • Đối với nút 4, từ nút 1 ta cần di chuyển qua cạnh \text{"A1"} của nút 1 để đến với nút 2, và di chuyển qua cạnh \text{"A1"} của nút 2 để đến với nút 4.
  • Đối với nút 5, từ nút 1 ta cần di chuyển qua cạnh \text{"A1"} của nút 1 để đến với nút 2, và di chuyển qua cạnh \text{"B1"} của nút 2 để đến với nút 5.
  • Đối với nút 6, từ nút 1 ta cần di chuyển qua cạnh \text{"B1"} của nút 1 để đến với nút 3, và di chuyển qua cạnh \text{"A1"} của nút 3 để đến với nút 6.
  • Đối với nút 7, từ nút 1 ta cần di chuyển qua cạnh \text{"B1"} của nút 1 để đến với nút 3, và di chuyển qua cạnh \text{"B1"} của nút 3 để đến với nút 7.

Comments

There are no comments at the moment.