Ghép số (mrg.*)

Cho \(n\) số nguyên dương \(a_{1},{\ a}_{2},\ldots,\ a_{n}\). Từ các số này người ta tạo ra các số nguyên mới bằng cách viết tất cả các số trên liền với nhau theo một thứ tự bất kì.

Ví dụ, với dãy số \(20;\ 15;\ 30\) ta có thể ghép lại các số này để tạo ra các số mới như sau: \(201530;\ 203015;302015;301520;152030;153020,\ \)trong trường hợp này số nhỏ nhất tạo thành là \(152030\).

Yêu cầu: Hãy tìm số nhỏ nhất có thể ghép được theo quy tắc trên.

Dữ liệu vào:

- Dòng đầu tiên ghi số nguyên dương \(n\ (1 \leq \ n \leq 10^{5}).\)

- Dòng thứ hai ghi n số nguyên dương \(a_{1},{\ a}_{2},\ \ldots,\ a_{n}\) \((0 < a_{i} \leq 10^{3},\ \ 1 \leq i \leq n)\), mỗi số cách nhau bởi một khoảng trắng.

Kết quả: Ghi kết quả theo yêu cầu của bài toán.

Ví dụ:

Ràng buộc:

- 30% số test với \(1 \leq n \leq 10^{2}\) và các số của dãy có độ dài bằng nhau.

- 40% số test với \(10^{2} < n \leq 10^{5}\) và các số của dãy có độ dài bằng nhau.

- 30% số test còn lại không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Số T-PRIME (tpr.*)

Số T-Prime là số có đúng ba ước số nguyên dương khác nhau.

Yêu cầu: Hãy lập trình đếm xem có bao nhiêu số T-Prime không vượt quá\(\ n\).

Dữ liệu vào: Gồm một dòng ghi số nguyên dương \(n\).

Dữ liệu ra: ghi một số nguyên duy nhất là số lượng số T-Prime không vượt quá \(n\) \((4 \leq n \leq 10^{9})\).

Ví dụ:

Ràng buộc: - 30% số test với \(4 \leq n \leq 10^{3}\).

- 40% số test với \(10^{3} < n \leq 10^{6}\).

- 30% số test còn lại không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Đoạn bội

Cho hai đoạn chứa số nguyên dương \(\lbrack a,\ a\ + \ 1,\ \ldots,\ b\rbrack\) và \(\lbrack c,\ c\ + \ 1,\ \ldots,\ d\rbrack\). Hãy xác định xem tích \(c.(c\ + \ 1)\ldots d\) có chia hết cho tích \(a.(a\ + \ 1)\ldots b\) hay không.

Dữ liệu vào:

• Dòng đầu chứa số nguyên \(t\ (1\ \leq \ t\ \leq \ 10)\) là số lượng test cases.

• Mỗi dòng trong \(t\) dòng tiếp theo gồm bốn số nguyên dương \(a_{i},\ b_{i},\ c_{i},\ d_{i}\).

Kết quả:

Gồm t dòng. Với test cases thứ \(i\), in ra \(Y\) nếu tích \(c.(c\ + \ 1)\ldots d\) có chia hết cho tích \(a.(a\ + \ 1)\ \ldots b\), ngược lại in \(N\).

Ví dụ

Giải thích ví dụ 1:

Ta có 9.10 = 90 và 3.4.5.6 = 360. Kết quả là Y bởi vì 360 chia hết cho 90. Ta tính được 2.3.4.5 = 120 không thể bị chia hết bởi 7.8.9 = 504. Do đó kết quả là N.

Ràng buộc:

• \(1\ \leq \ a_{i}\ \leq \ b_{i}\ \leq \ 10^{7}\)

• \(1\ \leq \ c_{i}\ \leq \ d_{i}\ \leq \ 10^{7}\)

Bạn cần Đăng nhập để nộp bài

Bạn được cho một dãy số gồm \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\). Một thao tác được ghi nhận khi bạn thực hiện tăng hoặc giảm giá trị của bất kỳ số \(a_{i}\) nào trong dãy lên 1 đơn vị (tức là \(a_{i}\ = \ a_{i} + 1\) hoặc \(a_{i}\ = \ a_{i}\ - \ 1\)) và bạn có thể lặp đi lặp lại thao tác này vô số lần. Thầy giáo muốn bạn hãy thực hiện các thao tác tăng giảm giá trị đó để thu được một dãy số mới sao cho tích của các phần tử trong dãy số mới này bằng 1.

