Google Code Jam 2010 - Load Testing

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: 1500 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Sau khi bạn giành chiến thắng tại Code Jam và được Google tuyển dụng làm kỹ sư phần mềm, bạn đã được giao nhiệm vụ làm việc trên trang web tổ chức các cuộc thi lập trình cực kỳ phổ biến của họ.

Google đang mong đợi một lượng lớn người tham gia (\(P\)) trong Code Jam năm tới và họ muốn đảm bảo rằng trang web có thể hỗ trợ cùng lúc bấy nhiêu người đó. Trong Code Jam 2010, bạn đã biết rằng trang web có thể hỗ trợ ít nhất \(L\) người cùng lúc mà không gặp bất kỳ lỗi nào, nhưng bạn cũng biết rằng trang web hiện tại chưa thể hỗ trợ \(P\) người.

Để xác định xem bạn sẽ cần thêm bao nhiêu máy chủ, bạn muốn biết trong phạm vi một hệ số \(C\) xem trang web có thể hỗ trợ bao nhiêu người. Điều này có nghĩa là tồn tại một số nguyên \(a\) sao cho bạn biết trang web có thể hỗ trợ \(a\) người, nhưng bạn biết trang web không thể hỗ trợ \(a \times C\) người.

Bạn có thể thực hiện một loạt các bài kiểm tra tải (load tests), mỗi bài kiểm tra sẽ xác định xem trang web có thể hỗ trợ ít nhất \(X\) người hay không, với một giá trị nguyên \(X\) bất kỳ mà bạn chọn. Nếu bạn chọn một chiến lược tối ưu, chọn bài kiểm tra nào để chạy dựa trên kết quả của các bài kiểm tra trước đó, bạn cần bao nhiêu bài kiểm tra tải trong trường hợp xấu nhất?

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 các số nguyên \(L, P\) và \(C\) cách nhau bởi dấu cách theo đúng thứ tự đó.

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 bài kiểm tra tải bạn cần thực hiện trong trường hợp xấu nhất trước khi biết được trong phạm vi hệ số \(C\) số người mà trang web có thể hỗ trợ.

Ràng buộc

  • \(1 \le T \le 1000\).
  • \(2 \le C \le 10\).
  • \(L, P\) và \(C\) đều là các số nguyên.

Phân nhóm

  • Small dataset (Test set 1): \(1 \le L < P \le 10^3\).
  • Large dataset (Test set 2): \(1 \le L < P \le 10^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.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 14/36 38,89%
Test Set 2 22/36 61,11%

Ví dụ

Ví dụ 1

Input 
4
50 700 2
19 57 3
1 1000 2
24 97 2
Output 
Case #1: 2
Case #2: 0
Case #3: 4
Case #4: 2
Note
  • Trong Case #2, chúng ta đã biết trang web có thể hỗ trợ từ 19 đến 57 người. Vì các giá trị này nằm trong hệ số 3 (\(19 \times 3 = 57\)), chúng ta không cần thực hiện thêm bài kiểm tra nào.
  • Trong Case #4, chúng ta có thể kiểm tra 48; nhưng nếu trang web hỗ trợ được 48 người, chúng ta cần kiểm tra thêm, vì \(48 \times 2 < 97\). Chúng ta có thể kiểm tra 49; nhưng nếu trang web không hỗ trợ được 49 người, chúng ta cần kiểm tra thêm, vì \(24 \times 2 < 49\). Do đó, chúng ta cần hai bài kiểm tra.

Nguồn

Google Code Jam 2010, Vòng 1C, bài Load Testing.

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: