Простая задача

@Artemchek11 · Регистрация: 12.04.2020

Студворк — интернет-сервис помощи студентам

В этой задаче не будет длинного условия и простого решения. Все будет наоборот. Требуется провести непрерывную линию произвольного вида из точки с координатами (x1,y1) в точку с координатами (x2,y2) так, чтобы минимизировать количество точек на этой линии, в которых хотя бы одна координата является целым числом. Ответом к задаче будет являться количество таких точек. Если начальная или конечная точка линии будет иметь хотя бы одну целочисленную координату, то ее тоже надо учитывать.

Формат входных данных
Каждый тест в этой задаче будет содержать nn запросов. 1≤n≤100. Натуральное число nn будет записано в первой строке. Далее в nn строках записаны запросы. Каждый запрос располагается в отдельной строке и состоит из четырех чисел x1, y1,x2, y2, которые задают координаты двух точек. Точки не совпадают. Координаты могут быть целыми или вещественными числами не более чем с 2 знаками после точки. Координаты не превосходят 10^9 по абсолютной величине. Если координата является целым числом, то ее запись не содержит десятичной точки.

Формат выходных данных
Требуется вывести ответы на запросы по одному ответу в каждой строке.

Следующие рисунки поясняют ответ к тесту. Обратите внимание, что никакой фрагмент линии не может лежать на сетке, так как в этом случае количество точек с целочисленной координатой будет бесконечно большим.

Sample Input:
2
-2 -0.5 0.5 1.5
0 -2 0 2
Sample Output:
3
5

@iVan22822 · 08.11.2021, 00:34

кто-нибудь решил?????

@Temaaaaaaaaaaa · 08.11.2021, 07:37

iVan22822, видимо нет

@Gdez · 08.11.2021, 10:29

Алгоритм похоже:
1. - определить количество точек с "...хотя бы одной целой координатой...";
2. - "спустить" точки в нижний левый угол;
3. - ответ = максимум из модулей разницы координат ( x2 - x1; y2 - y1 ) плюс п.1

@Zeropus1 · 08.11.2021, 10:32

а как переделать в код)

@Федялвл · 08.11.2021, 11:18

Gdez Этого не достаточно. На этот алгоритм все предыдущие коды написаны, выше по теме. Нужно учесть граничные условия. Когда первая точка например только не целые координат и вторая тоже. В этом случае плюс 1 не надо делать.
Или линия между точка идет строго по координатной сетке, а так не должно быть, нужно сдвигать.
И возможно что то еще, что не позволяет пройти все тесты.

@Zeropus1 · 08.11.2021, 11:22

уже осталось пол часа до конца, значит все

@Gdez · 08.11.2021, 12:15

Федялвл, попробуй

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from math import ceil
num = int(input())
points =[list(map(float, input().split())) for _ in range(num)]
res = []
fun1 = lambda x: int(x) == x
fun2 = lambda x: int(x) - fun1(x)*(x>0) - (not fun1(x))*(x<0)
for p in points:
    print(*[fun2(i) for i in p])
    c = fun1(p[0]) or fun1(p[1])
    c += fun1(p[2]) or fun1(p[3])
    c += max(abs(fun2(p[2]) - fun2(p[0])),
             abs(fun2(p[3]) - fun2(p[1])))
    res.append(c)
 
print(*res, sep='\n')

@Федялвл · 08.11.2021, 20:43

Gdez Поздно

В 12:00 олимпиада закрылась. И уже не проверить. Тестовик не работает

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.

@Artemchek11 4 / 4 / 0 Регистрация: 12.04.2020 Сообщений: 56

	Простая задача 05.11.2021, 15:40. Показов 14166. Ответов 27 Метки нет (Все метки) В этой задаче не будет длинного условия и простого решения. Все будет наоборот. Требуется провести непрерывную линию произвольного вида из точки с координатами (x1,y1) в точку с координатами (x2,y2) так, чтобы минимизировать количество точек на этой линии, в которых хотя бы одна координата является целым числом. Ответом к задаче будет являться количество таких точек. Если начальная или конечная точка линии будет иметь хотя бы одну целочисленную координату, то ее тоже надо учитывать. Формат входных данных Каждый тест в этой задаче будет содержать nn запросов. 1≤n≤100. Натуральное число nn будет записано в первой строке. Далее в nn строках записаны запросы. Каждый запрос располагается в отдельной строке и состоит из четырех чисел x1, y1,x2, y2, которые задают координаты двух точек. Точки не совпадают. Координаты могут быть целыми или вещественными числами не более чем с 2 знаками после точки. Координаты не превосходят 10^9 по абсолютной величине. Если координата является целым числом, то ее запись не содержит десятичной точки. Формат выходных данных Требуется вывести ответы на запросы по одному ответу в каждой строке. Следующие рисунки поясняют ответ к тесту. Обратите внимание, что никакой фрагмент линии не может лежать на сетке, так как в этом случае количество точек с целочисленной координатой будет бесконечно большим. Sample Input: 2 -2 -0.5 0.5 1.5 0 -2 0 2 Sample Output: 3 5 0

@iVan22822 -18 / 0 / 0 Регистрация: 06.11.2021 Сообщений: 15
	08.11.2021, 00:34
	кто-нибудь решил????? 0

@Temaaaaaaaaaaa 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 6
	08.11.2021, 07:37
	iVan22822, видимо нет 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	08.11.2021, 10:29
	Алгоритм похоже: 1. - определить количество точек с "...хотя бы одной целой координатой..."; 2. - "спустить" точки в нижний левый угол; 3. - ответ = максимум из модулей разницы координат ( x2 - x1; y2 - y1 ) плюс п.1 0

@Zeropus1 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 21
	08.11.2021, 10:32
	а как переделать в код) 0

@Федялвл 1 / 0 / 0 Регистрация: 14.05.2021 Сообщений: 9
	08.11.2021, 11:18
	Gdez Этого не достаточно. На этот алгоритм все предыдущие коды написаны, выше по теме. Нужно учесть граничные условия. Когда первая точка например только не целые координат и вторая тоже. В этом случае плюс 1 не надо делать. Или линия между точка идет строго по координатной сетке, а так не должно быть, нужно сдвигать. И возможно что то еще, что не позволяет пройти все тесты. 0

@Zeropus1 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 21
	08.11.2021, 11:22
	уже осталось пол часа до конца, значит все 0

@Федялвл 1 / 0 / 0 Регистрация: 14.05.2021 Сообщений: 9
	08.11.2021, 20:43
	Gdez Поздно В 12:00 олимпиада закрылась. И уже не проверить. Тестовик не работает 0