Bài tập - TLEOJ

DISCOVERY

SpiceDangSpice

TLE-oj Cup Round 10 - Tổng and, or, xor

Sunlight

Cho dãy $a$ ban đầu không có phần tử nào và $q$ truy vấn, mỗi truy vấn thuộc một trong năm dạng sau:

+ m: Thêm một phần tử có giá trị $m$ vào $a$ .
& m: Thực hiện phép AND cho $m$ với tất cả các phần tử trong dãy.
| m: Thực hiện phép OR cho $m$ với tất cả các phần tử trong dãy.
^ m: Thực hiện phép XOR cho $m$ với tất cả các phần tử trong dãy.

Các bạn có thể xem về các phép thao tác bit tại đây.

Sau khi thực hiện $q$ thao tác bit, các bạn cần in ra tổng các phần tử của dãy.

Input, Output và Subtasks

Input: (SUMAOX.inp)

Dòng đầu tiên gồm số nguyên dương $q$ $(1 \le q \le 10^6)$ .
$q$ dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong bốn loại như ở trên. $(0 \le m \le 10^6)$ .

Output: (SUMAOX.out)

In ra kết quả bài toán.

Subtasks

Subtask 1 $(30\%)$ : $q \le 10^4$ .
Subtask 2 $(30\%)$ : $m \le 1$ cho mọi truy vấn.
Subtask 3 $(20\%)$ : $m \le 4$ cho mọi truy vấn.
Subtask 4 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Input (SUMAOX.inp)

5

+ 1
+ 2
& 1
^ 3
+ 4

Output (SUMAOX.out)

Note

Dãy ban đầu: $()$ .
Sau thao tác 1: $(1)$ .
Sau thao tác 2: $(1, 2)$ .
Sau thao tác 3: $(1, 0)$ .
Sau thao tác 4: $(2, 3)$ .
Sau thao tác 5: $(2, 3, 4)$ .

TLE-oj Cup Round 11 - Bộ ba số đẹp

huyhau6a2

Bạn được cho một dãy số $a$ gồm $n$ phần tử. Nhiệm vụ của bạn là đếm số bộ ba số $(i,j,k)$ thỏa mãn:

$i<j<k$
$a_i=a_j=a_k$

Input, Output và Subtasks

Input: (TRIBEAUT.inp)

Dòng đầu tiên gồm số nguyên dương $n$ $(1 \le n \le 10^6)$ .
Dòng tiếp theo gồm $n$ số $a_1,a_2,\dots,a_n$ ( $a_i\le 10^9$ )

Output: (TRIBEAUT.out)

In ra một số duy nhất là kết quả bài toán

Subtasks

Subtask 1 $(40\%)$ : $n\le 200$ .
Subtask 2 $(40\%)$ : $n\le 5000$ .
Subtask 3 $(10\%)$ : $a_i\le 10^6$
Subtask 4 $(10\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRIBEAUT.inp)

8
1 2 1 3 1 2 1 2

Output (TRIBEAUT.out)

Note

Các bộ ba thỏa mãn: $(1,3,5), (1,3,7), (1,5,7), (2,6,8), (3,5,7)$

TLE-oj Cup Round 11 - Bộ ba nguyên tố

huyhau6a2

Bạn được cho một dãy số $a$ gồm $n$ phần tử. Nhiệm vụ của bạn là đếm số bộ ba số $(i,j,k)$ thỏa mãn:

$i<j<k$
$a_i\cdot a_j\cdot a_k$ là một số nguyên tố

Input, Output và Subtasks

Input: (TRIPRIME.inp)

Dòng đầu tiên gồm số nguyên dương $n$ $(1 \le n \le 10^6)$ .
Dòng tiếp theo gồm $n$ số $a_1,a_2,\dots,a_n$ ( $a_i\le 10^7$ )

Output: (TRIPRIME.out)

In ra một số duy nhất là kết quả bài toán

Subtasks

Subtask 1 $(25\%)$ : $n\le 10$ .
Subtask 2 $(25\%)$ : $n\le 200$ .
Subtask 3 $(25\%)$ : $n\le 5000$ .
Subtask 4 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRIPRIME.inp)

8
1 2 1 3 6 2 4 2

Output (TRIPRIME.out)

Note

Các bộ ba thỏa mãn: $(1,2,3), (1,3,4), (1,3,6), (1,3,8)$

TLE-oj Cup Round 11 - Bộ ba chia hết

