APIO 2022

Như đã biết, các Pharaoh là những người đầu tiên khám phá vũ trụ. Họ đã phóng con tàu vũ trụ đầu tiên lên hành tinh Thutmus I (ngày nay được biết đến với tên gọi Sao Hỏa). Bề mặt hành tinh có thể được mô hình hóa bằng một lưới gồm \((2n+1)\times(2n+1)\) ô vuông, mỗi ô chứa đất hoặc nước. Trạng thái của ô ở hàng \(i\), cột \(j\) (\(0\le i,j\le 2n\)) được ký hiệu bởi \(s[i][j]\): \(s[i][j]=\) '1' nếu ô chứa đất và \(s[i][j]=\) '0' nếu ô chứa nước.

Hai ô đất được gọi là liên thông nếu tồn tại một đường đi chỉ gồm các ô đất nối chúng, trong đó hai ô liên tiếp luôn có chung một cạnh. Một hòn đảo trên hành tinh là một tập tối đại các ô đất sao cho hai ô bất kỳ trong tập đều liên thông với nhau.

Nhiệm vụ của con tàu là đếm số hòn đảo trên hành tinh. Tuy nhiên, nhiệm vụ này không dễ dàng vì con tàu sử dụng một máy tính cổ đại. Máy tính có bộ nhớ \(h\), là một mảng hai chiều kích thước \((2n+1)\times(2n+1)\). Mỗi phần tử của mảng chứa được một xâu nhị phân độ dài \(100\), trong đó mỗi ký tự là '0' (ASCII 48) hoặc '1' (ASCII 49). Ban đầu, ký tự đầu tiên của mỗi ô nhớ lưu trạng thái của ô tương ứng trên lưới:

với mọi \(0\le i,j\le 2n\). Tất cả các ký tự còn lại của \(h\) ban đầu đều là '0' (ASCII 48).

Để xử lý dữ liệu trong bộ nhớ, máy tính chỉ có thể truy cập một vùng \(3\times3\) và ghi đè giá trị tại ô trên cùng bên trái của vùng đó. Cụ thể, máy tính có thể truy cập các giá trị \(h[i..i+2][j..j+2]\) (\(0\le i,j\le 2(n-1)\)) rồi ghi đè giá trị tại \(h[i][j]\). Thao tác này được gọi là xử lý ô \((i,j)\).

Để khắc phục giới hạn của máy tính, các Pharaoh sử dụng cơ chế sau:

• Máy tính xử lý bộ nhớ qua \(n\) bước.
• Ở bước \(k\) (\(0\le k\le n-1\)), đặt \(m=2(n-k-1)\). Máy tính xử lý ô \((i,j)\) với mọi \(0\le i,j\le m\), theo thứ tự tăng dần của \(i\), và với mỗi \(i\) theo thứ tự tăng dần của \(j\). Nói cách khác, thứ tự xử lý là \((0,0),(0,1),\ldots,(0,m),(1,0),(1,1),\ldots,(1,m),\ldots,(m,0),(m,1),\ldots,(m,m)\).
• Ở bước cuối cùng (\(k=n-1\)), máy tính chỉ xử lý ô \((0,0)\). Sau đó, giá trị ghi tại \(h[0][0]\) phải biểu diễn số hòn đảo trên hành tinh dưới dạng nhị phân, với bit có trọng số nhỏ nhất nằm ở ký tự đầu tiên của xâu.

Hình dưới đây minh họa cách máy tính xử lý một bộ nhớ kích thước \(5\times5\) (\(n=2\)). Ô màu xanh lam là ô đang bị ghi đè; các ô được tô màu tạo thành vùng đang được xử lý.

Trong bước \(0\), máy tính xử lý các vùng dưới đây theo thứ tự từ trái sang phải:

Trong bước \(1\), máy tính chỉ xử lý một vùng:

Hãy cài đặt một phương pháp cho phép máy tính đếm số hòn đảo trên hành tinh Thutmus I theo đúng cơ chế hoạt động trên.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau. Chữ ký C++ trong tệp tiêu đề chính thức là:

std::string process(std::vector<std::vector<std::string>> a,
                    int i, int j, int k, int n);

• a: mảng \(3\times3\) biểu diễn vùng đang được xử lý; cụ thể, \(a=h[i..i+2][j..j+2]\). Mỗi phần tử của a là một xâu có độ dài đúng bằng \(100\), và mỗi ký tự là '0' (ASCII 48) hoặc '1' (ASCII 49).
• i, j: lần lượt là chỉ số hàng và cột của ô máy tính đang xử lý.
• k: chỉ số của bước hiện tại.
• n: tổng số bước; bề mặt hành tinh có kích thước \((2n+1)\times(2n+1)\) ô.
• Hàm phải trả về một xâu nhị phân độ dài đúng bằng \(100\). Giá trị trả về sẽ được lưu vào ô nhớ \(h[i][j]\).
• Lần gọi cuối cùng xảy ra khi \(k=n-1\). Trong lần gọi này, hàm phải trả về biểu diễn nhị phân của số hòn đảo trên hành tinh: bit có trọng số nhỏ nhất ở vị trí \(0\) (ký tự đầu tiên), bit có trọng số nhỏ thứ hai ở vị trí \(1\), và cứ tiếp tục như vậy.
• Hàm này bắt buộc phải độc lập với mọi biến tĩnh hoặc biến toàn cục; giá trị trả về chỉ được phụ thuộc vào các tham số truyền vào.

Mỗi test chứa \(T\) kịch bản độc lập, tương ứng với các bề mặt hành tinh khác nhau. Hoạt động của lời giải cho mỗi kịch bản phải độc lập với thứ tự của các kịch bản, vì các lời gọi process thuộc cùng một kịch bản có thể không diễn ra liên tiếp nhau. Tuy nhiên, đối với từng kịch bản, các lời gọi process được bảo đảm xuất hiện theo đúng trình tự đã mô tả ở trên.

Ngoài ra, trong mỗi test, nhiều phiên bản chương trình của bạn có thể được khởi chạy đồng thời. Giới hạn thời gian và bộ nhớ được tính gộp cho tất cả các phiên bản này. Mọi hành vi cố ý truyền dữ liệu ngoài giao thức giữa các phiên bản chương trình đều bị coi là gian lận và có thể dẫn đến việc bị loại khỏi kỳ thi.

Đặc biệt, mọi thông tin lưu trong biến tĩnh hoặc biến toàn cục trong một lần gọi process không được bảo đảm còn tồn tại ở các lần gọi tiếp theo.

Ràng buộc

• \(1\le T\le10\).
• \(1\le n\le20\).
• \(s[i][j]\) là '0' (ASCII 48) hoặc '1' (ASCII 49), với mọi \(0\le i,j\le2n\).
• Độ dài của \(h[i][j]\) đúng bằng \(100\), với mọi \(0\le i,j\le2n\).
• Mỗi ký tự của \(h[i][j]\) là '0' (ASCII 48) hoặc '1' (ASCII 49), với mọi \(0\le i,j\le2n\).

Trong mỗi lần gọi process:

• \(0\le k\le n-1\).
• \(0\le i,j\le2(n-k-1)\).

Phân nhóm

1. (\(6\) điểm) \(n\le2\).
2. (\(8\) điểm) \(n\le4\).
3. (\(7\) điểm) \(n\le6\).
4. (\(8\) điểm) \(n\le8\).
5. (\(7\) điểm) \(n\le10\).
6. (\(8\) điểm) \(n\le12\).
7. (\(10\) điểm) \(n\le14\).
8. (\(24\) điểm) \(n\le16\).
9. (\(11\) điểm) \(n\le18\).
10. (\(11\) điểm) \(n\le20\).

Ví dụ

'1' '0' '0'
'1' '1' '0'
'0' '0' '1'

process([["100","000","000"],["100","100","000"],["000","000","100"]],0,0,0,1)

