JOI 2018 Final Camp - Ngày 3

Alice sống tại Vương quốc JOI và định mời Bob, người đang sống tại Cộng hòa IOI, đến chơi. Trước đó, cô muốn gửi cho Bob bản đồ đường bay của vương quốc. JOI là quốc đảo gồm \(N\) hòn đảo, đánh số từ \(0\) đến \(N-1\), với \(M\) đường bay hai chiều. Với \(0\le i<M\), đường bay thứ \(i+1\) nối đảo \(A_i\) và đảo \(B_i\). Không có hai đường bay nối cùng một cặp đảo.

Alice phải sử dụng máy điện báo đặc biệt của vương quốc. Máy cho phép gửi một đồ thị vô hướng, nhưng số hiệu các đỉnh và các cạnh sẽ bị xáo trộn ngẫu nhiên. Cụ thể, gọi \(G\) là đồ thị Alice gửi, có \(V\) đỉnh và \(U\) cạnh:

1. Alice chỉ định \(V\) và \(U\), đánh số các đỉnh từ \(0\) đến \(V-1\) và các cạnh từ \(0\) đến \(U-1\).
2. Alice chỉ định hai dãy \(C_0,\ldots,C_{U-1}\) và \(D_0,\ldots,D_{U-1}\). Cạnh số \(j\) nối đỉnh \(C_j\) với đỉnh \(D_j\).
3. Vương quốc tạo một hoán vị \(p[0],\ldots,p[V-1]\) của \(0,\ldots,V-1\) rồi thay mỗi \(C_j\) bằng \(p[C_j]\) và mỗi \(D_j\) bằng \(p[D_j]\).
4. Tiếp đó, vương quốc tạo một hoán vị \(q[0],\ldots,q[U-1]\) của \(0,\ldots,U-1\). Hai dãy được thay đồng thời bằng \(C_{q[0]},\ldots,C_{q[U-1]}\) và \(D_{q[0]},\ldots,D_{q[U-1]}\).
5. Bob nhận \(V\), \(U\) và hai dãy \(C\), \(D\) sau các phép thay thế trên.

Máy chỉ truyền được đơn đồ thị, tức đồ thị không có cạnh song song hoặc khuyên. Nói cách khác, với mọi \(0\le i<j<U\), phải có \((C_i,D_i)\ne(C_j,D_j)\) và \((C_i,D_i)\ne(D_j,C_j)\); đồng thời \(C_i\ne D_i\) với mọi \(0\le i<U\).

Alice muốn truyền bản đồ bằng đồ thị có ít đỉnh nhất. Hãy viết hai chương trình:

• Chương trình thứ nhất nhận \(N\), \(M\), \(A\), \(B\) và xuất thông tin đồ thị \(G\) mà Alice gửi.
• Chương trình thứ hai nhận thông tin đồ thị \(G\) mà Bob nhận được và khôi phục bản đồ đường bay ban đầu, bao gồm số hiệu các đảo.

Chi tiết cài đặt

Trên LQDOJ, bạn nộp một tệp C++ khai báo #include "airline.h" và cài đặt cả hai hàm Alice và Bob dưới đây. Trình chấm chạy hai bản sao tách biệt của chương trình, vì vậy hai hàm không thể trao đổi dữ liệu qua biến toàn cục.

Hàm phía Alice có chữ ký:

void Alice(int N, int M, int A[], int B[]);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. N là số đảo, M là số đường bay; A và B là hai mảng độ dài \(M\) mô tả bản đồ. Hàm Alice dùng các hàm sau để xuất đồ thị:

void InitG(int V, int U);
void MakeG(int pos, int C, int D);

InitG chỉ định số đỉnh và số cạnh của \(G\):

• V phải là số nguyên từ \(1\) đến \(1500\), nếu không nhận Wrong Answer [1].
• U phải là số nguyên từ \(0\) đến \(V(V-1)/2\), nếu không nhận Wrong Answer [2].

MakeG chỉ định cạnh số pos, nối hai đỉnh C và D, với \(V\), \(U\) là các giá trị đã truyền cho InitG:

• pos phải thuộc \([0,U-1]\), nếu không nhận Wrong Answer [3].
• Không được gọi nhiều lần với cùng pos, nếu không nhận Wrong Answer [4].
• C và D phải thuộc \([0,V-1]\) và khác nhau, nếu không nhận Wrong Answer [5].

Trong Alice, phải gọi InitG đúng một lần, sau đó gọi MakeG đúng \(U\) lần:

• Gọi InitG lần thứ hai: Wrong Answer [6].
• Gọi MakeG trước InitG: Wrong Answer [7].
• Khi Alice kết thúc, chưa gọi InitG hoặc số lần gọi MakeG khác \(U\): Wrong Answer [8].
• Khi Alice kết thúc, đồ thị được mô tả không phải đơn đồ thị: Wrong Answer [9].

Nếu lần gọi Alice bị đánh giá sai, chương trình bị kết thúc ngay.

Hàm phía Bob có chữ ký:

void Bob(int V, int U, int C[], int D[]);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. V, U là số đỉnh và số cạnh của đồ thị nhận được; C, D là hai mảng độ dài \(U\) mô tả các cạnh. Hàm Bob dùng các hàm sau để khôi phục và xuất bản đồ:

void InitMap(int N, int M);
void MakeMap(int A, int B);

InitMap chỉ định số đảo và số đường bay đã khôi phục:

• N phải bằng đúng số đảo ban đầu, nếu không nhận Wrong Answer [10].
• M phải bằng đúng số đường bay ban đầu, nếu không nhận Wrong Answer [11].

MakeMap chỉ định một đường bay nối đảo A và đảo B, với \(N\) là giá trị đã truyền cho InitMap:

• A và B phải thuộc \([0,N-1]\) và khác nhau, nếu không nhận Wrong Answer [12].
• Nếu bản đồ ban đầu không có đường bay nối hai đảo này, nhận Wrong Answer [13].
• Không được xuất lại đường bay đã xuất. Khi gọi MakeMap(A,B), nếu đã từng gọi MakeMap(A,B) hoặc MakeMap(B,A), nhận Wrong Answer [14].

Trong Bob, phải gọi InitMap đúng một lần, sau đó gọi MakeMap đúng \(M\) lần:

• Gọi InitMap lần thứ hai: Wrong Answer [15].
• Gọi MakeMap trước InitMap: Wrong Answer [16].
• Khi Bob kết thúc, chưa gọi InitMap hoặc số lần gọi MakeMap khác \(M\): Wrong Answer [17].

Nếu lần gọi Bob bị đánh giá sai, chương trình bị kết thúc ngay.

Quy trình chấm

1. Gọi Alice một lần với các tham số mô tả bản đồ ban đầu.
2. Xáo trộn số hiệu đỉnh và cạnh của đồ thị \(G\) mà Alice chỉ định, rồi gọi Bob một lần với đồ thị thu được.
3. Đánh giá chương trình. Nếu phát hiện câu trả lời sai, chương trình bị kết thúc ngay.

Lưu ý quan trọng

• Bạn có thể cài đặt các hàm nội bộ và dùng biến toàn cục. Tệp nộp được biên dịch cùng trình chấm. Nên đặt các biến toàn cục và hàm nội bộ trong namespace ẩn danh hoặc khai báo static để tránh xung đột tên.
• Khi chấm thật, chương trình chạy thành hai tiến trình riêng cho Alice và Bob. Hai tiến trình không thể dùng chung biến toàn cục.
• Chương trình không được dùng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Có thể ghi thông tin gỡ lỗi ra luồng lỗi chuẩn.

Header airline.h được cung cấp trong phần tệp đính kèm. Trình chấm thật chạy hai vai trò trong hai tiến trình riêng và khác với trình chấm mẫu một tiến trình của đề gốc.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa hai số nguyên \(N\), \(M\), cách nhau bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i+1\) (\(0\le i<M\)) chứa hai số nguyên \(A_i\), \(B_i\), cách nhau bởi dấu cách, mô tả một đường bay.

Dữ liệu ra

Trình chấm mẫu ghi kết quả ra đầu ra chuẩn theo định dạng sau:

• Nếu chương trình bị đánh giá sai, trình chấm mẫu ghi loại lỗi, chẳng hạn Wrong Answer [1], rồi kết thúc.
• Nếu cả hai lần gọi Alice và Bob đều không bị đánh giá sai, trình chấm mẫu ghi Accepted. và còn xuất giá trị \(V\).

Các thông báo không có dấu ngoặc kép. Nếu có nhiều loại lỗi, trình chấm mẫu chỉ thông báo một loại.

Ràng buộc

• \(1\le N\le 1\,000\).
• \(0\le M\le N(N-1)/2\).
• \(0\le A_i,B_i\le N-1\) và \(A_i\ne B_i\) với \(0\le i<M\).
• \((A_i,B_i)\ne(A_j,B_j)\) và \((A_i,B_i)\ne(B_j,A_j)\) với \(0\le i<j<M\).

Phân nhóm

1. \(22\) điểm tối đa: \(N\le 10\)
2. \(15\) điểm tối đa: \(N\le 40\)
3. \(63\) điểm tối đa: Không có

Trong nhóm 1 và nhóm 2, chương trình được toàn bộ điểm của nhóm nếu giải đúng tất cả bộ dữ liệu của nhóm.

Trong nhóm 3, nếu chương trình giải đúng tất cả bộ dữ liệu, gọi \(\mathrm{MaxDiff}\) là giá trị lớn nhất của \(V-N\) trên các bộ dữ liệu của nhóm. Điểm được tính như sau:

Ở đây, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ giao tiếp

4 3
0 1
0 2
0 3

Các lời gọi diễn ra theo thứ tự sau. Tất cả các hàm trong bảng đều không trả về giá trị.

Các tham số mà trình chấm truyền vào hai hàm là:

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

Nguồn

JOI 2017/2018 Spring Training Camp, Contest Day 3, đề tiếng Anh chính thức và đề tiếng Nhật chính thức.

Có \(N\) thị trấn của hải ly, được đánh số từ \(1\) đến \(N\) theo thứ tự độ cao giảm dần. Không có hai thị trấn nào có cùng độ cao. Có \(M\) con kênh một chiều nối các cặp thị trấn khác nhau. Con kênh thứ \(i\) chảy từ thị trấn \(S_i\) đến thị trấn \(E_i\). Các con kênh đều chảy từ thị trấn cao xuống thị trấn thấp; không thể di chuyển ngược dòng.

Hải ly Bitaro có \(N\) người bạn, mỗi thị trấn có đúng một người bạn sinh sống. Bitaro dự định tổ chức \(Q\) bữa tiệc và mời bạn bè đến dự. Với bữa tiệc thứ \(j\), có \(Y_j\) người bạn bận nên không thể tham dự. Bữa tiệc này được tổ chức tại thị trấn \(T_j\); những người không thể đi từ thị trấn của mình đến \(T_j\) chỉ bằng các con kênh cũng không thể tham dự. Tất cả những người bạn còn lại đều đến dự tiệc.

Mỗi người đến địa điểm tổ chức tiệc bằng các con kênh. Có thể có nhiều đường đi, nhưng vì các bạn của Bitaro rất thích kênh nên họ luôn chọn một đường đi đi qua nhiều con kênh nhất.

Với mỗi bữa tiệc, hãy tính số con kênh mà người đi qua nhiều kênh nhất trong số những người tham dự đã sử dụng. Nếu không có ai tham dự, hãy trả lời \(-1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N, M, Q\): số thị trấn, số con kênh và số bữa tiệc.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i, E_i\), mô tả một con kênh một chiều từ \(S_i\) đến \(E_i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(T_j, Y_j\), sau đó là \(Y_j\) số nguyên \(C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}\). Bữa tiệc thứ \(j\) được tổ chức tại \(T_j\); những người bạn sống ở các thị trấn \(C_{j,1}, \ldots, C_{j,Y_j}\) đều bận.

