0

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

Требуется написать программу, определяющую, какую из трех спичек необходимо переместить.

Входные данные

Вводятся шесть целых чисел через пробел: l1, r1, l2, r2, l3, r3 –– координаты первой, второй и третьей спичек соответственно (0 ≤ li < ri ≤ 100). Каждая спичка описывается координатами левого и правого концов по горизонтальной оси OX.

Выходные данные

Выведите номер искомой спички. Если возможных ответов несколько, то выведите наименьший из них. В случае, когда нет необходимости перемещать какую-либо спичку, выведите 0. Если же требуемого результата достигнуть невозможно, то выведите -1.

Примеры

входные данные

0 2 4 5 3 6

выходные данные

1

входные данные

1 2 9 10 12 20

выходные данные

3

входные данные

1 5 0 1 4 8

выходные данные

0

Что получилось у меня:

def dist(l1, r1, l2, r2):
    res = max(l1, l2) - min(r1, r2)
    if res <= 0:
        return 0
    else:
        return res
l1, r1, l2, r2, l3, r3 = map(int, input().split())
if l2-r1<1 and (l3-r2<1 or l3-r1<1):
    print(0)
else:
    d1 = r1 - l1
    d2 = r2 - l2
    d3 = r3 - l3
    if dist(l1, r1, l2, r2) == 0:
        print(3)
    elif dist(l2, r2, l3, r3) == 0:
        print(1)
    elif dist(l1, r1, l3, r3) == 0:
        print(2)
    else:
        if dist(l1, r1, l2, r2) < d3:
            print(3)
        elif dist(l2, r2, l3, r3) < d1:
            print(1)
        elif dist(l1, r1, l3, r3) < d2:
            print(2)
        else:
            print(-1)

Этот код проходит 13 из 18 тестов. В остальных тестах выдаёт неправильный ответ. Какие ещё случаи я не учла?

2 ответа 2

1

По крайней мере, для print(0) вы не всё учли, и есть сомнения в то выведите наименьший из них и в соприкасались (хотя бы концами).

Попробуйте так

l1, r1, l2, r2, l3, r3 = map(int, input().split())
d12 = dist(l1, r1, l2, r2)
d13 = dist(l1, r1, l3, r3)
d23 = dist(l3, r3, l2, r2)

count = (d12==0) + (d13==0) + (d23==0)
if count >= 2:
    print(0)
else:
    d1 = r1 - l1
    d2 = r2 - l2
    d3 = r3 - l3
    if d23 <= d1:
        print(1)
    elif d13 <= d2:
        print(2)
    elif d12 <= d3:
        print(3)
    else:
        print(-1)
0

Логику описал в комментариях. Публиковал со смартфона, поэтому лишние пустые строки.

def dist(m1, m2):
    return max(max(m1[1],m2[1])-min(m1[2],m2[2]),0)


def which_match(input):
    input = list(map(int,input.split(' ')))

    # формируем список из спичек вида [[0, 0, 2], [1, 4, 5], [2, 3, 6]],

    # где первый элемент - номер спички 0..2, второй элемент - левая кордината, третий элемент - правая координата

    # Это делается для последующего перебора в цикле с извлечением спичек

    matches = [[i//2,input[i],input[i+1]] for i in range(0,len(input),2)]
    print('Спички: ' + ''.join([f'{m[0]+1}=({m[1]},{m[2]}) ' for m in matches]))
    cases, result = 0, -1

    for taken in range(2,-1,-1): # извлекаем по очереди спички, начиная с последней

        print(f'Убираем спичку № {taken+1}')

        st = [m for m in matches if m[0]!=taken] # список из оставшихся двух спичек

        d,l = dist(st[0],st[1]), matches[taken][2]-matches[taken][1] # вычисляем дистанцию между оставшимися двумя спичками и длину извлеченной спички

        print(st, f'дистанция = {d}', f'длина = {l}')

        cases += 1 if d==0 else 0 # количество случаев когда расстояние между парами спичек == 0

        if d <= l: # если длина извлеченной спички перекрывает дистанцию между оставшимися спичками, заносим в результат номер вынутой спички

            result = taken + 1 # +1 из-за того, что база от 0
    return result if cases < 2 else 0 # если между любыми двумя парами спичек расстояние == 0, значит они все уже соединены

 

# тест

for input in ('0 2 4 5 3 6','1 2 9 10 12 20','1 5 0 1 4 8','0 1 3 4 6 7'):

    result = which_match(input)
    if result>0:
        print(f"Нужно переложить спичку № {result}\n")
    elif result==0:
        print(f"Не нужно перекладывать спичку ({result})\n")
    else:
        print(f"Нет решения ({result})\n")

Спички: 1=(0,2) 2=(4,5) 3=(3,6)

Убираем спичку № 3

[[0, 0, 2], [1, 4, 5]] дистанция = 2 длина = 3

Убираем спичку № 2

[[0, 0, 2], [2, 3, 6]] дистанция = 1 длина = 1

Убираем спичку № 1

[[1, 4, 5], [2, 3, 6]] дистанция = 0 длина = 2

Нужно переложить спичку № 1

 

Спички: 1=(1,2) 2=(9,10) 3=(12,20)

Убираем спичку № 3

[[0, 1, 2], [1, 9, 10]] дистанция = 7 длина = 8

Убираем спичку № 2

[[0, 1, 2], [2, 12, 20]] дистанция = 10 длина = 1

Убираем спичку № 1

[[1, 9, 10], [2, 12, 20]] дистанция = 2 длина = 1

Нужно переложить спичку № 3

 

Спички: 1=(1,5) 2=(0,1) 3=(4,8)

Убираем спичку № 3

[[0, 1, 5], [1, 0, 1]] дистанция = 0 длина = 4

Убираем спичку № 2

[[0, 1, 5], [2, 4, 8]] дистанция = 0 длина = 1

Убираем спичку № 1

[[1, 0, 1], [2, 4, 8]] дистанция = 3 длина = 4

Не нужно перекладывать спичку (0)

 

Спички: 1=(0,1) 2=(3,4) 3=(6,7)

Убираем спичку № 3

[[0, 0, 1], [1, 3, 4]] дистанция = 2 длина = 1

Убираем спичку № 2

[[0, 0, 1], [2, 6, 7]] дистанция = 5 длина = 1

Убираем спичку № 1

[[1, 3, 4], [2, 6, 7]] дистанция = 2 длина = 1

Нет решения (-1)

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.