VK Online Round #01 - Thiên tày đất Quảng

Chép code 1

Time limit: 1.0s / Memory limit: 256M

Points: 100

Trong lớp ITK25, ntnhan_itk25 được mọi người kính nể gọi là thủ khoa. Cậu còn sở hữu một "kỹ năng" đặc biệt: bạn bên cạnh vừa gõ xong một dòng code thì trên màn hình của Thành Nhân đã xuất hiện một dòng giống hệt. Đáng tiếc, code được chép sang đầy đủ bao nhiêu thì ý tưởng lại thất lạc bấy nhiêu.

Ở buổi học trước, ntnhan_itk25 đã chép được một đoạn chương trình và vượt qua các bộ dữ liệu nhỏ. Hôm nay, thầy giáo tăng kích thước dữ liệu khiến chương trình chạy mãi không xong. Người bạn từng viết đoạn code lại vắng mặt, còn ntnhan_itk25 thì không nhớ nổi các biến B, p và t dùng để làm gì.

Đoạn code ntnhan_itk25 đã chép nhận một dãy số nguyên ~A~ gồm ~N~ phần tử và thực hiện như sau:

FOR i <- 1 TO N DO
    B[i] <- A[i]
    p <- i

    WHILE p > 1 DO
        IF B[p - 1] <= B[p] THEN
            BREAK
        END IF

        t <- B[p]
        B[p] <- B[p - 1]
        B[p - 1] <- t
        p <- p - 1
    END WHILE

    PRINT B[i] - B[1]
END FOR

Trong đoạn code trên:

Các mảng ~A~ và ~B~ được đánh số từ ~1~. Mảng ~B~ được giữ nguyên giữa các vòng lặp.
<- là phép gán. Các lệnh được thực hiện tuần tự từ trên xuống.
BREAK kết thúc ngay vòng lặp WHILE gần nhất.
PRINT x bổ sung giá trị ~x~ vào cuối dãy kết quả.

Không thể tiếp tục chờ người khác chép lời giải cho mình, ntnhan_itk25 đành nhờ bạn xác định dãy số mà đoạn code trên sẽ in ra.

Dữ liệu vào

Vào từ file văn bản COPYCODE1.INP gồm:

Dòng đầu tiên chứa số nguyên ~N~ (~1 \leq N \leq 2 \cdot 10^5~).
Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~-10^9 \leq A_i \leq 10^9~).

Dữ liệu ra

Ghi ra file văn bản COPYCODE1.OUT kết quả theo yêu cầu sau:

In ra một dòng gồm ~N~ số nguyên, theo đúng thứ tự được các lệnh PRINT tạo ra.

Ví dụ 1

Input

6
3 -5 4 -2 -8 7

Output

0 8 9 9 12 15

Giải thích

Ở vòng lặp đầu tiên, đoạn code gán ~B_1 = 3~ và in ra ~B_1 - B_1 = 0~.

Ở vòng lặp thứ hai, sau khi gán ~B_2 = -5~, đoạn code đổi chỗ hai giá trị ~3~ và ~-5~. Khi đó, ~B_1 = -5~, ~B_2 = 3~ và giá trị tiếp theo được in ra là ~8~. Tiếp tục thực hiện đoạn code thu được toàn bộ dãy kết quả như trên.

Ràng buộc

Subtask 1 (20%): ~N \leq 3000~.
Subtask 2 (80%): Không có ràng buộc nào thêm.

Năm ấy ta đã yêu

Submit

Time limit: 1.0s / Memory limit: 256M

Points: 100

Một ngày được biểu diễn bởi một bộ ba số nguyên gồm ngày, tháng và năm. Hai ngày liên tiếp trên lịch cách nhau đúng một ngày.

Trong bài toán này, lịch Gregory được sử dụng:

Các tháng ~1, 3, 5, 7, 8, 10, 12~ có ~31~ ngày.
Các tháng ~4, 6, 9, 11~ có ~30~ ngày.
Tháng ~2~ có ~28~ ngày trong năm thường và ~29~ ngày trong năm nhuận.
Một năm là năm nhuận nếu năm đó chia hết cho ~400~, hoặc chia hết cho ~4~ nhưng không chia hết cho ~100~.

