BOI 2020 - Ngày 1

Linda thích thỉnh thoảng đổi màu tóc và mong bạn trai Archie nhận ra sự khác biệt giữa màu tóc cũ và màu tóc mới. Archie nhận xét về màu tóc của Linda khi và chỉ khi anh nhận thấy sự khác biệt, nên Linda luôn biết liệu Archie có nhận ra việc đổi màu tóc hay không.

Trên thị trường vừa xuất hiện một dòng thuốc nhuộm tóc mới, trong đó các màu được đánh số bằng các số nguyên từ \(1\) đến \(N\). Chênh lệch giữa các số càng nhỏ thì sự khác biệt về màu sắc nhìn bằng mắt cũng càng nhỏ.

Linda giả thiết rằng với dòng thuốc nhuộm này, tồn tại một ngưỡng chênh lệch màu \(C\) (\(1\le C\le N\)): Archie nhận ra sự khác biệt giữa màu hiện tại \(\mathrm{color}_{\mathrm{new}}\) và màu trước đó \(\mathrm{color}_{\mathrm{prev}}\) nếu \(|\mathrm{color}_{\mathrm{new}}-\mathrm{color}_{\mathrm{prev}}|\ge C\), và không nhận ra nếu \(|\mathrm{color}_{\mathrm{new}}-\mathrm{color}_{\mathrm{prev}}|<C\).

Linda đã mua \(N\) bộ thuốc nhuộm thuộc dòng mới, mỗi màu từ \(1\) đến \(N\) có đúng một bộ, và sẵn sàng tiến hành thí nghiệm. Cô sẽ đổi màu tóc định kỳ và quan sát xem Archie có nhận ra hay không. Vì mỗi lần nhuộm phải dùng hết một bộ thuốc nhuộm để đạt được màu mong muốn, mỗi màu chỉ có thể được sử dụng nhiều nhất một lần.

Trước thí nghiệm, Linda dùng thuốc nhuộm thuộc một dòng khác, không tương thích với dòng mới. Vì vậy, phản ứng của Archie đối với màu đầu tiên được dùng trong thí nghiệm không có ý nghĩa.

Linda muốn xác định chính xác \(C\) với số lần nhuộm có giới hạn. Hãy viết chương trình tìm \(C\) bằng cách thử các màu trong \(N\) màu đã cho và quan sát phản ứng của Archie trước mỗi lần đổi màu tóc.

Yêu cầu cài đặt

Đây là bản điều chỉnh của bài tương tác Colors, sử dụng giao diện hàm C++ chạy trong cùng tiến trình với trình chấm. Nộp một tệp C++17 hoặc C++20, có #include "colors.h", hiện thực hàm sau và không viết hàm main:

long long find_threshold(long long N);

Trình chấm gọi find_threshold(N) đúng một lần cho mỗi bộ dữ liệu. Hàm chỉ nhận \(N\); giá trị \(C\) được giữ bí mật. Hàm phải trả về chính xác \(C\). Việc trả về kết thúc quá trình tìm kiếm, không tính là một truy vấn và không có phản hồi hay truy vấn tiếp theo.

Tệp colors.h cũng khai báo hàm do trình chấm cung cấp:

int query(long long P);

Mỗi lần gọi query(P) chọn màu tiếp theo, với \(1\le P\le N\). Hàm trả về 1 nếu Archie nhận ra sự khác biệt giữa hai màu được sử dụng gần nhất, hoặc 0 nếu không. Từ lần gọi thứ hai, phản hồi là 1 khi chênh lệch tuyệt đối giữa màu mới và màu ngay trước đó lớn hơn hoặc bằng \(C\), và là 0 khi chênh lệch nhỏ hơn \(C\).

Phản hồi của lần gọi đầu tiên không có ý nghĩa và có thể là 0 hoặc 1; lời giải phải hoạt động đúng với cả hai khả năng. Không được gọi với cùng một giá trị \(P\) hai lần. Được gọi query nhiều nhất \(64\) lần, tính cả lần đầu tiên, trong mọi phân nhóm.