huyhau6a2

Bạn được cho một số nguyên dương $n$ . Nhiệm vụ của bạn là đếm số bộ ba số $(i,j,k)$ thỏa mãn:

$1\le i\le j\le k\le n$
$i\cdot j=k$

Input, Output và Subtasks

Input: (TRIDIV.inp)

Gồm duy nhất một số nguyên dương $n$ ( $n\le 10^{14}$ )

Output: (TRIDIV.out)

In ra một số duy nhất là kết quả bài toán sau khi $mod\ 10^9+7$

Subtasks

Subtask 1 $(25\%)$ : $n\le 200$ .
Subtask 2 $(25\%)$ : $n\le 5000$ .
Subtask 3 $(25\%)$ : $n\le 10^7$ .
Subtask 4 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRIDIV.inp)

Output (TRIDIV.out)

Note

Các bộ ba thỏa mãn: $(1,1,1), (1,2,2), (1,3,3), (1,4,4), (1,5,5), (2,2,4)$

TLE-oj Cup Round 11 - Bộ ba tam giác

huyhau6a2

Bạn được cho một số nguyên dương $n$ . Nhiệm vụ của bạn là đếm số bộ ba số $(i,j,k)$ thỏa mãn:

$1\le i<j<k\le n$
$i,j,k$ là 3 cạnh của một tam giác

Input, Output và Subtasks

Input: (TRIANGLE.inp)

Dòng đầu tiên nhập số $t$ là số testcase ( $t\le 10^6$ )
$t$ dòng tiếp theo, mỗi dòng chứa duy nhất một số nguyên $n$ ( $n\le 10^{18}$ )

Output: (TRIANGLE.out)

Với mỗi truy vấn, in ra một số duy nhất là kết quả bài toán sau khi $mod\ 10^9+7$

Subtasks

Subtask 1 $(20\%)$ : $n\le 200,t=1$ .
Subtask 2 $(20\%)$ : $n\le 5000,t=1$ .
Subtask 3 $(20\%)$ : $n\le 10^6$
Subtask 4 $(20\%)$ : $n\le 10^9$
Subtask 5 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRIANGLE.inp)

1
5

Output (TRIANGLE.out)

Note

Các bộ ba thỏa mãn: $(2,3,4), (2,4,5), (3,4,5)$

TLE-oj Cup Round 11 - Bộ ba tăng dần

huyhau6a2

Bạn được cho một dãy số $a$ gồm $n$ phần tử. Bạn phải thực hiện $q$ truy vấn, mỗi truy vấn gồm 2 số $l,r$ . Nhiệm vụ của bạn là với mỗi truy vấn, bạn cần phải đếm số bộ ba số $i,j,k$ thỏa mãn

$l\le i<j<k\le r$
$a_i<a_j<a_k$

Input, Output và Subtasks

Input: (TRILIS.inp)

Dòng đầu tiên gồm hai số nguyên dương $n \le 5000$ và $q \le 10^6$ .
Dòng tiếp theo gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$ ( $a_i\le 10^9$ ).
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $l, r$ mô tả mỗi truy vấn. ( $1\le l\le r\le n$ )

Output: (TRILIS.out)

Gồm $q$ dòng, dòng thứ $i$ là kết quả truy vấn thứ $i$ .

Subtasks

Subtask 1 $(10\%)$ : $n,q\le 100$ .
Subtask 2 $(10\%)$ : $n\le 100$ .
Subtask 3 $(10\%)$ : $n,q\le 500$ .
Subtask 4 $(15\%)$ : $n\le 500$ .
Subtask 5 $(15\%)$ : $n,q\le 2000$ .
Subtask 6 $(15\%)$ : $n\le 2000$ .
Subtask 7 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRILIS.inp)

7 2
1 2 3 4 3 2 1
1 7
2 6

Output (TRILIS.out)

5
1

Note

Truy vấn 1: Các bộ ba thỏa mãn: $(1,2,3), (1,2,4), (1,2,5), (1,3,4), (2,3,4)$

TLE-oj Cup Round 12 - Nghịch đảo modulo

Sunlight

Lưu ý: bài này không được dùng ngôn ngữ C++17 và C++20, cũng như Python.

Lưu ý 2: trong C++ có cấu trúc dữ liệu unsigned long long cho phép lưu số nguyên từ $0$ đến $2^{64} - 1$ .

