dyslexic
edit
qrcode
+=≡-

Programming Contest Strategies

This is a small collection of basic strategies for an effective programming contest team.

Here some quick links:

Basic Rules

Different contests have different rules, but there is typically a common set of rules.

Preparing Before the Competition

Practice, practice, practice!

You can get access to many programming contest problems with a quick Google search. There are many online programming contests, for example Project Euler, LeetCode, Kattis, and CodeChef.

Look at previous contests, such as ACM ICPC

Know which languages are acceptable during the competition. Typically the accepted languages include C, C++, Java, and Python 3, but every competition is different.

Important

Be sure you practice for the language version that is available! For example, Kattis runs Python 3.11.11 (as of 2025.11.23), and Python 3.11's fractions.Fraction does not have __format__ (added only Python 3.12), so formatted prints can by tricky. If your team is using your own machine, it would be best install and practice on exactly the same version of the language with exactly the same libraries as what is accepted.

Be sure to have a basic familiarity with the following:

More advanced problems often involve:

To Bring

During the Competition

Cheat Sheet: Starter Code

The following sections contain useful Python 3 code.

Python 3 Starter Code #

Below is a bit of starter code written in Python 3.

You might not need to use all of the code below for every problem, so be sure to understand what each line of code is actually doing.

Warning

input() will throw EOFError if the input "runs out", so make sure you either catch the error or read only what you need to read.

Read Fixed or Known Number of Lines

If the input is fixed or includes a count of things to process or if there is a line indicating the end of the input, then you can use input() to read one line at a time. As an example of reading in a fixed number of things, the Quadrant Selection | Kattis problem has exactly two lines of input. As an example of reading in a certain number of things, the first line of input in the Solving for Carrots | Kattis problem contains the number of lines to read in (\(N\)). As an example of reading until a certain line, the What does the fox say? | Kattis requires you to read and process lines until you read the line what does the fox say?.

N = int(input())     # the first line has a count (N) of lines to read
for i in range(N):   # now, read in exactly N lines
    line = input()   # read one line of text
    print(line)      # do something with line...

Read Until End of Input

Some problems do not have a specific line that indicates the end of the input, but instead require you to read until the end of the input. As an example, the Adventures in Moving – Part IV | Kattis problem requires you to read in and process all the lines. You can still use input() to read in each line, however you must take care! The input() function will throw an EOFError exception if the input "runs out", so you will need to catch the error. If you don't catch it, your program will crash, and the competition server might think your solution is incorrect.

The easiest approach is to treat stdin as a stream.

import sys
for line in sys.stdin:   # IMPORTANT: line will end with a newline ('\n')
    line = line[:-1]     # remove '\n' from end
    print(line)          # do something with line...

Alternatively, you can catch the EOFError error and stop execution then.

try:
    while True:          # repeate forever (until EOFError)
        line = input()   # read one line of text
        print(line)      # do something with line...
except EOFError: pass    # we have run out of input

Read All Input First, Then Process Separately

As an alternative to reading in one line at a time, you can read in ALL the lines as a list of strings, and then you can process each line as you like. However, you must take care when indexing into the list!

import sys

#' read in all the lines as a list of strings
#' note: each string has a newline ('\n') at the end!  strip it off
lines = [ line.rstrip('\n') for line in sys.stdin ]

#' if you want to strip out and ignore empty lines
lines = [ line for line in lines if line.strip() ]

#' usually first line has the problem's size, so convert it into an int
problem_size = int(lines[0])

#' if you need to exit program quickly, sys.exit() is safe to use
if problem_size == 0:
    print('NO SOLUTION')
    sys.exit()

#' sometimes a line may contain items separated by spaces.  use split()
parts = lines[1].split(' ')

#' finally, print out your solution to STDOUT
print('SOLUTION')

See Kattis Help for starter code snippets for various languages.

Useful Python 3 Code #

The code listing below contains some common Python "recipes" that can be useful.

Conversions

ascii_val  = ord('A')   # ASCII number of character A is 65
ascii_char = chr(65)    # ASCII character of number 65 is A


int_value   = int('42')      # get int value in string: 42
float_value = float('3.14')  # get float value in string: 3.14
str_value   = str(42)        # convert argument to string: "42"

#' base conversions
#' decimal:42 -> binary:0b101010, octal:0o42, hexadecimal:0x2a
v2, v8, v16 = bin(42), oct(42), hex(42)
#' binary, octal, hexadecimal -> decimal
assert int(v2, 2)==42  and  int(v8, 8)==42  and  int(v16, 16)==42

