Оптимизация кода для задания "Карта сокровищ"

@PhantomTomato · Регистрация: 13.06.2020

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

Всем привет. Ребята, помогите, пожалуйста. Начал изучать python недавно, так что опыта пока в нём нет. Есть небезызвестная задача "Карта сокровищ" от Яндекс. Вот её условие:

"На пиратской карте отмечено 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"

Так вот. Я написал код для решения этой задачи, но бот Яндекса пишет мне, что превышен лимит времени выполнения программы (> 1 секунды).
Сам код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
num = int(input())
points = [input().split() for i in range(num)]
max_st = 0
for i in range(num):
    count = 0
    a, b = int(points[i][0]) // 10, int(points[i][1]) // 10
    for j in range(num):
        if ((int(points[j][0]) // 10) == a) & ((int(points[j][1]) // 10) == b):
            count += 1
    if count > max_st:
        max_st = count
print(max_st)

Помогите, пожалуйста, с оптимизацией. Можно было бы забить на эту программу, но очень хочется разобраться, как её можно оптимизировать.

@eaa · 13.06.2020, 18:29

А причем тут python? Вам нужно учить алгоритмы.

@Semen-Semenich · 13.06.2020, 18:33

почему бы сразу не работать с числами

Python
1
2
3
4
5
6
7
8
9
10
11
12
num = int(input())
points =[list(map(int,input().split())) for _ in range(num)]
max_st = 0
for i in range(num):
    count = 0
    a, b = points[i][0] // 10, points[i][1] // 10
    for j in range(num):
        if (points[j][0] // 10 == a) & (points[j][1] // 10 == b):
            count += 1
    if count > max_st:
        max_st = count
print(max_st)

@PhantomTomato · 14.06.2020, 03:52 **[ТС]**

eaa, возможно, вы правы. Но я пришёл в программирование с мыслью "Если я хочу программировать, то мне нужно изучить язык программирования". Буду рад, если подскажете, где можно побольше узнать про алгоритмы, а также какой алгоритм обеспечит наилучшую оптимизацию кода по времени выполнения для данной задачи.
Semen-Semenich, спасибо, возьму на заметку, что так можно делать. Однако, эта конструкция не дала никаких изменений во времени выполнения кода.

@u235 · 14.06.2020, 07:45

Еще вариант:

Python
1
2
3
4
5
6
7
8
9
num = int(input())
points =[list(map(int,input().split())) for _ in range(num)]
d=dict()
for i in range(num):
    square = points[i][0] // 10, points[i][1] // 10
    if square not in d:
        d[square]=0
    d[square]+=1
print(max(d.values()))

@PhantomTomato · 14.06.2020, 09:17 **[ТС]**

u235, благодарствую. Ваш вариант работает быстрее)

@eaa · 14.06.2020, 19:40

Python
1
2
3
4
5
6
d = dict()
for _ in range(int(input())):
    x, y = map(int, input().split())
    key = x // 10, y // 10
    d[key] = d.get(key, 0) + 1
print(max(d.values()))

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.06.2020, 18:29
	А причем тут python? Вам нужно учить алгоритмы. 0

@PhantomTomato 0 / 0 / 0 Регистрация: 13.06.2020 Сообщений: 3
	14.06.2020, 03:52 [ТС]
	eaa, возможно, вы правы. Но я пришёл в программирование с мыслью "Если я хочу программировать, то мне нужно изучить язык программирования". Буду рад, если подскажете, где можно побольше узнать про алгоритмы, а также какой алгоритм обеспечит наилучшую оптимизацию кода по времени выполнения для данной задачи. Semen-Semenich, спасибо, возьму на заметку, что так можно делать. Однако, эта конструкция не дала никаких изменений во времени выполнения кода. 0

@PhantomTomato 0 / 0 / 0 Регистрация: 13.06.2020 Сообщений: 3
	14.06.2020, 09:17 [ТС]
	u235, благодарствую. Ваш вариант работает быстрее) 0

Оптимизация кода для задания "Карта сокровищ"

Решение