Độ khó: Dễ (1/4 điểm)

Cho ~N~ ~(1 \le N \le 1000)~ bộ ba, mỗi bộ ba gồm 3 số nguyên dương không vượt quá ~1000~, trong đó có một số bộ ba mà mỗi bộ ba gồm 3 số tương ứng là độ dài 3 cạnh của một tam giác. Ví dụ: với ~N = 3~, ta nhập vào 3 bộ ba ~(1; 2; 3)~, ~(3; 4; 5)~, ~(10; 12; 14)~, trong đó có 2 bộ ba ~(3; 4; 5)~, ~(10; 12; 14)~ mà mỗi bộ ba gồm các số là độ dài 3 cạnh của một tam giác, bộ ba ~(1; 2; 3)~ gồm 3 số không phải là độ dài 3 cạnh của một tam giác.

Yêu cầu: Cho ~N~ bộ ba, đếm số lượng bộ ba có 3 số tương ứng là độ dài 3 cạnh của một tam giác.

Dữ liệu vào: Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất là số nguyên dương ~N~.
• ~N~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương tương ứng là các giá trị của mỗi bộ ba.

Dữ liệu ra: Số lượng bộ ba mà mỗi bộ ba có 3 số tương ứng là độ dài 3 cạnh của một tam giác.

Sample Input

3
1 2 3
3 4 5
10 12 14

Sample Output

2

Độ khó: Dễ (1/4 điểm)

Cho một xâu ~S~ có độ dài là một số nguyên dương tối đa không vượt quá ~1000~, chỉ gồm các chữ cái tiếng Anh in thường, in hoa và không chứa kí tự khoảng trống.

Yêu cầu: Cho xâu ~S~, tính số lượng chữ cái in thường và số lượng chữ cái in hoa thuộc xâu ~S~.

Dữ liệu vào: Đọc từ bàn phím một dòng duy nhất chứa xâu ~S~.

Dữ liệu ra: Xuất ra màn hình hai số nguyên là số lượng chữ cái in thường, số lượng chữ cái in hoa xuất hiện trong xâu ~S~, hai số trên một dòng và cách nhau một khoảng trắng.

Sample Input

AmdnBBG

Sample Output

3 4

Độ khó: Trung bình (2/4 điểm)

Cho phương trình ~X \cdot S(X) - A = 0~ (~X \cdot S(X)~ có nghĩa là ~X~ nhân với ~S(X)~). Trong đó:

• ~A~ là một số nguyên dương cho trước, ~X~ là biến.
• ~S(X)~ là tổng các chữ số của ~X~.

Ví dụ cho ~A = 22~, ta nhận thấy ~X = 11~, ~S(X) = 2~ và ~11 \cdot 2 - 22 = 0~. Vậy ~X = 11~ là nghiệm nguyên dương nhỏ nhất thỏa mãn phương trình trên vì các giá trị ~X~ ~(0 \lt X \lt 11)~ đều không phải là nghiệm.

Yêu cầu: Cho biết ~A~, tìm số nguyên dương ~X~ ~(0 \lt X \le 10^9)~ nhỏ nhất là nghiệm của phương trình.

Dữ liệu vào: Đọc từ bàn phím một dòng duy nhất chứa số nguyên dương ~A~ ~(1 \le A \le 10^9)~.

Dữ liệu ra: Xuất ra màn hình một số nguyên dương ~X~ nhỏ nhất thỏa mãn yêu cầu bài toán, trong trường hợp phương trình vô nghiệm thì đưa ra số ~-1~.

Giới hạn:

• ~80\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~1 \le A \le 10^6~.
• ~20\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~10^6 \lt A \le 10^9~.

Sample Input

22

Sample Output

11

Độ khó: Khá (3/4 điểm)

Cho trước hai số nguyên dương ~N, K~ ~(1 \le K \le N \le 10^6)~ và dãy gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~. Dãy con gồm các phần tử liên tiếp kề nhau thuộc dãy ~a_1, a_2, \dots, a_N~ có dạng ~a_L, a_{L+1}, a_{L+2}, \dots, a_R~ ~(1 \le L \le R \le N)~, độ dài của dãy con các phần tử liên tiếp kề nhau bằng số lượng phần tử của dãy.

Yêu cầu: Tìm dãy con của dãy ~a_1, a_2, \dots, a_N~ gồm các phần tử liên tiếp kề nhau, dài nhất có ~K~ số nguyên tố khác nhau (tức là có đúng ~K~ số nguyên tố phân biệt).

