Mở đầu

IN A.D. 2101
WAR WAS BEGINNING
...
CATS: HOW ARE YOU GENTLEMEN !!
CATS: ALL YOUR BASE ARE BELONG TO US

Dĩ nhiên, bài toán này diễn ra vào những ngày yên bình của năm 2100, trước khi toàn bộ căn cứ của chúng ta thuộc về Cats. Nó cũng cho thấy rõ tác giả vẫn đang sống trong năm 2001.

Mở đầu

IN A.D. 2101
WAR WAS BEGINNING
...
CATS: HOW ARE YOU GENTLEMEN !!
CATS: ALL YOUR BASE ARE BELONG TO US

Dĩ nhiên, bài toán này diễn ra vào những ngày yên bình của năm 2100, trước khi toàn bộ căn cứ của chúng ta thuộc về Cats. Nó cũng cho thấy rõ tác giả vẫn đang sống trong năm 2001.

Ý tưởng

Trong bài toán này, ta cần đọc một dãy ký hiệu và diễn giải chúng thành các chữ số của một số trong một cơ số nào đó. Trong bài toán này, ta cần đọc một dãy ký hiệu và diễn giải chúng thành các chữ số của một số trong một cơ số nào đó. Muốn số nhỏ nhất, ta dùng cơ số nhỏ nhất có thể. Nếu có \(k\) ký hiệu phân biệt thì cơ số là \(\max(k,2)\), vì cơ số 1 bị cấm.

Chữ số đầu không thể là 0 nên gán ký hiệu xuất hiện đầu tiên bằng 1. Ký hiệu mới tiếp theo được gán 0; các ký hiệu mới còn lại, theo thứ tự xuất hiện từ trái sang phải, nhận lần lượt 2, 3, ... Đây là cách làm nhỏ nhất chữ số có trọng số cao nhất trước. Ví dụ ab2ac999 thành 10213444 trong hệ 5, tức 85499.

Cài đặt

import sys

N = int(sys.stdin.readline().strip())
for qw in range(1, N+1):
  print 'Case #%d:' % qw,

  num = sys.stdin.readline().strip()
  values = {num[0]: 1}
  for c in num:
    if c not in values:
      sz = len(values)
      if sz == 1:
        values[c] = 0
      else:
        values[c] = sz
  result = 0
  base = max(len(values), 2)
  for c in num:
    result *= base
    result += values[c]
  print result

Độ phức tạp

\(O(n)\) thời gian và \(O(k)\) bộ nhớ cho một chuỗi dài \(n\) có \(k\) ký hiệu.

Ghi chú

Một thành viên Google Group lưu ý rằng ví dụ đầu ngầm giả định cách viết trái sang phải: đảo 11001001 thành 10010011 sẽ là 147 thay vì 201, khiến ta trễ 54 giây. Dù 2219 người giải được bài, giả định đó vẫn khá nguy hiểm!

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 1C - All Your Base, thuộc kho Google Coding Competitions (Apache-2.0).