Contest ôn thi HSG 9-10 (số 8)

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Số nguyên tố 40 (p) 1.0s 512M
2 Số bé hơn 40 (p) 1.0s 512M
3 Xâu bao phủ 20 (p) 1.5s 512M

1. Số nguyên tố

Điểm: 40 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: PRIME.INP Output: PRIME.OUT

Số nguyên tố là một số nguyên dương, có chính xác hai ước dương khác nhau là \(1\) và chính nó. Ví dụ: \(7\) là số nguyên tố (ước là \(1, 7\)), còn \(6\) thì không phải (có các ước \(2, 3\) khác với \(1, 6\)). Nhắc lại, với \(a, b \in \mathbb{Z}\), \(a\) được gọi là ước của \(b\) nếu như \(b\) chia hết cho \(a\).

Yêu cầu: Cho số nguyên \(n\). Hãy kiểm tra \(n\) có phải là số nguyên tố hay không.

Input

  • Dòng duy nhất chứa số nguyên \(n\) (\(|n| \le 10^{16}\)).

Output

  • In ra YES nếu \(n\) là số nguyên tố, ngược lại in ra NO.

Example

Test 1

Input 
5
Output 
YES
Note

Số \(5\) chỉ có \(2\) ước là \(1, 5\).

Test 2

Input 
1
Output 
NO
Note

Số \(1\) không phải là số nguyên tố.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(1 \le n \le 20\)
  • Subtask \(2\) (\(30\%\) số điểm): \(|n| \le 10^6\)
  • Subtask \(3\) (\(40\%\) số điểm): \(|n| \le 10^{12}\)
  • Subtask \(4\) (\(10\%\) số điểm): không có ràng buộc gì thêm.

2. Số bé hơn

Điểm: 40 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: LESSER.INP Output: LESSER.OUT

Cho dãy số nguyên \(a\) gồm \(n\) phần tử \(a_1, a_2, \dots, a_n\). Ta định nghĩa thứ bậc của số nguyên dương \(x\) là số lượng số nguyên dương nhỏ hơn \(x\) mà không xuất hiện trong dãy \(a\).

Yêu cầu: Tính và in ra thứ bậc của \(m\) số nguyên dương \(x_1, x_2, \dots, x_m\) trên dãy \(a\) cho trước.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n, m\) (\(1 \leq n, m \leq 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(1 \leq a_i \leq 10^9\)).
  • Dòng thứ ba chứa \(m\) số nguyên \(x_1, x_2, x_3, \dots, x_m\) (\(1 \leq x_j \leq 10^9\)).

Output

  • Với mỗi \(x_j\), in kết quả tính thứ bậc của \(x_j\) trên một dòng, theo thứ tự \(j = 1 \rightarrow m\).

Example

Test 1

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

Một vài số nguyên dương không xuất hiện trong \(a\) là 2, 4, 6, 9. Đây là các số bé hơn \(x_3 = 10\).

Scoring

  • Subtask 1 (\(25\%\) số điểm): \(n, m \leq 200\).
  • Subtask 2 (\(25\%\) số điểm): \(n, m, a_i, x_j \leq 2000\).
  • Subtask 3 (\(25\%\) số điểm): \(m, n \leq 4000\).
  • Subtask 4 (\(25\%\) số điểm): không có ràng buộc thêm.

3. Xâu bao phủ

Điểm: 20 (p) Thời gian: 1.5s Bộ nhớ: 512M Input: STRING.INP Output: STRING.OUT

Quỳnh mới khai trương một tiệm hoa, cô ấy muốn đặt tên tiệm là \(S_Q\) (một xâu kí tự). Khi Quỳnh hỏi ý kiến của tôi, tôi lại cho rằng tên \(S_T\) mới là đẹp. Hai bên bất đồng quan điểm, để tránh tranh cãi nhiều hơn nữa (có thể dẫn tới việc tôi bị đuổi khỏi nhà), đại ca L giấu tên đã hiến kế như sau: “Chi bằng ta chọn ra một xâu \(S_L\) ngắn nhất, sao cho cả \(S_Q\) và \(S_T\) đều là xâu con* của \(S_L\)”. Cả hội nhất trí, nhưng việc tính toán thì để ai? Tôi thà rửa bát còn hơn phải đụng vào đống giải thuật đã được 'đóng gói' cẩn thận trong kí ức (APAC) …

(*) xâu con (subsequence) là xâu thu được bằng cách xóa đi 0 hoặc nhiều ký tự từ xâu gốc mà vẫn giữ nguyên thứ tự của các ký tự còn lại.

Yêu cầu: Cho hai xâu \(S_Q, S_T\). Hãy tìm xâu \(S_L\) ngắn nhất sao cho \(S_Q, S_T\) là xâu con của nó.

Input

  • Dòng đầu tiên chứa xâu \(S_Q\). Dòng thứ hai chứa xâu \(S_T\). Kí hiệu \(|S|\) là độ dài xâu.
  • Dữ liệu đảm bảo \(S_Q, S_T\) chỉ chứa kí tự latin in thường và \(1 \leq |S_Q|, |S_T| \leq 2500\).

Output

  • Dòng duy nhất chứa độ dài của xâu \(S_L\) tìm được.

Example

Test 1

Input 
qqhana
quynhanh
Output 
10
Note

Một xâu \(S_L\) thỏa mãn là qquynhanha.

Scoring

  • Subtask 1 (\(30\%\) số điểm): \(|S_Q|, |S_T| \leq 5\).
  • Subtask 2 (\(30\%\) số điểm): \(|S_Q|, |S_T| \leq 27\).
  • Subtask 3 (\(40\%\) số điểm): không có ràng buộc gì thêm.