Cho hai bộ ngày, tháng, năm. Hãy tính số ngày chênh lệch giữa hai mốc thời gian này. Nếu mốc thời gian giống nhau thì kết quả bằng ~0~.

Dữ liệu vào

Vào từ file văn bản DAYCOUNT.INP gồm:

Dòng đầu tiên chứa ba số nguyên ~D_1, M_1, Y_1~, lần lượt là ngày, tháng và năm của mốc thứ nhất (~1 \leq D_1 \leq 31~, ~1 \leq M_1 \leq 12~, ~1 \leq Y_1 \leq 9999~).
Dòng thứ hai chứa ba số nguyên ~D_2, M_2, Y_2~, lần lượt là ngày, tháng và năm của mốc thứ hai (~1 \leq D_2 \leq 31~, ~1 \leq M_2 \leq 12~, ~1 \leq Y_2 \leq 9999~).
Hai mốc thời gian trong dữ liệu đều hợp lệ theo lịch đã mô tả.

Dữ liệu ra

Ghi ra file văn bản DAYCOUNT.OUT kết quả theo yêu cầu sau:

In ra một số nguyên duy nhất là khoảng cách giữa hai mốc thời gian.

Ví dụ 1

Input

31 1 2008
31 7 2008

Output

Giải thích

Năm ~2008~ là năm nhuận. Khoảng cách cần tìm là ~29 + 31 + 30 + 31 + 30 + 31 = 182~ ngày.

Ví dụ 2

Input

26 12 2008
01 10 9002

Output

Giải thích

Khoảng cách giữa hai mốc thời gian đã cho là ~2\,554\,419~ ngày.

Sản xuất theo lô

Submit

Time limit: 1.5s / Memory limit: 1G

Points: 100

Tại Vương quốc VibeKode, kho trung tâm đưa ~N~ sản phẩm lên một dây chuyền theo thứ tự từ ~1~ đến ~N~. Sản phẩm thứ ~i~ mang mã truy xuất nội bộ ~A_i~. Đây là mã cục bộ nên nhiều sản phẩm có thể mang cùng một mã.

Đức vua yêu cầu chia dãy sản phẩm thành đúng ~K~ lô liên tiếp không rỗng. Thứ tự các sản phẩm phải được giữ nguyên và mỗi sản phẩm thuộc đúng một lô.

Trong mỗi lô, hệ thống chỉ phân biệt các sản phẩm qua mã truy xuất. Một sản phẩm được gọi là truy xuất được nếu mã của nó xuất hiện đúng một lần trong lô chứa nó. Nếu một mã xuất hiện từ hai lần trở lên trong cùng một lô thì không sản phẩm nào mang mã đó trong lô được truy xuất.

Hãy chia dãy thành ~K~ lô sao cho tổng số sản phẩm truy xuất được là lớn nhất. Các lần xuất hiện của cùng một mã trong những lô khác nhau được xét độc lập.

Dữ liệu vào

Vào từ file văn bản LOTTRACE.INP gồm:

Dòng đầu tiên chứa hai số nguyên ~N, K~ (~1 \leq K \leq N \leq 2 \cdot 10^5~, ~N \cdot K \leq 10^6~).
Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~1 \leq A_i \leq 10^9~).

Dữ liệu ra

Ghi ra file văn bản LOTTRACE.OUT kết quả theo yêu cầu sau:

In ra số sản phẩm truy xuất được lớn nhất có thể đạt được.

Ví dụ 1

Input

5 2
1 2 1 3 2

Output

Giải thích

Chia dãy thành hai lô ~[1, 2]~ và ~[1, 3, 2]~. Trong mỗi lô, mọi mã đều xuất hiện đúng một lần nên cả ~5~ sản phẩm đều truy xuất được.

Ràng buộc

Subtask 1 (20%): ~K = 1~.
Subtask 2 (20%): ~K = 2~.
Subtask 3 (25%): ~N \leq 1000~, ~K \leq 10~.
Subtask 4 (35%): Không có ràng buộc nào thêm.

Khôi phục tệp

Submit

Time limit: 1.0s / Memory limit: 1G

Points: 100

