NOI Singapore 2026 - Vòng sơ khảo

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 NOI Singapore 2026 - Area 2 100 (p) 1.0s 1G
2 NOI Singapore 2026 - Hungry Cats 100 (p) 1.0s 1G
3 NOI Singapore 2026 - Airplane 2 100 (p) 1.0s 1G
4 NOI Singapore 2026 - Digits 100 (p) 1.0s 1G
5 NOI Singapore 2026 - Mushroom Ring 100 (p) 2.5s 1G

1. NOI Singapore 2026 - Area 2

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Ziv có \(n\) cặp que, được đánh số từ \(1\) đến \(n\). Cặp thứ \(i\) gồm hai que, mỗi que dài \(a_i\).

Ziv muốn chọn hai chỉ số khác nhau \(x\) và \(y\) (\(x \ne y\)) để dựng một khung hình chữ nhật. Hai cạnh của hình chữ nhật dài \(a_x\) và \(a_y\), nên diện tích bằng \(a_x \times a_y\).

Hãy tìm diện tích lớn nhất của một khung hình chữ nhật mà Ziv có thể dựng.

Dữ liệu vào

  • Dòng đầu chứa số nguyên \(n\).
  • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\).

Dữ liệu ra

In ra một số nguyên duy nhất: diện tích lớn nhất có thể.

Giới hạn

\[ 2 \le n \le 10 \]
\[ 1 \le a_i \le 1000 \]

Chấm điểm

Phần Điểm Giới hạn thêm
1 20 \(n=2\)
2 20 \(n=3\)
3 60 Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input 
2
8
9
Output 
72

Chỉ có một khung có thể tạo: \(8 \times 9\), diện tích bằng \(72\).

Ví dụ 2

Input 
3
16
44
18
Output 
792

Ba diện tích có thể tạo là \(16\times44=704\), \(16\times18=288\) và \(44\times18=792\). Giá trị lớn nhất là \(792\).

Ví dụ 3

Input 
8
6
7
6
7
99
99
69
1
Output 
9801

2. NOI Singapore 2026 - Hungry Cats

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Tại vương quốc mèo ăn thịt đồng loại, ngày hội National Cat Day sắp diễn ra. Có \(n\) con mèo tham gia, đánh số từ \(1\) đến \(n\). Con mèo thứ \(i\) có mức hạnh phúc \(h_i\).

Tại bất kỳ thời điểm nào, một con mèo có thể ăn một con mèo có mức hạnh phúc nhỏ hơn nghiêm ngặt. Sau đó:

  • mức hạnh phúc của con mèo vừa ăn tăng thêm \(1\);
  • nó không thể ăn thêm bất kỳ con mèo nào khác;
  • con mèo bị ăn biến mất.

Hãy xác định liệu có thể thực hiện các hành động sao cho cuối cùng chỉ còn đúng một con mèo hay không.

Dữ liệu vào

  • Dòng đầu chứa số nguyên \(n\).
  • Dòng thứ hai chứa \(n\) số nguyên \(h_1,h_2,\ldots,h_n\).

Dữ liệu ra

In YES nếu có thể chỉ còn một con mèo, ngược lại in NO.

Giới hạn

\[ 2 \le n \le 200\,000 \]
\[ 0 \le h_i \le 10^9 \]

Chấm điểm

Phần Điểm Giới hạn thêm
1 8 \(n=2\)
2 10 \(n\le3\)
3 6 \(h_1=h_n\)
4 18 \(n\le1000\)
5 28 \(h_i\le h_{i+1}\) với mọi \(1\le i<n\)
6 30 Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input 
2
3141 59
Output 
YES

Ví dụ 2

Input 
3
31 41 59
Output 
YES

Con mèo thứ hai có thể ăn con thứ nhất, sau đó bị con thứ ba ăn.

Ví dụ 3

Input 
5
10 0 24 25 10
Output 
NO

Không tồn tại thứ tự ăn nào để cuối cùng chỉ còn một con mèo.

Ví dụ 4

Input 
6
2 25 11 5 20 26
Output 
NO

3. NOI Singapore 2026 - Airplane 2

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trên một máy bay có \(h\) hàng ghế và \(w\) cột ghế. Hàng được đánh số từ \(1\) đến \(h\) theo chiều từ trên xuống, cột được đánh số từ \(1\) đến \(w\) theo chiều từ trái sang. Ghế ở hàng \(i\), cột \(j\) được ký hiệu \((i,j)\).

Pan bán vé cho \(k\) hành khách, đánh số từ \(1\) đến \(k\). Hành khách thứ \(i\) có cột đã định \(c_i\); Pan được chọn một hàng \(r_i\) bất kỳ cho người đó. Không được có hai hành khách ngồi cùng một ghế.

Để bảo đảm cân bằng, hành khách ở hàng trước không được ngồi ở cột nằm sau. Nói cách khác, với hai ghế đã gán \((a_1,b_1)\) và \((a_2,b_2)\), nếu \(a_1<a_2\) thì phải có \(b_1\le b_2\).

