Young ICT 2024 - Phòng thi thử - Bảng C

Vì quá mệt khi phải tìm ý tưởng để viết cốt truyện cho đề ôn Tin học trẻ lần này, Quý quyết định chọn 1 bài tập ngẫu nhiên để làm giải trí. Bài tập mà Quý chọn có đề bài như sau:

Cho \(1\) dãy \(A\) gồm \(n\) số nguyên dương và \(1\) số \(e\). Hãy đếm số cặp \((i,k)\) thỏa mãn các điều kiện sau:

• \(1 \le i, k\)
• \(i + e \times k \le n\)
• Tích \(a_i \times a_{i + e} \times a_{i + 2e} \times ... \times a_{i + ke}\) là 1 số nguyên tố

Nhắc lại, số nguyên tố là số lớn hơn \(1\) và chỉ có \(2\) ước dương là \(1\) và chính nó.

Tuy nhiên, Quý đã không còn đủ sức để làm được bài này nên muốn nhờ các bạn hãy thay Quý giải bài tập trên.

Input

• Dòng đầu tiên gồm số nguyên \(t\) (\(t \le 10\)) là số lượng test cases của bài toán.

Mỗi test có cấu trúc như sau:

• Dòng đầu tiên bao gồm \(2\) số nguyên dương \(n\) và \(e\) (\(1 \le e \le n \le 10^5\)) là kích thước của mảng \(A\) và số \(e\) đề bài cho.
• Dòng thứ \(2\) bao gồm \(n\) số nguyên dương \(a_1, a_2, a_3, ..., a_n\) \((a_i \le 10^6)\)

Output

