Tuyển sinh lớp 10 Chuyên KHTN 2026

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Bài 1: sqrt (TS10 KHTN - 2026) 3 (p) 1.0s 256M
2 Bài 2: card (TS10 KHTN - 2026) 3 (p) 1.0s 256M
3 Bài 3: TILE (TS10 KHTN - 2026) 2 (p) 1.0s 256M
4 Bài 4: LOTO (TS10 KHTN - 2026) 1 (p) 1.0s 256M
5 Bài 5: NGHT (TS10 KHTN - 2026) 1 (p) 1.0s 256M

1. Bài 1: sqrt (TS10 KHTN - 2026)

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

Hãy in ra số lượng phần tử trong dãy là số chính phương. Một số nguyên dương \(x\) được gọi là số chính phương nếu tồn tại một số nguyên dương \(k\) sao cho \(k^2 = x\).

Input

  • Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9, 1 \le i \le N\)).

Output

  • In ra số lượng số chính phương trong dãy.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N \le 100, a_i \le 100\) (\(1 \le i \le N\)).
  • Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc bổ sung.

Example

Test 1

Input 
5
1 4 7 16 10
Output 
3
Note

Có \(3\) số chính phương: \(1 = 1^2, 4 = 2^2, 16 = 4^2\).

2. Bài 2: card (TS10 KHTN - 2026)

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

Bạn có \(N\) lá bài đặt thành một hàng, lá bài thứ \(i\) có giá trị \(a_i\). Bạn chơi trò chơi sau:

  • Trong mỗi lượt, lấy hai lá bài ở đầu hàng bên trái ra so sánh giá trị.
  • Nếu một lá bài có giá trị lớn hơn, lá lớn hơn này được đặt lại vào đầu hàng, lá nhỏ hơn bị loại bỏ.
  • Nếu hai lá bài có giá trị bằng nhau, cả hai đều bị loại bỏ.

Lặp lại cho đến khi còn tối đa \(1\) lá bài. Hãy in ra giá trị của lá bài còn lại cuối cùng. Nếu không còn lá bài nào, in ra \(0\).

Input

  • Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \le N \le 10^6\)).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9, 1 \le i \le N\)).

Output

  • In ra một số nguyên duy nhất: giá trị lá bài còn lại, hoặc \(0\) nếu không còn lá nào.

Example

Test 1

Input 
5
3 1 4 1 5
Output 
5
Note
  • Lượt 1: so \(3\) và \(1 \rightarrow 3\) lớn hơn, hàng: \([3, 4, 1, 5]\)
  • Lượt 2: so \(3\) và \(4 \rightarrow 4\) lớn hơn, hàng: \([4, 1, 5]\)
  • Lượt 3: so \(4\) và \(1 \rightarrow 4\) lớn hơn, hàng: \([4, 5]\)
  • Lượt 4: so \(4\) và \(5 \rightarrow 5\) lớn hơn, hàng: \([5]\)
  • Còn lại: \(5\).

Test 2

Input 
4
2 2 3 3
Output 
0
Note
  • Lượt 1: so \(2\) và \(2 \rightarrow\) bằng, loại cả hai, hàng: \([3, 3]\)
  • Lượt 2: so \(3\) và \(3 \rightarrow\) bằng, loại cả hai, hàng: \([]\)
  • Không còn lá nào \(\rightarrow 0\).

Subtasks

  • Subtask 1 (40% số điểm): \(N \le 10^3\).
  • Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

3. Bài 3: TILE (TS10 KHTN - 2026)

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

Bạn cần lát đầy dải ô vuông kích thước \(1 \times N\) bằng các viên gạch có độ dài \(1, 2,\) hoặc \(3\).

  • Gạch có độ dài \(1\) có \(a\) màu khác nhau.
  • Gạch có độ dài \(2\) có \(b\) màu khác nhau.
  • Gạch có độ dài \(3\) có \(c\) màu khác nhau.

Hai cách lát được coi là khác nhau nếu tồn tại ít nhất một ô vuông kích thước \(1 \times 1\) mà viên gạch phủ trên đó khác nhau về độ dài hoặc màu sắc.

Hãy đếm số cách lát đầy dải \(1 \times N\), kết quả lấy dư cho \(998244853\).

