Tin học trẻ 2021

Từ dãy số tự nhiên \(1; 2; 3; ...; N\) người ta sắp xêp lại dãy số này theo số dư trong các phép chia các số hạng của dãy số cho một số lự nhiên \(K\) là ước nào đó của \(N\) như sau:

• Đoạn thứ nhất gồm tất cả các số chia hết cho \(K\);
• Đoạn thứ hai gồm tất cả các sổ chia \(K\) dư 1;
• Đoạn thứ ba gồm tất cả các số chia \(K\) dư 2;
• ...
• Đoạn cuối cùng gồm tất cà các số chia \(K\) dư \(K\) - 1.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiêu tăng dần.

Ví dụ: Với \(N = 12\) và \(K = 4\) sau khi sắp xếp ta có dãy số sau: \(4; 8; 12; 1; 5; 9; 2; 6; 10; 3; 7; 11\)

Yêu cầu: Cho trước 3 số nguyên dương \(N; K; M\) (với \(K\) là ước của \(N\) và \(M < N\)). Tìm số hạng thử \(M\) của dãy đã sắp xếp.

Dữ liệu

• 3 số nguyên dương \(N; K; M\) (\(N \le 10^{16}; K \le 10^9; K\) là ước của $N; M < N) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Kết quả

• Ghi ra số hạng thứ M của dãy số theo yêu cầu.

Input

12 4 6

Output

9

Giới hạn

• Có 20% test ứng với \(N \le 10^2\);
• Có 30% test ứng với \(10^2 < N \le 10^6\);
• Có 30% test ứng với \(10^6 < N \le 10^9\);
• Có 20% test ứng với \(10^9 < N \le 10^{16}\).

Nguồn: THTB - Cấp TP 2021.

Như chúng ta đã biết dịch cúm toàn cầu COVID-19 do virus Corona nhân bản và lây lan gây hội chứng suy hô hấp cấp tính nặng ở người. Người bệnh ban đầu không nhận biết được đã nhiễm bệnh do virus còn tiềm ẩn chưa khởi phát. Ở đâu đó những con virus đang ẩn mình, chúng ta cùng tìm chúng nhé!

Cho một xâu kí tự \(s\) chỉ chứa các kí tự C, O, R, N, A ở vị trí bất kì. Ta có thể thực hiện hoán đổi các kí tự này để tạo thành những cụm từ CORONA liên tiếp, mỗi cụm từ CORONA tương ứng với một con virus.

Ví dụ: Với xâu kí tự \(s =\) COOCROONRANNA, sau khi thực hiện hoán đổi các kí tự của xâu \(s\) ta được xâu CORONACORONAN có hai cụm từ CORONA tương ứng với hai con virus.

Yêu cầu

Hãy xác định số lượng con virus Corona sau khi thực hiện hoán đổi các kí tự trong xâu \(s\) theo yêu cầu như trên.

Input

• Một xâu \(s\) chỉ chứa các kí tự C, O, R, N, A và có độ dài \(L\) \((0 < L < 255)\).

Output

• Ghi ra một số nguyên là số lượng con virus Corona tạo ra sau khi hoán đổi các kí tự trong xâu \(s\).

Example

COOCROONRANNA

2

Nguồn: THTB - Cấp TP 2021.

Trong các số tự nhiên lừ 1 đến \(N\), số tự nhiên được gọi là số giàu có nhất nêu nó có tổng các ước lớn nhất trong các số này.

Ví du: Số \(12\) là số giàu có nhất trong các số tự nhiên từ 1 đến 15. (Tổng ước của \(12\) là \(1+2+3+4+6+12 = 28\)).

Yêu cầu: Hãy xác định số giàu có nhất trong các số tự nhiên từ 1 đến \(N\).

Dữ liệu

• Nhập từ bàn phím một số tự nhiên \(N\ (0 < N < 10^6)\)

Kết quả

• In ra màn hình số giàu có nhất trong các số tự nhiên từ 1 đến \(N\).

Chú ý: Nếu kết quả có nhiều hơn một số thì in ra sổ nhỏ nhất trong các số đó.

Input

15

Output

12

Giới hạn

• Có 80% test ứng với \(N < 10^5\);
• Có 20% test ứng với \(10^5 < N < 10^6\).

Nguồn: THTB - Cấp TP 2021.

Tý muốn cắt một sợi dây có chiều dài \(N\) (mét) thành 3 đoạn dây có chiêu dài mỗi đoạn là số nguyên dương (đơn vị mét) sao cho 3 đoạn dây này là 3 cạnh của một tam gịác cân có cạnh đáy lớn hơn cạnh bên.

Lưu ý: Tam giác cân là tam giác có hai cạnh bằng nhau, hai cạnh bằng nhau gọi là hai cạnh bên, cạnh còn lại gọi là cạnh đáy.

Yêu cầu: Em hãy giúp Tý tính có bao nhiêu cách cắt đoạn dây này.

Dữ liệu

• Một số nguyên dương \(N\) (\(N< 10^{16}\))

Kết quả

• Ghi ra số \(M\) là số cách cắt sợi dây theo yêu cầu.

Input

19

Output

2

Giải thích: Có 2 cách cắt sợi dây thành 3 đoạn thỏa mãn đề là: (\(5m; 5m; 9m\)) và (\(6m; 6m; 7m\)).

Lưu ý:: Các cách cắt sợi dây thành 3 đoạn (\(x\) mét; \(x\) mét; \(y\) mét) và các hoán vị của bộ 3 số . (\(x;x;y\)) chì được tính là 1 cách cắt. Chẳng hạn: Cách cắt thành các đoạn (\(5m; 5m; 9m\)) và các hoán vị của nó là (\(5m; 9m; 5m\)) hoặc (\(9m; 5m; 5m\)) chỉ được tính là 1 cách cắt.