Dùng kiểu long long cho \(N\), \(P\) và giá trị trả về \(C\). Bài nộp không đọc đầu vào chuẩn (stdin), không ghi đầu ra chuẩn (stdout) và không cần đẩy bộ đệm đầu ra (flush). Việc trả về đúng \(C\) không xóa các vi phạm trước đó: màu ngoài miền, màu lặp hoặc vượt quá giới hạn truy vấn vẫn khiến bài nộp không được chấp nhận.

Tệp đính kèm và chạy thử

Gói công khai boi20colors.zip gồm colors.h, public_grader.cpp, README.vi.md, sample.in và example.cpp. example.cpp chỉ là khung cần hoàn thiện, không phải lời giải. Viết lời giải vào solution.cpp và biên dịch cùng trình chạy thử công khai:

g++ -std=c++17 -O2 solution.cpp public_grader.cpp -o colors
./colors < sample.in
./colors 0 < sample.in
./colors 1 < sample.in

Trình chạy thử đọc một dòng N C từ tệp do bạn cung cấp; sample.in chứa 7 4. Chỉ trình chạy thử đọc dòng này, rồi gọi find_threshold(N). Hai lệnh cuối buộc phản hồi đầu tiên lần lượt là 0 và 1.

Nếu đáp án đúng và không có vi phạm, trình chạy thử in Accepted ra đầu ra chuẩn, in số truy vấn theo dạng <số truy vấn> queries ra đầu ra lỗi chuẩn (stderr) và kết thúc với mã \(0\). Nếu đáp án sai, lặp màu hoặc quá \(64\) truy vấn, trình chạy thử in Wrong Answer ra đầu ra chuẩn và kết thúc với mã \(1\). Một màu ngoài miền khiến trình chạy thử in Invalid query ra đầu ra lỗi chuẩn và kết thúc ngay với mã \(1\). Đây là thông báo của công cụ chạy thử; bài nộp chỉ cần trả về đáp án qua hàm.

Ràng buộc

