Bài tập - TLEOJ

TLEOJ Contest #15 - Truy vấn tổng GCD

Shirokito

Cho mảng $a$ gồm $n$ phần tử, mảng $b$ gồm $m$ phần tử. Cho $q$ truy vấn, mỗi truy vấn gồm 4 số ( $l,r,u,v$ ). Nhiệm vụ của bạn là với mỗi truy vấn, tính tổng của tất cả các cặp ước chung lớn nhất của $a_i$ và $b_j$ với mọi $l \le i \le r$ và $u \le j \le v$ . Hay nói cách khác, tính:

$\sum^{i=l}_{i \le r} \sum^{j = u}_{j \le v}gcd(a_i,b_j)$

Input, Output và Subtasks

Input: (bàn phím)

Dòng đầu chứa 2 số nguyên dương $n,m$ ( $1 \le n,m \le 10^5$ ).
Dòng tiếp theo chứa $a_1,a_2,...,a_n$ ( $1 \le a_i \le 10^3$ ).
Dòng tiếp theo chứa $b_1,b_2,...,b_m$ ( $1 \le b_j \le 10^3$ ).
Dòng tiếp theo chứa số nguyên dương $q$ ( $1 \le q \le 10^4$ ).
$q$ dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương $l,r,u,v$ ( $1 \le l \le r \le n$ , $1 \le u \le v \le m$ ).

Output: (màn hình)

Với mỗi truy vấn in ra kết quả cần tìm.

Subtasks

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

Sample

Input (bàn phím)

Output (màn hình)

13
12

Chung kết TLEOJ Cup 2024 - Hai quốc gia

Shirokito

TLEOJ Contest #15 - Tổng AND

Shirokito

Cho mảng $a$ gồm $n$ phần tử và mảng $b$ gồm $m$ phần tử. Cho $q$ truy vấn, mỗi truy vấn thuộc 1 trong 3 loại sau:

1 i x cập nhật phần tử ở vị trí thứ $a_i$ thành $x$ ( $1 \le x \le 10^6$ ).
2 i x cập nhật phần tử ở vị trí thứ $b_i$ thành $x$ ( $1 \le x \le 10^6$ ).
3 tính $\sum^{n}_{i=1} \sum^{m}_{j=1}$ $a_i$ & $b_j$ , trong đó & là phép toán bitwise and.

Input, Output và Subtasks

Input: (SUMAND.INP)

Dòng đầu chứa $2$ số nguyên dương $n,m$ ( $1 \le n,m \le 10^5$ ).
Dòng thứ $2$ chứa dãy số nguyên $a_1, a_2,...,a_n$ ( $1 \le a_i \le 10^6$ ).
Dòng thứ $3$ chứa dãy số nguyên $b_1, a_2,...,a_m$ ( $1 \le b_i \le 10^6$ ).
Dòng thứ $4$ chứa số nguyên dương $q$ ( $1 \le q \le 10^5$ ).
$q$ dòng tiếp theo, mỗi dòng chứa $1$ truy vấn thuộc $3$ loại truy vấn ở trên.

Output: (SUMAND.OUT)

Với mỗi truy vấn loại $3$ in ra đáp án cần tìm.

Subtasks

Subtask 1 ( $30\%$ ): $1 \le n,m,q \le 200$ .
Subtask 1 ( $70\%$ ): không có giới hạn gì thêm.

Sample

Input (SUMAND.INP)

Output (SUMAND.OUT)

24
26

TLEOJ Contest #16 - Chi phí băng số

icebearlovecode

Tại bảng số ở nhà Hiếu có $n$ ô vuông, ô thứ $i$ có giá trị là $a_i$ . Hiếu và Đại sẽ chơi một trò chơi như sau:

Đại bắt đầu từ ô thứ nhất, di chuyển đến ô bất kì có giá trị không là số nguyên tố cùng nhau với giá trị ô hiện tại.
Nếu như tồn tại một ô không thể đi đến theo bất cứ cách nào, Đại sẽ chiến thắng.
mỗi ô có thể đi đến nhiều lần.

Để Đại không thể chiến thắng dễ dàng như vậy, Hiếu quyết định sẽ sửa giá trị tại một số ô. Nếu Hiếu sửa giá trị thứ $i$ cách chọn một số nguyên dương $k$ bất kì và nhân nó với $a_i$ chi phí cho việc sửa giá trị sẽ là $k$ (nói cách khác $a_i=a_i \cdot k$ ).

