CEOI 2022 - Ngày 1

Đề bài

Tin Golubić, còn được biết đến với biệt danh Ngài Ảo Thuật, là một trong những ảo thuật gia trẻ tài năng nhất Varaždin. Sở trường của Tin là ảo thuật bài, và bài toán này được viết để tri ân những màn ảo thuật thực sự ấn tượng mà chúng ta đã được chứng kiến trong nhiều năm qua.

Trong màn ảo thuật này, Tin sử dụng một bộ bài gồm \(N\) lá. Trên mỗi lá bài ghi một số nguyên khác nhau từ \(1\) đến \(N\), và \(N\) là số chẵn. Tin sẽ thực hiện một chuỗi các lần xáo bài kiểu riffle. Bất cứ lúc nào, một khán giả cũng có thể hỏi: "Sau \(t\) lần xáo, số ghi trên lá bài thứ \(i\) tính từ dưới lên là bao nhiêu?" Tin sẽ lập tức trả lời chính xác.

Bí mật của màn ảo thuật là sự kết hợp giữa trí nhớ phi thường và kỹ năng điều khiển bài của Tin. Trước tiên, Tin ghi nhớ hoàn hảo trạng thái ban đầu của bộ bài, tức là biết chính xác vị trí ban đầu của từng lá.

Sau đó, Tin sử dụng một biến thể tinh tế của cách xáo riffle thông thường mà khán giả không nhận ra. Tin cầm nửa dưới của bộ bài bằng tay trái và nửa trên bằng tay phải, luôn úp các lá bài xuống, rồi lần lượt thả từng lá để tạo thành bộ bài mới trên bàn. Thay vì tùy ý thả lá dưới cùng của một trong hai tay, Tin luôn thả lá dưới cùng có số nhỏ hơn. Khi đã thả hết bài ở một tay, Tin thả toàn bộ số bài còn lại ở tay kia. Cuối cùng, Tin gom các lá đã thả lại và hoàn tất một lần xáo.

Bắt đầu từ bộ bài ban đầu, Tin liên tục áp dụng cách xáo trên lên trạng thái hiện tại của bộ bài. Mỗi lần xáo tạo ra một thứ tự mới, và lần xáo tiếp theo được thực hiện trên thứ tự đó.

Cho trạng thái ban đầu của bộ bài, hãy mô phỏng màn ảo thuật của Tin và trả lời \(Q\) câu hỏi của khán giả.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\), cách nhau bởi dấu cách. Dữ liệu bảo đảm \(N\) là số chẵn.

Dòng thứ hai chứa \(N\) số nguyên dương, là một hoán vị của tập \(\{1,2,\ldots,N\}\). Các số mô tả trạng thái ban đầu của bộ bài theo thứ tự từ dưới lên trên.

Dòng thứ \(j\) trong \(Q\) dòng tiếp theo chứa hai số nguyên \(t\) và \(i\), cách nhau bởi dấu cách \((1\le i\le N)\). Câu hỏi thứ \(j\) yêu cầu tìm số ghi trên lá bài thứ \(i\) tính từ dưới lên sau khi hoàn thành \(t\) lần xáo.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa một số nguyên dương từ \(1\) đến \(N\), là câu trả lời cho câu hỏi thứ \(j\).

Ràng buộc

Trong tất cả các subtask:

• \(2\le N\le 200\,000\).
• \(1\le Q\le 1\,000\,000\).
• \(0\le t\le 10^9\).

Phân nhóm

• Subtask 1 (10 điểm): \(N\le 1\,000\).
• Subtask 2 (40 điểm): Mọi câu hỏi có cùng giá trị \(t\).
• Subtask 3 (25 điểm): \(N,Q\le 100\,000\).
• Subtask 4 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

2
2
5

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

2
2
5
4
3
3

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

2
3
6
1
7
5
8
4
9
10

Đề bài

Helena vừa hoàn thành năm đầu tiên ở trường tiểu học. Cô bé là một học sinh gương mẫu, luôn đạt điểm cao và đặc biệt yêu thích toán học. Hiện Helena đang tận hưởng kỳ nghỉ xứng đáng cùng gia đình, nhưng cô bắt đầu nhớ những bài tập toán hằng ngày. May thay, anh trai của Helena quyết định thỏa mãn niềm đam mê ấy bằng bài toán sau.

Một biểu thức hợp lệ được định nghĩa đệ quy như sau:

• Xâu ? là một biểu thức hợp lệ, biểu diễn một số.
• Nếu \(A\) và \(B\) là các biểu thức hợp lệ thì min(A,B) và max(A,B) cũng là các biểu thức hợp lệ. Biểu thức thứ nhất trả về số nhỏ hơn trong hai đối số, còn biểu thức thứ hai trả về số lớn hơn.

Ví dụ, min(min(?,?),min(?,?)) và max(?,max(?,min(?,?))) là các biểu thức hợp lệ, còn ??, max(min(?)) và min(?,?,?) thì không.

Helena nhận được một biểu thức hợp lệ chứa tổng cộng \(N\) dấu hỏi. Mỗi dấu hỏi phải được thay bằng một số thuộc tập \(\{1,2,\ldots,N\}\) sao cho mỗi số trong tập xuất hiện đúng một lần trong biểu thức. Nói cách khác, các dấu hỏi được thay bằng một hoán vị của các số từ \(1\) đến \(N\).

Sau khi thay các dấu hỏi bằng số, ta có thể tính giá trị biểu thức; kết quả là một số nguyên từ \(1\) đến \(N\). Xét mọi cách gán số cho các dấu hỏi, Helena có thể thu được bao nhiêu giá trị khác nhau?

Dữ liệu vào

Dòng duy nhất chứa một biểu thức hợp lệ.

Dữ liệu ra

In một số nguyên từ \(1\) đến \(N\): số lượng giá trị khác nhau có thể thu được khi tính biểu thức.

Ràng buộc

Trong tất cả các subtask, \(2\le N\le 1\,000\,000\).

Phân nhóm

• Subtask 1 (10 điểm): \(N\le 9\).
• Subtask 2 (13 điểm): \(N\le 16\).
• Subtask 3 (13 điểm): Mỗi hàm trong biểu thức có ít nhất một đối số là dấu hỏi ?.
• Subtask 4 (30 điểm): \(N\le 1\,000\).
• Subtask 5 (34 điểm): Không có ràng buộc bổ sung.

Ví dụ

min(min(?,?),min(?,?))

1

max(?,max(?,min(?,?)))

2

min(max(?,?),min(?,max(?,?)))

3

Đề bài

"Sống bên bờ vực!" là một chương trình truyền hình mới dành cho những người yêu thích lý thuyết đồ thị. Trong mỗi tập, người dẫn chương trình đưa ra một bài toán mới cho các thí sinh. Người giải được bài toán sẽ giành giải thưởng lớn: một chuyến đi trọn gói đến bờ biển Croatia, kèm theo chuyến tham quan có hướng dẫn theo một chu trình Euler quanh những bức tường nổi tiếng của Dubrovnik.

Tomislav may mắn được chọn tham gia tập tiếp theo và lập tức bắt đầu chuẩn bị. Cậu trải qua nhiều đêm trong thư viện để đọc những định lý ít người biết nhất. Một đêm, cậu vô tình ngủ quên và mơ thấy mình xuất hiện trong chương trình. Khi tỉnh dậy, cậu vẫn nhớ rõ bài toán được đưa ra và việc mình đã không giải được nó.

Người dẫn chương trình vẽ hai cây có gốc, mỗi cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\). Hai cây được đánh số \(1\) và \(2\). Cả hai cây đều có trọng số dương trên các cạnh, nhưng các trọng số được giữ bí mật. Sau đó, Tomislav được chọn một tập con bất kỳ gồm đúng \(K\) nhãn đỉnh.

Sau khi chọn tập con, Tomislav được hỏi nhiều nhất \(Q\) câu hỏi dạng \((a,b)\), trong đó \(a\) và \(b\) là các nhãn đỉnh. Với mỗi câu hỏi, người dẫn trả về bộ bốn có thứ tự

Ở đây, \(d_t(x,y)\) là tổng trọng số các cạnh trên đường đi duy nhất giữa hai đỉnh \(x\) và \(y\) trong cây \(t\), còn \(l_t\) là nhãn của tổ tiên chung thấp nhất của \(a\) và \(b\) trong cây \(t\), tức là đỉnh xa gốc nhất nhận cả \(a\) và \(b\) làm hậu duệ, không nhất thiết là hậu duệ trực tiếp.

Để giành giải, Tomislav phải trả lời đúng chính xác \(T\) câu hỏi của người dẫn, mỗi câu có dạng \((p,q)\) với \(p\) và \(q\) đều thuộc tập con đã chọn. Với mỗi câu hỏi, Tomislav phải trả về khoảng cách giữa \(p\) và \(q\) trong cả hai cây, tức là bộ đôi

