Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.
This article is "005 --- 009 All Search: All Enumeration to Reduce the Number of Streets by Ingenuity".
[006. Sumitomo Mitsui Trust Bank Programming Contest 2019 D --Lucky PIN] was a little difficult. 007 and 009 can be difficult if you don't have a vector.
A, B, C, X, Y = map(int, input().split())
answer_1 = A * X + B * Y #When buying all at A and B
answer_2 = C * 2 * max(X, Y) #If you buy everything in C
# answer_3:A first,When buying B and then supplementing the rest with C
# answer_4:Buy C first and then the rest A,When supplementing with B
if X > Y:
answer_3 = A * Y + B * Y + C * (X - Y) * 2
answer_4 = A * (X - Y) + C * Y * 2
else:
answer_3 = A * X + B * X + C * (Y - X) * 2
answer_4 = B * (Y - X) + C * X * 2
answer = min(answer_1, answer_2, answer_3, answer_4)
print(answer)
To buy at the cheapest price, it is enough to try the following 4 ways.
The answer is to find the minimum value after calculating these four amounts.
import itertools
def find_index(l, x): #In the built-in function index, if it is not found, an error will occur.-Fixed to return 1
if x in l:
return l.index(x)
else:
return -1
if __name__ == "__main__":
N = int(input())
S = [int(c) for c in input()]
table = list(range(10))
count = 0
for p in itertools.product(table, repeat=3): #Allow duplication 1~Arrange three numbers of 9
target = list(p)
s1_index = find_index(S, target[0])
if s1_index == -1:
continue
s1 = S[s1_index+1:]
s2_index = find_index(s1, target[1])
if s2_index == -1:
continue
s2 = s1[s2_index+1:]
s3_index = find_index(s2, target[2])
if s3_index == -1:
continue
count += 1
print(count)
This answer is not good.
If you mainly search for the character string S, the maximum length of S is 30,000, and if you try all the methods to select three from here, it will be on the order of about 10 ** 12, so I will think of a different method.
If you think about how to select three numbers from 0 to 9 by allowing duplicate numbers instead of the main character string S, it will be in the order of 10 ** 3, so I feel like I can go if I think mainly about this.
The policy is
itertools.product
is.
import itertools
n = int(input())
dots = [tuple(map(int, input().split())) for _ in range(n) ]
dots_set = set(dots)
#Think of an ABCD square
max_area = 0
for A, B in itertools.combinations(dots, 2):
Ax, Ay = A
Bx, By = B
Cx, Cy = Bx - (By - Ay), By + (Bx - Ax)
Dx, Dy = Ax - (By - Ay), Ay + (Bx - Ax)
if (Cx, Cy) in dots_set and (Dx, Dy) in dots_set:
area = (Ax - Bx) ** 2 + (Ay - By) ** 2
max_area = max(max_area, area)
print(max_area)
If 2 points are determined from the given coordinates, 4 points and area for creating the square will be determined. Therefore, as a policy, we will try all the methods of selecting two points from the coordinates and judge whether or not a square can be created.
itertools
(let's call them A and B)is.
When determining whether points C and D are included in a given set of coordinates, the list in dots
usually results in `TLE```, so ` Must be
dots_set = set (dots) `` `.
N = int(input())
A = []
B = []
for _ in range(N):
a, b = map(int, input().split())
A.append(a)
B.append(b)
min_time = float('inf')
for a in A:
for b in B:
total_time = 0
for i in range(N):
total_time += abs(a - A[i]) + abs(A[i] - B[i]) + abs(b - B[i])
min_time = min(min_time, total_time)
print(min_time)
It seems best to place the entrance and exit in either the given Ai or Bi (probably there are other best places ...). So try all of A and B to find the one that will give you the least amount of time.
m = int(input()) #m is the number of stars in the constellation you are looking for
target = [tuple(map(int, input().split())) for _ in range(m)] #Coordinates of the constellation you want to find
n = int(input()) #n is the number of stars in the photo
stars = [tuple(map(int, input().split())) for _ in range(n)] #Coordinates of stars on the photo
set_stars = set(stars)
target_vector = [] #Hold relative position as vector
for i in range(m-1):
y1, x1 = target[i]
y2, x2 = target[i+1]
vector_y, vector_x = y2 - y1, x2 - x1
target_vector.append((vector_y, vector_x))
#Add vectors for all stars.
target_y, target_x = 0, 0
for star in stars:
y, x = star
new_y, new_x = y, x
count = 0
for vector in target_vector:
y_vector, x_vector = vector
new_y += y_vector
new_x += x_vector
if (new_y, new_x) not in set_stars:
break
count += 1
if count == m - 1: #If there are stars after all vector addition, the starting coordinates are the source of the answer
target_y, target_x = y, x
break
#The answer is the coordinates relative to the first coordinates of the target
answer_y = target_y - target[0][0]
answer_x = target_x - target[0][1]
print(answer_y, answer_x)
I did the subscripts y and x in the reverse of the problem setting, but there is an answer.
The policy is
break
, if there is, count the number of vectors used, and if it can be used
m-1``` times, the constellation is reproduced.is.
Recommended Posts