Ví dụ: với \(n = 3\) và dãy số gồm 3 phần tử là \(\lbrack 1,\ - 3,\ 0\rbrack\) chúng ta có thể thực hiện tăng 2 lần số -3 (tức \(a_{2}\)) để trở thành -1 và giảm 1 lần số 0 (tức \(a_{3}\)) để trở thành -1. Lúc này ta sẽ thu được dãy số mới là [1, -1, -1] và tích các phần tử trong dãy số này bằng 1. Như vậy, bạn sẽ mất tổng cộng 03 thao tác để thực hiện ba lần tăng/giảm giá trị. Có nhiều cách khác nhau để thực hiện việc tăng giảm để dãy mới thu được có tích bằng 1, tuy nhiên sẽ không tồn tại cách nào ít hơn ba thao tác.

Yêu cầu: Cho dãy số \(a\) gồm \(n\) số nguyên, hãy tìm ra chi phí ít nhất để biến đổi dãy số \(a\) đã cho trở thành dãy mới với tích các phần tử trong dãy bằng 1.

Dữ liệu vào: Dòng đầu là số nguyên dương \(n\). Dòng thứ 2 gồm \(n\) số nguyên \(a_{i}\) (\({- 10}^{9}\ \leq \ a_{i}\ \leq \ 10^{9}\)) với mỗi số được cách nhau bởi một dấu cách.

Kết quả: ghi chi phí ít nhất để biến đổi dãy số đã cho để trở thành dãy có tích các phần tử bằng 1.

Ví dụ:

Giải thích:

• Trong trường hợp đầu tiên, bạn có thể thay đổi -1 trở thành 1 hoặc là 1 trở thành -1. Với trường hợp này chi phí sẽ là 2 thao tác.

• Trong trường hợp thứ hai, bạn có thể thay -5 thành -1 (mất 4 thao tác), -3 thành -1 (mất 2 thao tác), 5 thành 1 (mất 4 thao tác), 3 thành 1 (mất 2 thao tác) và 0 thành 1 (mất 1 thao tác). Tổng sẽ là 13 thao tác.

Ràng buộc:

• 40% số điểm của bài có \(0 < n \leq 100\)

• 60% số điểm còn lại của bài có \(0 < n \leq 10^{5}\)

Bạn cần Đăng nhập để nộp bài

Mê cung có kích thước n × m, được chia thành n × m phòng có kích thước 1 × 1, giữa các phòng có các bức từng ngăn cách. Có thể xem mê cung như một ma trận phòng, phòng ở góc phía trên bên trái được gán nhãn (1, 1) và phòng ở góc phía dưới bên phải có được gán nhãn (n, m). Giữa các cặp phòng liền kề có một bức tường có 1 trong 4 màu: xanh lam (kí tự P), đỏ (kí tự C), xanh lá cây (kí tự Z) hoặc cam (kí tự N).

Hình minh hoạ là mê cung trong test 3. Căn phòng nơi Hải đang ở đánh đánh dấu bằng một chấm tròn màu đen, còn căn phòng Dương đang ở được đánh dấu bằng chấm tròn màu trắng. Một con đường từ Hải đến Dương được đánh dấu bằng màu xám đi qua các cánh cửa với 3 màu khác nhau (Đỏ, xanh lam, xanh lá cây – C, P, Z).

Có q câu hỏi, mỗi câu hỏi có dạng: Nếu Hải đang ở một phòng có nhãn (a_i, b_i) và Dương đang ở trong phòng có nhãn là (c_i, d_i), thì Hải cần phải đi qua tối thiểu bao nhiêu màu cửa để đến được chỗ của Dương.

Dữ liệu vào:

• Dòng đầu tiên chưa 2 số nguyên dương n, m (1 ≤ n, m ≤ 100, 1 < n × m) là kích thước của mê cung.

• Dòng thứ i trong n dòng tiếp theo, mỗi dòng chứa m-1 kí tự (P, C, Z hoặc N) trong đó chữ cái thứ j biểu thị màu cửa nối các phòng (i, j) và (i, j+1).

• Dòng thứ i trong n-1 dòng tiếp theo, mỗi dòng chứa m kí tự (P, C, Z hoặc N), trong đó chữ cái thứ j biểu thị màu cửa nối phòng (i, j) và (i+1, j).

