Google Code Jam 2008 - Mixing Bowls

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1800 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bạn đang làm theo một công thức để chuẩn bị bữa trưa của mình.

Công thức là một hỗn hợp được tạo ra bằng cách kết hợp các thành phần lại với nhau trong một chiếc bát. Mỗi thành phần sẽ là:

  • Một hỗn hợp khác mà bạn phải làm trước trong một chiếc bát riêng biệt; hoặc
  • Một nguyên liệu cơ bản mà bạn đã có sẵn trong bếp, có thể được thêm vào trực tiếp.

Để tạo ra một hỗn hợp, bạn cần chuẩn bị sẵn tất cả các thành phần của nó, lấy một chiếc bát trống và trộn các thành phần vào đó. Không thể tạo ra hỗn hợp bằng cách thêm các thành phần vào một hỗn hợp đã có sẵn trong bát.

Ví dụ, nếu bạn muốn làm CAKE (một hỗn hợp) từ CAKEMIX (một hỗn hợp) và lies (một nguyên liệu cơ bản), thì trước tiên bạn phải làm CAKEMIX trong bát riêng của nó, sau đó thêm CAKEMIX và lies vào một chiếc bát thứ hai để làm CAKE.

Khi bạn đã sử dụng một hỗn hợp như một thành phần và làm trống chiếc bát mà nó được chuẩn bị, bạn có thể tái sử dụng chiếc bát đó cho một hỗn hợp khác. Vì vậy, số lượng bát bạn cần để chuẩn bị công thức sẽ phụ thuộc vào thứ tự mà bạn quyết định thực hiện các hỗn hợp.

Hãy xác định số lượng bát tối thiểu mà bạn sẽ cần.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(C\), số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

  • Một dòng chứa số nguyên \(N\), số lượng hỗn hợp trong bộ dữ liệu.
  • \(N\) dòng, mỗi dòng cho một hỗn hợp, bao gồm:
    • Một chuỗi cho biết tên hỗn hợp;
    • Một số nguyên \(M\), số lượng thành phần trong hỗn hợp này;
    • \(M\) chuỗi, cho biết tên của từng thành phần của hỗn hợp này.

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

Hỗn hợp đầu tiên trong một bộ dữ liệu là công thức bạn đang thực hiện.

Tên của các hỗn hợp là các chuỗi có độ dài từ 1 đến 20 chữ cái VIẾT HOA.

Tên của các nguyên liệu cơ bản là các chuỗi có độ dài từ 1 đến 20 chữ cái viết thường.

Mỗi hỗn hợp được sử dụng trong đúng một hỗn hợp khác, ngoại trừ công thức chính (hỗn hợp đầu tiên), không được sử dụng trong bất kỳ hỗn hợp nào khác. Mỗi thành phần sẽ xuất hiện tối đa một lần trong danh sách thành phần của một hỗn hợp. Không có hỗn hợp nào (trực tiếp hoặc gián tiếp) yêu cầu chính nó như một thành phần.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất một dòng chứa "Case #\(X\): \(Y\)" trong đó \(X\) là số thứ tự của bộ dữ liệu (bắt đầu từ 1) và \(Y\) là số lượng bát trộn tối thiểu cần thiết.

Ràng buộc

  • \(1 \le C \le 10\)
  • \(2 \le M \le 10\)

Phân nhóm

  • Small dataset: \(1 \le N \le 10\)
  • Large dataset: \(1 \le N \le 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.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 5/14 35,71%
Test Set 2 9/14 64,29%

Ví dụ

Ví dụ 1

Input 
2
3
SOUP 3 STOCK salt water
STOCK 2 chicken VEGETABLES
VEGETABLES 2 celery onions
5
MILKSHAKE 4 milk icecream FLAVOR FRUIT
FRUIT 2 banana berries
FLAVOR 2 SPICES CHOCOLATE
SPICES 2 nutmeg cinnamon
CHOCOLATE 2 cocoa syrup
Output 
Case #1: 2
Case #2: 3
Note

Trong trường hợp đầu tiên, để thỏa mãn cơn thèm SOUP, bạn thực hiện các bước sau:

  1. Làm VEGETABLES bằng cách trộn celery và onions trong một chiếc bát.
  2. Làm STOCK trong chiếc bát thứ hai bằng cách trộn chicken và VEGETABLES từ chiếc bát đầu tiên. Chiếc bát đầu tiên trở nên trống rỗng.
  3. Làm SOUP trong chiếc bát đầu tiên bằng cách trộn STOCK, salt và water.

Trong trường hợp thứ hai, bạn có lựa chọn làm FLAVOR hoặc FRUIT trước khi trộn chúng với milk và icecream để làm MILKSHAKE.

Nếu chúng ta làm FRUIT trước, chúng ta sử dụng bốn chiếc bát:

  1. Làm FRUIT trong một chiếc bát bằng cách trộn banana và berries.
  2. Làm SPICES trong chiếc bát thứ hai bằng cách trộn nutmeg và cinnamon, và CHOCOLATE trong chiếc bát thứ ba bằng cách trộn cocoa và syrup (theo bất kỳ thứ tự nào).
  3. Làm FLAVOR trong chiếc bát thứ tư bằng cách trộn SPICES và CHOCOLATE.
  4. Làm MILKSHAKE trong chiếc bát thứ hai hoặc thứ ba bằng cách trộn FRUIT, FLAVOR, milk và icecream.

Tuy nhiên, nếu chúng ta làm FRUIT sau FLAVOR, chúng ta sử dụng ba chiếc bát:

  1. Làm SPICES trong một chiếc bát bằng cách trộn nutmeg và cinnamon, và CHOCOLATE trong chiếc bát thứ hai bằng cách trộn cocoa và syrup (theo bất kỳ thứ tự nào).
  2. Làm FLAVOR trong chiếc bát thứ ba bằng cách trộn SPICES và CHOCOLATE.
  3. Làm FRUIT trong chiếc bát đầu tiên bằng cách trộn banana và berries.
  4. Làm MILKSHAKE trong chiếc bát thứ hai bằng cách trộn FRUIT, FLAVOR, milk và icecream.

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài Mixing Bowls.

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

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: