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

@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()))

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@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

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

Решение