• Dòng tiếp theo là số nguyên dương q (1 ≤ q ≤ 100) là số câu hỏi

• q dòng tiếp theo mỗi dòng chứa 4 số nguyên a_i, b_i, c_i, d_i là thông tin của một câu hỏi. Dữ liệu các câu hỏi đảm bảo đôi một khác nhau.

Kết quả:

• Gồm q dòng, dòng thứ i viết câu trả lời tương ứng cho câu hỏi thứ i trong dữ liệu.

Ràng buộc:

• 15% số điểm có n = 1

• 15% số điểm có tất cả các cửa nối các phòng (i, j) và (i, j+1) có màu xanh lam và tất cả các cửa nối các phòng (i, j) và (i+1, j) đều có màu đỏ.

• 30% số điểm có tất cả các cửa sẽ có màu xanh hoặc đỏ

• 40% số điểm còn lại không có ràng buộc gì thêm.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Ở Singapore, có \(n\) trạm tàu điện được xếp thẳng hàng, được đánh số từ 1 đến \(n\). Sắp tới Ronaldo sẽ tới Singapore du lịch. Có \(m\) tuyến tàu điện, mỗi tuyến có đường ray riêng, đánh số từ 1 đến \(m\). Tuyến tàu thứ \(i\) được mô tả bởi 4 số nguyên \(A_{i},\ B_{i},\ C_{i}\) và \(D_{i}\). Tàu chạy hai chiều giữa hai trạm \(A_{i}\) và \(B_{i}\) (với \(A_{i} < B_{i}\)). Mỗi tuyến phục vụ hai loại tàu:

1. Tàu thường:

- Dừng ở tất cả các trạm từ \(A_{i}\) đến \(B_{i}\) (bao gồm cả hai đầu).

- Chi phí di chuyển từ trạm \(x\) đến trạm \(y\) (với \(A_{i}\ \leq x,\ y \leq B_{i}\)) là \(C_{i} \times |x - y|\).

2. Tàu tốc hành:

- Chỉ dừng ở \(A_{i}\) và \(B_{i}\).

- Chi phí di chuyển giữa hai trạm này (theo cả hai chiều) là \(D_{i}\). Để lên tàu, hành khách cần mua vé hành trình với giá \(T\) tại trạm xuất phát. Tuy nhiên, nếu chuyển tuyến tại cùng một trạm, bạn không cần mua vé mới. Nếu rời khỏi trạm và muốn tiếp tục hành trình ở trạm tiếp theo, bạn phải mua vé mới.

Ngoài ra, có tuyến xe buýt phủ toàn bộ các trạm. Việc di chuyển từ trạm \(x\) đến trạm \(y\) bằng xe buýt sẽ tốn \(K\ \times \ |x\ - \ y|\). Khách sạn của Ronaldo ở trạm \(P\), anh ấy muốn đi từ trạm \(P\) đến trạm \(Q\) bằng tàu hoặc xe buýt (hoặc kết hợp cả hai). Hãy giúp Ronaldo tìm ra chi phí thấp nhất để thực hiện hành trình này.

Dữ liệu vào:

- Một dòng gồm 6 số nguyên: \(n\ m\ K\ T\ P\ Q\) (tách nhau bằng dấu cách)

