Cho hai xâu $s$ và $t$. Với mỗi một thao tác, bạn có thể xóa một ký tự trong $s$ hoặc chèn một ký tự vào vị trí bất kỳ trong $s$. Đếm số lượng thao tác ít nhất để biến đổi xâu $s$ thành xâu $t$.

nguyenkhanhphuc
danghuyhau

11

Hôm nay, thầy giáo trên lớp của moi_hoc_code đã đưa ra một bài toán với độ khó xấp xỉ 3000 (cụ thể là 800 ) codeforces, với phần thưởng cho người đầu tiên giải được là một cặp vé xem phim. Bài toán có nội dung như sau:

Định nghĩa $f(i) = \frac{i}{p^{V_p(i)}}$. Tính $f(1) + f(2) + ... + f(n)$. Vì kết quả có thể rất lớn nên chỉ cần in ra kết quả đó sau khi chia lấy dư cho $10^9+7$.

Do moi_hoc_code mới học code nên không thể giải được bài toán siêu khủng này. Em liền đưa bài toán này cho khanhphucscratch, người mà em luôn đối xử trên cả tình bạn, với hy vọng có thể cùng nhau giành được một cặp vé xem phim chung. Tuy nhiên, khanhphucscratch, người đã có hai giải Nhất THTQG, lại chỉ giải được bài toán này với $p = 2$. Thất vọng, moi_hoc_code đành tìm đến sự trợ giúp của huyhau6a2, người cũng đã có một giải Nhất THTQG, nhưng thật không may, huyhau6a2 lại không nghiên cứu sâu về toán nên không biết $V_p(i)$ là gì. Bạn có thể giúp moi_hoc_code giải được bài toán này để giành lấy cặp vé xem phim hay không?

(Biết rằng: $V_p(i)$, hay lũy thừa của $p$ trong $i$, được định nghĩa trong bài tập này là số nguyên không âm $y$ lớn nhất không vượt quá $10^{18}$ sao cho $i \vdots p^y$. Ví dụ: Ta có $V_2(4) = 2$ do $4\vdots 2^2$ nhưng không chia hết cho $2^3$. Do đó $f(4) = \frac{4}{2^2} = 1$).

Giới hạn: $n, p \le 10^{18}$.

5 2

11

Cho một xâu $s$ có độ dài $n$ chỉ gồm các chữ cái la tinh thường. Định nghĩa một thao tác xoay xâu $s$ là một thao tác biến xâu $s_1s_2...s_n$ thành $s_ns_1...s_{n-1}$, hay nói cách khác, là chuyển ký tự cuối cùng của $s$ lên đầu xâu. Gọi $F_i$ là xâu $s$ sau khi xoay được $i$ thao tác. Hỏi rằng trong đa tập gồm các xâu $F_0, F_1, ..., F_{n - 1}$, xâu $F_0$ đứng thứ bao nhiêu về thứ tự từ điển (các xâu bằng nhau sẽ có thứ tự từ điển giống nhau).

bca

2

baba

3

Cho trước một số tự nhiên $x$ có $n$ chữ số và không có 2 chữ số nào giống nhau. Người ta thay đổi trật tự các chữ số của $x$ cho nhau để được một số tự nhiên mới cũng có $n$ chữ số và mỗi số mới này được gọi là một hoán vị của số $x$.
Yêu cầu: Tính tổng của số $x$ và tất cả các hoán vị của $x$.

123

1332

Một số được gọi là số nguyên tố đối xứng nếu nó là một số nguyên tố và khi đọc số này từ trái sang phải hay từ phải sang trái đều như nhau. Chẳng hạn $131$ là số nguyên tố đối xứng.
Yêu cầu: Cho trước một số nguyên dương $x$. Hãy tính xem có bao nhiêu số nguyên tố đối xứng lớn hơn $10$ và bé hơn $x$.

150

3

Yêu cầu: Nhập từ bàn phím một xâu kí tự $S$. Hãy đếm và in ra màn hình số lượng kí tự xuất hiện ít nhất $2$ lần trong xâu kí tự $S$ (có phân biệt chữ hoa và chữ thường).

abcbMbdmccccd

3

Số tự nhiên $y$ được gọi là một ước thực sự của số tự nhiên $x$ nếu $x$ chia hết cho $y$ và $x>y$.
Yêu cầu: Nhập vào bàn phím một số nguyên dương $x$ (với $x>1$), hãy tìm và in ra màn hình số $y$ là ước thực sự lớn nhất của số $x$.

10

5

huyhau6a2 thích chơi cờ vua. Cậu đã tạo ra $n$ bàn cờ có kích thước $k\cdot k$, được biểu diễn dưới dạng dãy $a$ 2 chiều với đặc điểm như sau:

• $a[i][j]=0$: Ô đó không có quân cờ
• $a[i][j]=1$: Ô đó có quân cờ

Tuy nhiên, sau khi chơi, có thể có các bàn cờ giống nhau. huyhau6a2 cần các bạn đếm số cặp bàn cờ giống nhau. Hai bàn cờ được coi là giống nhau khi một bàn cờ có thể xoay sao cho ra được bàn cờ còn lại

4 3
2 5 0
2 1 2
6 1 4
5 1 2

2

010
101
000

010
001
010

110
001
100

101
001
010

Cho ba số nguyên dương $l, r, k$, hãy đếm số lượng số nguyên dương $i$ sao cho $l \le i \le r$ và $i$ có đúng $k$ ước nguyên dương phân biệt.

1 50 3

4

Quân Vua trong bàn cờ vua có thể đi từ một ô đến 8 ô kề cạnh hoặc kề đỉnh với ô nó đang đứng. Hai quân Vua được xem là tấn công nhau khi và chỉ khi từ vị trí của quân Vua này có thể di chuyển đến vị trí của quân Vua kia trong một nước đi.

Nhiệm vụ của bạn là đếm số cách xếp những quân Vua trên bàn cờ $n\times m$ sao cho không có hai quân Vua nào tấn công nhau (có thể xếp bao nhiêu cũng được, kể cả không xếp)

2 3

11

000 | 100 | 010 | 001 | 000 | 000 | 000 | 101 | 100 | 001 | 000
000 | 000 | 000 | 000 | 100 | 010 | 001 | 000 | 001 | 100 | 101

3 3

35

4 7

16334

Trên một bàn cờ vua $k$ chiều, với kích thước được định trước bởi một dãy số nguyên $a_1, a_2, ..., a_k$, với ý nghĩa là ở chiều thứ $i$ có $a_i$ ô, có đặt một quân Hậu ở vị trí $(b_1, b_2, ..., b_k)$. Quân Hậu có thể di chuyển đến các ô cùng hàng hoặc cùng đường chéo với nó. Cùng hàng nghĩa là tồn tại giá trị $i$ sao cho $c_i \neq b_i$ và $c_j = b_j\ \forall j \neq i$. Cùng đướng chéo có nghĩa là $|c_1 - b_1| = |c_2 - b_2| = ... = |c_k - b_k|$. Đếm số ô mà quân Hậu có thể di chuyển đến trong một nước đi.

3
3 3 3
1 2 3

8

Trên một bàn cờ vua $k$ chiều, với kích thước được định trước bởi một dãy số nguyên $a_1, a_2, ..., a_k$, với ý nghĩa là ở chiều thứ $i$ có $a_i$ ô, có đặt một quân Mã ở vị trí $(b_1, b_2, ..., b_k)$.

Trong mỗi nước đi, quân Mã sẽ thực hiện thao tác sau:

• Chọn hai chiều $i$ và $j$.
• Thực hiện nước đi hình chữ $L$ như trên bàn cờ hai chiều.

Tổng quát hóa, quân Mã có thể đi được đến ô $(c_1, c_2, ..., c_k)$ khi và chỉ khi thỏa mãn hai điều kiện sau:

• $|c_1 - b_1| + |c_2 - b_2| + ... + |c_k - b_k| = 3$.
• $max(|c_1 - b_1|, |c_2 - b_2|, .., |c_k - b_k|) = 2$.

Đếm số ô mà quân Mã đến được trong một nước đi.

3
3 3 3
1 2 3

6

Trên một bàn cờ vua $k$ chiều, với kích thước được định trước bởi một dãy số nguyên $a_1, a_2, ..., a_k$, với ý nghĩa là ở chiều thứ $i$ có $a_i$ ô, có đặt một quân Xe ở vị trí $(b_1, b_2, ..., b_k)$. Quân Xe có thể di chuyển đến các ô cùng hàng với nó, nghĩa là các ô $(c_1, c_2, ..., c_k)$ sao cho tồn tại giá trị $i$ sao cho $c_i \neq b_i$ và $c_j = b_j\ \forall j \neq i$. Đếm số ô mà quân Xe có thể di chuyển đến trong một nước đi.

P/s: Đơn giản hóa cách đi của quân Xe như sau: Chọn một chiều $i$ cố định và thay đổi giá trị $b_i$ thành giá trị mới, giữ nguyên các giá trị còn lại.

3
3 3 3
1 2 3

6

Ta gọi số nguyên $M$ là số tiêu chuẩn nếu có có dạng $M=2^x+2^y$, với $x,y$ là hai số nguyên không âm phân biệt.
Bạn có một số nguyên dương $N$. Trong một bước bạn có thể tăng hoặc giảm $N$ đi $1$.

Yêu cầu: Tính số bước ít nhất để biến $N$ thành số tiêu chuẩn.

3
10
22
4

0
2
1

Cho một dãy số nguyên $a_1, a_2, ..., a_n$ và $q$ truy vấn, mỗi truy vấn gồm hai số nguyên dương $l, r$, hãy tìm số bộ ba số nguyên $a_i, a_j, a_k$ sao cho $l \le i < j < k \le r$ và $a_i + a_j + a_k = 0$.

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

2
1
4

Bạn được cho một số nguyên dương $n$. Với mỗi thao tác, bạn trừ $n$ cho tổng các chữ số của nó. Đếm số thao tác cần thiết để có $n = 0$.
Bạn phải trả lời $q$ truy vấn như vậy.

P/s: Bài này có giới hạn bộ nhớ là $600000KB$ (600 nghìn kilobytes).

3
18
19
20

2
2
3

Bạn được cho một số nguyên dương $n$. Với mỗi thao tác, bạn trừ $n$ cho tổng các chữ số của nó. Đếm số thao tác cần thiết để có $n = 0$.
Bạn phải trả lời $q$ truy vấn như vậy.

P/s: Bài này có giới hạn bộ nhớ là $600000KB$ (600 nghìn kilobytes).

3
18
19
20

2
2
3

Cho bàn cờ vua có kích cỡ $n\times n$, bạn cần tìm một cách xếp $n$ quân hậu trên bàn cờ sao cho không có quân hậu nào tấn công nhau.

4

YES
1 2
2 4
3 1
4 3

3

NO

This problem is the test for TLEOJ's judge
Just print "Hello world!" and you're done

Bạn được cho một dãy số nguyên dương $a_1$, $a_2$, $...$, $a_n$. Với mỗi thao tác, bạn được phép tăng hoặc giảm một phần tử bất kỳ $1$ đơn vị. Tìm số thao tác ít nhất để làm cho dãy sau khi biến đổi có ước chung lớn nhất lớn hơn $1$.

5
5 11 15 20 23

3