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

@Varwa · Регистрация: 06.01.2019

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

@CyberGame · 06.01.2019, 12:57

Varwa,

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)

If i help you, no forget press button 'Thanks'

@8Observer8 · 10.01.2019, 20:12

When I start solve these tasks I write a unit test, like this:

test_treasure.py

Python

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

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

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)

@Varwa 0 / 0 / 0 Регистрация: 06.01.2019 Сообщений: 2
		1
	Карта сокровищ 06.01.2019, 12:12. Просмотров 148. Ответов 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

Опции темы