2014-2015 Olympic 11¶

Bài 1: Thả diều (5 điểm)¶

Đề bài¶

Trong cuộc thi thả diều nhanh, ban tổ chức đưa ra thể lệ cuộc thi như sau: Những chiếc diều không được thả cùng một lúc, mà thả theo trình tự đăng ký nhanh. Khi một chiếc diều được thả lên trời, ban giám khảo căn cứ vào độ cao của chiếc diều và xếp hạng cho chiếc diều đó bằng cách so độ cao của nó với độ cao của những chiếc diều đã thả trước đó.

Chẳng hạn: Độ cao của 4 chiếc diều theo thứ tự được thả như sau: 78 24 68 40. Chiếc diều đầu tiên được xếp hạng nhất vì trước nó chưa có chiếc diều nào được thả. Chiếc diều thứ hai xếp hạng 2 vì 24 < 78. Chiếc diều thứ ba cũng xếp hạng 2 vì 24 < 68 < 78. Chiếc diều thứ tư xếp hạng 3 vì 24 < 40 < 68 < 78. Thứ tự công bố là: 1 2 2 3.

Yêu cầu: Có N chiếc diều lần lượt được thả, hãy cho biết dãy số biểu diễn giá trị xếp hạng của các chiếc diều.

Dữ liệu vào: Cho từ file văn bản KITE.INP có cấu trúc:

Dòng thứ nhất ghi số nguyên dương N cho biết số chiếc diều tham gia dự thi.
N dòng tiếp theo, mỗi dòng ghi một số nguyên dương mô tả độ cao của một chiếc diều, theo thứ tự mà nó được thả lên.

Kết quả: Ghi vào file văn bản KITE.OUT có cấu trúc gồm N dòng, dòng thứ i ghi số nguyên biểu diễn giá trị xếp hạng của chiếc diều thứ i tại thời điểm nó được thả lên.

Ví dụ:

KITE.INP	KITE.OUT
4 78 24 68 40	1 2 2 3

Hạn chế kỹ thuật:

\(N \le 45000\) và không có hai chiếc diều nào có cùng độ cao.
Độ cao của mỗi chiếc diều là một số nguyên dương không vượt quá \(2^{31}\).

Bài giải đề xuất¶

Ý tưởng chính¶

1. Với mỗi lần thả chiều diều mới, độ cao của diều mới được đưa vào vị trí sao cho thứ tự tăng dần theo độ cao của các chiều diều vẫn được bảo đảm.

Trong C++, kiểu dữ liệu hỗ trợ tự động sắp xếp là set. Sau khi chèn độ cao của diều mới, thứ tự của các độ cao vẫn được bảo đảm tăng dần.
Trong Python, do kiểu set không hỗ trợ tự động sắp xếp, ta phải tự viết hàm để tìm vị trí chèn diều mới vào và bảo đảm thứ tự danh sách là giảm dần sau khi chèn.

2. Như vậy, ta thực hiện đồng thời việc thêm từng độ cao vào tập hợp hoặc danh sách và xếp hạng ngay độ cao vừa thêm vào.

Trong C++, do thứ tự là tăng dần, độ cao cao nhất, tức hạng 1, nằm ở cuối tập hợp. Vì thế, ta cần so sánh các độ cao khác với độ cao nằm ở vị trí cuối để xếp hạng.
Trong Python, do danh sách có thứ tự giảm dần, ta tính thứ hạng bằng cách dựa vào chỉ số.

Viết chương trình¶

1. Khởi tạo

Gọi heights là tập hợp (C++) hoặc danh sách (Python) chứa các độ cao tăng dần, result là mảng lưu các thứ hạng để output.

Nạp độ cao đầu tiên vào heights và nạp thứ hạng 1 vào result.

C++Python

    // Đọc độ cao của diều đầu tiên
    int h;    
    cin >> h;
    heights.insert(h);

    // Diều đầu tiên được xếp hạng 1
    result.push_back(1);

    # Đọc độ cao của diều đầu tiên
    h = int(f.readline())
    heights.append(h)

    # Diều đầu tiên được xếp hạng 1
    rank = 1
    result.append(rank)

2. Xử lý

Lần lượt đọc từng độ cao còn lại, ứng với từng độ cao h, lặp thao tác:

Nạp h vào heights.
Tính thứ hạng của h và nạp và mảng result.

C++Python

    // Thứ hạng của mỗi diều
    int rank;

    // Duyệt từng dòng còn lại của dữ liệu đầu vào
    for (int i = 1; i < n; ++i)
    {
        // Đọc độ cao của một diều mới
        cin >> h;

        // Nạp vào set heights
        heights.insert(h);

        // Tính thứ hạng của h vừa nạp bằng cách so vị trí với phần tử cuối cùng trong set
        rank = distance(heights.find(h), heights.end()); // (1)!

        // Ghi nhận thứ hạng
        result.push_back(rank);
    }

Hàm std::distance() dùng để tính số lượng phần tử nằm giữa hai iterator.

    # Duyệt từng dòng còn lại của dữ liệu đầu vào
    for i in range(1, n):
        # Đọc độ cao của một diều mới
        h = int(f.readline())

        # Xác định vị trí sẽ chèn vào
        pos_to_insert = position(heights, h)

        # Nếu không có vị trí chèn phù hợp
        if pos_to_insert == -1:
            # thì thêm vào cuối danh sách heights
            heights.append(h)
        else:
            heights.insert(pos_to_insert, h)

        # Tính thứ hạng của h vừa nạp bằng cách dựa vào chỉ số
        rank = heights.index(h) + 1

        # Ghi nhận thứ hạng
        result.append(rank)

Trong đó, hàm position() dùng để tìm vị trí sẽ chèn vào độ cao mới và bảo đảm thứ tự của danh sách luôn giảm dần.

def position(A, value):
    # Duyệt từng phần tử trong danh sách A
    for i, element in enumerate(A):
        # Nếu gặp phần tử nhỏ hơn
        if element < value:
            # thì trả về vị trí của phần tử đó
            return i

    # Ngược lại, không có phần tử nhỏ hơn, thì trả về -1
    return -1

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bài 2: Đoán số (5 điểm)¶

Đề bài¶

Bờm và Cuội chơi trò chơi đoán số. Số đó là các số nguyên không âm chỉ gồm 0 và 5 và tăng dần gọi số tròn. Ví dụ: 0, 5, 50, 55, 500, ...

Bờm sẽ nói vị trí K và Cuội sẽ thông báo giá trị. Ví dụ: Bờm nói 0, Cuội nói 0, ...

Là hai siêu sao tin học nên càng lúc Bờm đưa số K càng lớn.

Yêu cầu: Hãy giúp Cuội xử lý bài toán này.

Dữ liệu vào: File văn bản knumber.inp gồm một số tự nhiên \(K\) cho biết chỉ số của dãy số tròn ở trên \((0 \le K \le 10^9)\).

Kết quả: Ghi ra file knumber.out một số nguyên cho biết phần tử thứ \(K\).

Ví dụ:

knumber.inp	knumber.out
2	5

Bài giải đề xuất¶

Ý tưởng chính¶

Nếu xem 5 là 1 thì đây là chuỗi nhị phân tăng dần số lượng chữ số, mà trong mỗi chuỗi, chữ số đầu tiên luôn là 1 và các chữ số còn lại là 0 hoặc 1.

Với k (input của đề bài) là vị trí của chữ số cần tìm khi ghép tất cả chuỗi nhị phân lại với nhau, ta cần tìm vị trí j, cũng chính là vị trí của k nhưng xét riêng trong nhóm chuỗi nhị phân có cùng số lượng chữ số.

Ví dụ:
Cho input k = 13, các biến được thể hiện như hình dưới đây:

length là độ dài, tức số chữ số, của mỗi nhóm số nguyên cần xét.

digit_amount là tổng số chữ số của mỗi nhóm số nguyên.

length = 1: digit_amount = 2
length = 2: digit_amount = 4
length = 3: digit_amount = 12

cumulative_digits là số chữ số tích luỹ ứng với tất cả độ dài length.

length = 1: cumulative_digits = 2
length = 2: cumulative_digits = 2 + 4
length = 3: cumulative_digits = 2 + 4 + 12

Tuy nhiên, ta sẽ dừng cộng dồn vào cumulative_digits để biến này không vượt quá k, mục đích là lấy được chỉ số (vị trí) j: j = k - cumulative_digits = 13 - 6 = 7.

j là vị trí của chữ số cần tìm, trùng với vị trí k, nhưng chỉ xét riêng trong nhóm số nguyên có length = 3 (màu xanh lá cây).

Sau khi đã tính được j, ta cần tính hai giá trị sau:

Vị trí của số cần tìm, tức 550 (màu xanh lá đậm), xét trong nhóm có length = 3. Đặt biến này là integer_pos: integer_pos = j // length = 7 //3 = 2.
Vị trí của chữ số cần tìm, tức 5 (màu cam), xét riêng trong số 550. Đặt biến này là target_pos: target_pos = j % length = 7 % 3 = 1.