'1' '1' '0' '1' '1'
'1' '1' '0' '0' '0'
'1' '0' '1' '1' '1'
'0' '1' '0' '0' '0'
'0' '1' '1' '1' '1'

process([["100","100","000"],["100","100","000"],["100","000","100"]],0,0,0,2)
process([["100","000","100"],["100","000","000"],["000","100","100"]],0,1,0,2)
process([["000","100","100"],["000","000","000"],["100","100","100"]],0,2,0,2)
process([["100","100","000"],["100","000","100"],["000","100","000"]],1,0,0,2)
process([["100","000","000"],["000","100","100"],["100","000","000"]],1,1,0,2)
process([["000","000","000"],["100","100","100"],["000","000","000"]],1,2,0,2)
process([["100","000","100"],["000","100","000"],["000","100","100"]],2,0,0,2)
process([["000","100","100"],["100","000","000"],["100","100","100"]],2,1,0,2)
process([["100","100","100"],["000","000","000"],["100","100","100"]],2,2,0,2)

"011", "000", "000", "100", "100"
"111", "111", "011", "000", "000"
"110", "010", "111", "100", "100"
"000", "100", "000", "000", "000"
"000", "100", "100", "100", "100"

process([["011","000","000"],["111","111","011"],["110","010","111"]],0,0,1,2)

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau; đây chỉ là giao diện của trình chấm mẫu, không phải giao diện chuẩn vào/ra của bài:

• Dòng \(1\): \(T\).
• Khối \(i\) (\(0\le i\le T-1\)) mô tả kịch bản thứ \(i\):
  • Dòng \(1\) của khối: \(n\).
  • Dòng \(2+j\) (\(0\le j\le2n\)): \(s[j][0]\ s[j][1]\ \ldots\ s[j][2n]\).

Trình chấm mẫu in trên dòng \(1+i\) giá trị trả về cuối cùng của process cho kịch bản thứ \(i\) dưới dạng thập phân.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2022, Ai Cập: gói nguồn chính thức của bài Mars.

Sau khi khám phá \(n\) hành tinh được đánh số từ \(0\) đến \(n-1\), các Pharaoh bắt đầu xây dựng một hệ thống giao thông giữa chúng bằng các đường dịch chuyển một chiều. Mỗi đường dịch chuyển có một hành tinh xuất phát và một hành tinh đích. Khi một du khách sử dụng đường dịch chuyển tại hành tinh xuất phát, họ được dịch chuyển đến hành tinh đích. Hành tinh xuất phát và hành tinh đích có thể trùng nhau. Đường dịch chuyển có hành tinh xuất phát \(u\) và hành tinh đích \(v\) được ký hiệu là \((u,v)\).

Để khuyến khích việc sử dụng rộng rãi hệ thống dịch chuyển, các Pharaoh tạo ra một trò chơi cho du khách trong khi di chuyển. Du khách có thể bắt đầu trò chơi từ bất kỳ hành tinh nào. Các hành tinh \(0,1,\ldots,k-1\) (\(k\le n\)) được gọi là hành tinh đặc biệt. Mỗi lần đi vào một hành tinh đặc biệt, du khách nhận được một con tem.

Ban đầu, với mỗi \(i\) (\(0\le i\le k-2\)), tồn tại một đường dịch chuyển \((i,i+1)\). Các đường dịch chuyển này, có tổng cộng \(k-1\) đường, được gọi là đường dịch chuyển ban đầu.

Các đường dịch chuyển mới được thêm lần lượt từng đường một. Khi các đường mới được thêm vào, du khách có thể bắt đầu nhận được vô hạn tem. Cụ thể, điều này xảy ra khi tồn tại một dãy các hành tinh \(w[0],w[1],\ldots,w[t]\) thỏa mãn:

• \(1\le t\).
• \(0\le w[0]\le k-1\).
• \(w[t]=w[0]\).
• Với mỗi \(i\) (\(0\le i\le t-1\)), tồn tại đường dịch chuyển \((w[i],w[i+1])\).

Du khách được phép sử dụng các đường dịch chuyển ban đầu và mọi đường dịch chuyển đã được thêm cho đến thời điểm hiện tại.

Hãy giúp các Pharaoh xác định, sau mỗi lần thêm một đường dịch chuyển, liệu du khách có thể nhận được vô hạn tem hay không.

Chi tiết cài đặt

Bạn cần cài đặt hai hàm sau. Chữ ký C++ trong tệp tiêu đề chính thức là:

void init(int n, int k);
int add_teleporter(int u, int v);

Hàm init:

• n: số hành tinh.
• k: số hành tinh đặc biệt.
• Hàm được gọi đúng một lần, trước mọi lời gọi add_teleporter.

Hàm add_teleporter:

• u, v: hành tinh xuất phát và hành tinh đích của đường dịch chuyển vừa được thêm.
• Hàm được gọi không quá \(m\) lần.
• Hàm phải trả về \(1\) nếu sau khi thêm đường dịch chuyển \((u,v)\), du khách có thể nhận được vô hạn tem; ngược lại, hàm phải trả về \(0\).
• Ngay khi hàm trả về \(1\), chương trình của bạn sẽ bị dừng.

Ràng buộc

• \(1\le n\le300\,000\).
• \(1\le m\le500\,000\).
• \(1\le k\le n\).

Trong mỗi lần gọi add_teleporter:

• \(0\le u\le n-1\) và \(0\le v\le n-1\).
• Trước khi thêm \((u,v)\), chưa có đường dịch chuyển nào từ hành tinh \(u\) đến hành tinh \(v\).

Phân nhóm

1. (\(2\) điểm) \(n=k\), \(n\le100\), \(m\le300\).
2. (\(10\) điểm) \(n\le100\), \(m\le300\).
3. (\(18\) điểm) \(n\le1\,000\), \(m\le5\,000\).
4. (\(30\) điểm) \(n\le30\,000\), \(m\le50\,000\), \(k\le1\,000\).
5. (\(40\) điểm) Không có ràng buộc bổ sung.

Ví dụ

init(6, 3);

init(4, 2);

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau; đây chỉ là giao diện của trình chấm mẫu, không phải giao diện chuẩn vào/ra của bài:

• Dòng \(1\): \(n\ m\ k\).
• Dòng \(2+i\) (\(0\le i\le m-1\)): \(u[i]\ v[i]\).

Đầu tiên, trình chấm mẫu gọi init(n, k). Sau đó, với \(i=0,1,\ldots,m-1\) theo đúng thứ tự, trình chấm gọi add_teleporter(u[i], v[i]).

Trình chấm mẫu in chỉ số của lời gọi add_teleporter đầu tiên trả về \(1\) (một số từ \(0\) đến \(m-1\)), hoặc in \(m\) nếu tất cả các lời gọi đều trả về \(0\). Nếu một lời gọi trả về số nguyên khác \(0\) và \(1\), trình chấm mẫu in \(-1\) rồi dừng chương trình ngay lập tức.

Các tệp ví dụ chính thức dành cho trình chấm mẫu là:

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

4

4 1 2
1 1

0

4 3 2
1 3
2 0
3 2

2

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2022, Ai Cập: gói nguồn chính thức của bài Game.

Các Pharaoh sử dụng chuyển động tương đối và lực hấp dẫn của các hành tinh để tăng tốc phi thuyền. Giả sử một phi thuyền lần lượt đi qua \(n\) hành tinh có tốc độ quỹ đạo \(p[0],p[1],\ldots,p[n-1]\). Với mỗi hành tinh, các nhà khoa học của Pharaoh có thể chọn dùng hành tinh đó để tăng tốc phi thuyền hoặc không. Để tiết kiệm năng lượng, sau khi tăng tốc bằng một hành tinh có tốc độ quỹ đạo \(p[i]\), phi thuyền không thể tiếp tục được tăng tốc bằng bất kỳ hành tinh nào có tốc độ quỹ đạo \(p[j]<p[i]\).

Nói cách khác, các hành tinh được chọn tạo thành một dãy con tăng dần của \(p[0],p[1],\ldots,p[n-1]\). Một dãy con của \(p\) là một dãy thu được bằng cách xóa đi không, một hoặc nhiều phần tử của \(p\) mà không thay đổi thứ tự các phần tử còn lại. Chẳng hạn, \([0]\), \([]\), \([0,2]\) và \([0,1,2]\) là các dãy con của \([0,1,2]\), còn \([2,1]\) thì không.

Các nhà khoa học xác định rằng có tổng cộng \(k\) cách khác nhau để chọn một nhóm hành tinh nhằm tăng tốc phi thuyền, nhưng họ đã làm mất toàn bộ dữ liệu về tốc độ quỹ đạo, kể cả giá trị \(n\). Tuy nhiên, họ nhớ rằng \((p[0],p[1],\ldots,p[n-1])\) là một hoán vị của \(0,1,\ldots,n-1\). Một hoán vị là một dãy chứa mỗi số nguyên từ \(0\) đến \(n-1\) đúng một lần. Hãy tìm một hoán vị \(p[0],p[1],\ldots,p[n-1]\) có thể xảy ra và có độ dài đủ nhỏ.

Bạn cần giải bài toán cho \(q\) phi thuyền khác nhau. Với phi thuyền thứ \(i\), bạn nhận được số nguyên \(k_i\), là số cách khác nhau để chọn một nhóm hành tinh tăng tốc phi thuyền. Hãy tìm một dãy tốc độ quỹ đạo có độ dài \(n_i\) đủ nhỏ sao cho có đúng \(k_i\) cách chọn một dãy con các hành tinh với tốc độ quỹ đạo tăng dần.

Lưu ý rằng dãy con rỗng cũng được tính là một dãy con tăng dần.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau. Chữ ký C++ trong tệp tiêu đề chính thức là:

std::vector<int> construct_permutation(long long k);

• k: số dãy con tăng dần mong muốn.
• Hàm phải trả về một mảng gồm \(n\) phần tử, mỗi phần tử nằm trong đoạn từ \(0\) đến \(n-1\).
• Mảng trả về phải là một hoán vị hợp lệ có đúng \(k\) dãy con tăng dần.
• Hàm được gọi tổng cộng \(q\) lần. Mỗi lần gọi phải được xử lý như một trường hợp độc lập.

Ràng buộc

• \(1\le q\le100\).
• \(2\le k_i\le10^{18}\) với mọi \(0\le i\le q-1\).

Phân nhóm và cách tính điểm

1. (\(10\) điểm) \(2\le k_i\le90\) với mọi \(0\le i\le q-1\). Nếu tất cả các hoán vị bạn trả về đều đúng và có độ dài không quá \(90\), bạn nhận được \(10\) điểm; nếu không, bạn nhận được \(0\) điểm cho phân nhóm này.

2. (\(90\) điểm) Không có ràng buộc bổ sung. Gọi \(m\) là độ dài lớn nhất trong tất cả các hoán vị bạn trả về. Điểm của phân nhóm này được tính như sau:

   Điều kiện	Điểm
   \(m\le90\)	\(90\)
   \(90<m\le120\)	\(90-\dfrac{m-90}{3}\)
   \(120<m\le5000\)	\(80-\dfrac{m-120}{65}\)
   \(m>5000\)	\(0\)

Ví dụ

construct_permutation(3);

construct_permutation(8);

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau; đây chỉ là giao diện của trình chấm mẫu, không phải giao diện chuẩn vào/ra của bài:

• Dòng \(1\): \(q\).
• Dòng \(2+i\) (\(0\le i\le q-1\)): \(k_i\).

Với mỗi \(k_i\), trình chấm mẫu in trên một dòng giá trị mà construct_permutation trả về, hoặc một thông báo lỗi nếu xảy ra lỗi.

Tệp ví dụ chính thức dành cho trình chấm mẫu là:

2
3
8

2
1 0
3
0 1 2

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2022, Ai Cập: gói nguồn chính thức của bài Permutation.