IOI 2017 - Ngày 2

Giải thưởng lớn là một trò chơi truyền hình nổi tiếng. Bạn là người chơi may mắn lọt vào vòng chung kết, đứng trước một dãy \(n\) hộp được đánh số từ \(0\) đến \(n-1\) theo thứ tự từ trái sang phải. Mỗi hộp chứa một giải thưởng mà bạn chưa biết cho đến khi mở hộp. Có \(v\ge 2\) loại giải thưởng, được đánh số từ \(1\) đến \(v\) theo thứ tự giá trị giảm dần.

Giải thưởng loại \(1\) có giá trị cao nhất: một viên kim cương. Có đúng một viên kim cương trong tất cả các hộp. Giải thưởng loại \(v\) có giá trị thấp nhất: một cây kẹo mút. Các giải thưởng ít giá trị hơn xuất hiện với số lượng nhiều hơn hẳn: với mọi \(2\le t\le v\), nếu có \(k\) giải thưởng loại \(t-1\), thì số giải thưởng loại \(t\) lớn hơn nghiêm ngặt \(k^2\).

Mục tiêu của bạn là giành được viên kim cương. Cuối trò chơi, bạn phải chọn mở một hộp và nhận giải thưởng trong đó. Trước khi chọn hộp, bạn được hỏi Rambod, người dẫn chương trình, một số câu hỏi. Trong mỗi câu hỏi, bạn chọn một hộp \(i\); Rambod trả lời bằng một mảng \(a\) gồm hai số nguyên:

• \(a[0]\) là số hộp ở bên trái hộp \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\).
• \(a[1]\) là số hộp ở bên phải hộp \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\).

Chẳng hạn, nếu \(n=8\), bạn hỏi về hộp \(i=2\) và nhận được \(a=[1,2]\), thì trong hai hộp \(0,1\) có đúng một hộp chứa giải thưởng giá trị hơn giải thưởng ở hộp \(2\); trong các hộp \(3,4,\ldots,7\) có đúng hai hộp như vậy.

Hãy tìm hộp chứa viên kim cương bằng cách sử dụng ít câu hỏi.

Chi tiết cài đặt

Đây là bài toán tương tác thông qua lời gọi hàm. Bạn cần khai báo sử dụng tệp prize.h và cài đặt hàm:

int find_best(int n);

Chương trình chấm gọi find_best đúng một lần, với n là số hộp. Hàm phải trả về nhãn \(d\) của hộp chứa viên kim cương: số nguyên duy nhất \(0\le d\le n-1\) mà hộp \(d\) chứa giải thưởng loại \(1\).

Trong quá trình thực hiện find_best, bạn có thể gọi hàm sau do chương trình chấm cung cấp:

std::vector<int> ask(int i);

• i là nhãn hộp được hỏi, phải thỏa mãn \(0\le i\le n-1\).
• Hàm trả về một mảng \(a\) có đúng hai phần tử. \(a[0]\) là số hộp bên trái \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\); \(a[1]\) là số hộp bên phải \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\).

Bạn chỉ cài đặt find_best; hàm ask và hàm main do chương trình chấm cung cấp. Chương trình của bạn nhận thông tin về các hộp thông qua ask và trả lời bằng giá trị trả về của find_best. Mỗi lần gọi ask đều được tính là một câu hỏi, kể cả khi hỏi lại một hộp. Không được gọi quá \(10\,000\) lần trong một bộ dữ liệu; gọi với chỉ số không hợp lệ, vượt giới hạn số câu hỏi hoặc trả về hộp không chứa kim cương sẽ bị chấm sai.

Hành vi thích nghi của chương trình chấm

Trong một số bộ dữ liệu, chương trình chấm có hành vi thích nghi: dãy giải thưởng không được cố định trước, và câu trả lời có thể phụ thuộc vào các câu hỏi mà chương trình của bạn đã đặt ra.

Sau mỗi câu trả lời, luôn tồn tại ít nhất một dãy giải thưởng thỏa mãn các ràng buộc của bộ dữ liệu và phù hợp với tất cả các câu trả lời đã đưa ra. Lời giải phải tìm được hộp chứa kim cương ngay cả khi làm việc với chương trình chấm thích nghi này.

Ví dụ

Chương trình chấm gọi:

find_best(8);

Giả sử các loại giải thưởng trong tám hộp lần lượt là \([3,2,3,1,3,3,2,3]\). Các lời gọi có thể thực hiện và giá trị trả về tương ứng là:

ask(0) → [0, 3]
ask(1) → [0, 1]
ask(2) → [1, 2]
ask(3) → [0, 0]
ask(4) → [2, 1]
ask(5) → [2, 1]
ask(6) → [1, 0]
ask(7) → [3, 0]