Giới hạn

• Có 20% test ứng với \(N \le 10^2\);
• Có 30% test ứng với \(10^2 < N \le 10^6\);
• Có 30% test ứng với \(10^6 < N \le 10^9\);
• Có 20% test ứng với \(10^9 < N \le 10^{16}\).

Nguồn: THTB - Cấp TP 2021.

Cho một dãy số nguyên có \(N\) phần tử. Dãy đẹp là dãy chỉ có các số \(0\) và \(1\) đồng thời trong dãy có ít nhất một số \(1\) và nhiều nhất một số \(0\).

Input

• Dòng đầu tiên chứa số nguyên \(n (1 \leq n \leq 1000)\).
• Dòng thứ hai chứa \(n\) số nguyên \((1 \leq i \leq N;0 \leq a_i \leq 9)\)

Output

• Dòng duy nhất in "YES" nếu dãy được nhập vào là dãy số đẹp. Ngược lại thì in "NO".

Example

3 
1 0 1 

YES

3 
1 0 0 

NO

Một chuỗi được gọi là siêu đối xứng nếu nó đối xứng ở chính giữa chuỗi, nửa bên trái nhìn qua gương giống nửa bên phải. Ví dụ, chuỗi \("oHo"\) là chuỗi siêu đối xứng, nhưng chuỗi \("aa"\) thì không. Chuỗi \(“aa”\) không phải là siêu đối xứng, bởi vì nửa sau của nó không phải là phản xạ qua gương của nửa đầu.

Biết rằng các kí tự đối xứng chính nó gồm: \(ilovwxAHIMOTUVWXY\)
Các cặp kí tự đối xứng gồm: \(bd\),\(pq\)
Cho một chuỗi kí tự tiếng Anh \(s\). Hãy tìm chuỗi siêu đối xứng dài nhất bằng cách lấy một số kí tự của \(s\) và sắp xếp chúng theo thứ tự bất kì.

Input

• Dòng duy nhất chứa chuỗi \(s\) (độ dài chuỗi \(s\) tối đa là \(10^5\))chỉ bao gồm các chữ cái tiếng Anh.

Output

• In ra độ dài của chuỗi siêu đối xứng dài nhất thu được.

Constraints

• Có 50% test có \(|s| \leq 100\)

Example

XHxHx 

5

AAoabc 

3

Error 

1

Ngọc là một nhà khảo cổ tài giỏi, cô được rất nhiều lời mời giải đáp các bí ẩn trên khắp thế giới. Lần này cô đang trên đường giải quyết mội câu đố bí ẩn được tìm thấy trong một ngôi đền ở Alantic. Cửa vào ngôi đền có một cánh cửa và một bệ đá, trên cánh cửa trên đó có chứa một dãy \(N\) viên đá được xếp thành một dãy thẳng hàng \((N \leq 10^4)\), mỗi một số trên tảng đá có giá trị là \(A_i (1 \leq A_i<10^9;1 \leq i \leq N)\). Để mở được cánh của trên ta phải đặt lên bệ đá \(M\) viên đá lấy từ cánh cửa. Với \(M\) là số lượng viên đá lấy ra từ cánh cửa sao cho các viên đá còn lại trên cánh cửa tạo thành một dãy số không giảm và dài nhất. Hãy xác định giúp Ngọc cần đặt lên bệ bao nhiêu viên đá

Input

• Dòng 1: Chứa 1 số nguyên \(N\) là số lượng viên đá trên cửa
• Dòng 2: Chứa \(N\) số mỗi số cách nhau 1 kí tự trống lần lượt là các số nguyên được ghi trên viên đá.

Output

• Chứa 1 số duy nhất là số viên đá cần đặt lên bệ đá

Example

5
6 3 5 4 7 

2

10
4 3 5 8 7 9 6 4 2 8 

6

Đức có \(N\) túi kẹo được xếp thành một đường thẳng \((1 \leq N \leq 5000)\), túi kẹo thứ \(i\) có \(A_i\) viên kẹo \((1 \leq A_i \leq 10^9;1 \leq i \leq N)\) anh ta muốn các túi kẹo phải được xếp thành một dãy sao cho túi kẹo bên phải có số kẹo lớn hơn hoặc bằng túi kẹo bên trái. Vì không muốn thay đổi thứ tự các gói kẹo nên Đức lấy ra hoặc thêm vào các túi kẹo một số kẹo nhất định. Vì cần có thời gian suy nghĩ nên mỗi lần Đức chỉ thực hiện một thao tác lấy ra khỏi túi 1 viên kẹo hoặc thêm 1 viên kẹo vào túi. Hỏi cần bao nhiêu ít nhất bao nhiêu thao tác để Đức có thể thu được kết quả như mong muốn.

Input

• Dòng 1: Chứa số nguyên \(N\) là số túi kẹo của Đức
• Dòng 2: Chứa \(N\) số nguyên mỗi số cách nhau 1 kí tự trống lần lượt là số kẹo \(A_i\) của túi kẹo thứ \(i\)

Output

• Chứa 1 số nguyên duy nhất là số lần thực hiện thao tác của Đức

Subtask

Dựa trên bộ test, trong đề thi gốc không có phần giới hạn này.

• Subtask \(1: n \le 20\)
• Subtask \(2: n \le 1000, a \le 10^5\)
• Subtask \(3:\) giới hạn gốc

Example

3
4 3 6 

1

5
2 3 1 5 4 

3