Google Code Jam 2010 - World Finals

Việc sở hữu một cửa hàng kẹo thật khó khăn! Bạn phải tối ưu hóa đủ mọi thứ. Gần đây, bạn đang bán một loại kẹo rất phổ biến gọi là Whizboppers. Những loại kẹo này rất nhanh hỏng, dẫn đến các đặc điểm sau:

• Bạn phải mua Whizboppers mới từ nhà cung cấp vào mỗi sáng.
• Bạn phải bán Whizboppers trong chính các hộp mà bạn đã mua từ nhà cung cấp sáng hôm đó.

Bạn có thể đặt hàng Whizboppers từ nhà cung cấp theo các hộp chứa bất kỳ số nguyên gam kẹo nào.

Mỗi ngày có tối đa \(k\) người đến cửa hàng của bạn, và bắt đầu từ người đầu tiên, họ sẽ chọn một số nguyên xu để chi cho Whizboppers: trong khoảng từ 1 đến \(C\) xu (bao gồm cả hai đầu). Bạn sẽ bán Whizboppers với giá 1 xu mỗi gam; vì vậy nếu một người muốn chi 4 xu, bạn sẽ đưa cho người đó đúng 4 gam kẹo. Bạn có thể thực hiện việc này bằng cách đưa cho họ một hộp 4 gam, hoặc có thể là một hộp 2 gam và hai hộp 1 gam.

Số lượng hộp tối thiểu bạn cần đặt hàng là bao nhiêu để bất kể mỗi người đặt mua bao nhiêu, bạn luôn có thể đưa cho tất cả mọi người khối lượng Whizboppers mà họ muốn?

Lưu ý: Khi một người chọn mua bao nhiêu kẹo, bạn biết những người khác đã mua gì trước đó, nhưng bạn không biết những người tiếp theo sẽ mua gì.

Ví dụ, nếu có tối đa 2 người đến cửa hàng mỗi ngày và mỗi người chi tối đa 2 xu (\(k=2, C=2\)), bạn có thể mua bốn hộp 1 gam từ nhà cung cấp. Nhưng bạn có thể làm tốt hơn: nếu bạn mua hai hộp 1 gam và một hộp 2 gam, bạn có thể làm hài lòng khách hàng của mình. Đây là cách thực hiện:

First Person   Boxes given   Second Person   Boxes given
--------------------------------------------------------
  2 cents      1 x 2-gram      2 cents       2 x 1-gram
                               1 cent        1 x 1-gram
  -----------------------------------------------------
  1 cent       1 x 1-gram      2 cents       1 x 2-gram
                               1 cent        1 x 1-gram

Bất kể người đầu tiên đặt hàng bao nhiêu, bạn có thể đưa ra các hộp sao cho người thứ hai vẫn có thể nhận được đúng lượng kẹo cần thiết. Vì vậy, với \(k=2, C=2\), bạn có thể phục vụ bất kỳ chuỗi đơn hàng nào với 3 hộp.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên: \(k\) và \(C\), số lượng người tối đa và số xu tối đa mỗi người có thể chi tiêu.

Dữ liệu ra

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

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset (Test set 1): \(1 \le k \le 20, 1 \le C \le 3\).
• Large dataset (Test set 2): \(1 \le k \le 1000, 1 \le C \le 10^{12}\).

Đ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ụ

4
1 5
2 2
10 3
2 50

Case #1: 3
Case #2: 3
Case #3: 19
Case #4: 11

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Candy Store.

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

Vào mùa hè, các thành phố cổ ở Châu Âu nườm nượp khách du lịch đi dạo trên các con phố và tham quan các địa điểm nổi tiếng.

Nhiều thành phố cổ được xây dựng một cách tự nhiên chứ không theo một kế hoạch kiến trúc nào, nhưng kỳ lạ thay, sự phát triển của chúng lại thể hiện một quy luật tương tự: các thành phố bắt đầu từ ba địa điểm tham quan ban đầu, với mỗi cặp địa điểm được kết nối bởi một con phố hai chiều; sau đó, dần dần, các địa điểm tham quan mới được thêm vào. Bất kỳ địa điểm tham quan mới nào cũng được kết nối bằng hai con phố hai chiều mới với hai địa điểm tham quan khác nhau đã có trước đó và hai địa điểm này vốn đã được kết nối trực tiếp bởi một con phố.

Một du khách đến thăm thành phố như vậy muốn thực hiện một chuyến tham quan đi qua càng nhiều địa điểm tham quan càng tốt. Chuyến tham quan có thể bắt đầu tại bất kỳ địa điểm nào và phải kết thúc tại chính địa điểm đó. Chuyến tham quan có thể đi qua mỗi con phố tối đa một lần và mỗi địa điểm tham quan tối đa một lần (ngoại trừ địa điểm xuất phát được đi qua đúng hai lần).

