Sau khi làm xong các bài tập thầy giáo giao, An quay sang đố Bình giải bài toán sau:

Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Tìm ba số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho. Biết số chính phương là số tự nhiên mà có thể viết dưới dạng bình phương của một số tự nhiên khác. Ví dụ: 0, 1, 2, 4, 9, 16, 25, … là các số chính phương, còn các số 2, 3, 5, 8, .. không là số chính phương.

Yêu cầu:

Hãy lập trình giúp Bình tìm ba số chính phương nhỏ nhất không xuất hiện trong dãy số.

Dữ liệu:

Cho từ tệp văn bản SOCP.INP gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~n~ (~1≤n≤10^6~)
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~0 \lt a_i \le 10^{12}, 1 \le i \le n~), các số ghi cách nhau một dấu cách.

Kết quả:

Ghi ra tệp văn bản SOCP.OUT một dòng duy nhất ghi ba số chính phương nhỏ nhất không xuất hiện trong dãy số theo thứ tự tăng dần, các số ghi cách nhau một dấu cách.

Ví dụ:

SOCP.INP

7 
0 3 6 7 10 25 4

SOCP.OUT

1 9 16

Giới hạn:

• 50% số test ứng với 50% số điểm có ~n≤10^3,0≤a_i≤10^4~.
• 30% số test ứng với 30% số điểm có ~10^3<n≤10^6, 0≤a_i≤10^6~.</li>
• 20% số test ứng với 20% số điểm có ~0≤a_i≤10^{12}~.

Bình vừa tham gia vào một câu lạc bộ của nhà trường. Trong câu lạc bộ có ~N~ học sinh được chia thành từng tổ khác nhau. Mỗi học sinh thuộc một tổ nào đó. Trong buổi làm quen cậu muốn biết câu lạc bộ có bao nhiêu tổ. Khi gặp từng người cậu hỏi duy nhất một câu hỏi: "Tổ cậu có bao nhiêu người?". Từ kết quả trả lời của từng học sinh, cậu đã xác định được số tổ của câu lạc bộ. Ví dụ: Với ~N~=7 và các câu trả lời lần lượt là 2, 3, 2, 3, 2, 2, 3 thì câu lạc bộ có 3 tổ khác nhau.

Yêu cầu:

Cho biết ~N~ và các các câu trả lời. Hãy xác định số tổ của câu lạc bộ. Dữ liệu luôn đảm bảo có kết quả.

Dữ liệu:

Cho từ tệp văn bản CLB.INP gồm:

• Dòng đầu tiên ghi số nguyên dương ~N~ (~N≤10^6~) là số lượng học sinh được hỏi
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1,a_2,…,a_N~ lần lượt là các câu trả lời của ~N~ học sinh được hỏi.

Kết quả:

Ghi ra tệp văn bản CLB.OUT một số nguyên dương là số tổ của câu lạc bộ.

Ví dụ:

CLB.INP

7
2 3 2 3 2 2 3

CLB.OUT

3

Câu 3 đề thi thử HSG tỉnh lớp 9 Yên Thành

Trong một đợt tổ chức hội thao cấp cụm dành cho học sinh trung học cơ sở, Ban Tổ chức hội thao đã nhận được sự hưởng ứng nhiệt tình của các bạn học sinh đến từ các trường học trung học cơ sở trên địa bàn cụm đăng ký tham gia với nhiều nội dung thi đấu. Có ~n~ học sinh đăng ký tham gia thi đấu tại hội thao. Các nội dung thi đấu được Ban Tổ chức hội thao đánh số từ 1 đến ~n~ và được phân loại theo nội dung thi đấu.

Theo kết quả phân loại, nội dung thi đấu thứ ~i~ được đặt tên là ~a_i~ (~1 ≤ i ≤ n~). Vì số lượng nội dung thi đấu tại hội thao lần này được học sinh đăng ký rất nhiều và đa dạng, nên việc bố trí trọng tài điều khiển các nội dung thi đấu tương đối khó khăn. Yêu cầu: Bạn hãy giúp Ban Tổ chức hội thao xác định số nội dung thi đấu khác nhau và nội dung thi đấu có nhiều học sinh đăng ký nhất trong hội thao lần này.