Trong một lần tham dự kỳ thi CTF (Capture The Flag), Đức gặp một thử thách khôi phục dữ liệu đặc biệt khó. Để tìm được flag, Đức vận dụng những kiến thức giải thuật đã được tôi luyện trong ba năm trung học phổ thông và nhận ra rằng thử thách về bản chất có thể được phát biểu dưới dạng bài toán sau:

Một chương trình lưu trữ cũ của VibeKode biểu diễn mỗi tệp bằng một ma trận gồm ~R~ hàng và ~C~ cột. Mỗi phần tử của ma trận là một chữ cái in hoa trong bảng chữ cái tiếng Anh.

Sau khi các cột bị xáo trộn, tệp được lưu dưới dạng ma trận ~B~. Để đọc lại tệp, chương trình cần một khóa phục hồi gồm ~C~ số nguyên ~s_0, s_1, \ldots, s_{C - 1}~. Các giá trị trong khóa thuộc đoạn từ ~0~ đến ~R - 1~ và đôi một khác nhau.

Nếu thử một khóa ~s~, ma trận được khôi phục ~A~ được xác định bởi:

$$ A[r][c] = B[(r + s_c) \bmod R][c] $$

với mọi ~0 \leq r < R~ và ~0 \leq c < C~. Nói cách khác, khóa ~s_c~ dịch vòng cột thứ ~c~ của ma trận ~B~ một lượng ~s_c~.

Khóa phục hồi đã bị thất lạc. Từ một bản sao lưu, VibeKode biết chính xác ~K~ hàng đầu tiên của tệp gốc. Các hàng này tạo thành ma trận ~P~ gồm ~K~ hàng và ~C~ cột. Tuy nhiên, một số ký tự trong ma trận lưu trữ có thể đã bị hỏng, nên không phải lúc nào toàn bộ tệp cũng có thể được khôi phục đúng.

Một cột ~c~ được xem là khôi phục đúng nếu:

$$ A[r][c] = P[r][c] $$

với mọi ~0 \leq r < K~.

VibeKode cần kiểm tra ~T~ tệp độc lập. Với mỗi tệp, hãy xác định có tồn tại một khóa gồm các giá trị đôi một khác nhau sao cho mọi cột đều được khôi phục đúng hay không.

Dữ liệu vào

Vào từ file văn bản FILESHIFT.INP gồm:

Dòng đầu tiên chứa số nguyên ~T~ (~1 \leq T \leq 20~), là số tệp cần kiểm tra.
Mỗi tệp được mô tả bởi:
- Dòng đầu tiên chứa ba số nguyên ~R, C, K~ (~1 \leq K, C \leq R \leq 2 \cdot 10^5~).
- ~R~ dòng tiếp theo mô tả ma trận ~B~. Mỗi dòng là một xâu gồm đúng ~C~ chữ cái in hoa.
- ~K~ dòng tiếp theo mô tả ma trận ~P~. Mỗi dòng là một xâu gồm đúng ~C~ chữ cái in hoa.
Tổng ~(R + K) \cdot C~ trên tất cả các tệp không vượt quá ~5 \cdot 10^6~.

Dữ liệu ra

Ghi ra file văn bản FILESHIFT.OUT kết quả theo yêu cầu sau:

Với mỗi tệp, in ra YES nếu tồn tại một khóa khôi phục đúng mọi cột; ngược lại, in ra NO.

Ví dụ 1

Input

2
5 3 2
XHD
AZE
BGD
AHE
BGZ
AGD
BHE
3 2 1
XY
AB
ZX
AB

Output

YES
NO

Giải thích

Với tệp thứ nhất, có thể chọn khóa ~(s_0, s_1, s_2) = (1, 2, 0)~. Ba giá trị trong khóa đôi một khác nhau. Hai hàng đầu của ma trận khôi phục khi đó lần lượt là:

AGD
BHE

Do đó, cả ba cột đều được khôi phục đúng và kết quả của tệp này là YES.

Với tệp thứ hai, để khôi phục hàng đầu thành AB, cả hai cột đều buộc phải sử dụng độ dịch ~1~. Do các giá trị trong khóa phải đôi một khác nhau, không thể khôi phục đúng đồng thời cả hai cột. Kết quả của tệp này là NO.

Ràng buộc