#' convert string with things to list of string with things
list_of_strs = '1 2 3'.split()  # splits str on spaces ['1', '2', '3']
str_of_list  = ' '.join(['1', '2', '3'])    # joins list of strs '1 2 3'
list_of_ints = list(map(int, list_of_strs)) # converts to list of ints

Formatted Prints

v = 3.14
print(v)           # prints 3.14
#' % printing (similar to C/C++)
print('%f' % v)    # prints 3.140000  (0s based on precision of float)
print('%.3f' % v)  # prints 3.140     (with 3 digits after decimal)
#' F-string prints
print(f'{v}')      # prints 3.14
print(f'{v:.3f}')  # prints 3.140     (with 3 digits after decimal)

print('foo', end='')    # print without newline
print()                 # print only newline

Math Functions and Operations

#' Different ways to round
#' floor: down.  round: to nearest int.  ceil: up.  int: toward zero
from math import floor, ceil   # round and int are built-in fns
assert floor(-3.9)==-4 and floor(-3.1)==-4 and floor(3.9)==3  # down
assert round(-3.9)==-4 and round(-3.1)==-3 and round(3.9)==4  # nearest
assert ceil( -3.9)==-3 and ceil( -3.1)==-3 and ceil( 3.9)==4  # up
assert int(  -3.9)==-3 and int(  -3.1)==-3 and int(  3.9)==3  # to 0

print(5 // 2, -5 // 2)   # integer division, rounds down
print(10 % 3, -10 % 3)   # modulus, always non-negative in Python

#' Rationals or Fractions: Numerator / Denominator
#' use like any other number
from fractions import Fraction
rat0, rat1 = Fraction(19, 3), Fraction(25, 6)   # 19 / 3  and 25 /6
ratsum = rat0 + rat1              # 19/3 + 25/6 = 21/2
print(ratsum)                     # prints "21 / 2"
print(floor(ratsum))              # prints "10"
print(ratsum.as_integer_ratio())  # prints "(21, 2)"
print(float(ratsum))              # prints "10.5"

#' Exponents and Logarithms
from math import pow, log
print(pow(2, 3))           # 2^3
print(log(3.14))           # log_e 3.14
print(log(3.14) / log(5))  # log_5 3.14, using log-base conversion

Graphs

#' Represent a graph using dictionary with lists
graph = {
    'A': ['B', 'C'],       #     A---B---D
    'B': ['A', 'C', 'D'],  #      \ /
    'C': ['A', 'B'],       #       C
    'D': ['B'],
}
#' Breadth-First Search
from collections import deque              # deques are efficient queues
path, working = {'C': None}, deque(['C'])  # BFS code, starting at C
while working:                             # keeping track of how we
    current = working.popleft()            # got there from C
    for other in graph[current]:
        if other not in path:
            path[other] = current
            working.append(other)

Lists and Double-Ended Queues (Deques)

names  = [
    'Alice', 'Zeus', 'Bob', 'Yasmin', 'Carol',
    'Xavier', 'Dave', 'Wanda', 'Edith'
]
names.sort()                # sort list
some_names = names[1:-2]    # get all but first and last
snames = sorted(names, key=lambda name: name[-1]) # sort by last letter
rnames = [name[::-1] for name in names]           # reverse names

#' itertools module has a BUNCH of useful functions over lists
from itertools import combinations, permutations
for grp in combinations(names, 2): print(grp) # print all groups of 2
for per in permutations(names, 2): print(per) # print all 2-permutations

#' Double-Ended Queues
from collections import deque
d = deque()
d.appendleft(-1) ; d.append(42)  # add LHS (prepend) or RHS (append)
d.popleft()      ; d.pop()       # pops off left or right
d.extend([2,4])      # extends RHS (keeps order)
d.extendLeft([6,8])  # extends LHS, REVERSE order!
d.rotate(4)          # rotates deque right (>0) or left (<0)

Sets

#' Set Manipulations
a_list = ['A','B','A','C','D']
a_set  = set(a_list)               # will not contain duplicates
b_set  = {'A','E','F'}
assert a_set | b_set == {'A','F','D','B','E','C'}  # union
assert a_set - b_set == {'B','C','D'}              # difference
assert a_set & b_set == {'A'}                      # intersection
assert a_set ^ b_set == {'B','C','D','E','F'}      # symmetric diff

Dictionaries

#' Dictionary
items = "abcdaefghijkalmnopqrsbatuvwxyz"
count = {}
for c in items:
    if c in count: count[c] += 1
    else:          count[c] = 1
#' alternative
count = {}
for c in items:
    count[c] = count.get(c, 0) + 1  # default val if key doesn't exist
#' alternative
count = {}
for c in items:
    count.setdefault(c, 0)          # default val if key doesn't exist
    count[c] += 1
#' alternative
from collections import defaultdict
count = defaultdict(lambda:0)       # default val if key doesn't exist
for c in items: count[c] += 1

Priority Queues

#' Priority Queues
from heapq import heappush, heappop
h = []   # heappush and heappop turn a list into priority queue
heappush(h, (5, 'write code'))      # 1st arg is priority queue
heappush(h, (7, 'release product')) # 2nd arg is item that has priority
heappush(h, (1, 'write spec'))      # in this case, 1st part of tuple
heappush(h, (3, 'create tests'))    #    acts as priority key
heappop(h)                          # (1, 'write spec')

Advanced

#' easy memoization (still must take care with calling order and args)
from functools import cache
@cache
def fibonacci(n):
    return n if n <= 1 else fibonacci(n-1) + fibonacci(n-2)

Note

Python will automatically switch to using "Big Integers" if the int value gets too large/small. This means that you do not have to worry about overflow and underflow. Other languages will have a separate type or a module that can do this, but it is built into Python.

Use Caution: big integer arithmetic is much slower than plain int arithmetic! This is especially true with exponents!

Advanced #

The following Bash code will execute your program using sample.in as input and testing the output agaist sample.ans. If nothing is printed, then success! Otherwise, something isn't correct.

$ diff <(python3 your_program.py < sample.in) sample.ans

All combinations using bitwise manipulations (source)

uint64_t set_n_bits(int t) { return (1 << (t+1)) - 1; }
uint64_t cycle_combo(uint64_t prev) {
    uint64_t t = prev | (prev - 1);   // set least sig 0 bits
    // set the most significant bit to change
    // clear the least significant ones
    // add the necassary 1 bits
    return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(prev) + 1));
}