Dữ liệu:

• Dòng đầu tiên: chứa một số nguyên ~n~ (~1 ≤ n ≤ 10^6~).

• Dòng thứ hai: chứa ~n~ số nguyên ~a_1, a_2, ... , a_n~ tương ứng với các nội dung mà học sinh đăng ký thi đấu (~1 ≤ a_i ≤ 10^6, 1 ≤ i ≤ n~).

  Kết quả:

• Dòng thứ nhất: chứa số nguyên duy nhất chính là số nội dung khác nhau mà học sinh đăng ký thi đấu.

• Dòng thứ hai: là số nguyên chính là nội dung thi đấu có nhiều học sinh đăng ký nhất (trường hợp có nhiều nội dung đăng ký nhiều nhất bằng nhau thì đưa ra nội dung ứng với số nhỏ nhất).

  Ví dụ:

Input

6
1 4 4 2 5 4

Output

4
4

Câu 2 đề thi thử HSG L9 Yên Thànhf năm 2024-2025

Nhân dịp các bạn lớp 9A đi học trở lại sau Tết, vì có một số bạn chưa làm bài tập Tết nên thầy giáo quyết định đưa ra hình phạt như sau: Nếu một bạn bất kì không làm bài tập Tết thì số điểm cộng của các bạn khác trong lớp sẽ được cộng thêm 1 đơn vị.

Yêu cầu:

Cho số lượng học sinh trong lớp, danh sách điểm cộng trước Tết của các bạn và số bạn chưa làm bài tập Tết. Đưa ra danh sách điểm cộng mới của các bạn lớp 9A.

Dữ liệu

• Dòng thứ nhất ghi 2 số nguyên dương ~n,k~ (~1 ≤ n ≤ 2∗10^5,1 ≤ k ≤ 2∗10^5~)tương ứng là số lượng học sinh trong lớp và số học sinh không làm bài tập Tết.
• Dòng thứ hai chứa dãy ~a_1,a_2,...,a_n~ (~1 ≤ ai ≤ 10^6~) điểm cộng của các bạn lớp 9A trước Tết.
• Tiếp theo là ~k~ dòng, dòng thứ ~i~ chứa số nguyên Ki (~1 ≤ Ki ≤ n~) thứ tự của bạn học sinh không làm bài tập Tết.

• Dữ liệu đảm bảo danh sách các bạn không làm bài tập tết là đôi một khác nhau.

  Kết quả

• In ra danh sách điểm cộng mới trên một dòng.

  Ví dụ

I

Input

6 4
3 5 3 1 7 8
3
4
5
1

Output

6 9 6 4 10 12

Đề HSG L9 huyện Đô Lương năm 2023-2024

An rất thích nuôi thỏ, lần này An mua về ~n~ con thỏ, mỗi con mang một mã số ~a_i~. Mỗi chuồng An chỉ nhốt một cặp thỏ, nhưng lạ thay nếu nhốt hai con thỏ có tổng mã số khác 6 thì thỏ sẽ cắn nhau.

Yêu cầu:

Em hãy lập trình giúp An tính xem có bao nhiêu cách ghép các cặp thỏ để chúng không cắn nhau.

Dữ liệu:

Cho từ tệp văn bản GC.INP gồm:

• Dòng đầu chứa số nguyên dương ~n~ (~n ≤ 10^6~) là số lượng con thỏ
• Dòng 2 chứa ~n~ số nguyên dương ~a_1; a_2 ; … ; a_n~ (~1≤a_i≤5~) là mã số của từng con thỏ.

Kết quả:

ghi ra tệp văn bản GC.OUT số cách ghép.

Ví dụ:

GC.Inp

5
1 4 5 3 2

GC.out

2

Cho một số nguyên dương ~N~ (~N≤5×10^{17}~).

Yêu cầu:

Tìm chữ số nhỏ thứ ~Q~ trong ~N~ và kiểm tra nó có phải là nguyên tố hay không.

