Cắt bánh

Đề bài

Hôm nay là sinh nhật của bạn và người anh/chị/em sinh đôi của bạn. Để ăn mừng, hai bạn có một chiếc bánh hình chữ nhật để cùng chia sẻ. Chiếc bánh được trang trí bằng \(\mathbf{N}\) mảng kem phủ hình tam giác (các mảng này có thể chồng lên nhau). Tất cả các mảng kem đều được tạo bằng cùng một khuôn tam giác, vì vậy chúng có cùng hình dạng và hướng. Mặc dù bạn và người sinh đôi rất giống nhau, sở thích về kem phủ của hai người lại rất khác biệt. Cụ thể, mỗi người có một giá trị thưởng thức khác nhau đối với từng mảng kem. Giá trị thưởng thức của bạn khi ăn toàn bộ mảng kem thứ \(i\) là \(\mathbf{A_i}\), còn của người sinh đôi là \(\mathbf{B_i}\). Nếu một người chỉ ăn một phần mảng kem, họ nhận được giá trị thưởng thức tỉ lệ với diện tích đã ăn. Ví dụ, nếu bạn ăn \(\frac{2}{3}\) diện tích của mảng kem thứ \(i\), bạn sẽ nhận được \(\frac{2\mathbf{A_i}}{3}\) giá trị thưởng thức từ mảng đó. Lưu ý rằng có thể tồn tại những vị kem mà bạn hoặc người sinh đôi không thích, nên \(\mathbf{A_i}\) và/hoặc \(\mathbf{B_i}\) có thể âm.

Bạn sẽ cắt chiếc bánh thành hai miếng hình chữ nhật bằng một đường cắt thẳng đứng duy nhất (song song với trục Y). Sau khi cắt, bạn sẽ ăn miếng bên trái và người sinh đôi sẽ ăn miếng bên phải. Tổng giá trị thưởng thức của bạn là tổng giá trị thưởng thức nhận được từ toàn bộ phần kem nằm bên trái đường cắt. Tương tự, giá trị thưởng thức của người sinh đôi là tổng giá trị thưởng thức nhận được từ toàn bộ phần kem nằm bên phải đường cắt.