Cheat Sheet: Math Equations  #

Sources:

Constants and Approximations

Symbol Value* Description Python†
\(\pi\) 3.14159 Pi math.pi
\(\tau\) 6.28318 Tau (twice pi) math.tau
\(\e\) 2.71828 Euler's number math.e
\(\sqrt{2}\) 1.41421 Square-root of 2 math.sqrt(2)
\(\varphi\) 1.618033 Golden Ratio (1+math.sqrt(5))/2
\(\i\) \(\sqrt{-1}\) Imaginary unit 1j

*approximate. †must import math.

Geometry

Area of a Triangle

\[ A = \frac{bh}{2} = rs = \frac{ab}{2} \sin \theta = \frac{abc}{4R} = \sqrt{(s)(s-a)(s-b)(s-c)} \]

Where \(A\) is the area, \(b\) is the base, and \(h\) is the height. In the second equation, \(r\) is the inradius (radius of circle that can be inscribed inside the triangle) and \(s\) is the semiperimeter (which is half the perimeter of triangle). In the third equation, \(\theta\) is the angle between two sides \(a\),\(b\) of the triangle. In the fourth equation, \(a\),\(b\),\(c\) are the sides of the triangle with circumradius \(R\) (radius of circle that passes through all three vertices of triangle). In the final equation (Heron's Formula), \(a\),\(b\),\(c\) are the side lengths of triangle with \(s\) as the semiperimeter.

Pythagorean Theorem and Right Triangles

\[ a^2 + b^2 = c^2 \]

Where \(c\) is the hypotenuse of a right triangle with legs \(a\) and \(b\). Note that there are some "special" right triangles. These include right triangles with angle measures \(45^\circ\)–\(90^\circ\)–\(45^\circ\) and \(30^\circ\)–\(60^\circ\)–\(90^\circ\).

Distance Formula

\[ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \]

Where \((x_1, y_1)\) and \((x_2, y_2)\) are points on a coordinate plane and \(d\) is the distance between them. This is essentially the Pythagorean Theorem restated for points on a plane.

In 3D (where points are \((x_i, y_i, z_i)\)), the distance is

\[ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2} \]

Trigonometry