Hãy viết chương trình giúp Tomislav giải bài toán trong giấc mơ.

Giao tiếp

Đây là bài tương tác. Chương trình của bạn đóng vai Tomislav và giao tiếp với chương trình của ban tổ chức, chương trình này đóng vai người dẫn.

Trước tiên, chương trình đọc một dòng chứa bốn số nguyên \(N\), \(K\), \(Q\) và \(T\), cách nhau bởi dấu cách.

Tiếp theo, chương trình đọc mô tả của hai cây trên hai dòng: dòng đầu mô tả cây thứ nhất và dòng thứ hai mô tả cây thứ hai. Mỗi cây được cho bởi \(N\) số nguyên \(p_1,p_2,\ldots,p_N\), trong đó \(p_i\in\{-1,1,2,\ldots,N\}\) là cha của đỉnh \(i\), hoặc bằng \(-1\) nếu cây có gốc tại đỉnh \(i\).

Sau đó, chương trình phải in \(K\) số nguyên đôi một khác nhau \(x_1,x_2,\ldots,x_K\) \((1\le x_i\le N)\), cách nhau bởi dấu cách. Đây là tập nhãn đỉnh Tomislav chọn. Hãy đẩy dữ liệu đầu ra sau khi in dòng này.

Chương trình được phép hỏi nhiều nhất \(Q\) câu hỏi. Mỗi câu hỏi được in trên một dòng theo dạng:

? a b

với \(1\le a,b\le N\). Khi đã hỏi xong, chương trình phải in riêng ký tự ! trên một dòng rồi đẩy dữ liệu đầu ra.

Sau đó, chương trình đọc câu trả lời cho từng câu hỏi đã đặt, theo đúng thứ tự. Mỗi câu trả lời là một dòng chứa bốn số nguyên

Tiếp theo, chương trình đọc toàn bộ \(T\) câu hỏi của người dẫn. Mỗi câu hỏi nằm trên một dòng và gồm hai số nguyên \(p\) và \(q\), với \(p,q\in\{x_1,x_2,\ldots,x_K\}\).

Cuối cùng, với mỗi câu hỏi \((p,q)\) theo đúng thứ tự nhận được, chương trình in một dòng gồm hai số nguyên \(d_1(p,q)\) và \(d_2(p,q)\). Sau khi in đủ \(T\) câu trả lời, chương trình phải đẩy dữ liệu đầu ra lần cuối.

Bạn có thể tải mã nguồn mẫu từ hệ thống chấm. Mã nguồn này giao tiếp đúng với chương trình của ban tổ chức, bao gồm việc đẩy dữ liệu đầu ra, và giải được ví dụ đầu tiên.

Ràng buộc

Các trọng số cạnh bí mật là số nguyên dương không vượt quá \(2\,000\).

Trong tất cả các subtask:

• \(2\le K\le 100\,000\).
• \(1\le T\le\min(K^2,100\,000)\).

Phân nhóm

• Subtask 1 (10 điểm): \(N=500\,000\), \(Q=K-1\), hai cây giống hệt nhau, kể cả các trọng số cạnh bí mật.
• Subtask 2 (25 điểm): \(N=500\,000\), \(Q=2K-2\).
• Subtask 3 (19 điểm): \(N=500\,000\), \(K=200\), \(Q=K-1\).
• Subtask 4 (22 điểm): \(N=1\,000\,000\), \(K=1\,000\), \(Q=K-1\).
• Subtask 5 (24 điểm): \(N=1\,000\,000\), \(Q=K-1\).

Ví dụ giao tiếp

![Hai cây có trọng số trong ví dụ; các đỉnh thuộc tập được chọn được tô màuhttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_879e7f39.png

Trong ví dụ này, chương trình chọn tập \(\{1,5,7\}\). Sau đó, chương trình hỏi hai câu \((1,5)\) và \((1,7)\).

Với câu hỏi thứ nhất, tổ tiên chung thấp nhất của \(1\) và \(5\) lần lượt là \(l_1=1\) và \(l_2=7\). Câu trả lời là

Với câu hỏi thứ hai, tổ tiên chung thấp nhất của \(1\) và \(7\) lần lượt là \(l_1=1\) và \(l_2=7\). Câu trả lời là

Cuối cùng, chương trình nhận các câu hỏi \((1,7)\), \((7,5)\) và \((5,1)\). Các câu trả lời tương ứng là \((3,5)\), \((5,3)\) và \((2,8)\).