Input

  • Dòng duy nhất chứa bốn số nguyên dương \(N, a, b, c\) (\(1 \le N \le 10^6, 1 \le a, b, c \le 10^9\)).

Output

  • In ra một số nguyên duy nhất là số cách lát dải, lấy dư cho \(998244853\).

Constraints

  • \(50\%\) số test có ràng buộc bổ sung: \(N \le 10^3\).
  • \(50\%\) số test còn lại không có ràng buộc bổ sung.

Example

Test 1

Input 
3 2 1 1
Output 
13
Note

Với \(N=3, a=2, b=1, c=1\):

  • Ba gạch độ dài \(1\): \(2^3 = 8\) cách.
  • Gạch độ dài \(1\) + gạch độ dài \(2\): \(2 \cdot 1 = 2\) cách.
  • Gạch độ dài \(2\) + gạch độ dài \(1\): \(1 \cdot 2 = 2\) cách.
  • Một gạch độ dài \(3\): \(1\) cách.
  • Tổng cộng: \(8 + 2 + 2 + 1 = 13\) cách.

4. Bài 4: LOTO (TS10 KHTN - 2026)

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

Trường H tổ chức chương trình tuyển chọn học sinh cho đội tuyển chuyên. Có \(2026\) chuyên đề kiến thức được đánh số thứ tự từ \(1\) đến \(2026\). Hội đồng chuyên môn xác định \(M\) chuyên đề trọng tâm, trong đó \(K\) chuyên đề đầu tiên được xem là các chuyên đề cốt lõi quan trọng nhất.

Mỗi học sinh đăng ký đúng \(K\) chuyên đề mà mình tự tin nhất (các chuyên đề đôi một khác nhau). Dựa trên mức độ phù hợp giữa lựa chọn của học sinh và danh sách chuyên đề trọng tâm, hội đồng phân loại học sinh theo các nhóm năng lực sau (ưu tiên nhóm có số thứ tự nhỏ nhất mà học sinh đạt được):

  • Nhóm năng lực 1: Toàn bộ \(K\) chuyên đề đăng ký đều nằm trong \(K\) chuyên đề cốt lõi.
  • Nhóm năng lực 2: Toàn bộ \(K\) chuyên đề đăng ký đều nằm trong \(M\) chuyên đề trọng tâm.
  • Nhóm năng lực 3: Có thể chọn ra \(K - 1\) chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc \(K - 1\) chuyên đề cốt lõi đầu tiên.
  • Nhóm năng lực 4: Có thể chọn ra \(K - 1\) chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc \(K\) chuyên đề cốt lõi.
  • Nhóm năng lực 5: Có thể chọn ra \(K - 1\) chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc \(M\) chuyên đề trọng tâm.
  • Nhóm năng lực 6: Có thể chọn ra \(K - 2\) chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc \(M\) chuyên đề trọng tâm.

Có \(J\) học sinh tham gia đăng ký. Mỗi học sinh được xếp vào nhóm năng lực có số thứ tự nhỏ nhất mà học sinh đó thỏa mãn điều kiện.

Viết một chương trình để xác định:

  • Nhiệm vụ 1: Số lượng học sinh được xếp vào nhóm năng lực \(C\) cụ thể. Các nhóm năng lực được đánh số \(1, 2, \dots, 6, 7\). Nhóm năng lực 7 dành cho những học sinh không thuộc nhóm nào ở trên.
  • Nhiệm vụ 2: Các chuyên đề nhiều học sinh đăng ký nhất, được viết theo thứ tự tăng dần nếu có nhiều hơn 1 chuyên đề thỏa mãn.

Input

  • Dòng đầu tiên ghi mã số nhiệm vụ (\(1\) hoặc \(2\)).
  • Dòng thứ hai ghi 3 số \(M, K, C\) (\(1 \le M \le 2026, 5 \le K \le M, 1 \le C \le 7\)).
  • Dòng thứ ba ghi số thứ tự \(M\) chuyên đề trọng tâm, theo thứ tự ưu tiên (cốt lõi trước, mở rộng sau).
  • Dòng thứ tư ghi một số tự nhiên \(J\) (\(1 \le J \le 5 \cdot 10^4\)), biểu thị số lượng học sinh.
  • Mỗi dòng trong số \(J\) dòng tiếp theo ghi \(K\) số tự nhiên, biểu thị các chuyên đề mà học sinh đó đăng ký.

