Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)

1. Purpose

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".

2. Summary

[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.

3. Main story

005 --009 All search: All enumeration to reduce the number of streets by devising

5. AtCoder Beginner Contest 095 C - Half and Half

Answer

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.

1. When buying all at A and B
2. If you buy everything in C
3. When buying up to a small quantity of A and B first and then supplementing the rest with C
4. When buying a small quantity with C first and then supplementing the rest with A and B

The answer is to find the minimum value after calculating these four amounts.

006. Sumitomo Mitsui Trust Bank Programming Contest 2019 D --Lucky PIN

Answer

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

1. Enumerate 3-digit numbers using 0-9 in itertools.product
2. Find out the index number where the number in the left digit first appears in the string S
3. Check the index number where the middle digit appears for the first time in the character string S after the index number found above.
4. Check the index number where the number in the right digit appears for the first time in the character string S after the index number found above.
5. If the index number is not found because it is 2 to 3, `` `break``` respectively

is.

007. JOI 2007 Final Selection 3-The Oldest Ruins

Answer

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.

1. List how to select 2 points from coordinates with itertools (let's call them A and B)
2. Find the remaining two points C and D when creating a square from two points
3. Determine if C, D are given and included in the set of coordinates
4. If included, find the area and record the maximum value

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) `` `.

8. Square869120Contest #6 B - AtCoder Markets

Answer

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.

009. JOI 2008 Qualifying 4-Search for constellations

Answer

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

1. Hold the desired constellation shape as a vector `` `target_vector``` (counterclockwise)
2. Move all the stars in the photo according to the vector and check if there are stars in the coordinates after the movement.
3. If there is no star, break, if there is, count the number of vectors used, and if it can be used m-1``` times, the constellation is reproduced.
4. If you can reproduce the constellation, take the difference between the coordinates that became the starting point and the first coordinates of the target constellation, and that is the answer.

is.