Я решал задачку «Покупка футболок», но оказалось, что она работает очень медленно. Причин я не могу понять, так как не слишком хорошо знаю питон. Но одно я понимаю точно, что это странно, так как оно имеет хорошую ассимптотику и не должно долго работать.
n = int(raw_input())
price = [int(value) for value in raw_input().split(' ')]
front = [1 << (int(value) - 1) for value in raw_input().split(' ')]
back = [1 << (3 + int(value) - 1) for value in raw_input().split(' ')]
result = {}
for index in range(0, n):
if not(front[index] + back[index] in result):
result[front[index] + back[index]] = [price[index]]
else:
result[front[index] + back[index]].append(price[index])
for item in result:
result[item] = sorted(result[item])
cust = int(raw_input())
fav = [1 << (int(value) - 1) for value in raw_input().split(' ')]
index = 0
for itemCust in fav:
minValue = 2000000000
minItem = -1
for item in result:
priceValue = result[item]
if (item & itemCust != 0 or item & (itemCust << 3) != 0) and len(priceValue) > 0 and priceValue[0] < minValue:
minValue = priceValue[0]
minItem = item
if minItem != -1:
result[minItem] = result[minItem][1:]
print minValue
else:
print -1
Комментарий по задаче. У нас есть пары чиселок от 1 до 3 (футболки). Есть запросы (покупатели) в виде одной чиселки от 1 до 3, которым важно, чтобы среди пар чиселок (футболок) была хотя бы одна такая же, как и у них.
Для решения мы кидаем все футболки в мапу, кодируя их следующим образом. Каждая футболка -- это бит-число из 2х единиц. Первые 3 единицы отвечают первой чиселке из пары. Вторые 3 единицы отвечают второй чиселке из пары.
1 1 --> 100100 (т.е. 1ый бит и (1 + 3)ый бит)
1 2 --> 100010 (т.е. 1ый бит и (2 + 3)ый бит)
3 2 --> 001010 (т.е. 3ий бит и (2 + 3)ый бит)
и т.д.
Собственно, для каждого бинарного кода заведём мапу и будем хранить список цен, отсортированных в порядке убывания. После чего переберём всех покупателей поочереди и будем выбирать за 6 шагов самую подходящую футболку.
dict
и сортировках.