Bạn được cho mô tả về cách thành phố đã phát triển. Hãy tìm số lượng địa điểm tham quan khác nhau lớn nhất mà một chuyến tham quan có thể đi qua trong thành phố này.

Dữ liệu vào

Dòng đầu tiên của tệp dữ liệu vào chứa số lượng bộ test, T. Tiếp theo là T bộ test.

Mỗi bộ test bắt đầu bằng số nguyên N - tổng số địa điểm tham quan trong thành phố. Các địa điểm được ký hiệu bằng các số từ 1 đến N; các số 1, 2 và 3 ký hiệu cho ba địa điểm ban đầu khi thành phố bắt đầu hình thành, trong khi các số 4, ..., N ký hiệu cho các địa điểm khác theo thứ tự chúng được thêm vào thành phố.

N-3 dòng tiếp theo, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách A, B, cho biết địa điểm tham quan tương ứng được kết nối bằng các con phố tới các địa điểm A và B. Dòng đầu tiên trong số này tương ứng với địa điểm số 4, dòng thứ hai tương ứng với địa điểm số 5, v.v.

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 địa điểm tham quan lớn nhất mà một chuyến tham quan có thể thực hiện trong thành phố này.

Ràng buộc

• 1 ≤ T ≤ 50.

Phân nhóm

• Small dataset (Test set 1 - Visible): 4 ≤ N ≤ 15.
• Large dataset (Test set 2 - Hidden): 4 ≤ N ≤ 1000.

Đ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
1 2
2 1
6
1 2
1 4
4 5

Case #1: 4
Case #2: 6

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài City Tour.

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

Roland là một giáo viên toán trung học. Mỗi ngày, ông nhận được hàng trăm bài kiểm tra từ học sinh của mình. Với mỗi bài, ông cẩn thận chọn một điểm chữ cái: 'A', 'B' hoặc 'C'. (Học sinh của Roland quá thông minh để nhận các điểm thấp hơn như 'D' hay 'F'). Sau khi các điểm số đã được quyết định, Roland chuyển các bài kiểm tra cho trợ lý của mình - chính là bạn. Công việc của bạn là đóng dấu điểm số chính xác lên mỗi tờ giấy.

Bạn có một con dấu chữ cái công nghệ thấp nhưng vẫn hoạt động tốt. Để in một chữ cái, bạn gắn một tấm khuôn đặc biệt tương ứng với chữ cái đó vào mặt trước của con dấu, nhúng nó vào mực, rồi đóng lên giấy.

Điều thú vị là thay vì tháo tấm khuôn ra khi bạn muốn đổi chữ cái, bạn có thể chỉ cần đặt một tấm khuôn mới lên trên tấm khuôn cũ. Thực tế, bạn có thể coi các tấm khuôn trên con dấu như một ngăn xếp (stack), hỗ trợ các thao tác sau:

• Push một chữ cái vào đỉnh ngăn xếp. (Tương ứng với việc gắn một tấm khuôn mới vào mặt trước con dấu.)
• Pop một chữ cái khỏi đỉnh ngăn xếp. (Tương ứng với việc tháo tấm khuôn ở mặt trước con dấu.)
• Print chữ cái ở đỉnh ngăn xếp. (Tương ứng với việc thực sự sử dụng con dấu.) Tất nhiên, ngăn xếp phải có ít nhất một chữ cái để thực hiện việc này.

Cho một chuỗi các điểm chữ cái ('A', 'B', và 'C'), bạn cần bao nhiêu thao tác để in toàn bộ chuỗi theo đúng thứ tự? Ngăn xếp ban đầu trống, và bạn phải để ngăn xếp trống khi hoàn thành. Tuy nhiên, bạn có nguồn cung cấp không giới hạn cho mỗi loại khuôn chữ cái để sử dụng trong quá trình thực hiện.

Ví dụ, nếu bạn muốn in chuỗi "ABCCBA", bạn có thể thực hiện trong 12 thao tác như bảng dưới đây:

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test, T. T bộ test tiếp theo, mỗi bộ trên một dòng. Mỗi dòng chứa một chuỗi duy nhất S, đại diện cho chuỗi các ký tự mà bạn muốn in ra theo thứ tự.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: N", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và N là số lượng thao tác ngăn xếp tối thiểu cần thiết để in ra S.

Ràng buộc

• S là một chuỗi không rỗng chỉ chứa các chữ cái 'A', 'B', và 'C'.