Yêu cầu: Tìm tổng chi phí nhỏ nhất để Đại không thể thắng.

Input and Output

Input

Dòng đầu tiên chứa một số nguyên dương $n$ ( $n\le 10^5$ ).
Dòng thứ hai chứa $n$ số nguyên dương $a_i$ , $i=1,2,3\dots n$ ( $a_i\le 10^5$ )

Output

Gồm một dòng duy nhất chứa tổng chi phí nhỏ nhất.

Subtask

Subtask $1$ ( $20\%$ ) : Với mọi $1\le i < j \le n$ thì $\text{gcd}(a_i,a_j)=1$ .
Subtask $2$ ( $20\%$ ) : $n\le 10,a_i\le 10$ .
Subtask $3$ ( $20\%$ ) : $a_i\le 2$ .
Subtask $4$ ( $40\%$ ) : không có giới hạn gì thêm

Test

Input

4
4 10 5 3

Output

Note

Nhân $a_4$ với $2$ ta được dãy $a=\{4;10;5;6\}$ Đại sẽ đi theo các ô như sau:
$1\rightarrow 4\rightarrow 2 \rightarrow 3$ .
dưới đây là hình minh họa cho test ví dụ.

Bedan Contest #05 - G - Xếp xe

flo

Cho một bàn cờ với kích thước là $n \times n$ , hãy đếm số lượng cách xếp $n$ quân xe lên bàn cờ đó sao cho không có bất kì cặp xe nào tấn công nhau.

Input, Output and Scoring

Input

Số nguyên dương $t$ $(1 \le t \le 10^2)$ .
$t$ dòng tiếp theo, mỗi dòng gồm $1$ số nguyên dương $n$ $(1 \le n \le 10^{18})$ .

Output

Với mỗi dòng, hãy in ra kết quả sau khi chia lấy dư cho $1234567891$ .

Test

Input

2
69
420

Output

1038218250
600140498

Bedan Contest #05 - F - Đảo ngược

flo

Cho dãy $a$ và $b$ gồm $n$ phần tử là hoán vị của $n$ . Bạn được thực hiện thao tác tối đa $n$ lần:

Chọn $2$ số nguyên dương $l$ và $r$ $(1 \le l \le r \le n)$ , sau đó đảo ngược đoạn con $[l, r]$ của $a$ .

Nhiệm vụ của bạn là in ra $m$ $(0 \le m \le n)$ là số thao tác và $m$ thao tác bạn cần thực hiện để biến đổi dãy $a$ thành $b$ .

Input and Output

Input

Số nguyên dương $n$ $(1 \le n \le 10^3)$ .
Dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ $(1 \le a_i \le n)$ .
Dãy $b$ gồm $n$ phần tử $b_1, b_2, ..., b_n$ $(1 \le b_i \le n)$ .

Output

In ra $m$ là số thao tác, sau đó là $m$ dòng tương ứng với $m$ thao tác cần thực hiện.
Nếu có nhiều cách thực hiện thao tác thỏa mãn, hãy in ra một cách bất kì.

Test

Input

5
4 2 3 5 1
1 5 4 2 3

Output

Note

Ngoài cách trên, đảo ngược đoạn $[1, 5]$ rồi đến $[1, 3]$ cũng được tính là đúng.

Bedan Contest #05 - E - Tổng chữ số

flo

Ta định nghĩa $S(n)$ là tổng chữ số của $n$ trong hệ thập phân.

Cho số nguyên dương $n$ , hãy tìm $1$ cặp số $(x, y)$ thỏa mãn:

$1 \le x \le n; 1 \le y \le n$ .
$x+S(x)+y+S(y) = n$ .

Input and Output

Input

Số nguyên dương $t$ $(1 \le t \le 10^5)$ .
$t$ dòng tiếp theo, mỗi dòng gồm $1$ số nguyên dương $n$ $(1 \le n \le 10^{18})$ .

Output

Với mỗi dòng, hãy in ra cặp số $(x, y)$ thỏa mãn. Nếu không có, hãy in ra $-1$ .

Test

Input

2
12
7

Output

2 4
-1

Bedan Contest #05 - D - Phép cộng

flo

Hãy để ý rằng bộ nhớ của bài này khá bất thường và khác với các bài còn lại, cụ thể là $16$ MB.

Cho $2$ dãy bit $s_1$ và $s_2$ lần lượt biểu diễn $a$ và $b$ trong hệ nhị phân. Hãy tìm dãy bit $s_3$ biểu diễn $a+b$ trong hệ nhị phân.

Input and Output

Input

Dãy bit $s_1$ gồm các bit $0$ và $1$ $(1 \le |s_1| \le 10^5)$ .
Dãy bit $s_2$ gồm các bit $0$ và $1$ $(1 \le |s_2| \le 10^5)$ .

Output

In ra dãy bit $s_3$ gồm các bit $0$ và $1$ thỏa mãn.

Test

Input

1101
1000

Output

Note

$13_{10} = 1101_{2}; 8_{10} = 1000_{2}; 21_{10} = 10101_{2}$

Bedan Contest #05 - C - Xâu đối xứng

flo

Cho xâu $s$ gồm $n$ kí tự, có $q$ truy vấn cần thực hiện có dạng sau:

l r: Hãy kiểm tra có tồn tại một cặp số $(i, j)$ nào thỏa mãn $s_is_{i+1}...s_j$ là xâu đối xứng hay không $(l \le i < j \le r)$ .

Input and Output

Input

Hai số nguyên dương $n, q$ $(1 \le n, q \le 10^5)$ .
Xâu $s$ gồm $n$ kí tự $s_1s_2...s_n$ ( $s_i$ là chữ cái Latin thường).
$q$ dòng tiếp theo, dòng thứ $i$ là truy vấn thứ $i$ có dạng l r $(1 \le l \le r \le n)$ .

Output

Với mỗi truy vấn, hãy in ra Yes nếu có và No nếu ngược lại.

Test

Input

10 4
aabcbaddac
1 6
8 10
3 9
4 7

Output

Yes
No
Yes
No

Note

Trong đoạn $[1, 6]$ , ta có cặp $(2, 6)$ thỏa mãn vì abcba là xâu đối xứng.
Trong đoạn $[8, 10]$ , dễ dàng thấy không có cặp $(i, j)$ nào thỏa mãn.
Trong đoạn $[3, 9]$ , ta có cặp $(7, 8)$ thỏa mãn vì dd là xâu đối xứng.
Trong đoạn $[4, 7]$ , dễ dàng thấy không có cặp $(i, j)$ nào thỏa mãn.

Bedan Contest #05 - B - Tổng GCD

flo

Hoán vị của $n$ là các dãy $p$ gồm $n$ phần tử phân biệt từ $1$ đến $n$ . Ví dụ $[1, 2, 3], [3, 1, 2], [2, 3, 1]$ là hoán vị của $3$ , trong khi $[1, 2], [3, 4, 2]$ thì không. Và với mỗi số nguyên dương $n$ , ta sẽ có tất cả $n!$ hoán vị.

Cho số nguyên dương $n$ , hãy tìm hoán vị $p$ của $n$ thỏa mãn:

Tồn tại một cặp $(i, j)$ thỏa mãn $p_i > p_j$ và $i < j$ .
$\sum_{i = 1}^n gcd(i, p_{n-i+1})$ đạt giá trị nhỏ nhất.

Input and Output

Input

Số nguyên dương $n$ $(1 \le n \le 10^6)$ .

Output

In ra hoán vị $p$ của $n$ bất kỳ thỏa mãn.

Test

Input

Output

3 4 1 2

Note

Với hoán vị $p$ trên, ta có $\sum_{i = 1}^4 gcd(i, p_{n-i+1}) = 4$ là nhỏ nhất.
Lưu ý rằng không chỉ có hoán vị $p$ trên mới là đáp án đúng.

Bedan Contest #05 - A - Biểu thức

flo

Cho dãy $a$ gồm $n$ phần tử, hãy thêm $n-1$ dấu + và - vào giữa các phần tử để tạo thành một biểu thức có kết quả là lớn nhất.

Input and Output

Input

Số nguyên dương $n$ $(1 \le n \le 10^6)$ .
Dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ $(1 \le |a_i| \le 10^9)$ .

Output

In ra $n-1$ dấu + và - để thêm vào thỏa mãn yêu cầu bài toán.

Test

Input

3
1 -2 2

Output

-+

Note

Với cách thêm $2$ dấu -+, ta có $1-(-2)+2 = 5$ là lớn nhất.

Trò chơi sắp xếp số

haizuka

Trong trò chơi sắp xếp số, bạn có một ma trận kích thước NxN (N hàng và N cột) gồm các số từ 1 đến $N^2 - 1$ và một ô trống mang giá trị $0$ , được hoán đổi ngẫu nhiên. Mục tiêu của trò chơi là dịch chuyển các số kề cạnh ô trống vào ô trống đó sao cho ma trận số được sắp xếp theo thứ tự tăng dần từ trái qua phải và từ trên xuống dưới. Tuy nhiên, không phải mọi ma trận ban đầu đều có thể sắp xếp theo yêu cầu. Ví dụ, dưới đây là một trường hợp không thể sắp xếp được.

1	3
2

Cho trước một ma trận gồm các số từ 0 đến $N^2 - 1$ , hãy kiểm tra xem liệu ma trận đó có thể sắp xếp lại được hay không. Trả về 1 nếu có, 0 nếu ngược lại.

Input, Output and Scoring

Input

$1$ số nguyên dương n $(2 \le n \le 10^3)$ .
$n$ dòng tiếp theo, mỗi dòng gồm $n$ số tự nhiên a[i][j] không trùng lặp từ 0 đến N^2-1

Output

Trả về 1 nếu có thể sắp xếp, 0 nếu không thể.

Scoring

Subtask $1$ $(30\%)$ : $2 \le n \le 10$ .
Subtask $2$ $(30\%)$ : $2 \le n \le 10^2$ .
Subtask $3$ $(40\%)$ : Không giới hạn gì thêm.

Example 1

Input

2
1 3
2 0

Output

0

Example 2

Input

3
1 2 0
4 5 3
7 8 6

Output

1

Explain

Có thể sắp xếp bằng các bước sau:
- Di chuyển số 3 lên trên
- Di chuyển số 6 lên trên

Số Chuẩn_1 (TS10 ĐN 2024)

Sunlight

Từ vựng (TS10 ĐN 2024)

Sunlight

Nobita (TS10 ĐN 2024)

Sunlight

Trung tâm (TS10 ĐN 2024)

Sunlight

Make It The Same

Noobcoder

Cho hai số tự nhiên $A$ , $B$ , có tối đa $15$ chữ số và không có những chữ số $0$ vô nghĩa ở đầu. Bạn có thể chọn thực hiện một trong hai thao tác sau, có thể thực hiện vô hạn lần thao tác, với một số $K$ cố định cho trước:

[Thao tác $1$ ]: Chia số $A$ cho $K$ và làm tròn kết quả đến số nguyên không âm lớn nhất không lớn hơn kết quả $A/K$ ban đầu. Lấy đó làm giá trị $A$ mới.
[Thao tác $2$ ]: Chia số $B$ cho $K$ và làm tròn kết quả đến số nguyên không âm lớn nhất không lớn hơn kết quả $B/K$ ban đầu. Lấy đó làm giá trị $B$ mới.

Ví dụ: Nếu $A = 69$ , $B = 420$ , $K = 10$ , thì nếu áp dụng [Thao tác $1$ ] thì số $A$ lúc này bằng $6$ (vì $6 \times K = 60 < A$ và $7 \times K = 70 > A$ ), còn nếu áp dụng [Thao tác $2$ ] thì số $B$ lúc này bằng $42$ (vì $42 \times K = 420 = B$ và $43 \times K = 430 > B$ ).

Hãy cho biết số lượng thao tác ít nhất cần sử dụng để đạt $A = B$ .

Input [standard]

Mỗi test có nhiều test cases. Dòng đầu tiên chứa số lượng các test cases, $t$ $(1≤t≤5)$ – số lượng các test cases. Sau đây là mô tả về các test cases.
Mỗi test case gồm $3$ dòng, dòng một là một số $A$ $(1≤A<10^{15})$ , dòng hai là một số B $(1≤B<10^{15})$ , dòng ba là một số $K$ $(2≤K≤100)$ .

Output [standard]

Với mỗi test case, in ra một giá trị duy nhất là số lượng thao tác ít nhất cần sử dụng để cho $A = B$ .

Scoring

$100\%$ số test có giới hạn như đề đã cho.

Example Tests

Example Test #1

INPUT

OUTPUT

5
5

Explanation

Ở test case $1$ , lúc đầu $A = 6$ , $B = 9$ . Một cách thực hiện là như sau:
Bước 1: Thực hiện [Thao tác $2$ ], lúc này $B = 4$ .
Bước 2: Thực hiện [Thao tác $1$ ], lúc này $A = 3$ .
Bước 3: Thực hiện [Thao tác $2$ ], lúc này $B = 2$ .
Bước 4: Thực hiện [Thao tác $1$ ], lúc này $A = 1$ .
Bước 5: Thực hiện [Thao tác $2$ ], lúc này $B = 1$ .
Sau bước 5, lúc này A=B=1, chương trình của test case này kết thúc.

