Dzisiaj nie chciało mi się kombinować więc zadanie rozwiązałem po prostu w Pythonie.

Zadanie

Treść nie jest była dzisiaj skomplikowana, w każdej lini otrzymujemy liczbę i listę liczb, pomiędzy liczby z listy musimy umieścić operatory (+ albo *), w taki sposób żeby uzyskać pierwszą liczbę w linii. (operacje wykonywane są od lewej do prawej).

190: 10 19      # 190 = 10 * 19
100: 3 60 10    # nie da się
83: 17 5        # nie da się
4: 1 1 2        # 4 = (1 + 1) * 2

Rozwiązanie

Do sprawdzenia czy dana linia jest poprawna (możemy w niej dobrać odpowiednie operatory), napisałem prostą rekurencyjną funkcję. Sprawdza ona wszystkie kombinacje operatorów, aż znajdzie ten poprawny.

def is_valid(target, acc, arr):
    if not arr:
        return target == acc

    return (
        is_valid(target, acc + arr[0], arr[1:]) or
        is_valid(target, acc * arr[0], arr[1:])
    )

Reszta kodu to tylko parsowanie wejścia i zliczanie poprawnych lini oraz wypisanie wyniku:

import fileinput  # z biblioteki standardowej

res = 0
for line in fileinput.input():  # czytamy stdin
    s = line.strip().split()
    num = int(s[0][:-1])
    arr = list(map(int, s[1:]))
    if is_valid(num, arr[0], arr[1:]):
        res += num

print(res)

Otrzymujemy poprawny wynik!

Część druga

Nie różni się ona bardzo od pierwszej, dochodzi nam jedynie jeszcze jeden możliwy operator. Konkatenacja (||), np. 10 || 4 = 104, jedyne zmiany jakie musimy wprowadzić, będą w funkcji is_valid

def is_valid(target, acc, arr):
    if not arr:
        return target == acc

    return (
        is_valid(target, acc + arr[0], arr[1:]) or
        is_valid(target, acc * arr[0], arr[1:]) or
        is_valid(target, int(str(acc) + str(arr[0])), arr[1:])
    )

Działa, ale dość wolno (2 sekundy), jesteśmy w stanie na pewno zoptymalizować nasze rozwiązanie, pierwzszym pomysłem jest zakończenie przeszukania w momencie, w którym przekroczymy wartość poszukiwaną, działa to ponieważ wszystkie wszystkie wartości są dodatnie, a nasze operatory gwarantują że każda kolejna wartość będzie większa.

def is_valid(target, acc, arr):
    if not arr:
        return target == acc

    if acc > target:
        return False

    return (
        is_valid(target, acc + arr[0], arr[1:]) or
        is_valid(target, acc * arr[0], arr[1:]) or
        is_valid(target, int(str(acc) + str(arr[0])), arr[1:])
    )

Ta prosta zmiana ściąga czas wykonywania do 1.2 sekundy.

Optymalizacja pamięci

Minus naszej poprzedniej funkcji jest taki że w każdym wykonaniu funkcji tworzymy slice z naszej listy, gdzie tak na prawdę wymagamy jedynie wglądu w wartości na poszczególnych pozycjach. Dlatego możemy trzymać w zmiennej pos aktualną pozycję w liście i przekazywać też wskaźnik do całej listy arr:

def is_valid(target, acc, pos, arr):
    if pos == len(arr):
        return target == acc

    if acc > target:
        return False

    return (
        is_valid(target, acc + arr[pos], pos + 1, arr) or
        is_valid(target, acc * arr[pos], pos + 1, arr) or
        is_valid(target, int(str(acc) + str(arr[pos])), pos + 1, arr)
    )
copy

Ta optymalizacja pozwala zejść nam do 0.5 sekund.