Cho ba số nguyên $n, m, r$ $(0 \le n, r < 2^m)$ . Tìm một số nguyên $x$ $(0 \le x < 2^m)$ sao cho $n \times x - r$ chia hết cho $2^m$ .

Input, Output và Subtasks

Input: (MODINV.inp)

Dòng đầu tiên gồm số nguyên dương $t \le 10^6$ - số truy vấn.
$t$ dòng tiếp theo mỗi dòng gồm ba số nguyên $n, m, r$ $(1 \le m \le 64)$ .

Output: (MODINV.out)

Gồm $t$ dòng, dòng thứ $i$ là kết quả truy vấn thứ $i$ . Nếu không tìm được số nguyên nào in ra $-1$ , nếu có nhiều số in ra số nhỏ nhất.

Subtasks

Subtask 1 $(20\%)$ : $m \le 20, t = 1$ .
Subtask 2 $(20\%)$ : $m \le 32$ .
Subtask 3 $(10\%)$ : $m \le 60$ .
Subtask 4 $(20\%)$ : $m \le 63$ .
Subtask 5 $(30\%)$ : Không có giới hạn gì thêm.

Sample

Input (MODINV.inp)

2
5 3 7
5 4 6

Output (MODINV.out)

3
14

Note

$5 \times 3 - 7 = 8$ chia hết cho $8$ .
$5 \times 14 - 6 = 64$ chia hết cho $16$ .

TLE-oj Cup Round 12 - Trò chơi Nim chuẩn

Sunlight

huyhau6a2 và khanhphucscratch rủ nhau chơi một trò chơi. huyhau6a2 mang đến $n$ viên sỏi và hai người dự định sẽ chơi một trò chơi Nim chuẩn. Trò chơi được phát biểu như sau:

Phát biểu trò chơi

Có $k$ đống sỏi, và mỗi đống lần lượt có $p_1,p_2,…,p_k$ sỏi, trong đó mỗi số $p_i$ là một số nguyên không âm. Mỗi trạng thái trò chơi tương ứng với mỗi bộ $n$ cho biết số sỏi của từng đống này.

Có hai người chơi thay phiên nhau bỏ sỏi. Người chơi trong lượt hiện tại có thể loại bỏ bao nhiêu sỏi tùy thích, miễn là tất cả các sỏi đều cùng một đống. Hình thức hơn, người chơi sẽ chọn một đống sỏi $i$ và số lượng sỏi $s$ để loại bỏ khỏi đống $(0<s≤p_i)$ , sau đó thay $p_i$ bằng $p_i−s$ . Chú ý rằng người chơi không thể bỏ qua lượt của mình mà không bỏ viên sỏi nào cả. Sau đó, đến lượt người chơi kia loại bỏ sỏi, lần lượt như vậy tới khi trò chơi kết thúc.

Trò chơi kết thúc khi không còn sỏi trên bàn chơi. Người chiến thắng là người lấy được viên sỏi cuối cùng. Nói cách khác, người thua cuộc là người đầu tiên không thể lấy sỏi trong lượt của mình.

(Nguồn: VNOI Wiki)

khanhphucscratch đã chọn ra một số nguyên dương $k$ . huyhau6a2 buộc phải chia $n$ viên sỏi thành $k$ đống, mỗi đống có ít nhất một viên và khanhphucscratch sẽ là người được bốc sỏi trước ở trò chơi này. Bạn hãy giúp huyhau6a2 bằng cách chỉ ra một cách chia sỏi sao cho huyhau6a2 luôn thắng cho dù khanhphucscratch có đi như thế nào.

Input, Output và Subtasks

Input: (NIMGAME.inp)

Một dòng duy nhất gồm hai số nguyên dương $n, k$ $(1 \le k \le \min(10^6, n), 1 \le n \le 10^{18})$

Output: (NIMGAME.out)

Dòng đầu tiên in YES nếu tồn tại cách sắp xếp cho huyhau6a2 luôn thắng, và NO trong trường hợp ngược lại.
Nếu dòng đầu tiên in YES, dòng thứ hai in ra một dãy $p$ bất kỳ thỏa mãn điều kiện.

Subtasks

Subtask 1 $(20\%)$ : $n \le 10$ .
Subtask 2 $(30\%)$ : $n \le 100$ .
Subtask 3 $(20\%)$ : $n \le 1000$ .
Subtask 4 $(30\%)$ : Không có giới hạn gì thêm.

Sample 1

