Форум программистов, компьютерный форум, киберфорум
Наши страницы
Python для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Varwa
0 / 0 / 0
Регистрация: 06.01.2019
Сообщений: 2
1

Карта сокровищ

06.01.2019, 12:12. Просмотров 662. Ответов 2
Метки нет (Все метки)

На пиратской карте отмечено 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
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2019, 12:12
Ответы с готовыми решениями:

Сбор сокровищ
Через две недели защита курсовой. У меня игра, сбор сокровищ. Хочу в три уровня. На клик мыши...

Остров сокровищ!!!
Здравствуйте, уважаемые обитатели форума!!!) У меня к вам огромнейшая просьба..помогите...

Поиск сокровищ
Программу надо сделать с input.txt/output.txt.! Капитан Флинт зарыл клад на Острове сокровищ. Он...

Остров сокровищ
Капитан Флинт зарыл клад на Острове сокровищ. Есть описание, как найти клад. Описание состоит из...

программа в Pascal Abc Вывод координат сокровищ из файла и расставить сокровища по экрану
Написать программу вывода координат сокровищ из файла и расставить сокровища по экрану

2
CyberGame
146 / 33 / 14
Регистрация: 27.07.2018
Сообщений: 298
Завершенные тесты: 1
06.01.2019, 12:57 2
Varwa,
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)
If i help you, no forget press button 'Thanks'
0
8Observer8
3442 / 1871 / 328
Регистрация: 05.10.2013
Сообщений: 5,671
Записей в блоге: 140
10.01.2019, 20:12 3
When I start solve these tasks I write a unit test, like this:

test_treasure.py

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import unittest
 
class TestTreasure(unittest.TestCase):
 
    def test_one_treasure(self):
        # Arrange
        treasure = Treasure()
        input = [(15, 16)]
        expectedAmount = 1
 
        # Act
        actualAmount = treasure.GetAmount(input)
 
        # Assert
        self.assertEqual(expectedAmount, actualAmount)
I run it using command:

python -m unittest
I see the error message in the terminal:

treasure = Treasure()
NameError: name 'Treasure' is not defined
I define the Treasure class:

treasure.py

Python
1
2
3
class Treasure:
    def GetAmount(self, input):
        return -1
And import it to test_treasure.py

Python
1
2
3
import unittest
 
from treasure import Treasure
Run test:
python -m unittest
I see:

Python
1
2
    self.assertEqual(expectedAmount, actualAmount)
AssertionError: 1 != -1
I start to implement a logic to make my first test pass. If you want you can to write the logic and add second test.

Добавлено через 15 минут
You can make the test pass like this:

treasure.py

Python
1
2
3
4
5
class Treasure:
    def GetAmount(self, input):
        if len(input) == 1:
            return 1
        return -1
I run test and see that test is pass:
> python -m unittest
.
----------------------------------------------------------------------
Ran 1 test in 0.001s

OK
Add the second test with two treasures. Expected amount is equal to 2 in the second test:

test_treasure.py:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import unittest
 
from treasure import Treasure
 
class TestTreasure(unittest.TestCase):
 
    def test_one_treasure(self):
        # Arrange
        treasure = Treasure()
        input = [(15, 16)]
        expectedAmount = 1
 
        # Act
        actualAmount = treasure.GetAmount(input)
 
        # Assert
        self.assertEqual(expectedAmount, actualAmount)
 
    def test_two_treasures(self):
        # Arrange
        treasure = Treasure()
        input = [(15, 16), (16, 18)]
        expectedAmount = 2
 
        # Act
        actualAmount = treasure.GetAmount(input)
 
        # Assert
        self.assertEqual(expectedAmount, actualAmount)
Run tests:

python -m unittest
See the result:

Python
1
2
3
test_treasure.py", line 29, in test_two_treasures
    self.assertEqual(expectedAmount, actualAmount)
AssertionError: 2 != -1
We need to pass test again. This is a process of TDD (Test-Driven Development)
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2019, 20:12

Правда ли, что в материнской плате уже встроена звуковая карта и сетевая карта?
У меня возник вопрос, говорят, что в материнской плате уже встроена звуковая карта и сетевая карта....

SD-карта. Как снять блокировку, если карта не блокировалась
Карта используется в фотике. Если стоит в фотике, то невозможно снимать, просматривать отснятое...

Раз - карта, два - карта. Много карт
Здравствуйте. Пару - тройку месяцев тому купил я новый комп(стационарный) i7 7700 3,6 Гц, 8...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.