Phân nhóm

• Small dataset (Test set 1 - Visible):
  • 1 ≤ T ≤ 100.
  • S có tối đa 100 ký tự.
• Large dataset (Test set 2 - Hidden):
  • 1 ≤ T ≤ 20.
  • S có tối đa 7000 ký tự.

Đ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
ABCCBA
AAABAAB

Case #1: 12
Case #2: 13

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Letter Stamper.

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

Ninjutsu là võ thuật của các ninja bí ẩn. Bài tập đầu tiên của bạn là làm chủ móc dây: một chiếc móc gắn vào sợi dây rất bền, rất mảnh. Móc đã bám vào mục tiêu tại \((0,0)\); dây kéo dài sang trái và bạn ở đầu còn lại. Khi nhảy, bạn đu ngược chiều kim đồng hồ quanh mục tiêu.

Các mục tiêu khác nằm bên phải và phía trên \((0,0)\), tại \((x_i,y_i)\) với \(x_i,y_i\ge0\). Khi một điểm trong lòng dây (không phải hai đầu) chạm một hay nhiều mục tiêu, dây uốn quanh mục tiêu gần đầu đang chuyển động nhất. Bỏ qua vận tốc ban đầu: bạn đủ nhanh để tiếp tục uốn quanh các mục tiêu cho tới khi quay quanh đúng một mục tiêu.

Dây dài \(R\), nhưng trước khi đu bạn có thể cắt còn bất kỳ độ dài thực \(r\le R\). Bạn bắt đầu tại \((-r,0)\) và đu xuống (ngược chiều kim đồng hồ) hướng tới \((0,-r)\). Hỏi trong một lần đu, số khúc uốn lớn nhất là bao nhiêu? Một khúc uốn được tính khi dây chạm mục tiêu rồi quay quanh đó một góc khác 0. Ngoài các khúc uốn, dây luôn thẳng.

Ví dụ có sáu điểm \((0,0),(3,1),(12,4),(14,5),(13,7),(7,10)\) và dây dài 24. Không cắt dây, nó uốn quanh \((12,4),(14,5),(13,7)\) rồi quay quanh \((7,10)\), còn khoảng 0.1705 dây: tổng 4 khúc. Điểm \((3,1)\) không tính vì thẳng hàng với \((0,0),(12,4)\).

Cắt 0.18 đơn vị khiến dây không tới \((7,10)\) mà đi theo:

(0, 0)--(12, 4)--(14, 5)--(13, 7)--(12, 4)--(14, 5)

Nó kết thúc quanh \((14,5)\) với khoảng 1.3004 dây, tổng 5 khúc, là tối ưu.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(N,R\), sau đó là \(N\) cặp số nguyên \(x_i,y_i\), bắt đầu bằng mục tiêu \((0,0)\).

Dữ liệu ra

In Case #C: k, với \(k\) là số khúc uốn tối đa.

Ràng buộc

• \(1\le T\le100\); tọa độ nguyên, các mục tiêu khác nhau, điểm đầu là \((0,0)\).
• Tồn tại một độ dài tối ưu \(r\) sao cho \(r-0.999999\) vẫn cho cùng chuỗi uốn.
• Thời gian 60 giây mỗi bộ; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(1\le N\le10\), \(1\le R\le1000\), \(0\le x_i,y_i\le1000\).
• Lớn: \(1\le N\le1000\), \(1\le R\le10^9\), \(0\le x_i,y_i\le10^9\).

Đ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ụ

6
6 24
0 0
3 1
12 4
14 5
13 7
7 10
2 1
0 0
2 0
2 1
0 0
1 0
2 10
0 0
4 0
3 50
0 0
9 0
10 0
3 12
0 0
3 0
3 4

Case #1: 5
Case #2: 0
Case #3: 0
Case #4: 2
Case #5: 12
Case #6: 3

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Ninjutsu.

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

Cho một lưới hình chữ nhật gồm \(N\) hàng và \(M\) cột, mỗi ô có thể được gắn nhãn đen (Âm) hoặc trắng (Dương). Hai ô là láng giềng nếu chúng chung nhau một đoạn cạnh đơn vị. Lưới được gọi là hợp lệ nếu tất cả các ô đen tạo thành một đường đi, và tất cả các ô trắng tạo thành một đường đi. Một đường đi là một tập hợp \(S\) các ô được định nghĩa như sau:

• Các ô tạo thành một phần kết nối. Từ mỗi ô trong \(S\), bạn có thể đến bất kỳ ô nào khác trong \(S\) bằng cách di chuyển giữa các ô láng giềng trong \(S\).
• Có đúng hai ô trong \(S\) có đúng một láng giềng trong \(S\). Đây là hai "đầu mút" của đường đi.
• Mọi ô khác trong \(S\) có đúng hai láng giềng trong \(S\).

Ví dụ, trong hình dưới đây, lưới đầu tiên là hợp lệ, trong khi lưới thứ hai thì không -- mặc dù các ô đen tạo thành một đường đi, nhưng các ô trắng thì không.

Cho \(N\) và \(M\), hãy tính số lượng lưới hợp lệ. Lưu ý rằng tính đối xứng không quan trọng -- miễn là hai lưới hợp lệ khác nhau ở một vị trí thì chúng được coi là khác nhau, ngay cả khi lưới này có thể được xoay hoặc lật để trở thành lưới kia.

Dữ liệu vào

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

Dữ liệu ra

Với mỗi bộ test, xuất một dòng có dạng "Case #\(x\): \(A\)", trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(A\) là số lượng lưới hợp lệ có kích thước đã cho.

Ràng buộc

• \(1 \le T \le 50\)

Phân nhóm

• Test set 1 (Visible): \(4 \le N, M \le 10\).
• Test set 2 (Hidden):
  • Trong 80% số bộ test, \(4 \le N, M \le 50\).
  • Trong 90% số bộ test, \(4 \le N, M \le 70\).
  • Trong tất cả các bộ test, \(4 \le N, 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
4 4
4 6
5 5

Case #1: 24
Case #2: 44
Case #3: 48

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài The Paths of Yin Yang.

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

Trong một khám phá mới của các nhà thiên văn học Nam Cực, người ta ghi lại rằng có \(N\) hành tinh có sự sống trong không gian, tất cả đều nằm trên cùng một đường thẳng. Hành tinh thứ \(i\) nằm ở tọa độ \(X_i\) trên đường thẳng đó (\(i = 1, 2, \dots, N\)). Trái Đất là hành tinh đầu tiên, nằm ở tọa độ \(0\), vì vậy \(X_1\) sẽ luôn bằng \(0\).

Rất hào hứng với sự thật này, bạn bắt đầu lập kế hoạch cho một chuyến đi để thăm tất cả các hành tinh. Vì các hành tinh lạ có thể nguy hiểm, bạn muốn ghé thăm mỗi hành tinh đúng một lần trước khi quay trở lại Trái Đất. Bạn có \(F\) đơn vị nhiên liệu và bạn muốn tiêu tốn càng nhiều nhiên liệu càng tốt cho chuyến đi này để lần hạ cánh cuối cùng xuống Trái Đất được an toàn hơn. Con tàu vũ trụ của bạn khá cơ bản và chỉ có thể bay theo một đường thẳng từ bất kỳ hành tinh \(i\) nào đến bất kỳ hành tinh \(j\) nào khác, tiêu tốn \(|X_i - X_j|\) đơn vị nhiên liệu trên đường đi. Nó không thể quay đầu mà không hạ cánh.

Vì vậy, bạn cần lập một kế hoạch du hành yêu cầu tối đa \(F\) đơn vị nhiên liệu, bắt đầu từ Trái Đất, ghé thăm mỗi hành tinh khác đúng một lần, và sau đó quay trở lại Trái Đất. Nếu có nhiều kế hoạch như vậy, bạn nên tìm kế hoạch tiêu tốn nhiều nhiên liệu nhất. Hãy xuất ra lượng nhiên liệu tiêu thụ đó.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa số lượng hành tinh \(N\). Dòng tiếp theo chứa \(N\) số \(X_i\), tọa độ của các hành tinh. Dòng tiếp theo chứa lượng nhiên liệu \(F\) mà bạn có.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra một dòng chứa "Case #x: NO SOLUTION" nếu không có kế hoạch du hành nào như vậy, hoặc "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là lượng nhiên liệu tiêu thụ tối đa.

Ràng buộc

• \(1 \le F \le 10^{17}\).
• \(-10^{15} \le X_i \le 10^{15}\).
• \(X_1 = 0\).
• Tất cả các \(X_i\) đều khác nhau.

Phân nhóm

• Small dataset (Tập kiểm thử 1 - Hiển thị): \(1 \le T \le 100\); \(2 \le N \le 10\).
• Large dataset (Tập kiểm thử 2 - Ẩn): \(1 \le T \le 20\); \(2 \le N \le 30\).

Đ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
3
0 10 -10
40
5
0 1 2 3 4
13
5
0 1 2 3 4
7

Case #1: 40
Case #2: 12
Case #3: NO SOLUTION

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Travel Plan.

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