Make It Divisible By 6

moi_hoc_code

Cho một số $N$ có tối đa $100$ chữ số và không có chữ số $0$ vô nghĩa nào ở đầu. Bạn được phép thực hiện thao tác sau:

Chọn một vị trí trong số $N$ dưới dạng xâu kí tự (biết xâu kí tự này được đánh số bắt đầu từ $1$ ). Xóa số đó khỏi xâu và trả xâu mới đó về lại dạng số, tạo ra số $N$ mới. Nếu như số $N$ ban đầu chỉ có $1$ chữ số, thao tác này sẽ tự động đưa giá trị biến $N$ trở về $0$ .

Ví dụ: Nếu $N = 69420$ , với một thao tác thì các số $N$ mới có thể là $9420$ (xóa chữ số đầu), $6420$ (xóa chữ số thứ hai), $6920$ (xóa chữ số thứ ba), $6940$ (xóa chữ số thứ tư, và $6942$ (xóa chữ số thứ năm).

Hãy cho biết cần tối thiểu bao nhiêu lần thực hiện thao tác để tạo ra được một số $N$ mới lớn nhất có thể sao cho $N$ chia hết cho $6$ , và không có bất kì chữ số $0$ vô nghĩa nào.

Input [standard]

Mỗi test bao gồm một số duy nhất là số $N$ , có tối đa $100$ chữ số $(1≤N<10^{100})$ .

Output [standard]

In ra số $X$ lớn nhất thỏa
- $X ≤ N$ ;
- $X$ chia hết cho $6$ ;
- Số $X$ có thể thu được bằng một chuỗi các thao tác trên lên số $N$

Scoring

$100\%$ số test có giới hạn như đề đã cho.

Example Tests

Example Test #1

INPUT

OUTPUT

Explanation

Ở test ví dụ số 1, $0/6=0$ .

Example Test #2

INPUT

OUTPUT

Explanation

Ở test ví dụ số 2, $138/6=23$ .

Example Test #3

INPUT

OUTPUT

Explanation

Ở test ví dụ số 3, $69420/6=11570$ .

Lucky Trio

kitngao

Một buổi chào cờ được diễn ra để tổng kết năm học, gộp chung với chúc mừng ngày Quốc tế thiếu nhi. Sau các phần giới thiệu, văn nghệ, thành tích năm học khép lại một năm học của các em học sinh, sẽ đến với phần là trò chơi.

Hiện tại, một trò chơi nhận thưởng được diễn ra như sau:

Các em học sinh ngồi theo các hàng ghế song song với nhau. Trong đó có $N$ hàng, và hàng ghế thứ $i$ sẽ chứa $A_i$ em học sinh. Và thoả mãn một điều rằng, không một em học sinh nào trên ba hàng khác nhau ngồi thẳng hàng.

Thầy/cô dẫn chương trình sẽ bốc các tờ giấy ghi họ tên lớp của học sinh trong một cái thùng, và chỉ được bốc ba lần tương ứng ba tờ giấy.

Những bộ ba học sinh trùng thông tin với thông tin ghi trên tờ giấy sẽ được lên nhận thưởng “Bộ ba may mắn” với các món quà như chiếc bút chì, cái hộp bút, cục tẩy, bộ sách vở,...

Một sự ngẫu nhiên bất ngờ trong trò chơi này chính là với “Bộ ba may mắn” đó nếu nối vị trí ba em học sinh sẽ tạo được thành một hình tam giác có diện tích lớn hơn $0$ .

Các thầy/cô chuẩn bị cần phải đếm xem có bao nhiêu “Bộ ba may mắn” để có thể chuẩn bị quà phù hợp. Nhưng số lượng đó là quá lớn, các thầy/cô đã nhờ đến bạn, một học sinh giỏi toán và cũng giỏi lập trình để đếm trong thời gian nhanh nhất!

Input [standard]

Dòng đầu ghi một số nguyên $N$ $(2 ≤ N ≤ 100)$ – Số hàng ghế.
$N$ dòng sau, dòng thứ $i + 1$ $(1 ≤ i ≤ N)$ ghi một số nguyên $A_i$ $(1 ≤ A_i ≤ 1000)$ – Số học sinh trên hàng ghế thứ $i$ .