Input (NIMGAME.inp)

10 9

Output (NIMGAME.out)

NO

Note

Cách duy nhất để chia $10$ viên sỏi vào $9$ đống là có $8$ đống 1 viên và $1$ đống 2 viên. Với cách chia này thì huyhau6a2 luôn thua.

Sample 2

Input (NIMGAME.inp)

10 5

Output (NIMGAME.out)

YES
1 2 2 2 3

Note

Không có note.

TLE-oj Cup Round 11 - Bộ ba khắc hệ

huyhau6a2

Bạn được cho 6 giá trị $l_1,r_1,l_2,r_2,l_3,r_3$ . Nhiệm vụ của bạn là đếm số bộ ba $a_1,a_2,a_3$ thỏa mãn:

$l_i\le a_i\le r_i$
$a_i$ & $a_j=0$ với mọi $i\ne j$

Trong đó, phép toán & chính là phép toán bit AND. Các bạn có thể xem về các phép thao tác bit tại đây.

Input, Output và Subtasks

Input: (TRIHATER.inp)

Dòng đầu tiên chứa số $t$ chỉ số testcase ( $t\le 10^5$ )
Sau đó là $t$ dòng, mỗi dòng chứa 6 số $l_1,r_1,l_2,r_2,l_3,r_3$ ( $0\le l_i\le r_i\le 10^{18}$ )

Output: (TRIHATER.out)

Với mỗi testcase, xuất ra kết quả tương ứng. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi $mod\ 10^9+7$

Subtasks

Subtask 1 $(10\%)$ : $l_1=r_1=l_2=r_2=0$ .
Subtask 2 $(10\%)$ : $r_i-l_i\le 500,t=1$ .
Subtask 3 $(10\%)$ : $l_1=r_1=0$ .
Subtask 4 $(15\%)$ : $t=1$ .
Subtask 5 $(15\%)$ : $t\le 50$ .
Subtask 6 $(15\%)$ : $t\le 3000$ .
Subtask 7 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRIHATER.inp)

2
1 3 0 2 1 4
1 2 0 3 2 4

Output (TRIHATER.out)

7
5

Note

Testcase 1: Các bộ ba thỏa mãn: $(1,0,2);(1,0,4);(1,2,4);(2,0,1);(2,0,4);(2,1,4);(3,0,4)$
Testcase 2: Các bộ ba thỏa mãn: $(1,0,2);(1,0,4);(1,2,4);(2,0,4);(2,1,4)$

TLE-oj Cup Round 12 - Tìm X

Sunlight

Bạn được cho một phương trình chứa biến $x$ được mô tả bằng các ký tự số, dấu cộng, trừ, bằng và ký tự x (phương trình chỉ gồm các phép toán cộng trừ). Nhiệm vụ của bạn là tìm giá trị của $x$ .

Lưu ý giới hạn bộ nhớ của bài này chỉ có 3MB

Input, Output và Subtasks

Input: (FINDX.inp)

Dòng đầu tiên gồm ít nhất là một số nguyên $t$ là số thứ tự subtask. Nếu $t = 1$ , sẽ có thêm một số nguyên $l$ trên dòng đầu tiên, cách $t$ một dấu cách $(l \le 10^7)$ .
Dòng thứ hai gồm một xâu độ dài $l$ , mô tả phương trình cần giải.
Dữ liệu đầu vào đảm bảo phương trinh luôn có đúng 1 lần $x$ , không có hệ số trước $x$ và không có một số nào có giá trị lớn hơn $10^9$ .

Output: (FINDX.out)

Một dòng duy nhất là giá trị $x$ cần tìm.

Subtasks

Subtask 1 $(20\%)$ : $l$ được cho trong input.
Subtask 2 $(10\%)$ : Phương trình chỉ có dạng $x = a$ với $a$ là một số nguyên.
Subtask 3 $(20\%)$ : $l \le 500$ .
Subtask 4 $(20\%)$ : Các ký tự đầu tiên của xâu đầu vào là x=.
Subtask 5 $(30\%)$ : Không có giới hạn gì thêm.

Sample 1

Input (FINDX.inp)

1 14
-x+1+2+3=4+5+6

Output (FINDX.out)

-9

Note

Sau khi rút gọn ta có phương trình $-x + 6 = 15$ , suy ra $x = -9$ .

Sample 2

Input (FINDX.inp)

3
x=1+2+3+4+5

Output (FINDX.out)

