bnr2_t1

[Ngày 1] Mạng dữ liệu

Nộp bài
Time limit: 2.0 / Memory limit: 1G

Point: 100

Trong một hệ thống giám sát phân tán, có ~N~ trạm được nối với nhau tạo thành một cây.
Các trạm được đánh số từ ~1~ đến ~N~. Giữa mọi cặp trạm luôn tồn tại đúng một đường đi đơn.

Ban đầu, tại trạm ~i~ có ~A[i]~ gói dữ liệu đang chờ xử lý.

Hệ thống diễn ra ~Q~ sự kiện theo thứ tự thời gian. Mỗi sự kiện thuộc một trong hai loại sau:

  • SYNC x: bộ điều phối trung tâm kích hoạt quá trình đồng bộ tại trạm ~x~.
  • CHECK x y: bộ kiểm tra ghi nhận rằng hiện tại trạm ~x~ có đúng ~y~ gói dữ liệu. Bạn phải xác định nhận định đó là đúng hay sai.

Khi xảy ra sự kiện SYNC x, mỗi gói dữ liệu trong hệ thống sẽ di chuyển đúng một cạnh trên đường đi duy nhất từ vị trí hiện tại của nó tới trạm ~x~.
Riêng các gói dữ liệu đã nằm sẵn ở trạm ~x~ thì không di chuyển.

Nói cách khác, sau mỗi lần đồng bộ, mọi gói dữ liệu trong mạng đều tiến thêm đúng một bước về phía trạm được chọn.

Nhiệm vụ

Cho cấu trúc cây, số lượng gói dữ liệu ban đầu tại mỗi trạm và dãy ~Q~ sự kiện, hãy trả lời mọi sự kiện kiểu CHECK.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~.
  • Dòng thứ hai chứa ~N~ số nguyên không âm ~A[1], A[2], \dots, A[N]~, trong đó ~A[i]~ là số gói dữ liệu ban đầu ở trạm ~i~.
  • ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u~ và ~v~, mô tả một cạnh nối hai trạm ~u~ và ~v~.
  • Mỗi trong số ~Q~ dòng tiếp theo mô tả một sự kiện, thuộc một trong hai dạng:
    • SYNC x
    • CHECK x y

Dữ liệu ra

Với mỗi sự kiện kiểu CHECK, in ra một dòng:

  • in Yes nếu nhận định là đúng;
  • ngược lại in No.

Ràng buộc

  • ~1 \le N, Q \le 100000~
  • ~0 \le A[i] \le 10^9~
  • ~1 \le \sum_{i=1}^{N} A[i] \le 10^9~
  • ~1 \le x \le N~ với mọi sự kiện
  • ~0 \le y \le 10^9~ với mọi sự kiện kiểu CHECK

Subtasks

Subtask 1 (10 điểm)
  • ~\sum_{i=1}^{N} A[i] = 6~
Subtask 2 (10 điểm)
  • ~1 \le N, Q \le 1000~
Subtask 3 (10 điểm)
  • Chỉ có nhiều nhất ~30~ trạm ban đầu có ~A[i] > 0~
Subtask 4 (10 điểm)
  • ~A[i] \ge 1~ với mọi ~i~
  • Mọi truy vấn CHECK đều có ~y = 0~
Subtask 5 (15 điểm)
  • Cây là một đường thẳng:

~ 1 - 2 - 3 - \cdots - N ~

Subtask 6 (15 điểm)
  • Mọi sự kiện SYNC đều có ~x = 1~
Subtask 7 (30 điểm)
  • Không có ràng buộc bổ sung

Ví dụ

Sample Input
6 4
1 1 1 2 2 2
1 2
2 3
2 4
4 5
3 6
SYNC 6
SYNC 6
CHECK 6 4
CHECK 6 3
Sample Output
Yes
No

[Ngày 1] Chữ Nôm

Nộp bài
Time limit: 2.0 / Memory limit: 1G

Point: 100

Tải tài liệu bài ở đây: https://drive.google.com/drive/folders/1gPW-SBKagDijmn8BmOEYncaBl0yVNLUZ?usp=sharing

An và Bình sắp làm một bài kiểm tra về từ vựng chữ Nôm.

