Задача «Вася строит дом»

Question

Всем здравствуйте! Только начал изучать Python. Не могу решить одну задачу:

Мальчик Вася живёт на координатной прямой. На этот прямой в точке ? располагается школа, а в точке ? — любимый Васин компьютерный клуб. Также в точках …, −?, 0, ?, …, ?⋅?, …, где ? — произвольное целое число, а ? — чётное натуральное число, расположены киоски с мороженым.

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

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

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

Помогите Васе выбрать точку, где строить дом, а также выведите расстояние до ближайшего киоска с мороженым.

Входные данные:
В единственной строке входных данных заданы три числа — ?, ? и ?. Гарантируется, что ? и ? — целые числа, по модулю не превышающие 2⋅10**9, ?≠?. ? — чётное натуральное число, 2 ≤ ? ≤ 2⋅10**9.

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

Примеры:
Ввод 1:

1 5 4

Вывод 1:

3 1

Ввод 2:

1 6 4

Вывод 2:

4 0

Пояснения к примерам 1 и 2:

Я многократно пытался решить задачу, но все попытки тщетны: моё решение помечается как неверное (Программа выдаёт неверный ответ). Хотя я сам проверял свою программу на около десятке примеров, и всё получалось как надо. Мой код:

A,B,d = map(int, input().split())

if (A+B) % 2 == 0:
    C = (A+B)//2
elif (A+B) % 2 == 1:
    C = (A+B)//2
    if C%d == 0:
        C = (A+B)//2
    elif ((A+B)//2 + (A+B)%2)%d == 0:
        C = (A+B)//2 + (A+B)%2
    elif C%d < (C+(A+B)%2)%d:
        C = (A+B)//2 + (A+B)%2
    else:
        C = (A+B)//2

n = C%d

if n < d/2:
    s = n
else:
    s = d-n

print(C, s)

Помогите, пожалуйста, найти ошибку. Я уже просто сбился с толку в решении этой задачи…

Answer 1

В существующем решении не учтено это условие задачи:

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

Нужно рассмотреть оба потенциальных места дома, и выбрать то, которое ближе к киоску с мороженным.

Тут еще видно, что при некоторых вариантах входных данных (A=1, B=2, d=1) оба варианта размещения дома будут на одинаковом расстоянии от киоска. Так что в таких случаях задача допускает несколько правильных решений.

Answer 2

Что-нибудь вроде такого, с учётом нечетной суммы и отрицательных чисел:

A,B,d = map(int, input().split())
summ = A + B
C = summ // 2
D = C % d
s = min(D, d - D)
if summ % 2:
    C2 = (summ + 1) // 2 if summ >= 0 else (summ - 1) // 2
    D = C2 % d
    s2 = min(D, d - D)
    if s2 < s:
        s = s2
        C = C2
print(C, s)

Answer 3

В этой задаче вижу следующие тонкости:

Не сказано, что дом обязательно должен быть между школой и клубом, соответственно возможен вариант, когда школа и клуб рядом, а дом надо ставить справа или слева от них. Например, в комбинации 4 5 7 дом можно поставить на 3 и на 6. От 3 расстояние до ближайшего киоска с мороженым (находится в 0) равно 3, от 6 расстояние до ближайшего (находится в 7) равно 1. Следовательно выбираем 6.
Нужно учитывать возможную разницу в знаках:
- в случае 1 5 4 расстояние = 4.
- в случае -1 5 4 расстояние = 6.

Решение

def find_house_place():
    school, club, ice_interval = map(int, input().split())

    school_club_dist = abs(school - club)

    if school_club_dist > 1:
        first = school_club_dist // 2
        second = school_club_dist - first
    else:
        first = -1
        second = 2 

    leftest_point = min(school, club)

    point_1 = leftest_point + first
    point_2 = leftest_point + second

    remainder_1 = point_1 % ice_interval
    remainder_2 = point_2 % ice_interval

    dist_to_ice_1 = min(remainder_1, ice_interval - remainder_1)
    dist_to_ice_2 = min(remainder_2, ice_interval - remainder_2)

    res = (point_1, dist_to_ice_1) if dist_to_ice_1 <= dist_to_ice_2 else (point_2, dist_to_ice_2)

    print(res[0], res[1])

Тестирование

for _ in range(5):
    find_house_place()

input.txt

Output

Answer 4

    Только списывайте так, чтобы не понятно было

A, B, d = map(int,input().split())
s = 0 #Координата дома
k = 0 #Расстояние до киоска
if A > B:#Чтобы потом не маяться 
    A, B = B, A
if (B-A) % 2 == 0:#Четность
    s = A+(B-A)//2
    k = min(s%d, d-s%d)
else:
    s = A+(B-A)//2
    k = min(min(s%d,(s+1)%d),min(d-s%d, d-(s+1)%d))
    if (s+k)%d != 0 and (s-k)%d != 0:
        if(s+k+1)%d != 0:# Чтобы проходили отрицательные
            s-=1
        else:
            s+=1#Не за что  
print(s, k)

БЛОГ НА HUSL

Задача «Вася строит дом»

Ответы (4 шт):

Решение

Тестирование