Note

Rút gọn phương trình ta được $x = 15$ .

Sample 3

Input (FINDX.inp)

2
x=123456789

Output (FINDX.out)

123456789

Note

Không có note.

Mật mã kho báu (TS10 QNi 2023)

Sunlight

Gần đây nhóm của An đã khám phá ra một kho báu trên một hòn đảo hoang. Trên cánh cửa lối vào, An thấy có ghi một xâu nhị phân $S$ (xâu chỉ chứa các chữ số $0$ và $1$ ). Ký hiệu $|S|$ là độ dài của xâu $S$ , tức là số ký tự của xâu $S$ . Các ký tự của xâu $S$ được đánh chỉ số từ $1$ đến $|S|$

Sau khi nghiên cứu các tài liệu và bản khảo cổ, An biết được mật mã để mở cửa kho báu này là một bộ 4 số $l_1,r_1,l_2,r_2$ , trong đó $[l_1,r_1]$ và $[l_2,r_2]$ là 2 đoạn chữ số khác nhau của xâu $S$ . Hai đoạn này phải có cùng độ dài và dài nhất có thể, hơn nữa tổng các chữ số của 2 đoạn phải bằng nhau. Cụ thể, mật mã của kho báu là 4 số $l_1,r_1,l_2,r_2$ sao cho:

$1\le l_1\le r_1\le |S|$ và $1\le l_2\le r_2\le |S|$
$[l_1,r_1]$ và $[l_2,r_2]$ là 2 đoạn khác nhau của $S$ , tức là $l_1\ne l_2$ hoặc $r_1\ne r_2$
$r_1-l_1=r_2-l_2$
$S_{l_1}+S_{l_1+1}+\dots+S_{r_1}=S_{l_2}+S_{l_2+1}+\dots+S_{r_2}$
$r_1-l_1$ lớn nhất

Theo như An tìm hiểu được từ bản thảo, nếu có nhiều bộ 4 số thỏa mãn thì bất kỳ bộ nào trong chúng đều có thể làm mật mã. Bây giờ An cần tìm mật mã cho kho báu, nhưng anh ấy không thể tìm được nếu không có sự giúp đỡ của bạn. Bạn hãy giúp An tìm mật mã của kho báu.

Input, Output và Subtasks

Input: (pass.inp)

Dòng đầu tiên chứa số nguyên $t$ ( $1\le t\le 5$ ) là số test. Mỗi dòng trong $t$ dòng tiếp theo chứa một xâu nhị phân $S$ (xâu $S$ chỉ bao gồm các chữ số $0,1$ và $1\le |S|\le 10^6$ )

Output: (pass.out)

Với mỗi test, in kết quả trên 1 dòng: nếu không tồn tại một bộ 4 số như vậy thì in ra $-1$ , ngược lại in ra 4 số $l_1,r_1,l_2,r_2$ là mật mã cần tìm. Nếu có nhiều câu trả lời thì in ra một câu trả lời bất kỳ trong số chúng

Subtasks

Subtask 1 $(25\%)$ : Tổng độ dài tất cả xâu $S$ không vượt quá $50$
Subtask 2 $(25\%)$ : Tổng độ dài tất cả xâu $S$ không vượt quá $500$
Subtask 3 $(25\%)$ : Tổng độ dài tất cả xâu $S$ không vượt quá $10^4$
Subtask 4 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (pass.inp)

Output (pass.out)

1 5 2 6
2 5 3 6
-1

Note

Trong test đầu tiên, đoạn $[1,5]$ ứng với xâu con 11111 và đoạn $[2,6]$ ứng với xâu con 11111 là 2 đoạn khác nhau có cùng độ dài và có cùng tổng các chữ số bằng $5$ . Không tồn tại 2 đoạn nào có độ dài lớn hơn thỏa mãn tất cả các điều kiện
Trong test thứ hai, đoạn $[2,5]$ ứng với xâu con 1010 và đoạn $[3,6]$ ứng với xâu con 0101 là 2 đoạn khác nhau có cùng độ dài và có cùng tổng các chữ số bằng $2$ . Không tồn tại 2 đoạn nào có độ dài lớn hơn thỏa mãn tất cả các điều kiện
Trong test thứ ba, không tồn tại 2 đoạn nào thỏa mãn tất cả điều kiện

Ký tự

Sunlight

Cho xâu ký tự $S$ và số nguyên dương $K$ . Biết rằng xâu $S$ không chứa ký tự a ở $K$ vị trí cuối cùng.

