| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2015 - Googol | 100 (p) | 4.0s | 512M |
| 2 | Xâu đường đi đối xứng | 100 (p) | 1.0s | 1G |
| 3 | USACO 2015 - Trapped in the Haybales (Gold) | 100 (p) | 4.0s | 512M |
Mệt mỏi vì phải lọc qua các kết quả tìm kiếm trên web dành cho những loài vật nuôi khác, đàn bò quyết định ra mắt công cụ tìm kiếm của riêng mình. Không may, do vô cùng thiếu kinh nghiệm trong việc quản lý các dự án phần mềm lớn, số nhân viên \(N\) (\(1 \le N \le 10^{100}\)) trong công ty của chúng cuối cùng lại lớn hơn đáng kể so với kế hoạch ban đầu. Để tìm một cái tên phù hợp cho công ty, đàn bò lấy cảm hứng từ cận trên của \(N\) và quyết định đặt tên công ty là "Googol", tên gọi của số \(10^{100}\).
Trong nỗ lực tuyệt vọng nhằm cải thiện cơ cấu quản lý của công ty, đàn bò tổ chức công ty dưới dạng một cây nhị phân, trong đó mỗi nhân viên chịu trách nhiệm quản lý hai cấp dưới trực tiếp, được gọi là cấp dưới "trái" và "phải" theo cấu trúc cây. Để cân bằng khối lượng quản lý của mỗi nhân viên, đàn bò sắp xếp cây tổ chức sao cho với mỗi nhân viên E, tổng số nhân viên trong cây con trái của E hoặc bằng, hoặc lớn hơn đúng một so với tổng số nhân viên trong cây con phải của E.
Mỗi nhân viên có một mã số nguyên phân biệt trong khoảng \(1 \ldots N\), trong đó CEO (gốc của cây) có mã số 1. Bạn có thể tương tác để truy vấn bất kỳ nhân viên nào nhằm xác định mã số của hai cấp dưới của cô ấy. Để thực hiện truy vấn, hãy ghi mã số của nhân viên đó ra luồng đầu ra chuẩn (stdout), theo sau bởi một ký tự xuống dòng. Phản hồi bạn nhận được sẽ là một dòng chứa hai số nguyên, lần lượt là mã số của cấp dưới trái và cấp dưới phải của nhân viên này. Cả hai mã số có thể bằng 0 nếu nhân viên đó không có cấp dưới, hoặc chỉ mã số bên phải có thể bằng 0 nếu nhân viên đó chỉ có cấp dưới trái (lưu ý rằng do điều kiện cân bằng ở trên, một nhân viên không thể có cấp dưới phải mà không có cấp dưới trái).
Không may, đàn bò đã quên mất giá trị chính xác của \(N\). Hãy tính số này và in Answer N (theo sau bởi một ký tự xuống dòng) làm dòng cuối cùng của đầu ra. Chương trình của bạn được phép thực hiện nhiều nhất \(70{,}000\) truy vấn và có giới hạn thời gian chạy 4 giây (8 giây đối với Java hoặc Python).
Dưới đây là một ví dụ về một lượt tương tác có thể xảy ra giữa chương trình của bạn và trình chấm:
Ví dụ 1
CHƯƠNG TRÌNH CỦA BẠN: 1
TRÌNH CHẤM: 4 3
CHƯƠNG TRÌNH CỦA BẠN: 4
TRÌNH CHẤM: 2 0
CHƯƠNG TRÌNH CỦA BẠN: 3
TRÌNH CHẤM: 0 0
CHƯƠNG TRÌNH CỦA BẠN: Answer 4Cây tương ứng với lượt tương tác này là:
1
4 3
2
Không cần hỏi về các con của nút 2, vì từ việc nút 4 không có con phải, ta có thể suy ra nút 2 không có con nào.
Lưu ý kỹ thuật: bài toán này được chấm bằng một trình chấm tương tác, một phần mới trong hệ thống chấm của chúng tôi. Nếu bạn gặp hành vi nào có vẻ là sự cố kỹ thuật với trình chấm, vui lòng báo tới [email protected]. Chúng tôi cho rằng điều này không cần thiết, nhưng nếu mã của bạn có vẻ bị treo trong lúc chấm, hãy thử thêm các lệnh xả luồng đầu ra (chẳng hạn fflush(stdout) hoặc cout.flush()), phòng trường hợp dữ liệu bị lưu đệm ngoài dự kiến và không đến được trình chấm. Nếu việc này có vẻ cần thiết để mã của bạn hoạt động, vui lòng gửi thông báo tới [email protected] để chúng tôi có thể khắc phục sự cố trong tương lai.
USACO 2015 US Open, Gold — Googol. Tác giả đề: Brian Dean, 2015.
Cho lưới ô vuông kích thước \(n\) x \(n\), các hàng đánh số \(1…n\) từ trên xuống dưới, các cột đánh số \(1…n\) từ trái sang phải. Mỗi ô trong lưới chứa một kí tự chữ cái latin in hoa. Xét các đường đi từ ô \((1;1)\) đến ô \((n;n)\) chỉ đi từ một ô sang ô kề cạnh bên phải hoặc bên dưới. Mỗi đường đi được đại diện bởi một xâu kí tự là dãy các kí tự trong các ô trên đường đi dọc theo hành trình. Đếm số đường đi có xâu đại diện là xâu đối xứng.
Test 1
4
ABCD
BXZX
CDXB
WCBA12Farmer John vừa nhận một lô gồm \(N\) kiện cỏ khô lớn (\(1 \le N \le 100{,}000\)) và đặt chúng tại nhiều vị trí khác nhau dọc theo con đường dẫn đến chuồng. Không may, ông hoàn toàn quên mất rằng cô bò Bessie đang gặm cỏ dọc con đường, và giờ cô có thể đã bị mắc kẹt giữa các kiện cỏ!
Mỗi kiện cỏ \(j\) có kích thước \(S_j\) và vị trí \(P_j\) cho biết nơi nó nằm trên con đường một chiều. Bessie có thể tự do di chuyển dọc theo đường, kể cả đi tới đúng vị trí của một kiện cỏ, nhưng cô không thể đi xuyên qua vị trí này. Tuy nhiên, nếu chạy theo cùng một hướng trên quãng đường dài \(D\), cô sẽ đạt đủ tốc độ để phá xuyên qua và loại bỏ vĩnh viễn bất kỳ kiện cỏ nào có kích thước nhỏ hơn nghiêm ngặt \(D\). Dĩ nhiên, sau khi làm vậy, cô có thể có thêm không gian để lấy đà lao vào các kiện cỏ khác và tiếp tục phá chúng.
Bessie có thể thoát ra ngoài nếu cuối cùng cô phá xuyên qua được kiện cỏ ngoài cùng bên trái hoặc ngoài cùng bên phải. Hãy tính tổng độ dài của phần đường gồm các vị trí bắt đầu có giá trị thực mà từ đó Bessie không thể thoát.
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một kiện cỏ, gồm hai số nguyên cho biết kích thước và vị trí của kiện cỏ; mỗi số đều nằm trong khoảng \(1 \ldots 10^9\). Mọi vị trí đều phân biệt.
In một số nguyên duy nhất: độ dài của phần đường mà từ đó Bessie không thể thoát.
Ví dụ 1
5
8 1
1 4
8 8
7 15
4 2014USACO 2015 US Open, Gold — Trapped in the Haybales (Gold). Tác giả đề: Brian Dean, 2015.