Andrew là một chuyên gia về nấm đang nghiên cứu các loài nấm bản địa của Singapore.

Trong quá trình nghiên cứu, Andrew đã thu thập \(n\) cây nấm, được gán nhãn từ \(0\) đến \(n-1\). Mỗi cây nấm thuộc một trong hai loài, được gọi là A và B.

Andrew biết rằng cây nấm \(0\) thuộc loài A, nhưng vì hai loài trông giống nhau nên anh không biết loài của các cây nấm từ \(1\) đến \(n-1\).

May mắn thay, Andrew có một chiếc máy trong phòng thí nghiệm có thể giúp anh. Để sử dụng máy, cần đặt ít nhất hai cây nấm thành một hàng bên trong máy, theo thứ tự bất kỳ, rồi bật máy. Máy sẽ tính số cặp nấm liền kề khác loài. Chẳng hạn, nếu đặt các cây nấm thuộc các loài \([A,B,B,A]\) theo đúng thứ tự này vào máy, kết quả sẽ là \(2\).

Tuy nhiên, vận hành máy rất tốn kém nên số lần sử dụng máy bị giới hạn. Ngoài ra, tổng số cây nấm được đặt vào máy qua tất cả các lần sử dụng không được vượt quá \(100\,000\). Hãy sử dụng máy để giúp Andrew đếm số cây nấm loài A đã thu thập.

Chi tiết cài đặt

Bạn cần cài đặt hàm C++ sau:

int count_mushrooms(int n);

• \(n\): số cây nấm Andrew đã thu thập.
• Hàm được gọi đúng một lần và phải trả về số cây nấm thuộc loài A.

Trong hàm này, bạn có thể gọi hàm do trình chấm cung cấp:

int use_machine(std::vector<int> x);

• \(x\): mảng có độ dài từ \(2\) đến \(n\), tính cả hai đầu mút, mô tả nhãn các cây nấm được đặt vào máy theo đúng thứ tự.
• Các phần tử của \(x\) phải là các số nguyên đôi một khác nhau, từ \(0\) đến \(n-1\), tính cả hai đầu mút.
• Gọi \(d\) là độ dài của \(x\). Hàm trả về số chỉ số \(j\) thỏa mãn \(0 \le j \le d-2\) mà hai cây nấm \(x[j]\) và \(x[j+1]\) thuộc hai loài khác nhau.
• Hàm use_machine được gọi nhiều nhất \(20\,000\) lần.
• Tổng độ dài các mảng \(x\) truyền vào use_machine qua tất cả các lần gọi không được vượt quá \(100\,000\).

Trong một số test, trình chấm hoạt động thích nghi: trình chấm không có một dãy loài nấm cố định sẵn. Thay vào đó, câu trả lời có thể phụ thuộc vào các lời gọi use_machine trước đó. Tuy nhiên, sau mỗi lần tương tác, luôn tồn tại ít nhất một dãy loài nấm phù hợp với tất cả các câu trả lời đã đưa ra tính đến thời điểm đó.

Ràng buộc

Phân nhóm

Nếu trong bất kỳ test nào, các lời gọi use_machine không tuân thủ những quy tắc ở trên, hoặc giá trị trả về của count_mushrooms không đúng, điểm của bài làm sẽ là \(0\).

Ngược lại, gọi \(Q\) là số lần gọi use_machine lớn nhất trong số tất cả các test. Điểm được tính theo bảng sau:

Ví dụ

Các ví dụ dưới đây mô tả lời gọi hàm, giá trị trả về và một chuỗi tương tác có thể thực hiện.

count_mushrooms(3)

1

count_mushrooms(4)

3

Dữ liệu vào

Trình chấm mẫu đọc mảng số nguyên \(s\) mô tả loài nấm. Với mọi \(0 \le i \le n-1\), \(s[i]=0\) nghĩa là cây nấm \(i\) thuộc loài A, còn \(s[i]=1\) nghĩa là cây nấm \(i\) thuộc loài B.

Dữ liệu vào có hai dòng theo định dạng:

n
s[0] s[1] ... s[n-1]

Trình chấm mẫu không hoạt động thích nghi.

Dữ liệu ra

Trình chấm mẫu in:

• Dòng \(1\): giá trị trả về của count_mushrooms.
• Dòng \(2\): số lần gọi use_machine.

Nguồn

IOI 2020, Ngày 2 — Counting Mushrooms (mushrooms). Đề chính thức tiếng Anh và bản dịch tiếng Việt.