1560-A, *800

Problem - 1560A - Codeforces

문제

• 1부터 다음 조건을 만족하는 수$x$를 나열할 때, $k(1\leq k \leq 1000)$번째 수는?
• $x$는 3의 배수가 아니며 일의자리수가 3이 아니다

 

$O(\frac{5}{3}k)\approx O(k)$

1부터 하나하나 따질 때 시간복잡도 분석을 해보자

살구색 음영은 3의 배수인 수들이고 빨간색 빗금은 3의 배수가 아닌 수 중 일의자리수가 3인 수이다
위 수들은 주황색 점선을 기준으로 주기가 반복된다. 따라서
$$\frac{18}{30}\cdot \text{(last number)}\leq k$$

like = [0]
 
k = 1
while len(like) <= 1001:
    if k % 3 != 0 and k % 10 != 3: like.append(k)
    k += 1
 
for _ in range(int(input())): print(like[int(input())])cs