Hai bạn biết ~N~ chữ Nôm, được đánh số từ ~0~ đến ~N-1~, và ~M~ từ, được đánh số từ ~0~ đến ~M-1~. Từ số ~i~ bắt đầu bằng chữ ~A[i]~, kết thúc bằng chữ ~B[i]~, và mất ~C[i]~ đơn vị thời gian để viết.

  • ~A[i] \ne B[i]~ với mọi ~i~.
  • Mỗi cặp ~(A[i], B[i])~ là duy nhất.

Ta có thể xem mỗi từ như một cạnh có hướng từ ~A[i]~ đến ~B[i]~ với trọng số ~C[i]~.

Trong bài kiểm tra có ~Q~ câu hỏi. Câu hỏi thứ ~j~ yêu cầu:

Hãy viết một chuỗi nối từ bắt đầu từ chữ ~S[j]~ và kết thúc ở chữ ~T[j]~.

Một chuỗi nối từ là một dãy từ sao cho chữ cuối của từ trước trùng với chữ đầu của từ sau. Chuỗi dùng để trả lời câu hỏi ~j~ phải thỏa:

  • từ đầu tiên bắt đầu bằng ~S[j]~,
  • từ cuối cùng kết thúc bằng ~T[j]~,
  • tổng thời gian viết là nhỏ nhất có thể.

Nếu có nhiều đáp án tối ưu thì Bình có thể in ra bất kỳ đáp án nào.

Tình huống

Ngay trước giờ kiểm tra, Bình quên mất thời gian viết của đúng ~K~ từ:

~ U[0], U[1], \dots, U[K-1] ~

Điểm đặc biệt là các từ này đều có cùng chữ bắt đầu:

~ A[U[0]] = A[U[1]] = \cdots = A[U[K-1]] ~

An vẫn nhớ toàn bộ dữ liệu. Trong lúc làm bài, An có thể gửi cho Bình một dãy bit. Mỗi lần An chỉ gửi được đúng một bit 0 hoặc 1.

Bạn cần thiết kế chiến lược để:

  • Bình luôn trả lời đúng tất cả câu hỏi.
  • Số bit An phải gửi là ít nhất có thể.

Nhiệm vụ

Trong bộ chấm của bài này, bạn chỉ nộp một file C++ và cài đặt hai namespace:

namespace An {
    std::vector<int> tap_sequence(
        int N, int M,
        std::vector<int> A, std::vector<int> B, std::vector<long long> C,
        int Q, std::vector<int> S, std::vector<int> T,
        int K, std::vector<int> U
    );
}

namespace Binh {
    std::vector<std::vector<int>> solve(
        int N, int M,
        std::vector<int> A, std::vector<int> B, std::vector<long long> C,
        int Q, std::vector<int> S, std::vector<int> T,
        int K, std::vector<int> U,
        std::vector<int> X
    );
}

Ý nghĩa các hàm

An::tap_sequence

Hàm này đóng vai An.

  • Nhận toàn bộ dữ liệu thật của đề, bao gồm cả mảng thời gian C.
  • Phải trả về một dãy bit X.
  • Mỗi phần tử của X phải là 0 hoặc 1.
  • Độ dài của X không được vượt quá 1000.
Binh::solve

Hàm này đóng vai Bình.

  • Nhận cùng dữ liệu đầu vào như phía An.
  • Tuy nhiên, với mọi chỉ số i thuộc tập {U[0], U[1], ..., U[K-1]}, ta có C[i] = -1.
  • X là dãy bit mà An::tap_sequence đã gửi.

Hàm phải trả về một mảng answers gồm đúng ~Q~ phần tử, trong đó:

  • answers[j] là danh sách chỉ số các từ Bình dùng để trả lời câu hỏi j.
  • answers[j] phải không rỗng.
  • Các từ trong answers[j] phải xuất hiện theo đúng thứ tự viết ra.

Điều kiện đúng

