Kim tự tháp chữ

[rogp10]

[COCI 2014/2015 - vòng 1, bài 3 - 100/650 điểm]

Đề bài An và Bình là hai bạn thân. Một ngày nọ, hai bạn dùng gạch thẻ xếp thành một kim tự tháp nho nhỏ rồi lấy gạch khắc một từ lên đó, trông như thế này:

# PEPE
    P # ---->
   P E # <----
  E P E # ---->
 E P E P # <----

An lấy K tầng trong kim tự tháp và đố Bình có bao nhiêu kí tự nào đó ở K tầng này. Là anh/chị/cô/chú của Bình, hãy viết chương trình để trả lời câu hỏi “hóc búa” trên.

I/O

• Input: stdin
  • Dòng đầu tiên là số tầng của kim tự tháp: 1 <= N <= 10^18
  • Dòng thứ hai là một từ chỉ gồm các kí tự từ A đến Z có độ dài L <= 10^6
  • Dòng thứ ba là số câu hỏi của An: K <= 10^5
  • K dòng tiếp theo gồm tầng số <= N và một kí tự từ A đến Z.
• Output: stdout
  • Gồm K dòng là một con số là tần suất của kí tự đó tương ứng với input.

Giới hạn:

• 50 điểm: N <= 1000
• 70 điểm: L <= 10^5
• Thời gian tối đa: 1s
• Bộ nhớ: 32MB ■

[Shiharoku]

An lấy K tầng trong kim tự tháp và đố Bình có bao nhiêu kí tự nào đó ở tầng này.

Ý anh là tầng K?

[rogp10]

Ý anh là tầng K ?

Không phải, K tầng đó em. Tức là sẽ có K truy vấn đó.

[Shiharoku]

À, vậy thì đoạn sau phải là :

Ở K tầng này.

[Shiharoku]

Nếu từ đưa vào là SHIHAROKU thì tháp sẽ là:

    S
   I H
  H A R
 S U K O
H I H A R

Vậy thì bài làm khá đơn giản.

Với K tầng thì sẽ có 1 + 2 + . . . + K = K * (K + 1) / 2 (ký tự).

Hay đơn giản thì là có K * (K + 1) / 2 div len từ (với len là độ dài của từ) cộng với K * (K + 1) / 2 mod len ký tự đầu của từ.

Để đếm xem trong K tầng đó có bao nhiêu ký tự c thì chỉ cần đếm xem trong từ có bao nhiêu ký tự c đó rồi nhân với số từ trong K tầng.

Lại đếm tiếp trong K * (K + 1) / 2 mod len ký tự đầu của từ rồi cộng với kết quả có được ở trên.

Độ phức tạp là O(L) (L là độ dài từ).

Code

int shifun(const char *s, const int k, const char c) {
    int len = strlen(s);
    if (!len) return 0;
    int n = k * (k + 1) / 2;
    int quotient = n / len;
    int surplus = n % len;
    int count = 0, sur = 0;

    for (int i = 0; i < len; i++, surplus--)
        if (s[i] == c) {
            count++;
            if (surplus > 0) sur++;
        }
    return count * quotient + sur;
}

Test

https://ideone.com/y48h3Q

P/s: Với điều kiện là tháp như đã nói ở trên, còn không thì là Sai. Mà nếu vậy thì cho số tầng ban đầu là không cần thiết. Chắc sai rồi.

[rogp10]

Cái này có một query à bạn K query lận.

[Shiharoku]

Anh vô phần test á.

Còn code em chỉ để thuật toán thôi.

[rogp10]

K*L <= 10^6 * 10^5 = 10^11 chắc 60đ thôi.

[Shiharoku]

Ít vậy

Em cũng chỉ mới học, nghĩ sao làm vậy .

Vậy phải nhờ mọi người chỉ bảo thêm rồi.

[rogp10]

Đi thi kẹt quá thì ăn mấy test nhỏ cũng được nhưng thay số vào big-O mà quá giây*10^9 thì ko trọn điểm.

[noname00 (HK boy)]

Bài này chắc dùng toán thôi.

Đến tầng k thì có tổng cộng k*(k+1)/2 tất cả -> có floor(L / (k*(k+1)/2)) lần xâu s xuất hiện. Vậy nên là lấy dư của L cho (k*(k+1)/2) rồi đếm thông thường thôi.

Vì xâu không đổi nên lưu lại frequency của từng kí tự A-Z trong xâu s, tính thêm tổng cộng dồn frequency cho từng kí tự, sau đó nhân chia cộng trừ thêm vào.

Độ phức tạp O(L * 26 + N K).

[tntxtnt]

giải thích ko có chữ N nào sao trong đpt lại có N Chữ K mới đúng chứ

[noname00 (HK boy)]

N là số test case mà anh ơi

[tntxtnt]

N là số tầng mà, chả cần dùng nó trong bài này :V K là số test case

[noname00 (HK boy)]

Èo để em sửa :v