Dữ liệu:

Vào từ file văn bản SONTTQ.INP:

• Dòng đầu ghi số nguyên ~N~.

• Dòng thứ hai chứa số ~Q~ (~0<Q≤9~) </p>

Kết quả:

Ghi ra file văn bản SONTTQ.OUT

gồm chữ số nhỏ thứ ~Q~ và chữ "Yes" nếu là số nguyên tố hoặc từ "No" nếu không phải là số nguyên tố. Trường hợp không tìm thấy chữ số nhỏ thứ ~Q~ thì ghi -1.

Ví dụ 1

SONTTQ.INP  
92457
4
SONTTQ.OUT
7 Yes

Ví dụ 2

SONTTQ.INP  
5568924
5
SONTTQ.OUT
8 No

Ví dụ 3

SONTTQ.INP
55557
5
SONTTQ.OUT
-1

Cho một số nguyên dương ~S~ gồm ~N~ chữ số (~1≤N≤6~).

Yêu cầu:

Hãy liệt kê các chữ số ~a_i~ (~1≤i≤N~) là số nguyên tố xuất hiện trong ~S~ theo thứ tự từ trái sang phải, nếu các chữ số tìm được trùng nhau thì chỉ liệt kê lần xuất hiện đầu tiên

Dữ liệu:

Vào từ file văn bản CSNT.INP:

• Một dòng chứa số nguyên dương ~S~.

Kết quả:

Ghi ra file văn bản CSNT.OUT:

Một dãy các số ~a_i~ tìm được thỏa mãn yêu cầu đề bài. Trường hợp không tìm được thì ghi số ra 0

Ví dụ

CSNT.INP
23271
CSNT.OUT
2 3 7

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự "0" hoặc "1". Xâu ~v~ gọi là xâu con của ~w~ nếu xâu ~v~ có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu ~w~. Ví dụ: xâu "010" có các xâu con là "0", "1", "0", "01", "10", "010".

Yêu cầu:

Cho trước một giá trị k, hãy đếm xem có bao nhiêu xâu con chứa đúng ~k~ ký tự "1".

Dữ liệu vào:

-Dòng 1: chứa một số nguyên ~k~ (~0 ≤ k ≤ 10^6~)

-Dòng 2: chứa một xâu nhị phân có độ dài ~≤ 10^6~

Dữ liệu ra:

-Ghi ra một số nguyên duy nhất là kết quả tìm được.

Ví dụ

Input

2

01010

Output

4

Giải thích ví dụ:

có 4 xâu con chứa 2 ký tự 1 là: "101", "0101", "1010", "01010"

Ràng buộc:

gọi n là độ dài xâu

• Có 30% số test ứng với 30% số điểm của bài có n ≤ 100.

• Có 30% số test ứng với 30% số điểm của bài có 100 < n ≤ 1000.

• Có 40% số test ứng với 40% số điểm của bài có 1000 < n ≤ 1.000.000.

Lớp học múa khiêu vũ dạ hội của giáo sư Padegras có ~n~ học sinh nam và nữ ghi tên. Giáo sư cho tất cả học sinh xếp thành một hàng dọc và chọn một nhóm các học sinh liên tiếp nhau cho buổi học đầu tiên với yêu cầu là số học sinh nam và nữ phải bằng nhau.

Hãy xác định, giáo sư Padegras có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.

Input:

•Dòng đầu tiên chứa số nguyên ~n~ (~1 ≤ n ≤ 10^6~),

•Dòng thứ 2 chứa xâu độ dài ~n~ bao gồm các ký tự từ tập {~a, b~} xác định dòng xếp hàng, ~a~ là nam, ~b~ – nữ.

Output:

Một số nguyên – số cách lựa chọn.

Ví dụ

Input

8

abbababa

Output

13

Ràng buộc:

• 30% số test tương ứng với n ≤ 500

• 40% số test tiếp theo tương ứng với 500 < n ≤ 10000

• 30% số test cuối cùng tương ứng với 10000 < n ≤ ~10^6~