CF 1560A - Dislike of Threes

CF 1560A - Dislike of Threes

Rating: 800
Tags: implementation
Solve time: 1m 40s
Verified: yes

Solution

Problem Understanding

We are asked to generate a sequence of positive integers that Polycarp "likes." A number is liked if it is not divisible by 3 and does not end with the digit 3. Given an integer $k$, the task is to output the $k$-th number in this sequence. Multiple test cases are provided, each with a separate $k$.

The input consists of $t$, the number of test cases, followed by $t$ integers $k$. Each $k$ can be as large as 1000, and there can be up to 100 test cases. Since the largest number we might need is modest (in the low thousands), we can afford simple methods like iterating through integers sequentially. The constraints rule out solutions that would require searching through millions of numbers but allow linear approaches that filter numbers until reaching the $k$-th valid one.

Non-obvious edge cases arise because numbers divisible by 3 or ending with 3 must be skipped. For example, the naive approach of assuming every third number is bad fails: numbers like 13, 23, 16 are skipped differently because the ending digit matters in addition to divisibility. A small example shows this: the 9th liked number is 14, not 13 or 15. Careless indexing can easily miscount here.

Approaches

The brute-force approach is straightforward. Start at 1 and iterate through integers, skipping those divisible by 3 or ending in 3. Count how many liked numbers we have seen, and stop when we reach the $k$-th. This is guaranteed to work because we check every number, but it can be slow if $k$ were very large, since it requires potentially iterating over more than $k$ numbers.

A key observation simplifies this. Any number ending in 3 or divisible by 3 must be skipped. There is no direct formula to jump to the $k$-th number because the skips are irregular: every tenth number that ends with 3 is bad, and every third number divisible by 3 is bad, and sometimes these overlap. However, for $k \le 1000$, simply generating numbers sequentially is fast enough, and optimizing beyond this is unnecessary. If $k$ were much larger, one could use a precomputed list or mathematical pattern based on counting skipped numbers, but the complexity of such a formula is higher than just iterating.

The comparison table:

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(k) per test case	O(1)	Accepted
Precompute list	O(max_k)	O(max_k)	Accepted but unnecessary

Algorithm Walkthrough

1. Initialize a counter for how many liked numbers we have seen. Start at zero.
2. Initialize the current number to 1.
3. While the counter is less than $k$, check the current number.
4. If the number is divisible by 3 or ends with 3, skip it. Otherwise, increment the counter.
5. Increment the current number and repeat step 3.
6. Once the counter reaches $k$, the last number considered is the $k$-th liked number. Return it.

The invariant is that the counter accurately tracks how many liked numbers we have seen. We only increment the counter for valid numbers, so when the counter equals $k$, we are guaranteed to have reached the $k$-th liked number.

Python Solution

import sys
input = sys.stdin.readline

def kth_liked_number(k):
    count = 0
    num = 1
    while True:
        if num % 3 != 0 and num % 10 != 3:
            count += 1
            if count == k:
                return num
        num += 1

t = int(input())
for _ in range(t):
    k = int(input())
    print(kth_liked_number(k))

The function kth_liked_number walks through integers sequentially, only incrementing the counter when a number is liked. The main loop handles multiple test cases. Care is taken with the condition num % 10 != 3 rather than checking the string representation, which is slightly faster. Using while True allows us to exit as soon as the $k$-th number is found.

Worked Examples

Example 1: k = 4

num	num % 3	num % 10	liked?	count
1	1	1	yes	1
2	2	2	yes	2
3	0	3	no	2
4	1	4	yes	3
5	2	5	yes	4

The 4th liked number is 5.

Example 2: k = 10

num	num % 3	num % 10	liked?	count
1	1	1	yes	1
2	2	2	yes	2
3	0	3	no	2
4	1	4	yes	3
5	2	5	yes	4
6	0	6	no	4
7	1	7	yes	5
8	2	8	yes	6
9	0	9	no	6
10	1	0	yes	7
11	2	1	yes	8
12	0	2	no	8
13	1	3	no	8
14	2	4	yes	9
15	0	5	no	9
16	1	6	yes	10

The 10th liked number is 16.

These traces confirm the counting invariant and handling of numbers ending with 3 or divisible by 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k) per test case	We may need to check slightly more than k numbers to find the k-th liked number, but never more than roughly 1.5k.
Space	O(1)	Only counters and current number are stored; no extra arrays needed.

For the maximum constraints, t=100 and k=1000, the solution processes at most ~1500 numbers per test case, totaling ~150,000 iterations, which is well within the 1-second limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    # call solution
    t = int(input())
    def kth_liked_number(k):
        count = 0
        num = 1
        while True:
            if num % 3 != 0 and num % 10 != 3:
                count += 1
                if count == k:
                    return num
            num += 1
    for _ in range(t):
        k = int(input())
        print(kth_liked_number(k))
    return output.getvalue().strip()

# Provided samples
assert run("10\n1\n2\n3\n4\n5\n6\n7\n8\n9\n1000\n") == "1\n2\n4\n5\n7\n8\n10\n11\n14\n1666", "sample 1"

# Custom cases
assert run("3\n1\n13\n20\n") == "1\n25\n33", "varied k"
assert run("1\n1000\n") == "1666", "max k"
assert run("1\n100\n") == "153", "middle k"
assert run("2\n1\n2\n") == "1\n2", "smallest k repeated"

Test input	Expected output	What it validates
"3\n1\n13\n20\n"	"1\n25\n33"	General varied k and skips over multiples of 3 and numbers ending in 3
"1\n1000\n"	"1666"	Maximum k boundary
"1\n100\n"	"153"	Intermediate k, confirms counting works beyond first few numbers
"2\n1\n2\n"	"1\n2"	Smallest k values, ensures initial sequence correct

Edge Cases

For k = 1, the first liked number is 1. The algorithm starts counting from 1 and correctly increments the counter only when a number is liked. No skipped numbers occur before the first one. For k = 1000, the algorithm continues until 1666, correctly skipping all multiples of 3 and numbers ending with 3. Edge cases around numbers like 3, 6, 13, 33 are handled by the conditional num % 3 != 0 and num % 10 != 3, which ensures the counter only increases for valid numbers.