.gitignore

/.cache/v/cache/lastfailed

input1.txt

3 5
21 12 19
10 20 10 20 10

input2.txt

3 5
1 1 1
10 10 10 20 20

test_task2.py

#!/usr/bin/env python3
"""Task #2 from http://oi-minsk.id1945.com/2015-16/city/statements2.pdf

XXX two unsuccessful attempts p_min, p_min_grow
"""
from math import inf
import pytest  # $ pip install pytest


def ints_from_input_line():
    return list(map(int, input().split()))


def main():
    M, N = ints_from_input_line()
    H = ints_from_input_line()
    B = ints_from_input_line()
    assert len(H) == M and len(B) == N and N >= M >= 2
    try:
        p = p_min(H, B)
    except ValueError:
        print(-1)  # no solution
    else:
        print(* [k + 1 for k in p])


def p_min(H, B):
    """Take eagerly the first possible p[i]."""
    M, N = map(len, (H, B))
    for k in range(N - M + 1):
        p = [None] * M
        p[0] = k
        for i in range(1, M):
            try:
                p[i] = next(
                    j for j in range(p[i - 1] + 1, N - M + i + 1)
                    if H[i] + B[j] > H[i - 1] + B[p[i - 1]])
            except StopIteration:
                break  # no solution
        else:  # found solution
            return p
    raise ValueError("no solution")


def p_min_grow(H, B):
    """Take eagerly p[i] that increases the sum the least."""
    M, N = map(len, (H, B))
    p = [None] * M
    p[0] = min(range(N - M + 1), key=lambda j: H[0] + B[j])
    for i in range(1, M):
        p[i] = min(
            range(p[i - 1] + 1, N - M + i + 1),
            key=lambda j: H[i] + B[j] if H[i] +
            B[j] > H[i - 1] + B[p[i - 1]] else inf
        )
        if not (H[i] + B[p[i]] > H[i - 1] + B[p[i - 1]]):
            raise ValueError("no solution")
    return p


def assert_valid(f, H, B, p):
    assert all(H[i + 1] + B[p[i + 1]] > H[i] + B[p[i]] and p[i + 1] > p[i]
               for i in range(len(H) - 1))
    assert f(H, B) == p


@pytest.mark.parametrize("f", [p_min, p_min_grow])
def test(f):
    assert_valid(f, [21, 12, 19], [10, 20, 10, 20, 10], [0, 1, 3])
    with pytest.raises(ValueError):
        f([1, 1, 1], [10, 10, 10, 20, 20])
    assert_valid(f, [21, 12, 19], [10, 20, 10, 20, 10] + [1] * 10, [0, 1, 3])
    assert_valid(f, [21, 12, 19], [100, 10, 27, 20, 10, 20, 10], [1, 3, 5])


if __name__ == '__main__':
    main()