Lời giải được coi là đúng nếu đồng thời thỏa tất cả các điều kiện sau:

  • Dãy X do An::tap_sequence trả về có độ dài không quá 1000.
  • Mọi phần tử của X đều là 0 hoặc 1.
  • Binh::solve trả về đúng ~Q~ câu trả lời.
  • Với mỗi câu hỏi j, dãy answers[j] tạo thành một chuỗi nối từ hợp lệ.
  • Với mỗi câu hỏi j, từ đầu tiên phải bắt đầu bằng S[j] và từ cuối cùng phải kết thúc bằng T[j].
  • Với mỗi câu hỏi j, tổng thời gian viết phải là nhỏ nhất có thể theo dữ liệu thật.

Nếu có nhiều đáp án tối ưu cho một câu hỏi thì trả về đáp án nào cũng được.

Lưu ý chấm

  • Đây là bản đóng gói một file. Về ý tưởng, An::tap_sequence và Binh::solve tương ứng với hai phía giao tiếp độc lập của bài gốc.
  • Không dùng biến toàn cục để truyền trực tiếp thông tin từ namespace An sang namespace Binh. Bình chỉ được suy luận từ dữ liệu đầu vào của mình và dãy bit X.

Bạn sẽ được cung cấp một khung code dạng:

#include <vector>
using namespace std;

namespace An {
    vector<int> tap_sequence(
        int N, int M,
        vector<int> A, vector<int> B, vector<long long> C,
        int Q, vector<int> S, vector<int> T,
        int K, vector<int> U
    ) {
        (void)N; (void)M; (void)A; (void)B; (void)C;
        (void)Q; (void)S; (void)T; (void)K; (void)U;
        return {};
    }
}

namespace Binh {
    vector<vector<int>> solve(
        int N, int M,
        vector<int> A, vector<int> B, vector<long long> C,
        int Q, vector<int> S, vector<int> T,
        int K, vector<int> U,
        vector<int> X
    ) {
        (void)N; (void)M; (void)A; (void)B; (void)C;
        (void)Q; (void)S; (void)T; (void)K; (void)U; (void)X;
        return {};
    }
}

Định dạng input của bộ chấm cục bộ

  • Dòng 1: N M Q K
  • M dòng tiếp theo: A[i] B[i] C[i]
  • Q dòng tiếp theo: S[j] T[j] Z[j]
  • K dòng cuối: U[k]

Trong đó Z[j] là tổng thời gian nhỏ nhất của một đáp án hợp lệ cho câu hỏi j.

Ràng buộc

  • ~2 \le N \le 300~
  • ~1 \le M \le N(N-1)~
  • ~0 \le A[i], B[i] < N~
  • ~A[i] \ne B[i]~
  • ~(A[i], B[i]) \ne (A[j], B[j])~ với mọi ~i \ne j~
  • ~1 \le C[i] \le 10^{16}~
  • ~1 \le Q \le 60~
  • ~0 \le S[j], T[j] < N~
  • ~S[j] \ne T[j]~
  • ~(S[i], T[i]) \ne (S[j], T[j])~ với mọi ~i \ne j~
  • Với mọi câu hỏi, luôn tồn tại ít nhất một chuỗi nối từ từ S[j] đến T[j]
  • ~1 \le K \le 5~
  • ~0 \le U[k] < M~
  • Các giá trị U[k] đôi một khác nhau
  • Các từ Bình quên đều có cùng chữ bắt đầu

Subtasks

Subtask 1 (10 điểm)
  • ~Q \le 10~
  • Với mọi câu hỏi, luôn tồn tại một đáp án dùng không quá ~10~ từ
  • Độ dài dãy bit gửi đi không vượt quá 1000
Subtask 2 (22 điểm)
  • Độ dài dãy bit gửi đi không vượt quá 180
Subtask 3 (8 điểm)
  • Độ dài dãy bit gửi đi không vượt quá 160
Subtask 4 (40 điểm)
  • Độ dài dãy bit gửi đi không vượt quá 90
Subtask 5 (20 điểm)

Gọi ~L~ là độ dài dãy bit gửi đi lớn nhất trên mọi test của subtask này.

  • Nếu ~L \le 64~: được 20 điểm
  • Nếu ~64 < L < 90~: được

~ \left\lfloor \left( \frac{90 - L}{90 - 64} \right)^2 \cdot 20 \right\rfloor ~

điểm

  • Nếu ~L \ge 90~: được 0 điểm

Ví dụ

