Google Code Jam 2010 - Round 1B

Trên các máy tính Unix, dữ liệu được lưu trữ trong các thư mục (directories). Có một thư mục gốc (root directory), và thư mục này có thể chứa nhiều thư mục con bên trong, mỗi thư mục có tên khác nhau. Các thư mục này lại có thể chứa thêm nhiều thư mục khác nữa, và cứ tiếp tục như vậy.

Một thư mục được xác định duy nhất bởi tên của nó và thư mục cha (thư mục trực tiếp chứa nó). Điều này thường được mã hóa trong một đường dẫn (path), bao gồm nhiều phần, mỗi phần được bắt đầu bằng một dấu gạch chéo ('/'). Phần cuối cùng là tên của thư mục, và tất cả các phần còn lại tạo nên đường dẫn của thư mục cha. Ví dụ, xét đường dẫn:

/home/gcj/finals

Đường dẫn này tham chiếu đến thư mục có tên "finals" nằm trong thư mục được mô tả bởi "/home/gcj", thư mục này lại tham chiếu đến thư mục có tên "gcj" trong thư mục được mô tả bởi đường dẫn "/home". Trong đường dẫn "/home", chỉ có một phần, nghĩa là nó tham chiếu đến thư mục có tên "home" trong thư mục gốc.

Để tạo một thư mục, bạn có thể sử dụng lệnh mkdir. Bạn chỉ định một đường dẫn, và sau đó mkdir sẽ tạo thư mục được mô tả bởi đường dẫn đó, nhưng chỉ khi thư mục cha của nó đã tồn tại. Ví dụ, nếu bạn muốn tạo các thư mục "/home/gcj/finals" và "/home/gcj/quals" từ đầu, bạn sẽ cần bốn lệnh:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Cho tập hợp đầy đủ các thư mục đã tồn tại trên máy tính của bạn và một tập hợp các thư mục mới mà bạn muốn tạo (nếu chúng chưa tồn tại), bạn cần sử dụng bao nhiêu lệnh mkdir?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một khoảng trắng.

\(N\) dòng tiếp theo, mỗi dòng cho biết đường dẫn của một thư mục đã tồn tại trên máy tính của bạn. Danh sách này sẽ bao gồm mọi thư mục đã có trên máy tính ngoại trừ thư mục gốc. (Thư mục gốc có trên mọi máy tính, vì vậy không cần liệt kê rõ ràng.)

\(M\) dòng tiếp theo, mỗi dòng cho biết đường dẫn của một thư mục mà bạn muốn tạo.

Mỗi đường dẫn trong dữ liệu vào được định dạng như mô tả trong đề bài ở trên. Cụ thể, một đường dẫn bao gồm một hoặc nhiều chuỗi ký tự chữ-số thường (tức là các chuỗi chỉ chứa các ký hiệu 'a'-'z' và '0'-'9'), mỗi chuỗi được bắt đầu bởi một dấu gạch chéo duy nhất. Các chuỗi chữ-số này không bao giờ để trống.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng lệnh mkdir bạn cần sử dụng.

Ràng buộc

• \(1 \le T \le 100\).
• Không có đường dẫn nào dài quá 100 ký tự.
• Không có đường dẫn nào xuất hiện hai lần trong danh sách các thư mục đã có, hoặc trong danh sách các thư mục muốn tạo. Tuy nhiên, một đường dẫn có thể xuất hiện một lần trong cả hai danh sách (Xem ví dụ 2 bên dưới).
• Nếu một thư mục được liệt kê là đã có trên máy tính, thì thư mục cha của nó cũng sẽ được liệt kê, trừ khi cha là thư mục gốc.
• Tệp dữ liệu vào sẽ không dài quá 100,000 bytes tổng cộng.

Phân nhóm

• Small dataset (Test set 1): \(0 \le N \le 10, 1 \le M \le 10\).
• Large dataset (Test set 2): \(0 \le N \le 100, 1 \le M \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
0 2
/home/gcj/finals
/home/gcj/quals
2 1
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b

Case #1: 4
Case #2: 0
Case #3: 4

Nguồn

Google Code Jam 2010, Vòng 1B, bài File Fix-it.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Một đàn gà con chạy về phía đông trên đường thẳng hẹp, mỗi con có vận tốc không đổi. Khi bắt kịp con trước, nó phải chậm lại theo vận tốc con đó. Bạn lái cần cẩu phía sau; có thể nhấc tạm một con để con ngay sau vượt qua rồi đặt lại. Thao tác tức thời, chỉ áp dụng cho hai con kề nhau; dù nhiều con cùng vị trí, mỗi lần đổi chỗ chỉ cho một con vượt.

Biết vị trí đầu \(X_i\), vận tốc tự nhiên \(V_i\), vị trí chuồng \(B\) và hạn \(T\), hãy tìm số lần đổi chỗ ít nhất để ít nhất \(K\) trong \(N\) con tới chuồng không muộn hơn \(T\).

Dữ liệu vào

Dòng đầu là \(C\). Mỗi test gồm \(N,K,B,T\); dòng sau là \(N\) vị trí \(X_i\) tăng nghiêm ngặt; dòng cuối là \(N\) vận tốc \(V_i\). Đơn vị lần lượt là mét, mét/giây và giây.

Dữ liệu ra

In Case #x: S, với \(S\) nhỏ nhất, hoặc IMPOSSIBLE.

Ràng buộc

• \(1\le C\le100\), \(1\le B\le10^9\), \(1\le T\le1000\).
• \(0\le X_i<B\), \(1\le V_i\le100\); các \(X_i\) khác nhau và tăng.
• Thời gian 30 giây mỗi bộ; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(1\le N\le10\), \(0\le K\le\min(3,N)\).
• Lớn: \(1\le N\le50\), \(0\le K\le N\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
5 3 10 5
0 2 5 6 7
1 1 1 1 4
5 3 10 5
0 2 3 5 7
2 1 1 1 4
5 3 10 5
0 2 3 4 7
2 1 1 1 4

Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2010, Vòng 1B, bài Picking Up Chicks.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Trò chơi này có thể chơi trên bất kỳ tập con \(S\) nào của các số nguyên dương. Một số trong \(S\) được coi là thuần khiết (pure) đối với \(S\) nếu, bắt đầu từ nó, bạn có thể liên tiếp lấy thứ hạng (rank) của nó trong \(S\), và nhận được một số cũng nằm trong \(S\), cho đến khi sau một số bước hữu hạn, bạn chạm đến số 1, số này không nằm trong \(S\).

Khi cho trước \(n\), có bao nhiêu cách để bạn chọn \(S\), một tập con của \(\{2, 3, \dots, n\}\), sao cho \(n\) là thuần khiết đối với \(S\)? Câu trả lời có thể là một số rất lớn, bạn cần đưa ra kết quả theo modulo 100003.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên duy nhất \(n\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là câu trả lời như mô tả ở trên.

Ràng buộc

• \(T \le 100\).

Phân nhóm

• Small dataset (Test set 1): \(2 \le n \le 25\).
• Large dataset (Test set 2): \(2 \le n \le 500\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5
6

Case #1: 5
Case #2: 8

Nguồn

Google Code Jam 2010, Vòng 1B, bài Your Rank is Pure.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.