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 "015 --017 Full Search: Permutation Full Search".
Permutation problems can often be solved by using itertools
well.
permutaions
Whencombination
Whenproduct
I use it a lot, so I learned this area by trying various sample data.
N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]
total_distance = 0
count = 0
for start in range(N-1):
for end in range(start+1, N):
start_x, start_y = towns[start]
end_x, end_y = towns[end]
total_distance += ((end_x - start_x)**2 + (end_y - start_y)**2)**0.5
count += 1
# factor = math.factorial(N)Then
# answer = total_distance * (factor * (N - 1) / count) /It becomes a factor and the formula can be transformed as follows
answer = total_distance * ((N - 1) / count)
print(answer)
There are various calculation methods here.
To be honest, I enumerate all the arrangements with permutation
, find the distance in all, and take the average.
I think this will still work, but I tried it as an answer with a little less calculation.
The policy is
(N -1) / number of combinations
`.is The above 2 is derived from the expression transformation left as a comment in the code.
import itertools
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
count = 1
for p in itertools.permutations(range(1, N+1)):
if p == P:
count_P = count
if p == Q:
count_Q = count
count += 1
ans = abs(count_P - count_Q)
print(ans)
Believe that python's itertools.permutations
will list them in lexicographic order (!) I'll write it straightforwardly.
The policy is
itertools.permutations
`count_P``` and
`count_Q``` where P and Q match.is.
itertools
If you don't have one, you'll have to think a little more, but it's convenient, so I used it without thinking.
import itertools
import copy
def flag_queen_load(grid, r, c):
for i in range(1, 8):
if 0 <= c+i and c+i < 8:
grid[r][c+i] = -1 #right
if 0 <= c-i and c-i < 8:
grid[r][c-i] = -1 #left
if 0 <= r+i and r+i < 8:
grid[r+i][c] = -1 #under
if 0 <= r-i and r-i < 8:
grid[r-i][c] = -1 #Up
if 0 <= r-i and r-i < 8 and 0 <= c+i and c+i < 8:
if grid[r-i][c+i] == 9:
continue
grid[r-i][c+i] = -1 #Upper right
if 0 <= r+i and r+i < 8 and 0 <= c+i and c+i < 8:
if grid[r+i][c+i] == 9:
continue
grid[r+i][c+i] = -1 #Lower right
if 0 <= r+i and r+i < 8 and 0 <= c-i and c-i < 8:
if grid[r+i][c-i] == 9:
continue
grid[r+i][c-i] = -1 #Lower left
if 0 <= r-i and r-i < 8 and 0 <= c-i and c-i < 8:
if grid[r-i][c-i] == 9:
continue
grid[r-i][c-i] = -1 #upper left
grid[r][c] = 9 #myself
return grid
if __name__ == "__main__":
k = int(input())
grid = [[0] * 8 for _ in range(8)]
for _ in range(k):
r, c = map(int, input().split())
grid = flag_queen_load(grid, r, c)
# 0~Try all 7 numbers in a permutation
#Think of the generated permutations as row numbers for subscripts and column numbers for elements
for perm in itertools.permutations(range(8)):
copy_grid = copy.deepcopy(grid) #Use a new grid every time
count = 0
for row, col in enumerate(perm):
if copy_grid[row][col] == -1:
break
if copy_grid[row][col] == 9:
continue
copy_grid[row][col] = 9
copy_grid = flag_queen_load(copy_grid, row, col)
count += 1
if count == 8 - k: # 8-break if you put k queens
break
#Answer display
for row in range(8):
for col in range(8):
if copy_grid[row][col] == -1:
print('.', end='')
else:
print('Q', end='')
print()
Originally I wrote it in Numpy, but can't AOJ use Numpy? I couldn't submit it due to an error, so I rewrote it with a normal list. The policy is
`flag_queen_load ()`
that updates the board when a queen is placed at a certain coordinate
(r, c)
.`break```, if it is 9, it is OK, so
`continue```is.
The function ``` flag_queen_load ()` `` is dirty, so I should have written it a little cleaner.
Recommended Posts