Giới hạn ban đầu của bài này là \(k \le 1000\).

Sau đây là hướng giải của cả bài gốc lẫn bài mới:

\(k \le 1000\)

Làm theo yêu cầu đề bài:

• Duyệt từng số, kiểm tra số có chia hết cho \(3\), hoặc tận cùng bằng \(3\) không.
• Nếu không, tức thỏa mãn đề, ta tăng biến đếm số lượng số thỏa mãn.
• Nếu dãy có đủ k số, ta lập tức in ra số vừa cho vào.

Dưới đây là gợi ý cài đặt cho thuật toán trên:

def kiemtra(num):
    if num % 3 == 0 or num % 10 == 3: 
        return False
    return True

i = 1; cnt = 0
while True:
    if kiemtra(i) == True:
        cnt += 1
        if cnt == k:
            print(i)
            break
    i += 1

Cải tiến (chạy được tầm \(k \le 10^5\) hoặc \(10^6\))

Nhận xét: dãy của chúng ta không bao giờ đổi, vì thế chúng ta có thể xây dựng trước mảng, để xem số thứ \(k\) thỏa mãn là số nào.

• Vẫn duyệt từng số và kiểm tra điều kiện
• Nếu thỏa mãn đề, ta cho số đó vào dãy

Sau đó, với mỗi truy vấn, ta chỉ cần in ra số thứ k.

#=================================
# phần xây dựng mảng
arr = [0]              # chúng ta đếm từ 1, nhưng python đếm từ 0, nên phải chèn 1 số vào
MAX = 100000

i = 1; cnt = 0
while cnt <= MAX:
    if kiemtra(i) == True:
        arr.append(i)
        cnt += 1
#=================================
# phần xử lý cho mỗi truy vấn
print(arr[k])
#=================================

\(k \le 10^9\)

Nhận xét 1

Nhìn vào biểu đồ Venn trên, ta nhận thấy, trong các số từ \(1 \rightarrow n\):

• (không thích) \(=\) (chia hết cho 3) \(+\) (tận cùng bằng 3) \(-\) (thỏa mãn cả hai)
• (thích) = \(n\) \(-\) (không thích)

Một số công thức:

• Số lượng số chia hết cho \(3\) từ \(1 \rightarrow n = \lfloor \frac{n}{3} \rfloor\) (phép \(\lfloor \frac{a}{b} \rfloor\) trong python là a // b)
• Số lượng số tận cùng bằng \(3\) từ \(1 \rightarrow n\):
• Nếu tận cùng của \(n\) nhỏ hơn \(3\): \(\lfloor \frac{n}{10} \rfloor\)
• Nếu lớn hơn hoặc bằng: \(\lfloor \frac{n}{10}\rfloor + 1\)
• Số lượng số chia hết cho \(3\), và tận cùng bằng \(3\) từ \(1 \rightarrow n\):
  
  Ta nhận thấy những số đó có dạng \(X3\), với \(X\) là một số tự nhiên chia hết cho \(30\). Vậy:
• Nếu tận cùng của \(n\) nhỏ hơn \(3\): \(\lfloor \frac{n}{30} \rfloor\)
• Nếu lớn hơn hoặc bằng: \(\lfloor \frac{n}{30}\rfloor + 1\)

Hoặc chúng ta có thể dùng công thức \(\lfloor\frac{n+7}{10}\rfloor; \lfloor\frac{n+27}{30}\rfloor\) lần lượt thay cho việc chia hai trường hợp ở mỗi công thức trên, lợi dụng việc \(7; 27\) là phần bù của số \(3\) khi chia cho \(10; 30\).

Nhận xét 2

Khi \(n\) tăng dần, số lượng số mà Polycarp thích càng tăng.

Vì thế ta sẽ dùng thuật toán tìm kiếm nhị phân, để tìm số \(n\) nhỏ nhất có ít nhất \(k\) số thỏa mãn.

• Đặt \(lo = 1, hi = 2*10^9\)

#=====================================================================
# hàm tính số lượng số được thích
def like(n):
    return n - ((n // 3) + ((n + 7) // 10) - ((n + 27) // 30))
#=====================================================================
# tìm kiếm nhị phân cho mỗi truy vấn:

lo = 1; hi = 3000000000; ans = 0
while lo <= hi:
    mid = (lo + hi) // 2
    cnt = like(mid)

    if cnt >= k: ans = mid; hi = mid - 1
    else: lo = mid + 1
print(ans)
#=====================================================================