3

Всем здравствуйте! Только начал изучать 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)

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

1
  • 2
    не рассмотрен второй вариант для нечётной суммы
    – MBo
    1 июн 2020 в 13:33

4 ответа 4

4

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

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

1 5 4 
1 6 4 
0 101 70
-51 20 5 
4 5 7

Output

3 1
4 0
51 19
-15 0
6 1
4

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

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

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

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

3
  • Здравствуйте! Я написал код по Вашему решению, но почему-то моё решение не принимается. Не пойму, где я допустил ошибку. Я обновил свой вопрос, добавив в него новый код. Не подскажите, где я допустил ошибку? 1 июн 2020 в 13:18
  • 1
    Я изменил ответ, чтобы он соответствовал новому вопросу. 1 июн 2020 в 13:42
  • Roman Konoval, я учёл Ваши рекомендации и сильно переработал своё решение, но моё решение до сих пор отмечается, как неверное. Пожалуйста, помогите снова найти ошибку. У меня просто не получается… Я изменил вопрос, добавив новый код. 1 июн 2020 в 16:54
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)
2
  • Здравствуйте! Я ввёл Ваш ответ, но почему-то он отметился как неверный. Очень странно. 1 июн 2020 в 21:54
  • @Daniil Savinov Не спешите с принятием ответов. Возможно, я тоже чего-то не учёл.
    – MBo
    2 июн 2020 в 2:12
1
    Только списывайте так, чтобы не понятно было

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) 

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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