Math Python Math Python
\(x=\cos \theta\) x = math.cos(t) \(\theta=\cos^{-1} x = \arccos x\) t = math.acos(x)
\(x=\sin \theta\) x = math.sin(t) \(\theta=\sin^{-1} x = \arcsin x\) t = math.asin(x)
\(x=\tan \theta\) x = math.tan(t) \(\theta=\tan^{-1} x = \arctan x\) t = math.atan(x)

Note

However, use atan2 instead of atan when possible, because it handles quadrants better. For example: \(\tan^{-1} (y/x)\) is computed as math.atan2(y, x)

Radians and Degrees

Conversion Math Python
degrees→radians \(\text{radians} = \text{degrees} \cdot \frac{2\pi}{360}\) math.radians(d)
radians→degrees \(\text{degrees} = \text{radians} \cdot \frac{360}{2\pi}\) math.degrees(r)

Trigonometric Identities

Note that \(\tan \theta = \frac{\sin\theta}{\cos\theta}\). Also \(\sec \theta = \frac{1}{\cos\theta}\) and \(\csc \theta = \frac{1}{\sin \theta}\). Therefore, the identities for \(\tan\), \(\cot\), \(\sec\), \(\csc\) are easily derived from the identities for \(\sin\) and \(\cos\)

Double Angle:

\[ \sin 2\theta = 2\sin\theta\cos\theta \qquad \cos 2\theta = \cos^2\theta - \sin^2\theta \]

Negative Angles:

\[ \cos -\theta = \cos \theta \qquad \sin -\theta = -\sin \theta \]

Pythagorean Identities:

\[ \sin^2 \theta + \cos^2 \theta = 1 \qquad \cot^2 \theta + 1 = \csc^2 \theta \qquad \tan^2 \theta + 1 = \sec^2 \theta \]

Addition / Subtraction Identities:

\[ \sin \alpha + \beta = \sin \alpha \cos \beta + \sin \beta \cos \alpha \qquad \sin \alpha - \beta = \sin \alpha \cos \beta - \sin \beta \cos \alpha \] \[ \cos \alpha + \beta = \cos \alpha \cos \beta - \sin \beta \sin \alpha \qquad \cos \alpha - \beta = \cos \alpha \cos \beta + \sin \beta \sin \alpha \]

Half Angle Identities:

\[ \sin \frac{\theta}{2} = \pm \sqrt{\frac{1 - \cos\theta}{2}} \qquad \cos \frac{\theta}{2} = \pm \sqrt{\frac{1 + \cos\theta}{2}} \]

Longitude and Latitude

The point on a unit sphere given longitude and latitude

\[(x,y,z) = (\cos \theta \cos \phi, \sin\theta \cos\phi, \sin\phi) \]

where \(\phi\) is latitude (\(\phi \in [-90^\circ, 90^\circ]\)) and \(\theta\) is longitude (\(\theta \in [0, 360^\circ) \))

Circle

\[ \text{Area} = \pi r^2 \quad\quad \text{Circumference} = 2 \pi r \]

Arc Length

\[ l = \theta r \]

Where \(l\) is length of arc, \(\theta\) is center angle of the arc in radians, and \(r\) is radius of circle.

Algebra

Quadratic Formula and Discriminant

\[ x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \]

Where \(a\),\(b\),\(c\) are the coefficients of the \(x^2\), \(x^1\), \(x^0\) terms respectively. If the discriminant (\(d = b^2 - 4ac\)) is \(0\), the quadratic will have one real solution. If the discriminant is positive, the quadratic will have two real solutions. If the discriminant is negative, the quadratic will have no real solutions (only imaginary).

Logarithm Rules

Logarithmic to Exponential \( \log_a b = x \Rightarrow a^x = b \)
Addition \( \log_a b + \log_a c = \log_a bc \)
Subtraction \( \log_a b - \log_a c = \log_a \frac{b}{c} \)
Exponent Reducing \( \log_a b^c = c \log_a b\)
Change of Base \( \log_a b = \frac{\log_c b}{\log_c a} \)
Reciprocals \( \log_a b = \frac{1}{\log_b a} \)

Logarithms in Python

Math Python Details
\(\log_a b\) math.log(b, a) base defaults to \(\e\) if not given
\(a^b\) math.pow(a, b) use when a and b are floats
\(a^b\) pow(a, b) use when a and b are ints
\(a^b\) a**b similar to built-in pow
\(a^b \bmod m\) pow(a,b,m) use when a,b,m are ints

Discrete

Permutations and Combinations

