В этом контесте мы задались целью показать, что декларативный подход к решению задач может быть удобнее традиционного императивного. Впрочем, первые несколько задач были предназначены для знакомства с базовым синтаксисом языка и его библиотеками. Все авторские решения написаны kit1980.

530A - Квадратное уравнение

Решение квадратного уравнения требовало использования библиотечной функции sqrt и конструкции if-then-else. Кроме того, эта задача должна была продемонстрировать, что в языке есть числа с плавающей точкой :-)

main =>
    A = read_real(), B = read_real(), C = read_real(),
    D = B * B - 4 * A * C,
    X1 = (-B - sqrt(D)) / (2 * A),
    X2 = (-B + sqrt(D)) / (2 * A),
    if D == 0 then
        println(X1)
    else
        printf("%w %w%n", min(X1, X2), max(X1, X2))
    end.

530B - Строка наизнанку

Задача на работу со строками: библиотечная функция slice позволяет получить подстроку заданной строки, reverse разворачивает ее, а ++ — оператор конкатенации. Как вариант, можно было использовать цикл и вывести ответ посимвольно.

main =>
    S = read_line(),
    N = length(S),
    X = reverse(slice(S, 1, N // 2)) ++ reverse(slice(S, 1 + N // 2)),
    println(X).

530C - Диофантово уравнение

Эту задачу можно решить полным перебором (для каждого X проверить, существует ли подходящий Y). Авторское решение использует constraint programming ("программирование в ограничениях"), которое по сути реализует перебор с отсечениями, позволяющее избавиться от явного цикла перебора.

import cp.
main =>
    A = read_int(), B = read_int(), C = read_int(),
    X #> 0, Y #> 0,
    if A * X + B * Y #= C then
        Solutions = solve_all([X, Y])
    else
        Solutions = []
    end,
    println(length(Solutions)),
    foreach ([I, J] in Solutions)
        printf("%d %d%n", I, J)
    end.

Выражение A * X + B * Y #= C задает ограничение на переменные. Уже на этом этапе система может понять, что решений нет, и перейти в ветку else. Иначе функция solve_all вернет список всех решений.

530D - Разность множеств

Эту задачу можно решить множеством способов: от императивных циклов до того же constraint programming. Авторское решение использует библиотечную функцию subtract, которая вычитает из одного отсортированного списка другой. A..B формирует список чисел от A до B. Для вывода используется list comprehension. Эта задача — единственная, в которой авторское решение использует := — чисто императивный оператор деструктивного присваивания.

import ordset.
import util.
main =>
    X = 1..1000,
    N = read_int(),
    foreach (_I in 1..N)
        A = read_int(), B = read_int(),
        X := subtract(X, A..B)
    end,
    println(join([to_string(V) : V in [length(X) | X]])).

530E - Сумма и произведение

Эту задачу можно решать как минимум двумя способами. "Математический" способ предлагает заметить, что решение, состоящее из N-2 единиц, двойки и N+D, всегда подходит под описанные условия. В некоторых случаях существуют другие решения, например, для теста N = 4, D = 1 подходит решение 1, 1, 3, 3.

Авторское решение использует constraint programming, что позволяет не думать, а просто перевести условие задачи на Picat.

import cp.
import util.
main =>
    N = read_int(), D = read_int(),
    Vals = new_list(N),
    Vals :: 1..10000,
    prod(Vals) #= sum(Vals) + D,
    solve(Vals),
    println(join([to_string(V) : V in Vals])).

530F - Прыгающие лягушки

На обычном языке программирования эта задача решалась бы поиском в глубину или в ширину. Такой поиск можно реализовать и на Picat. В Picat, как и в Prolog, поиск в глубину с возвратами встроен в язык. Техника tabling используется для мемоизации и для автоматического поиска максимума: выражение table(+, +, +, max) означает, что первые три параметра предиката — входные, последный — выходной, и его надо максимизировать. ?=> означает недетерминизм: сам по себе вызов jump может возвращать разные значения для одних и тех же входных параметров, table выбирает из них максимальное. best_frog использует ту же самую технику, чтобы избежать явного цикла по лягушкам для поиска лучшей из лягушек.

table(+, +, +, max)
jump(X, Y, K, Dist) ?=>
    (
      NewX = X + K, NewY = Y ;
      NewX = X - K, NewY = Y ;
      NewX = X, NewY = Y + K ;
      NewX = X, NewY = Y - K
    ),
    land(NewX, NewY),
    jump(NewX, NewY, K, Dist).
jump(X, Y, _K, Dist) =>
    Dist = abs(X) + abs(Y).

table(-, max)
best_frog(K, Dist) ?=>
    between(1, 10, K),
    jump(0, 0, K, Dist).

main =>
    N = read_int(),
    Facts = [$land(X, Y) : _I in 1..N, X = read_int(), Y = read_int()],
    cl_facts(Facts),
    best_frog(_K, Dist),
    println(Dist).

530G - Расстояние Левенштейна

Классическая задача на динамическое программирование. Авторское решение использует tabling для реализации рекурсии с мемоизацией, аналогично задаче 530F - Прыгающие лягушки.

table(+, +, min)
edit(I, J, Cost) ?=>
    str(S), goal(G),
    N = length(S), M = length(G),
    (
        I <= N, J <= M,
        edit(I + 1, J + 1, NextCost),
        Cost = abs(ord(S[I]) - ord(G[J])) + NextCost
    ;
        I <= N,
        edit(I + 1, J, NextCost),
        Cost = ord(S[I]) - 0'a + 1 + NextCost
    ;
        J <= M,
        edit(I, J + 1, NextCost),
        Cost = ord(G[J]) - 0'a + 1 + NextCost
    ;
        I > N, J > M,
        Cost = 0
    ).

main =>
    S = read_line(), G = read_line(),
    cl_facts([$str(S), $goal(G)]),
    edit(1, 1, Cost),
    println(Cost).

530H - Точки в треугольнике

Эта задача требует разумного перебора возможных вершин треугольника с проверкой того, лежат ли все точки внутри. Поскольку координаты точек принимают значения до 100, координаты вершин треугольника никогда не будут больше 200.

import cp.
main =>
    N = read_int(),
    A :: 1..200, B :: 1..200,
    foreach (_I in 1..N)
        Xi = read_int(), Yi = read_int(),
        B * Xi #<= A * (B - Yi)
    end,
    solve([$min(A * B)], [A, B]),
    println(A * B / 2).

530I - Разные переменные

Эта задача, по сути, задача раскраски графа. Авторское решение использует constraint programming с ограничениями all_distinct. Для ускорения работы программы можно заметить, что первая переменная всегда принимает значение 1. С этим наблюдением можно использовать ограничение all_different (эти ограничения отличаются внутренней реализацией алгоритмов), без него all_different слишком медленно.

import cp.
import util.
main =>
    N = read_int(), K = read_int(),
    Vars = new_array(N),
    Vars :: 1..N, Vars[1] #= 1,
    foreach(_I in 1..K)
        [_ | Indexes] = [to_integer(A) : A in split(read_line())],
        all_distinct([Vars[Idx] : Idx in Indexes])
    end,
    List = to_list(Vars), MaxC #= max(List),
    solve([$min(MaxC)], Vars),
    println(join([to_string(V) : V in Vars])).