Yêu cầu: Với mỗi ký tự a xuất hiện trong xâu $S$ , thực hiện phép dịch chuyển ký tự a đi $K$ vị trí về phía bên phải và giữ nguyên vị trí tương đối của các ký tự còn lại.

Input, Output và Subtasks

Input: (HUBSHCHR.inp)

Dòng đầu ghi xâu $S$ chỉ gồm các ký tự chữ cái a-z ( $1\le |S|\le 100$ )
Dòng tiếp theo ghi số nguyên $K\ (1\le K\le 50)$

Output: (HUBSHCHR.out)

Dòng duy nhất ghi xâu $S$ sau khi đã được biến đổi

Sample

Input (HUBSHCHR.inp)

aaadddaaabccccb
2

Output (HUBSHCHR.out)

ddaaadbcaaacccb

Domino

Sunlight

Domino là trò chơi dựa trên các thẻ khoét lỗ. Mỗi thẻ có hai đầu được khoét một số lỗ (hoặc có thể không khoét lỗ) độc lập với nhau. Số lỗ trên các thẻ phụ thuộc vào kích thước của bộ cờ. Giả sử bộ cờ có kích thước $N$ thì số lỗ trên mỗi đầu của thẻ có giá trị từ $0$ đến $N$ . Hai thẻ gọi là khác nhau nếu một trong hai đầu của chúng là khác nhau. Ví dụ, thẻ bài có hai đầu khoét lỗ $(8,2)$ sẽ khác với thẻ $(8,3)$ nhưng sẽ giống với thẻ $(2,8)$ . Bộ cờ Domino hoàn chỉnh là bộ chứa các thẻ không trùng nhau có hai đầu mỗi thẻ được khoét số lỗ trong giới hạn từ $0$ đến $N$ . Dưới đây là bộ các thẻ trong bộ cờ Domino kích thước 2:

Yêu cầu: Cho biết kích thước của bộ cờ, đếm tổng số lỗ khoét trên các thẻ.

Input, Output và Subtasks

Input: (HUBDOMI.inp)

Một dòng duy nhất ghi số nguyên $N$ là kích thước của bộ cờ $(1\le n\le 1000)$

Output: (HUBDOMI.out)

Một dòng duy nhất ghi tổng số lỗ được khoét trên cả bộ cờ.

Sample

Input (HUBDOMI.inp)

Output (HUBDOMI.out)

Sample

Input (HUBDOMI.inp)

Output (HUBDOMI.out)

Note

Trong bộ cờ Domino kích thước $3$ , các quân cờ lần lượt là: [0|0], [0|1], [0|2], [0|3], [1|1], [1|2], [1|3], [2|2], [2|3] và [3|3]

Maxsum

Sunlight

Nam và Tài đang chơi một trò chơi toán học. Trong trò chơi này, Nam sẽ lần lượt ghi lên bảng mỗi lần một cặp số $A_i,B_i$ . Tài có nhiệm vụ sắp xếp lại các số $A$ và các số $B$ đã cho theo thứ tự nào đó sao cho: tổng lớn nhất có thể tạo được giữa các cặp $A_i,B_i$ trong cách sắp xếp đo là nhỏ nhất.

Yêu cầu: Biết cặp số $A,B$ mà Nam đã ghi lên bảng tại mỗi lượt, hãy cho biết giá trị nhỏ nhất theo mô tả ở trên mà Tài tìm được.

Input, Output và Subtasks

Input: (HUBMAXS.inp)

Dòng đầu tiên ghi số nguyên $N$ $(1\le n\le 100000)$ là số cặp $A,B$ ghi lên bảng.
$N$ dòng tiếp theo mỗi dòng ghi một cặp $A,B$ tương ứng mỗi lần ghi $(1\le A,B\le 100)$

Output: (HUBMAXS.out)

Tương ứng một cặp $A,B$ được ghi thêm lên bảng, ghi ra giá trị mà Tài tìm được.

Sample

Input (HUBMAXS.inp)

Output (HUBMAXS.out)

10
10
9

Note

Ở lượt ghi cuối, Nam ghi lên bảng $(1,4)$ . Khi đó, các giá trị tương ứng là $A(2,3,1), B(8,1,4)$ . Xét cách sắp xếp lại $A, B$ ta được $A(1,2,3),B(8,1,4)$ . Tổng lớn nhất giữa các cặp tương ứng là $9$ . Tổng này là nhỏ nhất trong các phương án sắp xếp.