Các số trên cùng một dòng được phân cách bằng dấu cách.

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa số con kênh lớn nhất mà một người tham dự bữa tiệc thứ \(j\) đi qua. Nếu không có ai tham dự bữa tiệc này, in \(-1\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(0 \le M \le 200\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le S_i < E_i \le N\) với \(1 \le i \le M\).
• \((S_i,E_i) \ne (S_j,E_j)\) với \(1 \le i < j \le M\).
• \(1 \le T_j \le N\) với \(1 \le j \le Q\).
• \(0 \le Y_j \le N\) với \(1 \le j \le Q\).
• \(1 \le C_{j,1} < C_{j,2} < \cdots < C_{j,Y_j} \le N\) với \(1 \le j \le Q\).
• \(Y_1+Y_2+\cdots+Y_Q \le 100\,000\).

Phân nhóm

1. \(7\) điểm: \(N \le 1000\), \(M \le 2000\), \(Q=1\).
2. \(7\) điểm: \(Q=1\).
3. \(86\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

1
3
0

12 17 10
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12
3 7 1 2 3 4 5 6 7
11 3 1 3 5
9 2 1 9
8 4 1 2 3 4
1 1 1
12 0
10 3 1 6 10
11 8 2 3 5 6 7 9 10 11
8 7 2 3 4 5 6 7 8

1
-1
3
1
3
-1
5
2
4
4

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 3: Bitaro's Party.

Công ty Just Odd Inventions, gọi tắt là công ty JOI, chuyên tạo ra những phát minh kỳ lạ. Để ngăn thông tin mật bị rò rỉ, công ty lắp một cổng an ninh tại cửa ra vào. Mọi người đều phải đi qua cổng khi vào hoặc ra khỏi công ty, và không thể có từ hai người trở lên đi qua cổng cùng một lúc.

Mỗi khi một người đi qua, cổng ghi lại người đó đang vào hay ra. IOI-kun, một nhân viên của JOI, có bản ghi của cổng trong một ngày, được biểu diễn bằng xâu \(S\). Nếu ký tự thứ \(i\) của \(S\) là (, người thứ \(i\) đi qua cổng đã vào công ty; nếu ký tự đó là ), người ấy đã ra khỏi công ty. IOI-kun biết rằng lúc bắt đầu và kết thúc ngày hôm đó, trong công ty đều không có ai.

Không phải mọi xâu chỉ gồm ( và ) đều có thể là bản ghi hợp lệ. Chẳng hạn, ())( không hợp lệ vì có lúc số người trong công ty sẽ âm; (() không hợp lệ vì cuối ngày vẫn còn người trong công ty.

Ngay sau khi IOI-kun kiểm tra bản ghi, một vi-rút máy tính trong công ty đã sửa đổi xâu \(S\)! Sau khi điều tra, anh cho rằng vi-rút đã thực hiện hai bước sau:

1. Chọn một đoạn liên tiếp trong \(S\) và đảo từng ký tự trong đoạn: ( thành ), còn ) thành (. Gọi xâu thu được là \(S'\). Đoạn được chọn có thể có độ dài \(0\), tức là có thể có \(S'=S\).
2. Thay không hoặc nhiều ký tự trong \(S'\) thành x. Gọi xâu thu được là \(S''\).

IOI-kun không nhớ \(S\) và muốn khôi phục nó từ \(S''\). Trước hết, anh muốn đếm số xâu có thể là \(S'\), không phải \(S\).

Cho \(S''\), hãy tính số xâu khác nhau có thể là \(S'\), lấy phần dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), là độ dài của xâu \(S''\).
• Dòng thứ hai chứa xâu \(S''\) có độ dài \(N\), chỉ gồm các ký tự (, ) và x.

Dữ liệu ra

In một dòng chứa số xâu có thể là \(S'\), lấy phần dư khi chia cho \(1\,000\,000\,007\). Nếu không có xâu nào thỏa mãn, in \(0\).

Ràng buộc

• \(1 \le N \le 300\).

Phân nhóm

1. \(4\) điểm: \(N \le 100\); số ký tự x trong \(S''\) không quá \(4\).
2. \(8\) điểm: \(N \le 100\); số ký tự x trong \(S''\) không quá \(12\).
3. \(18\) điểm: \(N \le 100\); số ký tự x trong \(S''\) không quá \(20\).
4. \(43\) điểm: \(N \le 100\).
5. \(27\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4
x))x

3

10
xx(xx()x(x

45

5
x))x(

0

10
xxxxxxxxxx

684

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 3: Security Gate.