- \(m\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(A_{i}\ B_{i}\ C_{i}\ D_{i}\) (tách nhau bằng dấu cách)

Kết quả:

- In ra chi phí nhỏ nhất cần thiết để đi từ trạm \(P\) đến \(Q\).

Ràng buộc:

- \(2\ \leq \ n\ \leq \ 100000;\) \(1\ \leq \ m\ \leq \ 200000\ \)

- \(1\ \leq \ K\ \leq \ 100000\)

- \(0\ \leq \ T\ \leq \ 100000\)

- \(1\ \leq \ P,\ Q\ \leq \ n,\ P\ ≠ \ Q\)

- \(1\ \leq \ A_{i} < \ B_{i} \leq \ n\)

- \(1\ \leq \ C_{i}\ \leq \ 100000\)

- \(1\ \leq \ D_{i}\ \leq \ 10^{9}\)

Subtasks:

- 10% điểm: \(A_{i} = \ 1,\ B_{i} = \ n\)

- 20% điểm: \(n \leq 1000,\ M \leq 5,\ T = 0\)

- 20% điểm: \(m\ \leq \ 5\)

- 20% điểm: \(T\ = \ 0\)

- 30% điểm: Không có ràng buộc bổ sung

Ví dụ:

Giải thích:

- Mua vé 1 tại trạm 9, đi tàu thường đến trạm 10 (chi phí: 10)

- Chuyển sang tàu tốc hành về trạm 7 (miễn phí chuyển tuyến, chi phí: 8)

- Đi xe buýt từ trạm 7 đến 6 (chi phí: 10)

- Mua vé mới tại trạm 6 (1), đi tàu thường đến trạm 5 (chi phí: 8)

Tổng chi phí: 1 + 10 + 8 + 10 + 1 + 8 = 38

Bạn cần Đăng nhập để nộp bài

Tại một ngôi làng nhỏ ở Lộc Hà, có \(n\) ngôi nhà xếp thành một hàng. Ngôi nhà thứ \(i\) có \(a_{i}\) thành viên trong gia đình. Để tăng thu nhập cho làng, trưởng làng tổ chức một chương trình. Mỗi ngày, ông sẽ chọn đúng \(k\) nhóm nhà sao cho:

- Mỗi nhóm gồm ít nhất một ngôi nhà.

- Mỗi ngôi nhà chỉ thuộc về một nhóm duy nhất.

- Các ngôi nhà trong cùng một nhóm phải nằm liền kề nhau.

Sau đó, mỗi nhóm sẽ quyên góp một số tiền bằng với Ước chung lớn nhất (GCD) của số thành viên trong tất cả các ngôi nhà trong nhóm đó. Trưởng làng sẽ luôn chọn cách phân nhóm khác nhau mỗi ngày. Lễ hội kết thúc khi tất cả các cách phân nhóm \(k\) nhóm khác nhau đã được thực hiện. Trưởng làng muốn biết tổng số tiền quyên góp được sau lễ hội là bao nhiêu. Do kết quả có thể rất lớn, hãy trả lời phần dư của kết quả chia cho \(10^{9} + 7\)

Dữ liệu vào:

- Dòng đầu tiên: \(n\) và \(k\)

- Dòng thứ hai: \(a_{1},a_{2},\ldots,a_{n}\)

Kết quả:

- Một dòng duy nhất in tổng thu nhập thu được sau toàn bộ lễ hội, chia dư cho \(10^{9} + 7\).

Ví dụ:

Giải thích:

Các cách chia nhóm và thu nhập tương ứng:

- [6] [4] 5 → 6 + 4 = 10

- [6] 4 [5] → 6 + 5 = 11

- [6] [4 5] → 6 + 1 = 7

- [6 4] [5] → 2 + 5 = 7

- 6 [4] [5] → 4 + 5 = 9

Tổng cộng: 10 + 11 + 7 + 7 + 9 = 44

Ràng buộc:

- \(1\ \leq \ n\ \leq \ 50,000\ \)

- \(1\ \leq \ k\ \leq \ min(n,\ 20)\)

- \(1\ \leq \ a_{i}\ \leq \ 100,000\)

Subtasks:

- 10% điểm: \(n\ \leq \ 10\)

- 10% điểm: \(n\ \leq \ 500,\ k = 1\)

- 10% điểm: \(n \leq 500,\ k \leq \ 2\)

- 20% điểm: \(k = 1\)

- 20% điểm: \(a_{1} = a_{2} = \ldots = a_{n}\)

- 30% điểm: Không có ràng buộc bổ sung

Bạn cần Đăng nhập để nộp bài

Bé Đăng có một bảng phi tiêu đặc biệt được biểu diễn dưới dạng lưới kích thước \(n \times m\), trong đó \(n\) và \(m\) đều là số lẻ. Các hàng được đánh số từ 1 đến \(n\), các cột được đánh số từ 1 đến \(m\). Với ô nằm ở hàng thứ \(i\) và cột thứ \(j\), giá trị của ô này được ký hiệu là \(v_{i,j}\), được xác định bằng cách nối hai số \(i\) và \(j\) lại với nhau. Ví dụ: \(v_{12,345}\ = \ 12345\) và \(v_{20,25}\ = \ 2025\). Đăng muốn ném phi tiêu vào đúng trung tâm của bảng. Tuy nhiên, “trung tâm” được xác định không phải theo tọa độ hình học mà là giá trị trung vị (median) của tất cả các ô trong lưới. Hãy giúp Đăng xác định giá trị trung vị của lưới!

Dữ liệu vào:

- Dòng đầu tiên chứa 1 số nguyên duy nhất \(T \leq \ 5\) (số testcase)

- \(T\) dòng tiếp theo mỗi dòng chứa hai số nguyên cách nhau bởi khoảng trắng: \(n\) và \(m\) (cả hai đều là số lẻ).

Kết quả:

- In ra giá trị trung vị của tất cả các ô trong bảng.

Subtasks:

- 10% điểm: \(n = 1,\ 1 \leq m \leq 10^{9}\)

- 30% điểm: \(1 \leq n,m \leq 1000\)

- 30% điểm: \(1 \leq n \leq 100000,\ 1 \leq m \leq 10^{9}\)

- 30% điểm: \(1 \leq \ n,\ m\ \leq \ 10^{9}\)

Ví dụ:

Giải thích: Lưới có giá trị như sau:

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

Giá trị trung vị là 23 (vì đây là phần tử đứng giữa khi sắp xếp toàn bộ các giá trị theo thứ tự tăng dần).

Bạn cần Đăng nhập để nộp bài

Bạn được cho một cây gốc (rooted tree) với đỉnh gốc là đỉnh số 1. Mỗi đỉnh trong cây được tô một màu nào đó. Chúng ta gọi màu \(c\) là màu thống trị trong cây con của đỉnh \(v\) nếu không có màu nào khác xuất hiện nhiều hơn màu \(c\) trong cây con của đỉnh \(v\). Có thể có nhiều hơn một màu thống trị trong cùng một cây con. Cây con của một đỉnh \(v\) bao gồm: Chính đỉnh \(v\), và Tất cả các đỉnh khác nằm phía dưới \(v\) trong cây (nghĩa là: mọi đỉnh mà đường đi từ nó đến gốc đều đi qua \(v\)).

Nhiệm vụ của bạn: Với mỗi đỉnh \(v\), hãy tính tổng tất cả các màu thống trị trong cây con của đỉnh đó.

Dữ liệu vào:

+ Dòng đầu tiên chứa một số nguyên \(n\ (1\ \leq \ n\ \leq \ 10⁵)\) — số lượng đỉnh trong cây.

+ Dòng thứ hai chứa \(n\) số nguyên \(c₁,\ c₂,\ ...,\ cₙ\) \((1\ \leq \ cᵢ\ \leq \ n)\), trong đó \(cᵢ\) là màu của đỉnh thứ \(i\).

+ Mỗi dòng tiếp theo trong số \(n\ - \ 1\) dòng tiếp theo chứa hai số nguyên \(xⱼ\) và \(yⱼ\) \((1\ \leq \ xⱼ,\ yⱼ\ \leq \ n)\), biểu diễn một cạnh của cây (nối đỉnh \(xⱼ\) với \(yⱼ\)).

Kết quả:

In ra \(n\) số nguyên, mỗi số là tổng các màu thống trị trong cây con của từng đỉnh (theo thứ tự từ 1 đến \(n\)).

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Cho một cây có \(n\) đỉnh và \(n\ - \ 1\) cạnh. Mỗi đỉnh i được gán một giá trị nguyên \(c_{i}\).

Yêu cầu: Với mỗi đỉnh \(i\), hãy tính số lượng giá trị khác nhau xuất hiện trong cây con gốc tại đỉnh đó (bao gồm cả chính đỉnh \(i\)).

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq \ n \leq \ 100000\)) — số lượng đỉnh của cây.

• Dòng thứ hai chứa n số nguyên \(c_{1},\ c_{2},\ ...,\ c_{n}\ (1 \leq \ c_{i} \leq \ n\)) — giá trị của từng đỉnh.

• \(n\ - \ 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\) và\(\ v\) \((1 \leq \ u,\ v \leq \ n),\) biểu thị có một cạnh nối giữa đỉnh \(u\) và đỉnh \(v\).

Kết quả:

In ra \(n\) số nguyên, số thứ \(i\) là số lượng giá trị khác nhau trong cây con gốc tại đỉnh \(i.\) Các số cách nhau bởi dấu cách.

Ví dụ:

Bạn cần Đăng nhập để nộp bài