Viên kim cương nằm trong hộp \(3\), nên find_best phải trả về \(3\).

Phần trên của hình thể hiện loại giải thưởng trong từng hộp. Phần dưới minh họa lời gọi ask(2): có một hộp được đánh dấu ở bên trái và hai hộp được đánh dấu ở bên phải, tương ứng với câu trả lời \([1,2]\).

Ràng buộc

• \(3\le n\le 200\,000\).
• Có \(v\ge 2\) loại giải thưởng; loại giải thưởng trong mỗi hộp là một số nguyên từ \(1\) đến \(v\).
• Có đúng một giải thưởng loại \(1\).
• Với mọi \(2\le t\le v\), nếu có \(k\) giải thưởng loại \(t-1\) thì có nhiều hơn \(k^2\) giải thưởng loại \(t\).

Tương đương, nếu \(c_t\) là số giải thưởng loại \(t\), thì:

Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

Ở subtask \(2\), bạn có thể nhận điểm thành phần. Nếu lời giải trả về đáp án đúng cho tất cả các bộ dữ liệu của subtask này, gọi \(q\) là số lần gọi ask lớn nhất trong tất cả các bộ dữ liệu đó. Điểm của subtask được tính như sau:

Trong khoảng \(5000<q\le 6000\), công thức tính điểm là:

Chương trình chấm mẫu

Chương trình chấm mẫu không thích nghi. Nó đọc và sử dụng một mảng giải thưởng cố định \(p\), trong đó \(p[b]\) là loại giải thưởng trong hộp \(b\) với mọi \(0\le b\le n-1\).

Dữ liệu vào của chương trình chấm mẫu có định dạng:

• Dòng \(1\): \(n\).
• Dòng \(2\): \(p[0]\ p[1]\ \ldots\ p[n-1]\).

Mảng \(p\) được chương trình chấm mẫu sử dụng để trả lời các lời gọi ask; hàm find_best chỉ nhận tham số \(n\).

Chương trình chấm mẫu C++ in giá trị trả về của find_best trên dòng đầu tiên. Dòng thứ hai có dạng Query count: q, trong đó \(q\) là tổng số lần gọi ask trong lần chạy đó. Chương trình chấm mẫu cũng giới hạn số lần gọi ask ở mức \(10\,000\) và yêu cầu mọi chỉ số được hỏi đều hợp lệ.

8
3 2 3 1 3 3 2 3

3
Query count: 8

Theo truyền thuyết Ba Tư cổ đại trong sử thi Shahnameh, Zal, người anh hùng huyền thoại của Ba Tư, yêu say đắm Rudaba, công chúa của Kabul. Khi Zal cầu hôn Rudaba, cha nàng đã đưa ra một thử thách.

Ở Ba Tư có \(n\) thành phố, được đánh số từ \(0\) đến \(n-1\), và \(m\) con đường hai chiều, được đánh số từ \(0\) đến \(m-1\). Mỗi con đường nối hai thành phố phân biệt. Giữa mỗi cặp thành phố có nhiều nhất một con đường. Một số con đường là đường hoàng gia, được hoàng gia sử dụng để đi lại. Nhiệm vụ của Zal là xác định tất cả các con đường hoàng gia.

Zal có một bản đồ thể hiện tất cả các thành phố và con đường ở Ba Tư. Anh không biết những con đường nào là đường hoàng gia, nhưng có thể nhờ Simurgh, chú chim nhân từ huyền thoại luôn bảo vệ anh, giúp đỡ. Simurgh không muốn tiết lộ trực tiếp tập các đường hoàng gia. Thay vào đó, Simurgh cho biết tập tất cả các đường hoàng gia là một bộ vàng. Một tập các con đường là bộ vàng khi và chỉ khi thỏa mãn cả hai điều kiện sau:

• Tập đó gồm đúng \(n-1\) con đường.
• Với mỗi cặp thành phố, có thể đi từ thành phố này đến thành phố kia chỉ bằng các con đường thuộc tập đó.

Như vậy, một bộ vàng là một cây khung của mạng lưới đường. Zal có thể đặt câu hỏi cho Simurgh. Trong mỗi câu hỏi, Zal chọn một bộ vàng, rồi Simurgh cho biết có bao nhiêu con đường trong bộ vàng đó là đường hoàng gia.

Hãy giúp Zal tìm tập tất cả các đường hoàng gia bằng cách đặt nhiều nhất \(q\) câu hỏi. Trình chấm sẽ đóng vai Simurgh. Giới hạn \(q\) được quy định riêng cho từng subtask.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, được khai báo trong tệp simurgh.h:

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v);