Subtask 1 (30%): Trong mỗi tệp, ~K = 1~ và với mỗi cột ~c~, có đúng một giá trị ~s~ thỏa mãn ~B[s][c] = P[0][c]~.
Subtask 2 (20%): Trong mỗi tệp, ~R \leq 100~. Ngoài ra, với mỗi độ dịch ~s~, có nhiều nhất một cột ~c~ sao cho việc chọn ~s_c = s~ sẽ khôi phục đúng cột ~c~.
Subtask 3 (20%): Trong mỗi tệp, với mỗi độ dịch ~s~, có nhiều nhất một cột ~c~ sao cho việc chọn ~s_c = s~ sẽ khôi phục đúng cột ~c~.
Subtask 4 (30%): Không có ràng buộc nào thêm.

Điểm giám sát

Submit

Time limit: 1.0s / Memory limit: 1G

Points: 100

Một hệ thống gồm ~N~ máy chủ được kết nối bởi ~M~ kênh truyền dữ liệu hai chiều. Các máy chủ được đánh số từ ~1~ đến ~N~, mỗi kênh truyền nối trực tiếp hai máy chủ khác nhau.

Một gói tin được gửi từ máy chủ nguồn ~S~ đến một máy chủ ~v~ bằng cách đi qua một số kênh truyền. Do mọi kênh truyền đều có cùng độ trễ, hệ thống luôn lựa chọn một đường đi sử dụng ít kênh truyền nhất. Khi có nhiều đường đi như vậy, hệ thống có thể lựa chọn bất kỳ đường nào.

Để giám sát hệ thống, quản trị viên có thể đặt thiết bị theo dõi tại một máy chủ. Với mỗi máy chủ đích ~v~, máy chủ ~u~ được gọi là điểm giám sát của ~v~ nếu mọi đường đi ngắn nhất từ ~S~ đến ~v~ đều đi qua ~u~.

Hai đầu mút cũng được tính là nằm trên đường đi. Vì vậy, ~S~ và ~v~ luôn là các điểm giám sát của ~v~. Riêng với ~v = S~, đường đi có độ dài bằng ~0~ chỉ chứa máy chủ ~S~.

Với mỗi máy chủ ~v~, hãy xác định số điểm giám sát của ~v~.

Dữ liệu vào

Vào từ file văn bản NETWATCH.INP gồm:

Dòng đầu tiên chứa ba số nguyên ~N, M, S~ (~1 \leq N \leq 2 \cdot 10^5~, ~0 \leq M \leq 2 \cdot 10^5~, ~1 \leq S \leq N~).
Trong ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \leq u, v \leq N~, ~u \neq v~), cho biết có một kênh truyền hai chiều nối trực tiếp hai máy chủ ~u~ và ~v~.
Giữa hai máy chủ có nhiều nhất một kênh truyền trực tiếp.
Dữ liệu bảo đảm có thể truyền dữ liệu từ ~S~ đến mọi máy chủ.

Dữ liệu ra

Ghi ra file văn bản NETWATCH.OUT kết quả theo yêu cầu sau:

In ra ~N~ số nguyên. Số thứ ~v~ là số điểm giám sát của máy chủ ~v~.

Ví dụ 1

Input

Output

1 2 2 2 3 3 3

Giải thích

Có hai đường đi ngắn nhất từ máy chủ ~1~ đến máy chủ ~4~:

$$ 1 \rightarrow 2 \rightarrow 4 $$

và

$$ 1 \rightarrow 3 \rightarrow 4. $$

Chỉ máy chủ ~1~ và máy chủ ~4~ xuất hiện trên cả hai đường đi, nên máy chủ ~4~ có ~2~ điểm giám sát.

Mọi đường đi ngắn nhất từ máy chủ ~1~ đến máy chủ ~7~ đều đi qua các máy chủ ~1, 4, 7~. Vì vậy, máy chủ ~7~ có ~3~ điểm giám sát.

Ràng buộc

Subtask 1 (20%): ~M = N - 1~.
Subtask 2 (25%): ~N, M \leq 2000~.
Subtask 3 (25%): Khoảng cách ngắn nhất từ ~S~ đến mọi máy chủ không vượt quá ~50~.
Subtask 4 (30%): Không có ràng buộc nào thêm.