Algorithmic Solutions for Seven Programming Problems (Number Cards, Grid Lines, Cube Packing, Shortest Path, Hamiltonian Cycle, Time Display, Pascal's Triangle)

1. Number Card Sequence

Given 2021 copies of each digit 0‑9, determine the largest integer N such that all numbers from 1 to N can be formed using the cards without reuse. The answer is 3181.

li = [2021 for i in range(10)]
ans = 1
while True:
    tmp = ans
    while tmp // 10:
        if li[tmp % 10] == 0:
            break
        li[tmp % 10] -= 1
        tmp //= 10
    if li[tmp % 10] == 0:
        break
    li[tmp % 10] -= 1
    ans += 1
print(ans - 1)

2. Straight Lines on a Grid

For all integer points (x, y) with 0 ≤ x < 20 and 0 ≤ y < 21, count the number of distinct lines determined by pairs of points. The result is 40257.

x, y = map(int, input().split())
points = [[i, j] for i in range(x) for j in range(y)]
line = set()
for i in range(len(points) - 1):
    x1, y1 = points[i]
    for j in range(i, len(points)):
        x2, y2 = points[j]
        if x1 == x2:
            continue
        k = (y2 - y1) / (x2 - x1)
        b = (x2 * y1 - x1 * y2) / (x2 - x1)
        line.add((k, b))
print(len(line) + x)

3. Cube Packing

Given n = 2021041820210418 identical unit cubes, count the ordered triples (L, W, H) of positive integers with L·W·H = n. The answer is 2430.

n = int(input())
line = set()
for i in range(1, int(pow(n, 1/2)) + 1):
    if n % i == 0:
        line.add(i)
        line.add(n // i)
ans = 0
for l in line:
    for w in line:
        for h in line:
            if l * w * h == n:
                ans += 1
print(ans)

4. Shortest Path in a Special Graph

A graph of 2021 vertices connects i and j when |i‑j| ≤ 21 with edge weight equal to lcm(i, j). The shortest distance from vertex 1 to vertex 2021 is 10266837.

import math

def gcm(x, y):
    return x * y // math.gcd(x, y)

n = int(input())
dp = [float('inf')] * (n + 1)
dp[1] = 0
for i in range(1, n + 1):
    for j in range(i + 1, i + 22):
        if j > n:
            break
        dp[j] = min(dp[j], dp[i] + gcm(i, j))
print(dp[n])

5. Hamiltonian Cycle on a Coprime Graph

Vertices 1‑21 are connected when their numbers are coprime. The number of Hamiltonian cycles starting and ending at vertex 1 is 881012367360.

from math import gcd
n = int(input())
m = 1 << n
dp = [[0 for j in range(n)] for i in range(m)]
load = [[False for j in range(n)] for i in range(n)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if gcd(i, j) == 1:
            load[i - 1][j - 1] = True
dp[1][0] = 1
for i in range(1, m):
    for j in range(n):
        if i & (1 << j):
            for k in range(n):
                if i - (1 << j) & (1 << k) and load[k][j]:
                    dp[i][j] += dp[i - (1 << j)][k]
print(sum(dp[m - 1]) - dp[m - 1][0])

6. Millisecond Timestamp to HH:MM:SS

Convert a Unix timestamp given in milliseconds to a time string "HH:MM:SS" (UTC). Two implementations are shown: one using the time module and another using arithmetic.

import time
n = int(input())
new_n = time.asctime(time.gmtime(n // 1000))
print(new_n[11:19])

n = int(input())
n //= 1000
day = 24 * 60 * 60
n %= day
s = n % 60
n //= 60
m = n % 60
n //= 60
h = n
print("{:02d}:{:02d}:{:02d}".format(h, m, s))

7. First Occurrence in Pascal's Triangle Sequence

Flatten Pascal's triangle row‑wise and find the position of the first occurrence of a given integer N. For N = 6 the answer is 13.

def find_n(n):
    if n == 1:
        return 1
    res = 3
    li, l = [1, 2], 3
    while n not in li:
        res += len(li) * 2 - l % 2
        li = [1] + [li[i] + li[i + 1] for i in range(len(li) - 1)] + ([li[-1] * 2] if l % 2 == 0 else [])
        l += 1
    return res + li.index(n) + 1

if __name__ == '__main__':
    n = int(input())
    print(find_n(n))

The collection demonstrates typical competitive‑programming techniques such as greedy simulation, combinatorial counting, graph shortest‑path DP, state‑compression DP, modular arithmetic, and direct arithmetic conversion.