• Với mỗi test, in ra \(1\) số nguyên là số lượng cặp (\(i\), \(k\)) thỏa mãn điều kiện đề bài trên một dòng.
• In ra tổng cộng \(t\) dòng cho \(t\) test.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, e \le 200, a_i \le 10^3\)
• Subtask \(2\) (\(30\%\) số điểm): \(e = 1, n \le 10^5, a_i \le 10^3\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

6
7 3
10 2 1 3 1 19 3
3 2
1 13 1
9 3
2 4 2 1 1 1 1 4 2
3 1
1 1 1
4 1
1 2 1 1
2 2
1 2

2
0
4
0
5
0

(Ở một tương lai xa xôi) Trên con đường mới được quy hoạch của thành phố X, có \(n\) tòa nhà cao tầng nằm trên một con đường (tạm coi như một đường thẳng). Nhà thứ \(i\) có độ cao là \(h_i\) mét.
Việt không thích những tòa nhà có cùng độ cao nằm gần nhau. Cậu định nghĩa một dãy nhà \([l,r] (l\le r)\) là "nhàm chán" nếu như trong toàn bộ những căn nhà thứ \(l,l+1,l+2,\dots,r-1,r\) chỉ có không quá \(k\) độ cao khác nhau.
Nhằm đánh giá con đường này, Việt cần tính số lượng dãy nhà nhàm chán. Vì đã thấm mệt sau khi đi từ đầu đường tới cuối đường để lấy thông tin về chiều cao của các tòa nhà, Việt nhờ bạn lập trình giải quyết vấn đề trên. Hãy giúp Việt nhé!
Bonus: sau khi hỏi thị trưởng, Việt đã có được một số thông tin giúp việc tính toán trở nên dễ dàng hơn. Thông tin này được kí hiệu bởi số \(\theta\)

Input

• Dòng đầu tiên chứa \(\theta\) \((\theta \in \{1,2,3,4,5\})\): thông tin mới có được từ thị trưởng
• Dòng thứ hai chứa \(n,k\) \((1 \le n,k \le 10^5)\): số tòa nhà, và số định nghĩa sự "nhàm chán"
• Dòng tiếp theo chứa \(n\) số nguyên dương \(h_1, h_2, h_3, \dots, h_n (1 \le h_i \le 10^9)\)

Output

• Dòng duy nhất chứa số dãy nhà nhàm chán mà bạn đếm được

Scoring

• Subtask 1 (\(20\%\) số điểm): \(\theta = 1, h_i \le n \le 100\)
• Subtask 2 (\(30\%\) số điểm): \(\theta = 2, h_i \le n \le 1000\)
• Subtask 3 (\(15\%\) số điểm): \(\theta = 3\) và các tòa nhà có chiều cao khác nhau đôi một.
• Subtask 4 (\(15\%\) số điểm): \(\theta = 4, k = 1\)
• Subtask 5 (\(20\%\) số điểm): \(\theta = 5\), không có ràng buộc gì thêm.

1
5 2
1 2 3 1 1

10

Cho dãy số \(a\) gồm \(n\) số nguyên không âm. Bạn được thực hiện thao tác: đổi chỗ hai vị trí liên tiếp trong mảng \(a\) không quá \(k\) lần. Hãy tìm cách đổi để thu được dãy có thứ tự từ điển lớn nhất.

Input

• Dòng đầu tiên chứa hai số \(n,k\): độ dài dãy và số thao tác cho phép \((1 \le n \le 10^5, 0 \le k \le 5.10^9)\).
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(a_1, a_2, a_3, \dots, a_n (0 \le a_i \le 10^9)\)

Output

• Dòng duy nhất chứa dãy \(a\) sau biến đổi mà có thứ tự từ điển lớn nhất.

Scoring

• Subtask 1 (\(25\%\) số điểm): \(n \le 5000\)
• Subtask 2 (\(75\%\) số điểm): \(n \le 10^5\)

4 2
1 3 2 4

3 2 1 4 

Thành phố Đà Nẵng vừa mới mở một khu du lịch ăn uống Danang Éating Park (DÉP). Tên thì giống công viên phần mềm, mà nhìn trông cũng na ná Chợ đêm Sơn Trà.

Theo quy hoạch, khu du lịch sẽ mở ra \(n\) kiosk ăn uống, khu thứ \(i\) có khả năng hút khách tự thân là \(w_i\). Các kiosk sẽ được nối với nhau bằng \(m\) con đường hai chiều, mỗi con đường kết nối hai kiosk khác nhau. Để đảm bảo trật tự, Ban quản lý DÉP đã thiết kế, xây dựng sao cho: không có hai con đường nào cùng nối hai thành phố lại với nhau, và từ một thành phố luôn có thể đi tới các thành phố khác thông qua \(m\) con đường đã xây. Nói cách khác, đây chính là đồ thị đơn vô hướng liên thông, có trọng số ở đỉnh.

GSPVH sau khi chơi đủ 3 triệu để nâng hạng thẻ Helio từ Hồng lên Vàng, thì rất được Helio quan tâm. Biết rằng Giáo sư rất thích trà sữa, Helio hỏi ông có muốn mở một cửa hàng trà sữa trong khuôn viên của DÉP hay không, nếu có thì họ sẽ hỗ trợ Giáo sư cả về chi phí lẫn thủ tục (đúng là thẻ vàng có khác)

Đúng lúc này, sau khi xem xét luồng giao thông đường (đi) bộ dự kiến, Ban quản lý quyết định sẽ định chiều toàn bộ \(m\) con đường này lại, biến chúng thành đường một chiều hết, đồng thời xây dựng vài cọn đường nhỏ để nếu có ai bí đường không thể quay lại thì có thể men theo chúng, nhưng chúng ta không cần quan tâm tới những con đường này.

Vì sự thay đổi này, nên sau khi định chiều đồ thị, khả năng hút khách thực sự \(p_u\) của khu thứ \(u\) sẽ bằng tổng khả năng hút khách tự thân \(w_v\) của các đỉnh \(v\) có thể đi được từ \(u\).

Để đảm bảo sự công bằng cũng như thu hút nhiều khách du lịch nhất có thể, Ban quản lý Danang Éating Park mong muốn định chiều \(m\) cạnh sao cho \(p_u\) nhỏ nhất trong số \(n\) khu bán hàng là lớn nhất có thể. Biết rằng GSPVH có nhiều đàn em như bạn, ban quản lý nhờ Giáo sư hỏi bạn xử lý bài toán này. Hãy giúp họ nhé!

Input

• Dòng đầu tiên chứa hai số \(n, m\) \((1 \leq n, m \leq 4 \times 10^{5})\) - là số kiosk và số đường đi trong khu ăn uống DÉP.
• Dòng thứ hai chứa \(n\) số nguyên \(w_1, w_2, \ldots, w_n\) \((1 \leq w_i \leq 10^{9})\) - \(w_i\) là khả năng hút khách tự thân của đỉnh \(i\)
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u\), \(v\) \((1 \leq u, v \leq n)\) thể hiện một đường đi giữa hai kiosk \(u\) và \(v\).

Output