Với hai giá trị trên, ta tìm cách tạo ra số nguyên liên quan, là 550, như sau:

Vì mỗi số nguyên phải có chữ số đầu là 5 nên ta chỉ xét các chữ số còn lại: remaining_length = length - 1 = 3 - 1 = 2.
Với integer_pos = 2, ta tính được chuỗi nhị phân tương ứng là binary = 10.
Thay 1 bằng 5, ta có: remaining_digits = 50.
Từ đó, ta tạo được số nguyên liên quan là 550. Cụ thể: integer_string = first_digit + remaining_digits = '5' + '50' = '550'.
Dựa trên target_pos = 1, ta lấy ra được chữ số 5 trong 550.

Viết chương trình¶

1. Khởi tạo

C++Python

    // Số lượng chữ số tích luỹ khi tăng độ dài của các số nguyên tạo thành
    lli cumulative_digits = 0; // (1)!

    // Độ dài (số chữ số) của một số nguyên tạo thành
    int length = 1;

typedef long long int lli;

    # Số lượng chữ số tích luỹ khi tăng độ dài của các số nguyên tạo thành
    cumulative_digits = 0

    # Độ dài (số chữ số) của một số nguyên tạo thành
    length = 1

2. Xử lý

Bước 1: Dùng vòng lặp để cộng dồn nhằm tính số lượng chữ số tích luỹ cumulative_digits và không vượt quá vị trí k.

C++Python

    int integer_amount;
    int digit_amount;
    while (true)
    {
        // Tính số lượng số nguyên tạo thành ứng với độ dài length
        if (length == 1)
        {
            // Với độ dài 1, chỉ có 0 và 5
            integer_amount = 2;
        }
        else
        {
            // Chữ số đầu là 5, các chữ số còn lại là 0 hoặc 5
            integer_amount = 1LL << (length - 1); // (1)!
        }

        // Số lượng chữ số của nhóm số nguyên có cùng độ dài
        digit_amount = integer_amount * length; // (2)!

        // Nếu vượt quá vị trí k thì ngắt vòng lặp
        if (cumulative_digits + digit_amount > k) break; // (4)!

        // Tính số lượng chữ số tích luỹ được và không vượt quá vị trí k
        cumulative_digits += digit_amount; // (3)!

        // Tăng độ dài để xét nhóm số nguyên tiếp theo
        length += 1;
    }

1LL là số nguyên có giá trị 1 thuộc kiểu long long (64 bit).

<< là toán tử dùng để dịch chuyển các bit của số nguyên liên quan sang trái theo số vị trí xác định.

(length - 1) chính là số vị trí xác định.

Trong trường hợp (length - 1) = 3 - 1 = 2, số vị trí dịch chuyển là 2, integer_amount = 1LL << (length - 1) = 1LL << (3 - 1) = 2^(3 - 1) = 4
digit_amount = integer_amount * length = 4 * 3 = 12
cumulative_digits += digit_amount = 2 + 4 = 6
cumulative_digits + digit_amount = 6 + 12 = 18 > k = 13:: ngắt vòng lặp

    while True:
        # Tính số lượng số nguyên tạo thành ứng với độ dài length
        if length == 1:
            # Với độ dài 1, chỉ có 0 và 5
            integer_amount = 2
        else:
            # Chữ số đầu là 5, các chữ số còn lại là 0 hoặc 5
            integer_amount = 2 ** (length - 1) # (1)!

        # Số lượng chữ số của nhóm số nguyên có cùng độ dài
        digit_amount = integer_amount * length # (2)!

        # Nếu vượt quá vị trí k thì ngắt vòng lặp
        if cumulative_digits + digit_amount > k: # (4)!
            break

        # Tính số lượng chữ số tích luỹ được và không vượt quá vị trí k
        cumulative_digits += digit_amount # (3)!

        # Tăng độ dài để xét nhóm số nguyên tiếp theo
        length += 1

integer_amount = 2 ** (length - 1) = 2 ** (3 - 1) = 4
digit_amount = integer_amount * length = 4 * 3 = 12
cumulative_digits += digit_amount = 2 + 4 = 6
cumulative_digits + digit_amount = 6 + 12 = 18 > k = 13:: ngắt vòng lặp

Bước 2: Tìm vị trí của số nguyên liên quan, tức chứa vị trí j, tính trong nhóm số nguyên có cùng độ dài length.

C++Python