Phần thưởng (TS10 TH 2023)

Sunlight

Lam là học sinh có thành tích cao trong kỳ thi tuyển sinh vào lớp 10 chuyên Tin. Phần thưởng cho em là một phần mềm diệt virus. Mã số của phần mềm là một dãy gồm $n$ số nguyên dương $a_1,a_2,\dots,a_n$ . Để cài đặt được phần mềm, Lam phải nhập vào mật khẩu của phần mềm. Mật khẩu là số lượng các số chia hết cho 90 của dãy số trên.

Yêu cầu: Hãy tìm mật khẩu để cài đặt phần mềm

Input, Output và Subtasks

Input: (CAU1.INP)

Dòng đầu là một số nguyên dương $n$ ( $1\le n\le 1000$ )
$n$ dòng sau, dòng thứ $i$ ghi số nguyên dương $a_i$ ( $0<a_i\le 10^{1000}$ )

Output: (CAU1.OUT)

Duy nhất một số là mật khẩu tìm được

Subtasks

Subtask 1 ( $85\%$ ): $n\le 100,a_i\le 10^9$
Subtask 2 ( $15\%$ ): Không có ràng buộc gì thêm

Sample

Input (CAU1.INP)

Output (CAU1.OUT)

Sample

Input (CAU1.INP)

1
9

Output (CAU1.OUT)

Số đẹp (TS10 TH 2023)

Sunlight

Số đẹp là số có tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố. Ví dụ: $23$ là một số đẹp vì $2^2+3^2=13$ là một số nguyên tố.

Dãy các số đẹp lần lượt là: $11,12,14,16,21,23,25,27,32,38,\dots$ . Các số đẹp được đánh số thứ tự tăng dần theo giá trị bắt đầu số thứ nhất là $11$ , số thứ hai là $12$ , ..., số thứ mười là $38$

Yêu cầu: Cho số nguyên dương $N$ . Hãy tìm số đẹp thứ $N$

Input, Output và Subtasks

Input: (CAU2.INP)

Chứa duy nhất một số nguyên dương $N$ ( $1\le N\le 10000$ )

Output: (CAU2.OUT)

Số đẹp thứ $N$

Subtasks

Subtask 1 $(70\%)$ : $N\le 10$ .
Subtask 2 $(30\%)$ : Không có giới hạn gì thêm.

Sample

Input (CAU2.INP)

Output (CAU2.OUT)

Sample

Input (CAU2.INP)

Output (CAU2.OUT)

Kế hoạch luyện tập (TS10 TH 2023)

Sunlight

Hè này, Lam xây dựng cho mình kế hoạch luyện tập chủ động trên một hệ thống lập trình trực tuyến. Hệ thống cung cấp $n$ bài toán, hai bài toán có nội dung liên quan được sắp xếp liền kề nhau. Các bài toán có độ khó lần lượt là $a_1,a_2,\dots,a_n$ . Lam đặt ra mục tiêu là kết thúc đợt nghỉ hè phải ôn luyện được một số nội dung nên phải làm được các bài toán liên quan và có tổng độ khó lớn hơn hoặc bằng $S$ .

Do trong hè còn có nhiều hoạt động khác, Lam cũng muốn mình phải làm ít nhất các bài toán mà vẫn đạt mục tiêu đặt ra

Yêu cầu: Hãy giúp Lam tính ra số lượng bài toán ít nhất liên tiếp nhau cần phải làm để đạt tổng độ khó tối thiểu là $S$

Input, Output và Subtasks

Input: (CAU3.INP)

Dòng 1 chứa 2 số nguyên dương $n$ và $S$ ( $1\le n\le 10^7,1\le S\le 10^{16}$ )
Dòng 2 chứa $n$ số nguyên dương $a_1,a_2,\dots,a_n$ ( $1\le a_i\le 10^9$ )

Output: (CAU3.OUT)

Một số nguyên là số lượng bài toán Lam cần làm. Trường hợp không có phương án thỏa mãn, ghi ra số -1

Subtasks

Subtask 1 ( $25\%$ ): $n\le 100,S\le 10^6,a_i\le 10^4$
Subtask 2 ( $25\%$ ): $n\le 5000,S\le 5\cdot 10^9,a_i\le 10^6$
Subtask 3 ( $25\%$ ): $n\le 10^5,S\le 10^{14},a_i\le 10^9$
Subtask 4 ( $25\%$ ): Không có ràng buộc gì thêm

Sample

Input (CAU3.INP)

10 18
5 1 3 9 10 7 4 9 2 8

Output (CAU3.OUT)

Sample

Input (CAU3.INP)

5 27
2 3 5 1 9

Output (CAU3.OUT)

-1

Biến đổi xâu (TS10 TH 2023)

Sunlight

Cho xâu $S=S_1 S_2 \dots S_i \dots S_j \dots S_n$ ( $1\le i\le j\le n$ ) chỉ gồm các chữ cái tiếng Anh in thường.

Phép đảo ngược xâu là phép biến đổi xâu ban đầu thành một xâu mới có thứ tự các ký tự ngược lại so với xâu ban đầu. Ví dụ ten đảo ngược thành net, time đảo ngược thành emit

Mỗi lần áp dụng phép đảo ngược xâu trên một xâu con liên tiếp từ vị trí $i$ đến vị trí $j$ của xâu $S$ sẽ thu được xâu $S'=S_1 S_2 \dots S_j \dots S_i \dots S_n$

Yêu cầu: Tính số lượng các xâu khác nhau nằm trong tập hợp $M$

Input, Output và Subtasks

Input: (CAU4.INP)

Gồm 1 dòng là xâu $S$ (độ dài không quá $2\cdot 10^5$ )

Output: (CAU4.OUT)

Một số nguyên là kết quả của bài toán

Subtasks

Subtask 1 ( $50\%$ ): Độ dài xâu $S$ không quá $100$
Subtask 2 ( $50\%$ ): Không có ràng buộc gì thêm

Sample

Input (CAU4.INP)

tent

Output (CAU4.OUT)

Note

Tập $M$ gồm: tent,etnt,nett,tnet,ttne,tetn

Xếp thùng sơn (TS10 QT 2023)

Sunlight

Cho $n$ thùng sơn màu đỏ và $m$ thùng sơn màu xanh xếp thành một hàng ngang. Các thùng sơn cùng màu được xếp liền nhau từ trái sang phải, hết màu này tiếp đến màu kia.

Yêu cầu: Nếu cần xếp $k$ thùng sơn lên xe, bắt đầu từ bên trái hàng sơn, hỏi có bao nhiêu thùng sơn màu đỏ được xếp

Input, Output và Subtasks

Input: (CAU1.INP)

Dòng đầu tiên ghi số nguyên dương $n$ ( $1\le n\le 100$ ) và 1 chữ cái $c_1$ , ghi cách nhau bởi một dấu cách, là số thùng sơn và màu sơn của các thùng sơn được xếp phía bên trái hàng sơn. Nếu chữ cái $c_1$ là R có nghĩa các thùng sơn màu đỏ, B là các thùng sơn màu xanh
Dòng thứ hai ghi số nguyên dương $m$ ( $1\le m\le 100$ ) và 1 chữ cái $c_2$ , ghi cách nhau bởi một dấu cách, là số thùng sơn và màu sơn của các thùng sơn được xếp phía bên phải hàng sơn. Nếu chữ cái $c_2$ ( $c_2\ne c_1$ ) là R có nghĩa các thùng sơn màu đỏ, B là các thùng sơn màu xanh
Dòng cuối cùng ghi số nguyên dương $k$ ( $1\le k\le n+m$ ) là số thùng sơn được xếp lên xe

Output: (CAU1.OUT)

Duy nhất một số là số thùng sơn màu đỏ được xếp lên xe

Sample

Input (CAU1.INP)

5 R
6 B
7

Output (CAU1.OUT)

Note

Có thể xem hàng sơn RRRRRBBBBBB thì số thùng sơn được xếp lên xe tương ứng là RRRRRBB. Có 5 thùng sơn màu đỏ được xếp lên xe

Sample

Input (CAU1.INP)

5 B
6 R
7

Output (CAU1.OUT)

Note

Có thể xem hàng sơn BBBBBRRRRRR thì số thùng sơn được xếp lên xe tương ứng là BBBBBRR. Có 2 thùng sơn màu đỏ được xếp lên xe

Sample

Input (CAU1.INP)

5 R
6 B
3

Output (CAU1.OUT)

Sample

Input (CAU1.INP)

5 B
6 R
3

Output (CAU1.OUT)

Tìm kiếm bài tập