Math Python Description
\( _nP_k = \frac{n!}{(n-k)!}\) math.comb(n, k) Number of ways (\(_nP_k\)) to choose \(k\) items
out of \(n\) when order matters.
\( \binom{n}{k} = \frac{n!}{k!(n-k)!} \) math.perm(n, k) Number of ways (\(\binom{n}{k}\)) to choose \(k\) items
out of \(n\) when order does not matter.

Greatest Common Divisor and Least Common Multiple

Name Python
Greatest Common Divisor math.gcd(a, b, c)
Least Common Multiple math.lcm(a, b, c)

Prime Number

import math
def is_prime(n):
    if n <= 1:     return False  # primes start at 2
    if n == 2:     return True   # first prime
    if n % 2 == 0: return False  # even numbers >2 are not prime
    # not prime if any odd number >=3 up to sqrt(n) divides number
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0: return False
    return True

Logic

Truth table for negation / not (\(\neg\)), conjunction / and (\(\wedge\)), disjunction / or (\(\vee\)), implication (\(\Rightarrow\)), and equivalence (\(\Leftrightarrow\)).

\(A\) \(B\) \(\neg A\) \(\neg B\) \(A \wedge B\) \(A \vee B\) \(A \Rightarrow B\) \(A \Leftrightarrow B\)
\(0\) \(0\) \(1\) \(1\) \(0\) \(0\) \(1\) \(1\)
\(0\) \(1\) \(1\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(1\) \(0\) \(0\) \(1\) \(0\) \(1\) \(0\) \(0\)
\(1\) \(1\) \(0\) \(0\) \(1\) \(1\) \(1\) \(1\)

Number Theory

Sum of an Arithmetic Series

\[\begin{array}{ccl} \sum_{i=1}^n a_i & = & a_1 + a_2 + \ldots + a_n = \frac{n}{2}(a_1 + a_n) \\ \sum_{x=1}^n x & = & 1 + 2 + \ldots + n = \frac{n(n+1)}{2} \\ \sum_{x=1}^n x & = & 1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6} \\ \end{array}\]

\[\begin{array}{ccll} \sum_{x=1}^n 2x+1 & = & n^2 & \text{ sum of first } n \text{ positive odd numbers} \\ \sum_{x=1}^n 2x & = & n(n+1) & \text{ sum of first } n \text{ positive even numbers} \\ \end{array}\]

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) allows you to solve a system of linear congruences. Let \(m_1\), \(m_2\), ..., \(m_r\) be a collection of pairwise relatively prime integers. Then the system of simultaneous congruences \(x \equiv a_1(\mod m_1)\), \(x \equiv a_2(\mod m_2)\), ..., \(x \equiv a_r( \mod m_r)\) has a unique solution modulo \(M = m_1 m_2, ..., m_r\) for any given integers \(a_1\), \(a_2\), ..., \(a_r\). This is easier to understand in an example and is very well explained in this YouTube video by Cathy Frey.

Fibonacci Numbers