Độ hài lòng chung là khoảng cách Manhattan nhỏ nhất giữa mọi cặp ghế đã gán. Khoảng cách giữa \((a_1,b_1)\) và \((a_2,b_2)\) là

\[ |a_1-a_2|+|b_1-b_2|. \]

Hãy tìm độ hài lòng chung lớn nhất trong mọi cách gán hàng hợp lệ, hoặc xác định rằng không tồn tại cách gán hợp lệ.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên \(h,w,k\).
  • Dòng thứ hai chứa \(k\) số nguyên \(c_1,c_2,\ldots,c_k\).

Dữ liệu ra

In độ hài lòng chung lớn nhất. Nếu không có cách gán hợp lệ, in \(-1\).

Giới hạn

\[ 1\le h,w\le10^9,\qquad 2\le k\le200\,000 \]
\[ 1\le c_i\le w \]

Chấm điểm

Phần Điểm Giới hạn thêm
1 5 \(w=1\)
2 5 \(c_i=i\) với mọi \(1\le i\le k\)
3 7 \(c\) là cấp số cộng: \(c_{i+1}-c_i=c_i-c_{i-1}\) với mọi \(2\le i<k\)
4 9 \(h,w,k\le8\)
5 31 \(h,w,k\le3000\)
6 16 Các \(c_i\) đôi một khác nhau
7 27 Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input 
5 1 6
1 1 1 1 1 1
Output 
-1
Note

Máy bay chỉ có \(5\) ghế nên không thể xếp \(6\) hành khách vào các ghế khác nhau.

Ví dụ 2

Input 
2 7 3
1 2 3
Output 
1

Ví dụ 3

Input 
3 7 3
1 4 7
Output 
4

Ví dụ 4

Input 
50 50 10
34 21 28 44 41 28 5 10 16 24
Output 
9

Ví dụ 5

Input 
4 11 5
1 1 11 7 3
Output 
2
Note

Một cách tối ưu là xếp hành khách thứ nhất ở hàng \(1\) và các hành khách còn lại ở hàng \(4\). Khoảng cách nhỏ nhất là khoảng cách giữa ghế \((4,1)\) và \((4,3)\), bằng \(2\).

Hình 1: Một cách xếp hợp lệ tối ưu cho ví dụ 5.

Hình 2: Một cách xếp không hợp lệ vì vi phạm điều kiện cân bằng giữa thứ tự hàng và cột.

4. NOI Singapore 2026 - Digits

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Số yêu thích của Jayden là chuỗi \(x\) gồm \(m\) chữ số. Ziv đưa cho cậu \(n\) chuỗi \(m\) chữ số khác, ký hiệu \(v_1,v_2,\ldots,v_n\). Mọi chữ số đều thuộc \([0,k-1]\). Ký hiệu \(v_i[j]\) là chữ số thứ \(j\) từ trái sang của \(v_i\).

Một thao tác trên \(v_i\) được thực hiện như sau:

  1. Chọn \(1\le l\le r\le m\).
  2. Với mọi \(l\le j\le r\), thay \(v_i[j]\) bởi \((v_i[j]+a_j)\bmod k\).

Chi phí của thao tác là \(c_l+c_r\) (nếu \(l=r\) thì chi phí là \(2c_l\)).

Với từng \(v_i\) một cách độc lập, hãy tìm tổng chi phí nhỏ nhất để biến \(v_i\) thành \(x\) bằng một số bất kỳ thao tác. Nếu không thể, in \(-1\).

Dữ liệu vào

  • Dòng đầu chứa \(n,m,k\).
  • Dòng thứ hai chứa \(a_1,a_2,\ldots,a_m\).
  • Dòng thứ ba chứa \(c_1,c_2,\ldots,c_m\).
  • Dòng thứ tư chứa chuỗi \(x\).
  • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa chuỗi \(v_i\).

Các chuỗi có thể có chữ số 0 ở đầu, vì vậy cần đọc chúng dưới dạng chuỗi.

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) là chi phí nhỏ nhất để biến \(v_i\) thành \(x\), hoặc \(-1\) nếu không thể.

Giới hạn

\[ 1\le n\le200\,000,\quad 1\le m\le5,\quad 2\le k\le10 \]
\[ 1\le a_i\le k-1,\qquad 1\le c_i\le10^9 \]

Chấm điểm

Phần Điểm Giới hạn thêm
1 5 \(m=1\) và mọi \(a_i=1\)
2 13 \(m=2\) và mọi \(a_i=1\)
3 10 \(k=2\) và mọi \(c_i\) bằng nhau
4 16 Mọi \(c_i\) bằng nhau
5 24 \(n\le20\)
6 32 Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input 
6 3 8
1 2 3
3 1 4
676
356
431
676
767
133
715
Output 
16
42
0
-1
25
37

Với \(v_1=356\), có thể thực hiện lần lượt các thao tác \([1,2]\), \([1,1]\), \([1,1]\) để được \(356\to476\to576\to676\), tổng chi phí \(4+6+6=16\). Chuỗi \(v_3\) đã bằng \(x\). Không có cách biến \(v_4=767\) thành \(676\).

Ví dụ 2

Input 
3 4 2
1 1 1 1
1 1 1 1
1001
1110
1100
0110
Output 
2
4
2

Ví dụ 3

Input 
1 1 10
1
67
6
7
Output 
1206

Ví dụ 4

Input 
1 2 10
1 1
1 1000000000
24
83
Output 
1000000007

5. NOI Singapore 2026 - Mushroom Ring

Điểm: 100 (p) Thời gian: 2.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Làng Ốc Sên gồm một vòng \(n\) cây nấm khổng lồ, đánh số từ \(1\) đến \(n\). Bên cạnh mỗi cây nấm có \(n-1\) biển chỉ đến tất cả các cây nấm khác, tổng cộng \(n(n-1)\) biển.

Trên một số biển có ghi \(m\) đoạn số liên tiếp. Biển đặt cạnh nấm \(u_i\) và chỉ đến nấm \(v_i\) mang mọi số từ \(a_i\) đến \(b_i\). Các biển ban đầu thỏa hai quy tắc rõ ràng:

  1. Biển cạnh nấm \(u_i\) không được chứa số \(u_i\), tức \(u_i<a_i\) hoặc \(b_i<u_i\).
  2. Hai đoạn trên các biển cạnh cùng một cây nấm không được chứa chung một số. Nếu \(i\ne j\) và \(u_i=u_j\) thì \(b_i<a_j\) hoặc \(b_j<a_i\).

Không có ràng buộc tương ứng nào đối với \(v_i\).

Một con ốc đang ở nấm \(c\) muốn đến nấm \(d\). Nếu \(c=d\), nó đã đến nơi. Nếu không, nó tìm trong các biển cạnh nấm \(c\) biển có chứa số \(d\), đi theo biển đó tới \(v_i\), rồi lặp lại. Nhờ hai quy tắc trên, tại mỗi cây nấm có nhiều nhất một biển chứa \(d\).

Ốc bị kẹt nếu không tìm được biển chứa \(d\); nó cũng có thể đi vào chu trình vô hạn mà không qua \(d\).

Độ hữu dụng của hệ thống biển là số cặp có thứ tự \((s,d)\) sao cho ốc xuất phát ở \(s\) có thể đến \(d\) bằng cách đi theo các biển.

Được phép thực hiện nhiều nhất \(k\) chỉnh sửa. Mỗi chỉnh sửa là thêm một số vào một biển hoặc xóa một số khỏi một biển. Sau chỉnh sửa, hai quy tắc rõ ràng vẫn phải được thỏa mãn; các số trên mỗi biển không nhất thiết còn tạo thành một đoạn liên tiếp.

Hãy tìm độ hữu dụng lớn nhất có thể đạt được.

Dữ liệu vào

  • Dòng đầu chứa \(n,m,k\).
  • \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(u_i,v_i,a_i,b_i\).

Dữ liệu ra

In một số nguyên: độ hữu dụng lớn nhất sau không quá \(k\) chỉnh sửa.

Giới hạn

\[ 2\le n\le150\,000,\quad 1\le m\le300\,000,\quad 0\le k\le10^{12} \]
\[ 1\le u_i,v_i\le n,\quad u_i\ne v_i,\quad 1\le a_i\le b_i\le n \]

Dữ liệu bảo đảm hai quy tắc rõ ràng nêu trong đề.

Chấm điểm

Phần Điểm Giới hạn thêm
1 6 \(n\le200,m\le400,k=0\)
2 6 \(n\le1500,m\le3000,k=0\)
3 22 \(n\le1500,m\le3000,k\le10\)
4 11 \(n\le1500,m\le3000,k\le1000\)
5 7 \(n\le1500,m\le3000\)
6 20 \(n\le30\,000,m\le60\,000,k=0\)
7 15 \(n\le30\,000,m\le60\,000\)
8 13 Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input 
6 7 0
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5
Output 
8
Note

Ví dụ, để đi từ nấm \(6\) tới nấm \(2\), ốc đi theo biển chứa số \(2\) tới nấm \(1\), rồi đi tới nấm \(2\). Tám cặp tới được là \((1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,2),(6,2)\).

Hình 1: Hệ thống biển chỉ đường ban đầu của ví dụ 1.

Ví dụ 2

Input 
6 7 1
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5
Output 
10
Note

Có thể thêm số \(2\) vào biển cạnh nấm \(5\) chỉ đến nấm \(6\), nhờ đó có thêm các cặp \((4,2)\) và \((5,2)\).

Hình 2: Hệ thống biển sau khi thêm số \(2\) vào biển từ nấm \(5\) đến nấm \(6\).

Ví dụ 3

Input 
6 7 2
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5
Output 
13
Note

Có thể xóa số \(3\) khỏi biển cạnh nấm \(6\) chỉ đến nấm \(1\), rồi thêm số \(3\) vào biển cạnh nấm \(6\) chỉ đến nấm \(3\). Khi đó mọi vị trí xuất phát đều có thể đến nấm \(3\).

Hình 3: Hệ thống biển sau hai chỉnh sửa của ví dụ 3.