• \(N\) và \(C\) là các số nguyên, \(1<N\le10^{18}\) và \(1\le C\le N\).
• Mỗi truy vấn dùng một số nguyên \(P\) với \(1\le P\le N\); mọi giá trị \(P\) đã truy vấn phải đôi một khác nhau.
• Chương trình được dùng nhiều nhất \(64\) lần gọi query, tính cả truy vấn đầu tiên, để tìm đúng \(C\).
• Giới hạn thời gian: \(0{,}3\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(9\) điểm: \(N\le64\).
2. \(13\) điểm: \(N\le125\).
3. \(21\) điểm: \(N\le1000\).
4. \(24\) điểm: \(N\le10^9\).
5. \(33\) điểm: không có ràng buộc thêm.

Ví dụ

Input        Output
7
             ? 2
1
             ? 7
1
             ? 4
0
             ? 1
0
             ? 5
1
             = 4

Ghi chú về giao thức gốc

Trong đề tương tác gốc, chương trình đọc \(N\), in ? P rồi đọc phản hồi cho mỗi truy vấn; khi biết đáp án thì in = C và dừng. Trình chấm không phản hồi đáp án cuối và không nhận thêm truy vấn. Bản dùng hàm thay mỗi cặp hỏi/đáp bằng query(P) và thay dòng đáp án cuối bằng giá trị trả về của find_threshold.

Đề gốc yêu cầu flush sau mỗi truy vấn và liệt kê các lệnh sau:

Trong C++, std::endl vừa in ký tự xuống dòng vừa đẩy dữ liệu trong bộ đệm ra ngoài. Những lệnh này chỉ mô tả giao thức gốc, không cần dùng trong bản nộp qua hàm.

Đề gốc lưu ý rằng vẫn có thể nhận Output isn't correct sau khi in đúng đáp án nếu đã vi phạm ràng buộc, và vi phạm giao thức có thể dẫn đến Execution killed. Trong bản dùng hàm, quy tắc tương ứng vẫn là: đáp án đúng không làm mất các vi phạm trước đó. Dữ liệu chạy thử do người dùng cung cấp trong đề gốc là một dòng N C, cũng là định dạng đầu vào của trình chạy thử công khai.

Joker trở lại thành phố Gotham để thực hiện một kế hoạch độc ác khác. Thành phố có \(N\) giao lộ, được đánh số từ \(1\) đến \(N\), và \(M\) con đường, được đánh số từ \(1\) đến \(M\). Mỗi con đường nối hai giao lộ khác nhau, và giữa hai giao lộ có nhiều nhất một con đường.

Để thực hiện kế hoạch, Joker cần một số lẻ con đường tạo thành một chu trình. Cụ thể, với một giao lộ \(S\) và một số nguyên dương chẵn \(k\), cần có một dãy giao lộ \(S,s_1,\ldots,s_k,S\) sao cho có đường nối \(S\) với \(s_1\), đường nối \(s_k\) với \(S\), và đường nối \(s_{i-1}\) với \(s_i\) với mọi \(i=2,\ldots,k\).

Tuy nhiên, cảnh sát đang kiểm soát các con đường của Gotham. Vào ngày \(i\), họ giám sát một tập các con đường có số hiệu liên tiếp: tất cả các đường \(j\) thỏa mãn \(l_i\le j\le r_i\). Joker không thể sử dụng những con đường bị giám sát trong kế hoạch của mình. Không may cho cảnh sát, Joker có gián điệp trong Sở Cảnh sát Gotham, nên hắn biết những con đường nào bị giám sát vào từng ngày.

Với một số ngày cho trước, hãy xác định liệu Joker có thể thực hiện kế hoạch vào mỗi ngày hay không. Muốn thực hiện được, vào ngày đó phải tồn tại một chu trình gồm một số lẻ con đường không bị giám sát.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(Q\), lần lượt là số giao lộ, số con đường và số ngày cần xét.

\(M\) dòng tiếp theo mô tả các con đường. Dòng thứ \(j\) (\(1\le j\le M\)) chứa hai số nguyên \(u,v\), cho biết con đường \(j\) nối hai giao lộ \(u\) và \(v\). Hai giao lộ này khác nhau; giữa hai giao lộ có nhiều nhất một con đường.

\(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i,r_i\), cho biết vào ngày \(i\) (\(1\le i\le Q\)), cảnh sát giám sát tất cả các con đường có số hiệu \(j\) thỏa mãn \(l_i\le j\le r_i\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) (\(1\le i\le Q\)) chứa YES nếu Joker có thể thực hiện kế hoạch vào ngày \(i\), hoặc NO nếu không thể.

Ràng buộc

• \(1\le N,M,Q\le200\,000\).
• \(1\le u,v\le N\), \(u\ne v\).
• Giữa hai giao lộ có nhiều nhất một con đường.
• \(1\le l_i\le r_i\le M\) với mọi \(1\le i\le Q\).
• Giới hạn thời gian: \(2{,}0\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(6\) điểm: \(1\le N,M,Q\le200\).
2. \(8\) điểm: \(1\le N,M,Q\le2000\).
3. \(25\) điểm: \(l_i=1\) với mọi \(i=1,\ldots,Q\).
4. \(10\) điểm: \(l_i\le200\) với mọi \(i=1,\ldots,Q\).
5. \(22\) điểm: \(Q\le2000\).
6. \(29\) điểm: không có ràng buộc thêm.

Ví dụ

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7

NO
YES

Serge, bếp trưởng của nhà hàng nổi tiếng “Salt, Pepper & Garlic”, đang cố gắng giành ngôi sao Michelin đầu tiên. Anh được báo rằng một chuyên gia ẩn danh dự định đến nhà hàng vào tối nay.

Dù danh tính của chuyên gia chưa được tiết lộ, Serge tin chắc mình biết vị khách sẽ gọi món nào trong thực đơn và có sở thích về hương vị ra sao. Cụ thể, chuyên gia yêu cầu tỉ lệ muối, tiêu và bột tỏi trong món ăn phải cực kỳ chính xác.

Trên một chiếc kệ riêng trong bếp, Serge có các chai chứa hỗn hợp muối, tiêu và bột tỏi. Với mỗi chai, anh biết chính xác khối lượng từng thành phần tính bằng kilôgam. Serge có thể kết hợp hỗn hợp từ một số chai bất kỳ, hoặc dùng trực tiếp hỗn hợp từ một chai, để thu được tỉ lệ cần thiết cho một món ăn.

May mắn thay, lượng hỗn hợp cần thêm vào món ăn rất nhỏ, nên có thể coi lượng hỗn hợp trong các chai luôn đủ dùng. Tuy nhiên, các giá trị số mô tả tỉ lệ có thể khá lớn.

Serge muốn biết liệu có thể tạo ra hỗn hợp yêu thích của chuyên gia từ các chai hiện có hay không; nếu có, anh muốn biết số chai ít nhất cần sử dụng. Các chai trên kệ có thể thay đổi theo thời gian khi Serge nhận thêm chai mới hoặc cho đầu bếp khác mượn chai của mình. Anh muốn trả lời câu hỏi sau mỗi thay đổi như vậy.

Ví dụ, giả sử tỉ lệ yêu thích của chuyên gia là \(1:1:1\), và trên kệ có ba chai sau. Các khối lượng trong bảng được tính bằng kilôgam.

Bảng 1: Các chai trên kệ.

Chỉ cần lấy cùng một khối lượng hỗn hợp từ mỗi chai \(1\) và \(2\) rồi trộn lại là thu được tỉ lệ mong muốn. Nếu bỏ chai \(2\) khỏi kệ thì không còn cách tạo ra hỗn hợp đó.

Hãy viết chương trình giúp Serge giải quyết bài toán này.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên không âm \(S_f,P_f,G_f\), mô tả khối lượng muối, tiêu và bột tỏi trong hỗn hợp yêu thích của chuyên gia. Với mọi số thực \(\alpha>0\), hỗn hợp \((\alpha S_f,\alpha P_f,\alpha G_f)\) cũng là hỗn hợp yêu thích của chuyên gia.

Dòng thứ hai chứa số nguyên dương \(N\), là số thay đổi trên kệ. Ban đầu, kệ không có chai nào.

Mỗi dòng trong \(N\) dòng tiếp theo mô tả một thay đổi:

• Nếu thêm một chai mới, dòng có dạng A Si Pi Gi, với chữ cái in hoa A và ba số nguyên không âm \(S_i,P_i,G_i\) mô tả khối lượng muối, tiêu và bột tỏi trong chai được thêm. Các chai được đánh số liên tiếp, duy nhất, bắt đầu từ \(1\): chai số \(i\) là chai được thêm vào lần thứ \(i\), tính riêng các thao tác thêm trong dữ liệu vào.
• Nếu bỏ một chai khỏi kệ, dòng có dạng R ri, với chữ cái in hoa R và số nguyên \(r_i\) là số hiệu chai bị bỏ. Các giá trị \(r_i\) trong những thao tác bỏ chai đôi một khác nhau và không vượt quá tổng số chai đã được thêm tính đến thời điểm đó.

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(j\) (\(1\le j\le N\)) chứa số \(x_j\), là số chai ít nhất cần dùng để pha được hỗn hợp có tỉ lệ muối, tiêu và bột tỏi yêu thích của chuyên gia từ các chai còn trên kệ sau \(j\) thay đổi đầu tiên. Nếu không thể pha được, in 0.

Ràng buộc

• \(S_f,P_f,G_f\ge0\) và \(0<S_f+P_f+G_f\le10^6\).
• \(1\le N\le100\,000\).
• Với mỗi chai được thêm, \(S_i,P_i,G_i\ge0\) và \(0<S_i+P_i+G_i\le10^6\).
• Mọi giá trị số trong đầu vào đều là số nguyên.
• Mỗi thao tác bỏ chai chỉ định một chai đã được thêm và chưa bị bỏ khỏi kệ.
• Giới hạn thời gian: \(2{,}0\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(13\) điểm: \(N\le50\) và \(0<S_i+P_i+G_i\le10^2\) với mọi chai được thêm.
2. \(17\) điểm: \(N\le500\) và \(0<S_i+P_i+G_i\le10^3\) với mọi chai được thêm.
3. \(30\) điểm: \(N\le5000\) và \(0<S_i+P_i+G_i\le10^4\) với mọi chai được thêm.
4. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

1 2 3
6
A 5 6 7
A 3 10 17
R 1
A 15 18 21
A 5 10 15
R 3

0
2
0
2
1
1