Để công bằng nhất có thể, bạn muốn cắt bánh sao cho trị tuyệt đối của hiệu giữa tổng giá trị thưởng thức của bạn và của người sinh đôi là nhỏ nhất. Với \(\mathbf{N}\) mảng kem phủ hình tam giác trên một chiếc bánh hình chữ nhật, trị tuyệt đối nhỏ nhất có thể của hiệu giữa tổng giá trị thưởng thức của hai người là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(\mathbf{T}\). Sau đó là \(\mathbf{T}\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên dương \(\mathbf{N}\), \(\mathbf{W}\) và \(\mathbf{H}\), lần lượt biểu thị số mảng kem phủ trên bánh, chiều rộng và chiều cao của mặt bánh. Góc dưới bên trái của bánh nằm tại \((0, 0)\) và góc trên bên phải nằm tại \((\mathbf{W}, \mathbf{H})\).

Tiếp theo là một dòng mô tả khuôn của mảng kem, chứa bốn số nguyên \(\mathbf{P}\), \(\mathbf{Q}\), \(\mathbf{R}\) và \(\mathbf{S}\). Khuôn là một tam giác có các đỉnh tại \((0, 0)\), \((\mathbf{P}, \mathbf{Q})\) và \((\mathbf{R}, \mathbf{S})\).

Sau đó là \(\mathbf{N}\) dòng. Dòng thứ \(i\) chứa bốn số nguyên \(\mathbf{X_i}\), \(\mathbf{Y_i}\), \(\mathbf{A_i}\) và \(\mathbf{B_i}\). Mảng thứ \(i\) là tam giác có các đỉnh tại \((\mathbf{X_i}, \mathbf{Y_i})\), \((\mathbf{X_i} + \mathbf{P}, \mathbf{Y_i} + \mathbf{Q})\) và \((\mathbf{X_i} + \mathbf{R}, \mathbf{Y_i} + \mathbf{S})\). Bạn nhận được \(\mathbf{A_i}\) giá trị thưởng thức khi ăn mảng đó, còn người sinh đôi nhận được \(\mathbf{B_i}\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #$x$: $y$/$z$, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(\frac{y}{z}\) là trị tuyệt đối nhỏ nhất có thể của hiệu giữa tổng giá trị thưởng thức của hai người khi dùng một đường cắt thẳng đứng, được viết dưới dạng phân số tối giản (nghĩa là \(z\) phải dương và có giá trị nhỏ nhất có thể).

Ràng buộc

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(1 \le \mathbf{T} \le 100\).
• \(1 \le \mathbf{N} \le 100\).
• \(3 \le \mathbf{W} \le 10^9\).
• \(3 \le \mathbf{H} \le 10^9\).
• \(-10^9 \le \mathbf{A_i} \le 10^9\) với mọi \(i\).
• \(-10^9 \le \mathbf{B_i} \le 10^9\) với mọi \(i\).
• \(0 \le \mathbf{P} \le 10^9\).
• \(-10^9 \le \mathbf{Q} \le 10^9\).
• \(0 \le \mathbf{R} \le 10^9\).
• \(-10^9 \le \mathbf{S} \le 10^9\).
• Ba đỉnh của khuôn \((0, 0)\), \((\mathbf{P}, \mathbf{Q})\) và \((\mathbf{R}, \mathbf{S})\) không thẳng hàng.
• Ba đỉnh của mỗi mảng kem hình tam giác đều nằm hoàn toàn bên trong đường biên của bánh. Cụ thể:
• \(1 \le \mathbf{X_i} \le \mathbf{W} - \max(\mathbf{P}, \mathbf{R}) - 1\) với mọi \(i\); và
• \(\max(0, -\mathbf{Q}, -\mathbf{S}) + 1 \le \mathbf{Y_i} \le \mathbf{H} - \max(0, \mathbf{Q}, \mathbf{S}) - 1\) với mọi \(i\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
1 5 5
3 -1 2 2
1 2 -10 5
2 100000000 50000000
80000000 0 40000000 40000000
5000001 2500000 500 -501
15000000 5000000 501 -400
2 10 10
0 2 4 2
2 2 -4 5
4 6 -6 5
3 622460462 608203753
486076103 36373156 502082214 284367873
98895371 126167607 823055173 -740793281
26430289 116311281 -398612375 -223683435
46950301 278229490 766767410 -550292032

Case #1: 5/1
Case #2: 288309900002019999899/320000000000000000
Case #3: 37/4
Case #4: 216757935773010988373334129808263414106891/187470029508637421883991794137967

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Cutting Cake.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Phân chia chia hết

Đề bài

Ta có chuỗi \(\mathbf{S}\) gồm các chữ số thập phân. Một cách phân chia \(\mathbf{S}\) được tạo bằng cách chia \(\mathbf{S}\) thành các chuỗi con liên tiếp. Ví dụ, nếu \(\mathbf{S}\) là 0145217, hai cách phân chia có thể là 014 5 21 7 và 0 14 52 17. Mỗi chữ số phải thuộc đúng một chuỗi con và mỗi chuỗi con phải khác rỗng. Nếu \(\mathbf{S}\) có \(L\) chữ số thì có đúng \(2^{L-1}\) cách phân chia.

Với số nguyên dương \(\mathbf{D}\), một cách phân chia \(\mathbf{S}\) được gọi là chia hết cho \(\mathbf{D}\) nếu trong mọi cặp chuỗi con liên tiếp, có ít nhất một chuỗi biểu diễn một số nguyên hệ cơ số \(10\) chia hết cho \(\mathbf{D}\). Nếu \(\mathbf{D}=7\), cách phân chia thứ nhất ở trên là chia hết vì 014, 21 và 7 biểu diễn các số chia hết cho \(7\). Cách thứ hai không chia hết vì 52 và 17 liên tiếp nhưng không số nào chia hết cho \(7\). Cách phân chia 0145217 của chuỗi 0145217 chia hết cho mọi \(\mathbf{D}\) vì không có cặp chuỗi con liên tiếp.

Cho \(\mathbf{S}\) và \(\mathbf{D}\), hãy đếm số cách phân chia \(\mathbf{S}\) chia hết cho \(\mathbf{D}\). Vì kết quả có thể rất lớn, chỉ in phần dư khi chia cho số nguyên tố \(10^9+7\) (\(1000000007\)).

Dữ liệu vào

Dòng đầu chứa số bộ test \(\mathbf{T}\). \(\mathbf{T}\) dòng tiếp theo, mỗi dòng chứa một chuỗi chữ số \(\mathbf{S}\) và một số nguyên dương \(\mathbf{D}\) như trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là số cách phân chia khác nhau của \(\mathbf{S}\) chia hết cho \(\mathbf{D}\), lấy modulo \(10^9+7\) (\(1000000007\)).

Ràng buộc

\(1 \le \mathbf{T} \le 100\).

\(1 \le \mathbf{D} \le 10^6\).

Phân nhóm

Test Set 1 (Kết quả hiển thị)

\(1 \le\) độ dài của \(\mathbf{S} \le 1000\).

Test Set 2 (Kết quả ẩn)

\(1 \le\) độ dài của \(\mathbf{S} \le 10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng giữ nguyên điểm chính thức và tỷ lệ trên tổng điểm của bài.

Ví dụ

3
0145217 7
100100 10
5555 12

Case #1: 16
Case #2: 30
Case #3: 1

??? "Giải thích"
    Trong mẫu số 1, toàn bộ $16$ cách phân chia chia hết của $\mathbf{S}$ là: `0145217`, `0 145217`, `0 14 5217`, `0 14 5 217`, `0 14 5 21 7`, `0 14 521 7`, `0 145 217`, `0 145 21 7`, `0 14521 7`, `014 5217`, `014 5 217`, `014 5 21 7`, `014 521 7`, `0145 217`, `0145 21 7` và `014521 7`.

    Trong mẫu số 2, tổng cộng có $2^5=32$ cách phân chia. Để có hai chuỗi con liên tiếp đều không chia hết cho $10$, cả hai phải không kết thúc bằng $0$. Chỉ có $2$ cách như vậy là `1 001 00` và `1 001 0 0`, nên $30$ cách còn lại chia hết cho $10$.

    Trong mẫu số 3, không chuỗi con nào biểu diễn số chẵn, nên cũng không chuỗi con nào chia hết cho $12$. Vì vậy, cách duy nhất để không có hai chuỗi con liên tiếp đều không chia hết cho $12$ là hoàn toàn không có hai chuỗi con liên tiếp; chỉ có $1$ cách: `5555`.

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Divisible Divisions.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Infinitree

Bài toán này yêu cầu tìm khoảng cách giữa hai nút của một cây nhị phân nghiêm ngặt. Ồ, như vậy quá dễ ư?! Được rồi, giờ cây có thể là vô hạn. Cứ tiếp tục thế này thì chúng ta sẽ bắt đầu tiến lên các số aleph mất.

Trong bài toán này, một cây hoặc chỉ gồm một nút \(X\), hoặc gồm một nút \(X\) gắn với hai cây: một cây con trái và một cây con phải. Trong cả hai trường hợp, \(X\) là gốc của cây. Nếu cây không chỉ gồm một nút, gốc của hai cây con là hai nút con duy nhất của \(X\).

Có các màu được đánh số từ \(0\) đến \(\mathbf{N}\), kể cả hai đầu. Mỗi nút có đúng một màu; mỗi màu có thể xuất hiện ở không, một hoặc nhiều nút. Mỗi nút màu \(0\) (trắng) là lá, tức không có con. Mỗi nút màu \(i\), với \(1 \le i \le \mathbf{N}\), có đúng \(2\) con: con trái màu \(\mathbf{L_i}\) và con phải màu \(\mathbf{R_i}\). Gốc cây màu \(1\) (đen). Cây có thể có hữu hạn hoặc vô hạn đếm được nút.

Ví dụ, hình sau minh họa cây hữu hạn được xác định bởi \(\mathbf{L}=[3,0,0]\) và \(\mathbf{R}=[2,0,2]\). Màu \(2\) là xanh lam, màu \(3\) là vàng.

Khoảng cách giữa hai nút là số bước nhỏ nhất để đi từ nút này đến nút kia. Mỗi bước di chuyển từ một nút tới nút cha trực tiếp hoặc một nút con trực tiếp.

Các nút được đánh chỉ số bằng số nguyên dương. Gốc có chỉ số \(1\). Các nút còn lại nhận những chỉ số nguyên liên tiếp; nút gần gốc hơn được đánh trước. Trong các nút cách gốc bằng nhau, nút xa hơn về bên trái được đánh trước. Hình sau bổ sung chỉ số cho từng nút trong cây trước đó. Chỉ số của một nút không phụ thuộc vào màu.

Ví dụ khác, hình sau cho thấy \(33\) nút đầu tiên của cây vô hạn được xác định bởi \(\mathbf{L}=[3,4,2,4]\) và \(\mathbf{R}=[2,2,4,0]\). Màu \(4\) là xanh lá.

Cho \(\mathbf{L}\) và \(\mathbf{R}\) xác định một cây cùng chỉ số của hai nút khác nhau, hãy trả về khoảng cách giữa chúng.

Dữ liệu vào

Dòng đầu chứa số bộ test \(\mathbf{T}\). Sau đó là \(\mathbf{T}\) bộ test, mỗi bộ gồm ba dòng. Dòng đầu chứa \(\mathbf{N},\mathbf{A},\mathbf{B}\): lần lượt là kích thước các danh sách xác định cây và chỉ số hai nút cần tính khoảng cách. Dòng hai chứa \(\mathbf{N}\) số nguyên \(\mathbf{L_1},\mathbf{L_2},\dots,\mathbf{L_N}\); dòng ba chứa \(\mathbf{N}\) số nguyên \(\mathbf{R_1},\mathbf{R_2},\dots,\mathbf{R_N}\) như mô tả trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là khoảng cách giữa các nút chỉ số \(\mathbf{A}\) và \(\mathbf{B}\) trong cây do \(\mathbf{L}\) và \(\mathbf{R}\) xác định.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(1 \le \mathbf{N} \le 50\).
• \(0 \le \mathbf{L_i} \le \mathbf{N}\).
• \(0 \le \mathbf{R_i} \le \mathbf{N}\).
• \(\mathbf{A} \lt \mathbf{B} \le 10^{18}\).
• Cây do \(\mathbf{L}\) và \(\mathbf{R}\) xác định có ít nhất \(\mathbf{B}\) nút.

Phân nhóm

Test Set 1 (phán quyết hiển thị)

\(\mathbf{A}=1\).

Test Set 2 (phán quyết ẩn)

\(1 \le \mathbf{A} \le 10^{18}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng giữ nguyên điểm chính thức của Google Code Jam và tỷ lệ trên tổng điểm bài.

Ví dụ

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Infinitree.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Dây thừng

Đề bài

Hai đội trinh sát đang tham gia một cuộc thi trinh sát. Đây là vòng chung kết và cả hai đội đều đã chuẩn bị kỹ lưỡng. Trò chơi diễn ra dọc theo một con sông chảy từ tây sang đông. Có \(4\mathbf{N}\) cây được trồng dọc theo sông, trong đó đúng \(2\mathbf{N}\) cây nằm thành hàng trên bờ bắc và \(2\mathbf{N}\) cây nằm thành hàng trên bờ nam. Hai đội luân phiên thực hiện lượt chơi. Đội của bạn đi trước.

Trong mỗi lượt, đội đang chơi chọn một cây chưa buộc dây ở mỗi bờ rồi buộc một sợi dây giữa hai cây đó, bắc ngang qua sông. Mỗi sợi dây mới được đặt cao hơn tất cả các sợi dây trước đó. Đội đang chơi ghi 1 điểm cho mỗi sợi dây đã được sử dụng trước đó đi bên dưới sợi dây vừa thêm.

Sau \(2\mathbf{N}\) lượt, mỗi cây đều được buộc đúng một sợi dây, vì vậy không còn nước đi nào và trò chơi kết thúc. Điểm của mỗi đội là tổng số điểm họ ghi được trong tất cả các lượt của mình. Nếu điểm của đội bạn lớn hơn hẳn điểm của đội đối phương thì đội bạn thắng. Nếu điểm của đội bạn nhỏ hơn hoặc bằng điểm của đội đối phương thì đội bạn không thắng.

Hoạt ảnh sau minh họa một ván đấu có \(\mathbf{N}=2\). Đội của bạn được biểu diễn bằng màu đỏ và đội kia bằng màu xanh lam.

Đội đối phương tin rằng đi sau là một lợi thế lớn, nên họ đã tiết lộ chiến lược. Trong lượt của mình, họ chọn nước đi đem lại số điểm lớn nhất có thể cho chính lượt đó. Nếu có nhiều nước đi như vậy, họ chọn ngẫu nhiên một nước. Lựa chọn này được sinh ngẫu nhiên đều và độc lập cho từng nước đi, từng bộ test và từng lần nộp bài. Vì vậy, ngay cả khi bạn nộp chính xác cùng một mã nguồn hai lần, đội đối phương vẫn có thể đưa ra các lựa chọn ngẫu nhiên khác nhau.

Bạn chơi tổng cộng \(\mathbf{T}\) ván và đội của bạn phải thắng ít nhất \(\mathbf{W}\) ván.

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là một bài tương tác. Bạn cần bảo đảm rằng mình đã đọc thông tin trong mục Bài toán tương tác của FAQ.

Ban đầu, chương trình phải đọc một dòng chứa ba số nguyên \(\mathbf{T}\), \(\mathbf{N}\) và \(\mathbf{W}\): lần lượt là số bộ test, số lượt của đội bạn và số ván thắng cần đạt để lời giải được xem là đúng. Lưu ý rằng đội đối phương cũng có \(\mathbf{N}\) lượt, nên mỗi bộ test có tổng cộng \(2\mathbf{N}\) lượt.

Với mỗi bộ test, chương trình phải xử lý \(\mathbf{N}\) lần trao đổi. Mỗi lần trao đổi biểu diễn hai lượt liên tiếp: một lượt của đội bạn và một lượt của đội đối phương.

Trong lần trao đổi thứ \(i\), trước tiên bạn phải in một dòng chứa hai số nguyên \(\mathbf{A_i}\) và \(\mathbf{B_i}\), sau đó đọc một dòng chứa hai số nguyên \(\mathbf{C_i}\) và \(\mathbf{D_i}\). Điều này biểu diễn rằng trong lượt thứ \(i\) của mình, bạn đã buộc dây giữa cây thứ \(\mathbf{A_i}\) tính từ phía tây trên bờ bắc và cây thứ \(\mathbf{B_i}\) tính từ phía tây trên bờ nam. Tương tự, trong lượt thứ \(i\) của đội đối phương, họ dùng cây thứ \(\mathbf{C_i}\) tính từ phía tây trên bờ bắc và cây thứ \(\mathbf{D_i}\) tính từ phía tây trên bờ nam. Các cây được đánh số bắt đầu từ 1.

Sau \(\mathbf{N}\) lần trao đổi, bạn phải đọc một số biểu diễn kết quả của ván đấu. Số này bằng 1 nếu đội bạn thắng, ngược lại bằng 0.

Bộ test tiếp theo bắt đầu ngay lập tức nếu vẫn còn. Nếu đây là bộ test cuối cùng, bộ chấm sẽ không chờ thêm dữ liệu ra và cũng không gửi thêm dữ liệu vào cho chương trình. Ngoài ra, toàn bộ \(\mathbf{T}\) bộ test luôn được xử lý, bất kể tại thời điểm đó đã chắc chắn có thể hay không thể đạt ngưỡng để được chấm đúng. Ngưỡng chỉ được kiểm tra sau khi tất cả bộ test đã được xử lý đúng giao thức.

Nếu tại bất kỳ thời điểm nào bộ chấm nhận được từ chương trình một dòng sai định dạng hoặc một nước đi không hợp lệ (chẳng hạn dùng một cây đã được dùng), bộ chấm sẽ in duy nhất số -1 và không in thêm gì nữa. Nếu chương trình vẫn tiếp tục chờ bộ chấm sau khi nhận -1, chương trình sẽ hết thời gian và nhận kết quả Time Limit Exceeded. Bạn có trách nhiệm để chương trình thoát kịp thời nhằm nhận kết quả Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình dùng quá giới hạn bộ nhớ hoặc gặp lỗi khi chạy, bạn sẽ nhận kết quả tương ứng.

Ràng buộc

\(\mathbf{T} = 2000\).
\(\mathbf{N} = 50\).

Phân nhóm

Test Set 1 (kết quả chấm hiển thị)

\(\mathbf{W} = 1200\) (\(\mathbf{W} = 0.6 \cdot \mathbf{T}\)).

Test Set 2 (kết quả chấm hiển thị)

\(\mathbf{W} = 1560\) (\(\mathbf{W} = 0.78 \cdot \mathbf{T}\)).

Test Set 3 (kết quả chấm hiển thị)

\(\mathbf{W} = 1720\) (\(\mathbf{W} = 0.86 \cdot \mathbf{T}\)).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để kiểm tra cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm tra cục bộ, bạn cần chạy công cụ song song với mã nguồn của mình; bạn có thể dùng trình chạy tương tác của chúng tôi cho việc đó. Để biết thêm thông tin, hãy đọc hướng dẫn trong các chú thích của tệp đó, đồng thời xem mục Bài toán tương tác trong FAQ.

Hướng dẫn dành cho công cụ kiểm thử được ghi trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn tự thêm các bộ test. Xin lưu ý rằng mặc dù công cụ kiểm thử được thiết kế để mô phỏng hệ thống chấm, nó KHÔNG phải hệ thống chấm thật và có thể hoạt động khác. Nếu mã nguồn vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy kiểm tra mục Lập trình trong FAQ để bảo đảm rằng bạn đang dùng cùng trình biên dịch với chúng tôi.

Tải công cụ kiểm thử

Ví dụ

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Ropes.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Gooli là một công ty khổng lồ sở hữu \(B\) tòa nhà ở vùng đồi. Năm năm trước, Gooli xây các cầu trượt một chiều để nhân viên đi giữa các tòa nhà, mở đầu truyền thống xây cầu trượt. Hiện có \(S\) cầu trượt.

Melek, Trưởng bộ phận Giao thông và là người mê giải bài, phải giữ cho hệ thống thú vị. Cô vô hiệu hóa một số cầu trượt sao cho chỉ còn các chu trình. Một chu trình là tập ít nhất hai tòa nhà \(b_1,\ldots,b_k\) sao cho có đúng một cầu bật từ \(b_i\) tới \(b_{i+1}\) và đúng một cầu bật từ \(b_k\) về \(b_1\). Không cầu nào khác đi vào hay đi ra các tòa nhà đó được bật. Một trạng thái là vui nếu mỗi tòa nhà thuộc đúng một chu trình.

Cầu trượt được đánh số \(1\) đến \(S\). Bảng điều khiển có hai thao tác bật/tắt, mỗi thao tác nhận \(\ell,r,m\) và tác động mọi cầu \(x\) thỏa \(\ell\le x\le r\) và \(m\mid x\). Bật chỉ hợp lệ khi mọi cầu bị tác động đang tắt; tắt chỉ hợp lệ khi mọi cầu bị tác động đang bật.

Hình sau minh họa chuỗi trạng thái với \(3\) tòa nhà, \(3\) cầu; màu xám nhạt là tắt, xám đậm là bật:

1. Ban đầu, mọi cầu tắt.
   
2. Sau E 1 2 1, cầu \(1,2\) bật.
   
3. Sau E 3 3 1, cả \(1,2,3\) bật.
   
4. Sau D 1 3 2, cầu \(1,3\) bật.
   
5. Sau D 1 3 3, chỉ cầu \(1\) bật.
   
6. Sau E 1 2 2, cầu \(1,2\) bật.
   Trạng thái trở lại đúng như hình ở bước 2.

Sult, mèo của Melek, tìm thấy bảng và thực hiện nhiều thao tác hợp lệ. Sau mỗi thao tác, Melek muốn biết trạng thái có thể trở thành vui bằng cách bật đúng một cầu đang tắt hay không; cô không thật sự bật cầu đó.

Trong hình, sau thao tác thứ nhất, ba và cuối, bật cầu tắt duy nhất tạo trạng thái vui. Sau thao tác thứ hai, không còn cầu tắt; hơn nữa trạng thái đã vui nên bật thêm bất kỳ cầu nào cũng phá tính vui. Sau thao tác thứ tư, có hai cầu tắt nhưng bật cầu nào cũng không vui.

Ban đầu mọi cầu tắt. Sau mỗi thao tác của Sult, hãy xác định cầu tắt nào, nếu có, Melek có thể bật để trạng thái vui.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ bắt đầu bằng \(B,S,N\). Tiếp theo \(S\) dòng; dòng \(i\) chứa \(X_i,Y_i\), nghĩa là cầu \(i\) đi từ \(X_i\) tới \(Y_i\). Cuối cùng \(N\) dòng chứa \(A_j,L_j,R_j,M_j\); \(A_j\) là E hoặc D, tác động các số cầu vừa thuộc \([L_j,R_j]\) vừa chia hết cho \(M_j\).

Dữ liệu ra

Với mỗi bộ, in Case #x: y_1 ... y_N. \(y_j\) là X nếu không thể bật đúng một cầu tắt để trạng thái sau \(j\) thao tác trở thành vui; nếu có, \(y_j\) là số hiệu một cầu như vậy.

Ràng buộc

• \(1\le X_i,Y_i\le B\), \(X_i\ne Y_i\); mọi cặp \((X_i,Y_i)\) phân biệt.
• \(A_j\in\{\mathtt E,\mathtt D\}\); \(1\le L_j\le R_j\le S\); \(1\le M_j\le S\).
• Mọi thao tác đều hợp lệ.

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le T\le100\); \(2\le B\le100\); \(2\le S\le1000\); \(1\le N\le1000\).
• Test Set 2 (Hidden Verdict): \(1\le T\le30\); \(2\le B\le3\cdot10^4\); \(2\le S\le3\cdot10^5\); \(1\le N\le3\cdot10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3 3 5
1 2
2 3
3 1
E 1 2 1
E 3 3 1
D 1 3 2
D 1 3 3
E 1 2 2
5 8 10
1 5
5 3
4 1
3 2
2 4
2 5
2 1
1 4
E 1 8 2
D 4 8 2
E 3 5 1
E 1 1 3
E 1 1 1
E 5 8 2
D 1 8 3
D 5 8 4
D 4 5 1
E 3 4 1

Case #1: 3 X 2 X 3
Case #2: 3 X 1 1 X X X 3 X 5

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Slide Circuits.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.