\[ \mathit{Fib}(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ \mathit{Fib}(n-1) + \mathit{Fib}(n-2) & \text{otherwise} \end{cases} \]

Factorials

\[ n! = \prod_{x=1}^n x = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n = \begin{cases} 1 & n = 0 \\ n \cdot (n-1)! & \text{otherwise} \end{cases} \]

Statistics

...

Calculus

estimate integral with sum

...

Example Problems

Below are some example problems with solutions (hidden).

What does the fox say? #

Problem: What does the fox say? | Kattis (2.1)

Try to solve this problem before revealing my solution below.

Solution: 

import fileinput

#' load in all of the input
#' note: fileinput.input() returns an iterable, not a list
#' note: each line of iterable includes the `\n` at end
lines = [line[:-1] for line in fileinput.input()]

tests = int(lines[0])  # str->int
i = 1

for test in range(tests):
    sounds = lines[i].split(' ')  # str->array of str
    i += 1
    other_sounds = set()
    while lines[i] != 'what does the fox say?':
        _,_,sound = lines[i].split(' ')
        i += 1
        other_sounds.add(sound)
    i += 1
    fox_sounds = [sound for sound in sounds if sound not in other_sounds]
    print(' '.join(fox_sounds))

Adventures in Moving – Part IV  #

Problem: Adventures in Moving – Part IV | Kattis (4.7)

Try to solve this problem before revealing my solution below.

Solution: 

import fileinput
import sys

#' read in and clean up input
lines = [line.rstrip(' \n') for line in fileinput.input()]
lines = [line for line in lines if line.strip()]

#' total distance from Waterloo to big city
total_dist = int(lines[0])

#' fuel stations are next in input
stations = [[int(v) for v in station.split(' ')] for station in lines[1:]]
nstations = len(stations)

#' here is the basic set up:
#'   costs[0]: starting point  [100]  <- cost to get here is 0
#'   costs[1]: 0th station     [0, 200]
#'   costs[2]: 1st station     [0, 200]
#'   costs[n]: last station    [0, 200]
#'   costs[n+1]: ending point  [100]  <- only care about this fuel amount
#'      print(costs[n+1][100])

#' data structure to keep track of costs
#' note: could simply keep a single dict of the previous stop rather
#'       than storing all of the previous costs!
#' note: using a dictionary so that we can
#'       1. specify exactly where we want to insert values
#'       2. use get() to return a default value if key doesn't exist
#' note: using float('inf') to indicate that a position and fuel
#'       amount is impossible to reach (ex: requiring >200L of fuel)

impossible = float('inf')

costs = {}

costs[0] = {}
costs[0][100] = 0

curmarker = 0
for istation in range(nstations):
    istop = istation + 1
    kmmarker, price = stations[istation]
    # compute distance from previous stop to current
    dist = kmmarker - curmarker
    # start a dict to hold costs for current stop
    costs[istop] = {}
    for fuel in range(0, 201):
        # cost to get to previous stop (burned fuel to get here)
        p0 = costs[istop-1].get(fuel+dist, impossible)
        # cost to get to current stop but with 1L less of fuel
        #   (add 1L of fuel)
        p1 = costs[istop].get(fuel-1, impossible) + price
        # keep whichever is cheaper
        costs[istop][fuel] = min(p0, p1)
        # note: could skip inserting into costs table if min
        #       is float('inf')
    curmarker = kmmarker # advance our truck to next stop

#' only need to look at a single value in costs table to know
#' the cheapest way to get there!
fuel = 100 # ending condition
dist = total_dist - curmarker
best = costs[nstations].get(fuel+dist, impossible)
#' costs[nstations+1][100] = best   # <- don't need to store this, but can

print(best if best != impossible else 'Impossible')

Fridge  #

Problem: Fridge | Kattis (3.1)

Try to solve this problem before revealing my solution below.

Solution: 

#!/usr/bin/python3

import fileinput
import sys

lines = [line.rstrip(' \n') for line in fileinput.input()]
lines = [line for line in lines if line.strip()]
line = lines[0] # only care about first line of input

#' if mincount == 0, then we can only produce single digit numbers, and
#'   min key with val==0 is the answer (except X=0 => 10)
#' if mincount == 1, then XX is a 2-digit number that we cannot produce,
#'   and the answer is X=min key with val==1 (except for X=0 =>100)
#' if mincount == 2, then XXX is a 3-digit number ...

#' so, the general answer is:
#' -  XX...X where X is smallest digit with smallest count, except for
#' - 100...0 if smallest digit with smallest count is 0

#' count number of each magnet digits
magnet_counts = { i:line.count(i) for i in '0123456789' }

#' find which magnet digit(s) we have least number
#' note: might have multiple, so find all digits with min count
min_count = min(magnet_counts.values())
min_digits = list(sorted(
    k for (k,v) in magnet_counts.items() if v == min_count
))

#' 0 always "lags" behind other digits, so handle it specially
if min_digits == ['0']:
    # 0 is the only digit, so first number we cannot produce
    # will be in form 10...0
    print('1' + '0' * (min_count+1))
else:
    # find smallest non-0 digit
    # if 0 is in min_digits, then use index 1
    # otherwise, use index 0
    idx = 1 if '0' in min_digits else 0
    print(min_digits[idx] * (min_count+1))

Simple Arithmetic  #

Problem: Simple Arithmatic | Kattis (1.2–4.4)

Try to solve this problem before revealing my solution below.

Solution: 

#!/usr/bin/python3

from math import floor
from fractions import Fraction

a, b, c = map(int, input().split(' '))

a = Fraction(a, 1)
b = Fraction(b, 1)
c = Fraction(c, 1)

v = a * b / c

#' Kattis uses Python 3.8 (https://open.kattis.com/languages/python3)
#' which means that Fraction does not have `__format__`.  so, need
#' to separate integer from decimal explicitly
iv = floor(v)
dv = (v - Fraction(iv, 1)) * Fraction(1000000, 1)

print(f'{iv}.{floor(dv):06d}')