Output

  • Đối với nhiệm vụ 1, in ra số lượng học sinh thuộc nhóm năng lực \(C\).
  • Đối với nhiệm vụ 2, in ra số thứ tự các chuyên đề được nhiều học sinh đăng ký nhất, viết theo thứ tự tăng dần.

Example

Test 1

Input 
1
6 5 1
11 12 13 14 15 16
1
15 14 13 12 11
Output 
1
Note

Nhiệm vụ 1. Hội đồng xác định 6 chuyên đề trọng tâm theo thứ tự là 11, 12, 13, 14, 15, 16. Mỗi học sinh đăng ký 5 chuyên đề. Có một học sinh duy nhất. Học sinh này đăng ký các chuyên đề 15, 14, 13, 12, 11. Học sinh được xếp vào Nhóm 1 vì đã đăng ký đúng 5 chuyên đề cốt lõi đầu tiên.

Test 2

Input 
1
6 5 4
21 22 23 24 25 26
2
29 21 25 23 22
23 21 25 22 24
Output 
1
Note

Nhiệm vụ 1. Có 2 học sinh. Một trong số họ được xếp vào Nhóm 1 và một học sinh được xếp vào Nhóm 4. Cần tìm số lượng học sinh thuộc Nhóm 4, kết quả là 1.

Test 3

Input 
1
6 5 7
91 92 93 94 95 96
3
2 35 6 8 14
1 3 47 18 29
12 32 7 4 93
Output 
3
Note

Có 3 học sinh. Không ai trong số họ thuộc bất kỳ nhóm nào từ 1 đến 6.

Test 4

Input 
2
6 5 4
71 72 73 74 75 76
2
79 71 75 73 72
73 71 75 72 74
Output 
71 72 73 75
Note

Nhiệm vụ 2. Các chuyên đề 71, 72, 73, 75 đều được cả hai học sinh đăng ký, nên chúng là các chuyên đề được nhiều học sinh đăng ký nhất.

Scoring

  • \(50\%\) số test có \(K \le 10^4, J \le 2 \cdot 10^4\).
  • \(50\%\) còn lại không có ràng buộc gì thêm.

5. Bài 5: NGHT (TS10 KHTN - 2026)

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

Con mã (ô S) tấn công các ô vuông (dấu x) trên bàn cờ như hình dưới. Có một bàn cờ kích thước \(4 \cdot n\), với \(4\) hàng và \(n\) cột, trong đó \(1 \le n \le 100\). Gọi \(Z\) là tập các ô trên bàn cờ. Các hàng được đánh số thứ tự từ trên xuống dưới, từ \(1\) đến \(4\), các cột được đánh số thứ tự từ trái qua phải, từ \(1\) đến \(n\). Quân mã chỉ có thể được đặt trên các ô không thuộc \(Z\) và hai quân bất kỳ không được ăn nhau.

Giả định trong mỗi cột có nhiều nhất một ô thuộc \(Z\). Vì vậy, tập \(Z\) có thể được mô tả bằng chuỗi \(k_1, k_2, \dots, k_n\) trong đó \(k_i \in \{0, 1, 2, 3, 4\}\). Nếu \(k_i = 0\) thì cột \(i\) không có ô nào thuộc \(Z\), ngược lại, ô ở hàng \(k_i\), cột \(i\) thuộc \(Z\).

Hãy tính số lượng tối đa của các quân mã \(M\), có thể đặt trên bàn cờ theo quy tắc trên và số lượng \(L\) cách sắp xếp có thể của \(M\) quân mã trên bàn cờ này.

Input

  • Dòng đầu tiên là số nguyên dương \(n\) (\(1 \le n \le 100\)).
  • Mỗi dòng trong \(n\) dòng sau ghi một số \(0, 1, 2, 3\) hoặc \(4\).

Output

  • In ra hai số \(M\) và \(L\).

Example

Test 1

Input 
2
1
0
Output 
4 8
Note

Xếp được tối đa \(4\) con mã và có \(8\) cách bố trí hợp lệ như hình dưới:

Subtasks

  • \(50\%\) số test có ràng buộc bổ sung: \(n \le 25\).
  • \(50\%\) số test còn lại không có ràng buộc bổ sung.