Dữ liệu vào: Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~K~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(0 \lt a_i \le 10^5,\ 1 \le i \le N)~.
• Các số trên một dòng cách nhau ít nhất một khoảng trắng.

Dữ liệu ra: Xuất ra màn hình một số nguyên dương là độ dài của dãy con dài nhất thỏa mãn yêu cầu bài toán, nếu không có dãy con nào thỏa mãn yêu cầu thì xuất ra màn hình số ~-1~.

Giới hạn:

• ~60\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~1 \le N \le 10^3~.
• ~40\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~10^3 \lt N \le 10^6~.

Sample Input 1

5 2
3 3 4 2 7

Sample Output 1

4

Sample Input 2

10 3
1 2 7 7 4 5 6 7 8 11

Sample Output 2

9

Giải thích: ví dụ đầu tiên, các dãy con liên tiếp kề nhau của dãy số ~\{3; 3; 4; 2; 7\}~ có 2 số nguyên tố khác nhau là: ~\{3; 3; 4; 2\}~, ~\{3; 4; 2\}~, ~\{4; 2; 7\}~, ~\{2; 7\}~; dãy con ~\{3; 3; 4; 2\}~ có 2 số nguyên tố khác nhau là ~3~ và ~2~, có số lượng phần tử là ~4~, độ dài lớn nhất trong các dãy con.

Độ khó: Trung bình (2/4 điểm)

Hùng dự định sẽ tặng túi xách cho các bạn học sinh nghèo nhân dịp năm học 2022-2023. Trong một lần đi du lịch Đà Nẵng anh vào một cửa hàng bán túi xách, trong cửa hàng có ~N~ túi xách khác nhau, được đánh số từ ~1~ đến ~N~. Giá tiền của từng túi xách được cho bởi dãy số nguyên dương ~a_1, a_2, \dots, a_N~, túi xách thứ ~i~ có giá là ~a_i~ ~(0 \lt a_i \le 10^4,\ 1 \le i \le N)~ (những túi xách khác nhau nhưng có thể giá tiền bằng nhau). Ngoài ra cửa hàng còn có chính sách khuyến mãi hấp dẫn: mỗi lần mua một túi xách bất kỳ từ cửa hàng, được nhận khuyến mãi ~K~ túi xách khác (tất cả ~K~ túi xách đều là các loại khác nhau) miễn phí. Khi mua một túi xách, nếu số lượng túi xách trong cửa hàng còn lại từ ~K~ túi trở lên thì được nhận ~K~ túi xách miễn phí; nếu số lượng túi xách còn lại ít hơn ~K~ thì được nhận miễn phí các túi xách còn lại.

Hùng sẽ mua từng túi xách và chọn các túi xách khuyến mãi cho đến khi mua hết ~N~ túi xách. Biết rằng Hùng có đủ tiền để mua hết ~N~ túi xách.

Yêu cầu: Tìm số tiền nhỏ nhất và số tiền lớn nhất để Hùng có thể mua tất cả ~N~ túi xách.

Dữ liệu vào: Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~K~ ~(1 \le K \le N \le 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ tương ứng là giá tiền của ~N~ túi xách khác nhau trong cửa hàng.
• Các số trên một dòng cách nhau ít nhất một khoảng trắng.

Dữ liệu ra: Xuất ra màn hình hai số nguyên dương tương ứng là số tiền nhỏ nhất và số tiền lớn nhất, hai số trên một dòng và cách nhau một khoảng trắng.

Giới hạn:

• ~50\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~1 \le N \le 10^3~.
• ~50\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~10^3 \lt N \le 10^5~.

Sample Input

5 2
3 2 1 4 1

Sample Output

2 7

Giải thích: trường hợp mua tất cả ~N~ túi xách với số tiền nhỏ nhất: đầu tiên mua túi xách thứ ba, chọn túi xách thứ nhất và túi xách thứ tư miễn phí. Tiếp theo mua túi xách thứ năm giá ~1~, túi xách thứ hai còn lại miễn phí. Vậy số tiền nhỏ nhất là ~1 + 1 = 2~. Trường hợp mua tất cả ~N~ túi xách với số tiền lớn nhất: đầu tiên mua túi xách thứ tư giá ~4~, chọn túi xách thứ ba và thứ năm miễn phí. Tiếp theo mua túi xách thứ nhất giá ~3~, túi xách thứ hai miễn phí. Vậy số tiền lớn nhất là ~3 + 4 = 7~. Có thể chọn phương án mua khác nhưng kết quả vẫn có số tiền nhỏ nhất là ~2~, lớn nhất là ~7~.