Какое максимальное количество точек сможет добавить в свой маршрут Капитан Крюк?

@Pavlin234 · Регистрация: 12.03.2017

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

На пиратской карте отмечено N точек, в которых зарыты сокровища. Каждая точка задана координатами (xi, yi). Координаты указаны в километрах.

Команда Капитана Крюка хочет составить маршрут, чтобы собрать как можно больше кладов. Однако есть ограничение: для любых двух соседних точек маршрута (xi, yi) и (xj, yj) координаты xi и xj могут различаться только последней цифрой, и координаты yi и yj тоже могут различаться только последней цифрой. Например, после точки (15, 10) они могут отправиться в точку (18, 16), а вот из точки (14, 68) в точку (19, 71) пройти уже не получится — ведь 68 и 71 различаются не только последней цифрой. Из точки (5, 12) в точку (13, 14) попасть тоже нельзя, так как числа 5 и 13 отличаются в разряде десятков.

По заданным координатам определите, какое максимальное количество точек сможет добавить в свой маршрут Капитан Крюк.
Формат ввода

В первой строке указано число N (1 ≤ N ≤ 10 000) — количество точек, отмеченных на карте сокровищ.

В следующих N строках содержатся пары координат: xi и yi — координаты i-ой точки. Координаты — целые числа не меньше нуля и не больше 1 000 000 000. Гарантируется, что совпадающих точек в списке нет.
Формат вывода

Выведите одно число — максимальное количество точек, которое Капитан Крюк сможет посетить по маршруту, построенному по описанным правилам.
Пример
Ввод
9
10 18
17 15
25 21
0 21
1 16
25 29
24 24
8 26
10 20
Вывод
3

Jabbson · 15.02.2018, 20:32

Не по теме:

Вы забыли добавить волшебное слово "быстро!" ;)

@geargoose · 20.12.2019, 19:41

Решение от пользователя CyberGame (Огромное ему спасибо):

Python

num = int(input())
point = []
for i in range(num):
    num, m = input().split()
    point.append((int(num), int(m)))
result = []
while len(point) > 0:
    same_route = []
    a = point[0][0] // 10 * 10
    b = point[0][1] // 10 * 10
    for i in range(0, len(point)):
        x = point[i][0] // 10 * 10
        y = point[i][1] // 10 * 10
        if x == a and y == b:
            same_route.append(point[i])
    result.append(same_route)
    point = list(filter(lambda p: p not in same_route, point))
quant = [len(result[i]) for i in range(len(result))]
qmax = max(quant)
print(qmax)

@AnkerreknA · 08.01.2020, 13:34

Python

def symbols(c, d):
    if int(c) < 10:
        a = 0
    else:
        a = c[:-1]
    if int(d) < 10:
        b = 0
    else:
        b = d[:-1]
    e = str(a) + str(b)
    return (e)
 
 
dict = {}
lst = []
for i in range(int(input())):
    koord = input().split()
    a = symbols(koord[0], koord[1])
    if a in dict:
        dict[a] += 1
    else:
        dict.update({a: 1})
for i in dict:
    lst.append(dict[i])
lst.sort()
print(lst[-1])

@Pavlin234 10 / 59 / 21 Регистрация: 12.03.2017 Сообщений: 514
		1
	Какое максимальное количество точек сможет добавить в свой маршрут Капитан Крюк? 11.02.2018, 10:12. Показов 15238. Ответов 22 Метки нет (Все метки) На пиратской карте отмечено N точек, в которых зарыты сокровища. Каждая точка задана координатами (xi, yi). Координаты указаны в километрах. Команда Капитана Крюка хочет составить маршрут, чтобы собрать как можно больше кладов. Однако есть ограничение: для любых двух соседних точек маршрута (xi, yi) и (xj, yj) координаты xi и xj могут различаться только последней цифрой, и координаты yi и yj тоже могут различаться только последней цифрой. Например, после точки (15, 10) они могут отправиться в точку (18, 16), а вот из точки (14, 68) в точку (19, 71) пройти уже не получится — ведь 68 и 71 различаются не только последней цифрой. Из точки (5, 12) в точку (13, 14) попасть тоже нельзя, так как числа 5 и 13 отличаются в разряде десятков. По заданным координатам определите, какое максимальное количество точек сможет добавить в свой маршрут Капитан Крюк. Формат ввода В первой строке указано число N (1 ≤ N ≤ 10 000) — количество точек, отмеченных на карте сокровищ. В следующих N строках содержатся пары координат: xi и yi — координаты i-ой точки. Координаты — целые числа не меньше нуля и не больше 1 000 000 000. Гарантируется, что совпадающих точек в списке нет. Формат вывода Выведите одно число — максимальное количество точек, которое Капитан Крюк сможет посетить по маршруту, построенному по описанным правилам. Пример Ввод 9 10 18 17 15 25 21 0 21 1 16 25 29 24 24 8 26 10 20 Вывод 3 0

Jabbson
	15.02.2018, 20:32 Какое максимальное количество точек сможет добавить в свой маршрут Капитан Крюк? #21
	Не по теме: Вы забыли добавить волшебное слово "быстро!" ;) 0

	08.01.2020, 13:34