Sample Input
4 5 3 2
2 1 10
0 2 20
3 1 30
0 1 40
3 0 50
3 0 50
3 1 30
0 1 30
1
3
Giải thích

Bình quên thời gian của hai từ 1 và 3, đều là các từ xuất phát từ chữ 0.

Ba câu hỏi có đáp án tối ưu lần lượt là:

  • 3 -> 0: dùng từ 4, tổng thời gian 50
  • 3 -> 1: dùng từ 2, tổng thời gian 30
  • 0 -> 1: dùng hai từ 1, 0, tổng thời gian 30

Một chiến lược hợp lệ là:

  • An::tap_sequence trả về dãy bit 0, 0, 1, 0
  • Binh::solve trả về:
    • câu 1: 4
    • câu 2: 2
    • câu 3: 1 0

[Ngày 1] Phủ bàn cờ

Nộp bài
Time limit: 10.0 / Memory limit: 1G

Point: 100

Đây là bài toán Output Only. Bạn hãy tải file input tại đây: https://drive.google.com/file/d/1H0HN7ulNHjsx5xlCNWQQ-_o3T_UK5ynL/view

Lưu ý rằng với test thứ ~i~, bạn phải nộp file output có tên là i_1.out. Ví dụ: file output của 1_1.in là 1_1.out.

Mô tả bài toán

Cho một bàn cờ lớn được chia thành ~n \times m~ bàn cờ con. Mỗi bàn cờ con là một bàn cờ vuông ~5 \times 5~, và trong mỗi bàn cờ con có nhiều nhất ~2~ ô đặc biệt.

Ví dụ, nếu ~n = 2, m = 3~ thì bàn cờ lớn gồm ~2~ hàng và ~3~ cột bàn cờ con, tức là toàn bộ bàn cờ có kích thước ~10 \times 15~ ô, với những ô đặc biệt được đánh dấu bằng X.

Bạn có hai loại miếng ghép:

Một loại phủ được lên ~4~ ô, loại còn lại phủ được ~3~ ô.

Mỗi miếng ghép có thể được xoay ~0^\circ~, ~90^\circ~, ~180^\circ~ hoặc ~270^\circ~ trước khi đặt lên bàn cờ.

Nhiệm vụ của bạn là dùng hai loại miếng ghép trên để phủ kín toàn bộ bàn cờ lớn, trừ các ô đặc biệt, sao cho số lượng cặp bàn cờ con cùng dùng chung một miếng ghép là nhỏ nhất có thể.

Cụ thể, nếu có một miếng ghép che các ô nằm trên hai bàn cờ con khác nhau, thì hai bàn cờ con đó được tính là một cặp cùng dùng chung một miếng ghép.

  • Nếu hai bàn cờ con cùng dùng chung nhiều hơn một miếng ghép, thì vẫn chỉ tính là một cặp.
  • Bạn cần tối thiểu hóa số lượng các cặp như vậy.

Ngoài ra, không có hai ô đặc biệt nào kề nhau theo ~8~ hướng. Nói cách khác, với mọi hai ô đặc biệt có tọa độ ~(a, b)~ và ~(c, d)~, ta luôn có:

max(|a - c|, |b - d|) > 1

Dữ liệu vào

Dữ liệu vào có dạng:

n m
a[1][1] a[1][2] ... a[1][5m]
a[2][1] a[2][2] ... a[2][5m]
...
a[5n][1] a[5n][2] ... a[5n][5m]

Trong đó:

  • ~n, m~ là số bàn cờ con theo chiều dọc và chiều ngang.
  • ~a[i][j]~ cho biết ô ở hàng ~i~, cột ~j~ có phải là ô đặc biệt hay không.
  • ~a[i][j]~ chỉ có thể là 0 hoặc -1.
  • 0 nghĩa là ô bình thường, có thể bị che.
  • -1 nghĩa là ô đặc biệt, không được che.

Dữ liệu ra

Bạn cần in ra một cách phủ bàn cờ dưới dạng:

b[1][1] b[1][2] ... b[1][5m]
b[2][1] b[2][2] ... b[2][5m]
...
b[5n][1] b[5n][2] ... b[5n][5m]