• n: số thành phố.
• u, v: hai mảng có độ dài \(m\). Với mọi \(0 \le i \le m-1\), con đường \(i\) nối hai thành phố \(u[i]\) và \(v[i]\).
• Hàm phải trả về một mảng có độ dài \(n-1\), chứa nhãn của tất cả các đường hoàng gia, theo thứ tự tùy ý.

Trong quá trình thực hiện, hàm find_roads được gọi hàm sau của trình chấm nhiều nhất \(q\) lần:

int count_common_roads(const std::vector<int>& r);

• r: mảng có độ dài \(n-1\), chứa nhãn các con đường của một bộ vàng, theo thứ tự tùy ý.
• Hàm trả về số đường hoàng gia trong bộ vàng được mô tả bởi r.

Mỗi truy vấn phải hợp lệ: các phần tử của r phải là \(n-1\) nhãn phân biệt trong khoảng từ \(0\) đến \(m-1\), và các con đường tương ứng phải nối được tất cả \(n\) thành phố. Chỉ có đủ \(n-1\) nhãn là chưa đủ để tạo thành một bộ vàng.

Ví dụ

Xét lời gọi:

find_roads(4, {0, 0, 0, 1, 1, 2}, {1, 2, 3, 2, 3, 3});

Trong ví dụ này có \(4\) thành phố và \(6\) con đường. Ký hiệu \((a,b)\) là con đường nối hai thành phố \(a\) và \(b\). Các đường mang nhãn từ \(0\) đến \(5\) lần lượt là \((0,1)\), \((0,2)\), \((0,3)\), \((1,2)\), \((1,3)\) và \((2,3)\). Mỗi bộ vàng gồm \(n-1=3\) con đường.

Giả sử các đường hoàng gia mang nhãn \(0\), \(1\) và \(5\), tức là các đường \((0,1)\), \((0,2)\) và \((2,3)\). Khi đó:

• count_common_roads({0, 1, 2}) trả về \(2\). Truy vấn này chọn các đường \((0,1)\), \((0,2)\) và \((0,3)\), trong đó có hai đường hoàng gia.
• count_common_roads({5, 1, 0}) trả về \(3\). Truy vấn này chọn đúng tập tất cả các đường hoàng gia.

Hàm find_roads phải trả về mảng [5, 1, 0] hoặc một mảng độ dài \(3\) chứa đúng ba phần tử đó theo thứ tự khác.

Các lời gọi sau không hợp lệ:

• count_common_roads({0, 1}): mảng r không có độ dài \(3\).
• count_common_roads({0, 1, 3}): các đường \((0,1)\), \((0,2)\) và \((1,2)\) không tạo thành một bộ vàng, vì không thể đi từ thành phố \(0\) đến thành phố \(3\) chỉ bằng các đường này.

Ràng buộc

• \(2 \le n \le 500\).
• Số con đường thỏa mãn:

• Với mọi \(0 \le i \le m-1\), \(0 \le u[i],v[i] \le n-1\) và \(u[i] \ne v[i]\).
• Giữa mỗi cặp thành phố có nhiều nhất một con đường.
• Có thể đi lại giữa bất kỳ hai thành phố nào bằng các con đường đã cho.
• Tập tất cả các đường hoàng gia là một bộ vàng.
• Hàm find_roads được gọi count_common_roads nhiều nhất \(q\) lần. Trong mỗi lần gọi, các con đường được mô tả bởi r phải tạo thành một bộ vàng.
• Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2+i\), với mọi \(0 \le i \le m-1\): \(u[i]\ v[i]\).
• Dòng \(2+m\): \(s[0]\ s[1]\ \ldots\ s[n-2]\).

Ở đây, \(s[0],s[1],\ldots,s[n-2]\) là nhãn của các đường hoàng gia.

Trình chấm mẫu in YES nếu find_roads gọi count_common_roads nhiều nhất \(30\,000\) lần và trả về đúng tập các đường hoàng gia. Ngược lại, trình chấm mẫu in NO.

Hàm count_common_roads trong trình chấm mẫu không kiểm tra đầy đủ các tính chất của bộ vàng. Nó đếm và trả về số nhãn đường hoàng gia xuất hiện trong mảng r. Tuy nhiên, nếu bài nộp gọi count_common_roads với một tập nhãn không mô tả một bộ vàng, bài nộp sẽ nhận kết quả Wrong Answer.

Dữ liệu mẫu

4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5

Với chương trình tìm đúng tập đường hoàng gia và tuân thủ giới hạn số lần gọi, trình chấm mẫu in:

YES

Chú ý kỹ thuật

Trong C++ và Pascal, hàm count_common_roads sử dụng cách truyền tham số bằng tham chiếu để tăng hiệu quả. Bạn vẫn có thể gọi hàm theo cách thông thường. Trình chấm bảo đảm không thay đổi giá trị của r.