• Dòng đầu tiên in ra một số nguyên thể hiện khả năng hút khách nhỏ nhất trong phương án tối ưu.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) thể hiện con đường được định chiều từ \(u\) đến \(v\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m \le 2000\).
• Subtask \(3\) (\(20\%\) số điểm): \(m < n\).
• Subtask \(4\) (\(20\%\) số điểm): \(w[i] = w[i + 1] \forall 1 \leq i \leq n - 1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Sample

Test 1

Input

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

Output

6
2 4
5 2
3 6
1 3
7 1
4 5
6 1
5 1
****
*********

Note

Đây là biểu diễn đồ thị của đáp án được đưa ra:

Khi đó, \(p = {6, 12, 6, 12, 12, 6, 10}\), vì vậy \(\min p_i = p[1] = 6\).
Có thể chứng minh được không có cách định chiều đồ thị nào có \(\min p_i < 6\).

Nhân thích học toán. Đương nhiên là Nhân cũng thích nhân. Đối với Nhân, mọi thứ đều có thể biểu diễn được dưới dạng những con số. Hôm nay, Nhân đã gặp phải \(n\) sự vật sự việc khác nhau và cậu đã ghi vào nhật kí của mình một dãy \(a\) gồm \(n\) số tượng trưng cho những thứ ấy.
Để đánh giá mỗi ngày trôi qua tốt hay xấu, Nhân sẽ dựa vào một con số. Số này được tính bằng: Nhân sẽ nhân toàn bộ \(n\) số của ngày hôm đó lại. Nếu tích này vượt quá \(10^{18}\), Nhân sẽ coi như con số đó là \(-1\).
Tuy nhiên khá xui là Nhân đã bỏ quên máy tính ở trường nên không thể nhân được! Bạn hãy nhân giúp Nhân số trên (cho ngày hôm nay) nhé.

Input

• Dòng đầu tiên chứa \(n\) \((2 \le n \le 10^5)\): độ dài dãy
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(a_1, a_2, a_3, \dots, a_n (0 \le a_i \le 10^{18})\)

Output

• Dòng duy nhất chứa tích theo mô tả của đề bài

2
1000000000 1000000000

1000000000000000000

3
999999000001 9901 101

-1

Trải qua quá nhiều năm thăng trầm trong đầu tư chứng khoán, Nam đã trở thành một bậc thầy đầu tư. Hơn cả thế, Nam còn có năng lực dự đoán tương lai và biết trước được giá cổ phiếu IVN sẽ lên xuống \(n\) lần trong hôm nay. Cụ thể, Nam biết trước nếu "vào lệnh" vào đợt thứ \(i\) thì sẽ đem lại lợi nhuận là \(a_i\) VNĐ. Nếu \(a_i\) âm nghĩa là Nam sẽ thua lỗ \(-a_i\) VNĐ khi vào lệnh ở đợt \(i\).
Tuy nhiên, vì đã quá giàu nên Nam không muốn tổng lợi nhuận là lớn nhất. Thay vào đó, Nam muốn độ "chất chơi" phải cao, tức là đặt lệnh vào càng nhiều đợt càng tốt, kể cả có những đợt âm rất nhiều tiền (và dù Nam đã biết trước điều đó!). Để không bị đánh giá là đầu tư thiếu thông minh, Nam muốn đảm bảo sau mỗi lần vào lệnh, tổng lợi nhuận thu được là không âm.
Là một trợ lý mới được tuyển dụng, bạn được Nam nhờ tính độ "chất chơi".

Input

• Dòng đầu tiên chứa \(n\) \((1 \le n \le 2.10^5)\): số đợt thay đổi của cổ phiếu
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n (-10^9 \le a_i \le 10^9)\): nếu Nam vào lệnh ở đợt thứ \(i\) thì tổng lợi nhuận tăng lên \(a_i\).

Output

• Dòng duy nhất chứa số lần vào lệnh nhiều nhất có thể, thỏa mãn yêu cầu trên.

Scoring

• Subtask 1 (\(40\%\) số điểm): \(1 \le n \le 20\)
• Subtask 2 (\(40\%\) số điểm): \(1 \le n \le 1000\)
• Subtask 3 (\(20\%\) số điểm): Không có giới hạn thêm.

6
4 -4 1 -3 1 -3

5

Xâu \(x\) được gọi là lớn hơn xâu \(y\) nếu xâu \(y\) là đoạn đầu của xâu \(x\) hoặc xét kí tự đầu tiên khác nhau thì kí tự của xâu \(x\) lớn hơn kí tự của xâu \(y\).

Để luyện tập về việc so sánh hai xâu, Hồng đã tạo ra bài toán sau: Từ hai số nguyên dương \(a,b (a < b)\), tạo ra một dãy số gồm \(b - a + 1\) số: \(a, a + 1, ... , b\). Sau đó, sắp xếp lại các số theo thứ tự từ điển (coi mỗi số là một xâu và sắp xếp tăng dần) bằng các thao tác như sau: Mỗi lần chọn
và lấy ra một số trong dãy rồi chèn lại vào dãy ở vị trí bất kì.

Ví dụ, nếu \(a = 9, b = 11\) ta có dãy số gồm \(3\) số \(9, 10, 11\), dãy số được sắp xếp theo thứ tự từ điển là \(10, 11, 9\) và cần ít nhất một thao tác (rút số \(9\) khỏi dãy và chèn vào cuối dãy).