```c++ linenums="62" // j cũng là vị trí k nhưng xét riêng trong nhóm số nguyên có cùng độ dài length lli j = k - cumulative_digits; // (1)!

// Vị trí của số nguyên liên quan (có chứa vị trí j) tính trong nhóm có cùng độ dài length
int integer_pos = j / length;
```
{ .annotate }

1.  `typedef long long int lli;`

    `j = k - cumulative_digits = 13 - 6 = 7`

2.  `integer_pos = j / length = 7 / 3 = 2`

    # j cũng là vị trí k nhưng xét riêng trong nhóm số nguyên có cùng độ dài length
    j = k - cumulative_digits # (1)!

    # Vị trí của số nguyên liên quan (có chứa vị trí j) tính trong nhóm có cùng độ dài length
    integer_pos = j // length # (2)!

j = k - cumulative_digits = 13 - 6 = 7
integer_pos = j // length = 7 // 3 = 2

Bước 3: Tạo số nguyên có liên quan

C++Python

    string integer_string = "";

    // Tạo số nguyên có liên quan
    if (length == 1)
    {
        vector<string> integers = {"0", "5"};
        integer_string = integers[integer_pos];
    }
    else
    {
        // Tạo chữ số đầu tiên, luôn là '5'
        string first_digit = "5";

        // Số chữ số còn lại cần tạo
        int remaining_length = length - 1; // (1)!

        // Tạo chuỗi nhị phân ứng với số nguyên cần tạo
        string binary = "";

        for (int i = remaining_length - 1; i >= 0; --i)
        {
            if (integer_pos & (1LL << i))
            {
                binary += "1";
            }
            else
            {
                binary += "0";
            }
        } // (2)!

        // Tạo các chữ số còn lại, thay 1 bằng 5
        string remaining_digits = "";
        for (char c : binary)
        {
            if (c == '1')
            {
                remaining_digits += "5";
            }
            else
            {
                remaining_digits += "0";
            }
        } // (3)!

        // Số nguyên tạo thành ở dạng chuỗi
        integer_string = first_digit + remaining_digits; // (4)!
    }

remaining_length = length - 1 = 3 - 1 = 2
(1LL << i) dùng để tạo ra số nhị phân mà bit 1 nằm ở vị trí i, các bit còn lại đều là bit 0, đóng vai trò là mặt nạ.

Toán tử bitwise & (AND) sẽ áp mặt nạ này vào integer_pos để kiểm tra vị trí i của integer_pos là bit 0 hay 1.

Nếu là bit 1 thì chuỗi binary được thêm '1', ngược lại thêm '0'.

Như vậy, với remaining_digits == 2, chuỗi binary sẽ có giá trị là "10".
Trong chuỗi binary, thay ký tự '1' thành 5, ta được remaining_digits.

Code này được tách ra vì mục đích tường minh. Ta có thể viết gộp vào với bước ngay trên.
integer_string = first_digit + remaining_digits = '5' + '50' = '550'

    if length == 1:
        integers = ['0', '5']
        int_string = integers[integer_pos]
    else:
        # Tạo chữ số đầu tiên, luôn là '5'
        first_digit = '5'

        # Số chữ số còn lại cần tạo
        remaining_length = length - 1 # (1)!

        # Chuỗi dùng để định dạng
        format_string = '{:0' + str(remaining_length) + 'b}' # (2)!

        # Tạo chuỗi nhị phân ứng với số nguyên cần tạo
        binary = format_string.format(integer_pos) # (3)!

        # Tạo các chữ số còn lại, thay 1 bằng 5
        remaining_digits = ''.join('5' if c == '1' else '0' for c in binary) # (4)!

        # Số nguyên tạo thành ở dạng chuỗi
        integer_string = first_digit + remaining_digits # (5)!

remaining_length = length - 1 = 3 - 1 = 2
format_string = '{:0' + str(remaining_length) + 'b}' = '{:02b}'
binary = format_string.format(integer_pos) = '{:02b}'.format(2) = '10'
remaining_digits = ''.join('5' if ch == '1' else '0' for ch in binary) = '50'
integer_string = first_digit + remaining_digits = '5' + '50' = '550'

Bước 4: Với số nguyên vừa tạo được ở dạng chuỗi, ta lấy ra chữ số cần tìm.

C++Python

    // Chữ số cần tìm
    int target_pos = j % length;
    result = integer_string[target_pos];

target_pos = j % length = 7 % 3 = 1
return integer_string[target_pos] = '550'[1] = 5

    ## Chữ số cần tìm
    target_pos = j % length # (1)!
    result = integer_string[target_pos] # (2)!

target_pos = j % length = 7 % 3 = 1
return integer_string[target_pos] = '550'[1] = 5

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.