Ý nghĩa:

  • Các ô thuộc cùng một miếng ghép phải được gán cùng một số nguyên dương.
  • Hai miếng ghép khác nhau không được dùng cùng một số.
  • Nhãn lớn nhất không được vượt quá ~15000~.
  • Các ô đặc biệt phải giữ nguyên giá trị -1.

Nói cách khác:

  • nếu một ô là ô đặc biệt thì output tại ô đó phải là -1;
  • nếu một ô không đặc biệt thì output tại ô đó phải là mã của đúng một miếng ghép phủ lên ô đó.

Ràng buộc

  • ~1 \le n \times m \le 1600~
  • ~-1 \le a[i][j] \le 0~
  • Mọi giá trị trong input đều là số nguyên
  • Trong mỗi bàn cờ con ~5 \times 5~, số ô đặc biệt không vượt quá ~2~
  • Luôn tồn tại ít nhất một cách phủ kín toàn bộ các ô không đặc biệt
  • Không có hai ô đặc biệt nào kề nhau theo ~8~ hướng

Chấm điểm

Bài có ~10~ test.

Với mỗi test, nếu file output của bạn đúng định dạng và phủ kín được toàn bộ các ô không đặc biệt, bạn nhận được số điểm:

S * max(1/10, 1/sqrt(q - p + 1))

trong đó:

  • ~S~ là trọng số điểm của test đó
  • ~p~ là số cặp bàn cờ con cùng dùng chung miếng ghép trong lời giải tốt nhất
  • ~q~ là số cặp bàn cờ con cùng dùng chung miếng ghép trong lời giải của bạn

Nếu output sai định dạng, hoặc không phủ kín được toàn bộ các ô không đặc biệt, bạn nhận ~0~ điểm.

Các test

Test 1: trọng số ~S = 4~, input 1_1.in, output 1_1.out, ~n = 1, m = 1~
Test 2: trọng số ~S = 4~, input 2_1.in, output 2_1.out, ~n = 1, m = 2~
Test 3: trọng số ~S = 6~, input 3_1.in, output 3_1.out, ~n = 1, m = 3~
Test 4: trọng số ~S = 8~, input 4_1.in, output 4_1.out, ~n = 2, m = 2~
Test 5: trọng số ~S = 10~, input 5_1.in, output 5_1.out, ~n = 10, m = 10~
Test 6: trọng số ~S = 12~, input 6_1.in, output 6_1.out, ~n = 10, m = 10~
Test 7: trọng số ~S = 8~, input 7_1.in, output 7_1.out, ~n = 1, m = 1599~
Test 8: trọng số ~S = 20~, input 8_1.in, output 8_1.out, ~n = 20, m = 24~
Test 9: trọng số ~S = 20~, input 9_1.in, output 9_1.out, ~n = 40, m = 40~
Test 10: trọng số ~S = 8~, input 10_1.in, output 10_1.out, ~n = 39, m = 39~

Ví dụ

Giả sử dữ liệu vào là:

2 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Một output hợp lệ có thể là:

1 1 2 2 3 3 11 12 12 12 12 21 21 21 21
1 -1 2 4 3 13 11 11 14 15 15 15 15 22 22
5 5 6 4 4 13 13 16 14 14 23 23 -1 22 24
5 7 6 6 8 8 17 16 16 18 23 25 25 24 24
9 7 7 10 8 19 17 17 20 18 18 25 26 27 27
9 9 28 10 10 19 19 35 20 20 41 26 26 27 42
29 29 28 28 30 -1 36 35 35 37 41 41 43 42 42
29 31 32 32 30 30 36 36 38 37 37 43 43 44 44
31 31 32 -1 33 33 39 38 38 -1 45 45 45 45 44
34 34 34 34 33 39 39 40 40 40 40 46 46 46 46

Trong ví dụ này, lời giải tốt nhất có số cặp bàn cờ con cùng dùng chung miếng ghép là ~1~, tức là ~p = 1~.

Output ở trên có số cặp bàn cờ con cùng dùng chung miếng ghép là ~7~, tức là ~q = 7~.

Vì vậy, nếu trọng số của test là ~S = 10~, thì output này nhận được số điểm:

10 * max(1/10, 1/sqrt(7 - 1 + 1)) ≈ 3.78