Yêu cầu: Cho hai số nguyên dương \(a, b (a < b)\), hãy tính số thao tác ít nhất để sắp xếp các số \(a, a + 1, ... , b\) theo thứ tự từ điển.

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương \(a, b (a < b \le 10^9)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên là số thao tác ít nhất để sắp xếp các số \(a, a + 1, ... , b\) theo thứ tự từ điển.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(b - a = 1\);
• Subtask \(2\) (\(20\%\) số điểm): \(b - a \le 10\);
• Subtask \(3\) (\(30\%\) số điểm): \(b − a \le 1000\);
• Subtask \(4\) (\(30\%\) số điểm): \(b − a \le 10^5\);

Example

9 11

1

Không biết các bài toán đa cấp có được cho vào chung một contest hay không, nhưng sau đây là một bài toán như thế:

CAO (Chief Air-conditioner Officer) của The Pyramid Company trực thuộc tập đoàn VierTech phát cho mỗi nhân viên tập sự một hình tam giác trống, gọi là tam giác cấp 0.

Khi một nhân viên mời đủ 3 người khác tham gia tập đoàn, tam giác của nhân viên đó sẽ được nâng lên cấp 1: Từ tam giác cấp 0, lấy trung điểm của 3 cạnh tam giác nối lại với nhau, chia hình cũ thành 4 hình tam giác cấp 0 nhỏ hơn.

Khi 3 người đó tiếp tục mời thêm 3 người nữa, các tam giác tiếp tục chia nhỏ như vậy, sẽ ra tam giác cấp 2 (gồm 4 hình tam giác cấp 1), cấp 3 (gồm 4 hình tam giác cấp 2), …

Lương của một nhân viên (tính bằng BTC) bằng số điểm trên tam giác mà nhân viên có. Theo hình ta thấy, lương bậc 0 là 3 BTC, bậc 1 là 6 BTC, ...

Vì là công ty đa cấp nên bạn KHÔNG CẦN BẰNG CẤP, chỉ cần có KHÁT KHAO LÀM GIÀU thì sẽ GIÀU NHANH. Cũng chẳng cần học toán, vì vậy khá nhiều nhân viên không biết lương của họ là bao nhiêu.

Một nhân viên cho bạn xem tam giác họ có, muốn nhờ bạn tính họ sẽ có bao nhiêu tiền. Tính giúp họ đê 😛

Input

• 1 dòng duy nhất gồm một số \(n\) là cấp của tam giác mà người hỏi sở hữu

Output

• Lương của người đó, tính bằng Satoshi, modulo \(10^9+7\)

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 20\)
• Subtask \(2\) (\(45\%\) số điểm): \(n \le 10^6\)
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^{18}\)

Example

2

15

Các số nguyên tố liệt kê theo thứ tự tăng dần \(2, 3, 5, 7, 11, 13, \dots\) tạo thành một dãy số và đánh số bắt đầu từ \(1\). Gọi \(p_i\) là số nguyên tố thứ \(i\), ta nói \(p_i\) là số nguyên tố đối xứng nếu nó bằng trung bình cộng của 2 số nguyên tố liền trước và liền sau nó. Nói cách khác \(p_i\) là số nguyên tố đối xứng nếu thỏa điều kiện:
\(\(p_i = \frac{p_{i-1} + p_{i + 1}}{2}\)\)

Như vậy, 10 số nguyên tố đối xứng đầu tiên là: \(5, 53, 157, 173, 211, 257, 263, 373, 563, 593\).

Yêu cầu: cho số nguyên \(n\). Cho biết \(n\) có phải số nguyên tố đối xứng hay không.

Input:

• Dòng đầu tiên ghi số nguyên \(t (1 ≤ t ≤ 10^5)\) – số lượng số \(n\) cần kiểm tra.
• \(t\) dòng tiếp theo, mỗi dòng ghi một số nguyên \(n (1 ≤ n ≤ 2 * 10^7)\)

Output: gồm \(t\) dòng, mỗi dòng ghi “YES” hoặc “NO” là câu trả lời tương ứng với câu hỏi trong input.

Sample Input:

3
11
5
373

Sample Output:

NO
YES
YES

Có một xâu kí tự \(S\) chỉ chứa các chữ cái thường (a..z), người ta muốn cắt xâu \(S\) thành các xâu con sao cho mỗi xâu con không chứa 2 kí tự nào giống nhau.

Yêu cầu: Viết chương trình nhập vào từ bàn phím xâu \(S\) có độ dài không quá 255 kí tự và có ít nhất 2 kí tự giống nhau. Hãy tính và in ra màn hình số lượng ít nhất các xâu con không chứa 2 kí tự nào giống nhau được cắt ra từ xâu \(S\).

Input

• Chứa duy nhất một xâu ký tự \(S\).

Output

• Số lượng xâu ít nhất theo yêu cầu của đề.

Example

abcbdetd 

3