Thành phố Tehran là nơi đặt Thư viện Quốc gia Iran. Kho báu quý giá nhất của thư viện được trưng bày trong một căn phòng dài, trên một dãy gồm \(n\) chiếc bàn được đánh số từ \(0\) đến \(n-1\) theo thứ tự từ trái sang phải. Mỗi bàn đặt một quyển sách cổ viết tay. Các quyển sách đang được sắp xếp theo niên đại, khiến khách tham quan gặp khó khăn khi tìm sách theo tiêu đề. Vì vậy, người điều hành thư viện quyết định sắp xếp lại các quyển sách theo thứ tự từ điển của tiêu đề.

Aryan là nhân viên thư viện được giao công việc này. Anh đã lập một mảng \(p\) có độ dài \(n\), gồm các số nguyên phân biệt từ \(0\) đến \(n-1\). Mảng này mô tả vị trí đích của mỗi quyển sách: với mọi \(0 \le i < n\), quyển sách ban đầu ở bàn \(i\) phải được chuyển đến bàn \(p[i]\).

Aryan bắt đầu ở bàn \(s\) và phải quay lại bàn này sau khi sắp xếp xong. Vì sách rất quý giá, tại mỗi thời điểm anh chỉ được mang theo nhiều nhất một quyển. Anh có thể thực hiện một dãy thao tác, mỗi thao tác thuộc một trong các loại sau:

• Nếu không mang sách và bàn tại vị trí đang đứng có sách, anh có thể nhặt quyển sách đó lên.
• Nếu đang mang sách và bàn tại vị trí đang đứng có một quyển sách khác, anh có thể đổi quyển sách đang mang với quyển sách trên bàn.
• Nếu đang mang sách và bàn tại vị trí đang đứng không có sách, anh có thể đặt quyển sách đang mang xuống bàn đó.
• Anh có thể di chuyển đến bất kỳ bàn nào, khi không mang sách hoặc khi mang đúng một quyển sách.

Với mọi \(0 \le i,j \le n-1\), khoảng cách giữa bàn \(i\) và bàn \(j\), tính bằng mét, là:

Hãy tính tổng quãng đường nhỏ nhất Aryan cần di chuyển để đưa tất cả các quyển sách về đúng bàn đích và quay lại bàn \(s\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, được khai báo trong tệp books.h:

long long minimum_walk(std::vector<int> p, int s);

• p: mảng có độ dài \(n\). Với mọi \(0 \le i < n\), quyển sách ban đầu ở bàn \(i\) phải được chuyển đến bàn \(p[i]\).
• s: chỉ số bàn nơi Aryan bắt đầu và phải quay lại sau khi sắp xếp xong.
• Hàm phải trả về tổng quãng đường nhỏ nhất, tính bằng mét, để Aryan hoàn thành công việc và quay lại bàn xuất phát. Giá trị trả về có kiểu số nguyên 64 bit long long.

Ví dụ

Xét lời gọi:

minimum_walk({0, 2, 3, 1}, 0);

Trong ví dụ này, \(n=4\) và Aryan bắt đầu ở bàn \(0\). Anh có thể sắp xếp các quyển sách như sau:

1. Di chuyển đến bàn \(1\) và nhặt quyển sách ở đó lên. Quyển sách này cần được đặt ở bàn \(2\).
2. Di chuyển đến bàn \(2\) và đổi quyển sách đang mang với quyển sách trên bàn. Quyển sách vừa nhặt lên cần được đặt ở bàn \(3\).
3. Di chuyển đến bàn \(3\) và đổi quyển sách đang mang với quyển sách trên bàn. Quyển sách vừa nhặt lên cần được đặt ở bàn \(1\).
4. Di chuyển đến bàn \(1\) và đặt quyển sách đang mang xuống bàn này.
5. Quay lại bàn \(0\).

Quyển sách ban đầu ở bàn \(0\) đã nằm đúng vị trí nên Aryan không cần nhặt nó lên. Tổng quãng đường anh di chuyển là:

Đây là phương án tối ưu, nên hàm phải trả về \(6\).

Ràng buộc

• \(1 \le n \le 1\,000\,000\).
• \(0 \le s \le n-1\).
• Mảng \(p\) chứa \(n\) số nguyên phân biệt trong đoạn từ \(0\) đến \(n-1\), kể cả hai đầu mút.
• Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ s\).
• Dòng \(2\): \(p[0]\ p[1]\ \ldots\ p[n-1]\).

Trình chấm mẫu in một dòng chứa giá trị trả về của minimum_walk.

Dữ liệu mẫu

4 0
0 2 3 1

Kết quả mẫu

6