First, if the left edge is vertical, there are 3 ways to paint. If it is horizontal, there are 6 ways with 3 * 2. Next, if the vertical comes next to the vertical, it should be different from the previous vertical color, so 2 If the horizontal comes next to the vertical, if you decide from the upper side, there are two ways because it should be different from the vertical, and then there is only one other way on the lower side, so there are two ways. Horizontal If the vertical comes next to, there is only one way because two colors have already been decided. When the horizontal comes next to the horizontal, there are three ways as follows.
0022 0011 0011
1100 1100 1122
All you have to do is add it up.
N = int(input())
S1 = input()
S2 = input()
if S1[0] == S2[0]:
result = 3
else:
result = 6
x = 0
W = len(S1)
while x < W:
if S1[x] == S2[x]:
if x + 1 == W:
break
result *= 2
result %= 1000000007
x += 1
else:
if x + 2 == W:
break
if S1[x + 2] != S2[x + 2]:
result *= 3
result %= 1000000007
x += 2
print(result)
There is no limit to the minimum movement, so go from the upper left to the right, go down one to the left when you reach the end, go down one to the right when you reach the end, and so on. Then, if it is an odd number, if you repeat sending to the next square, it will be either an even number or only the last square will be an odd number.
H, W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]
result = []
y = 0
while y < H:
x = 0
while x < W:
if a[y][x] % 2 == 1:
if x == W - 1:
if y == H - 1:
break
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 2, x + 1))
a[y + 1][x] += 1
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 1, x + 2))
a[y][x + 1] += 1
x += 1
if y == H - 1:
break
y += 1
x = W - 1
while x >= 0:
if a[y][x] % 2 == 1:
if x == 0:
if y == H - 1:
break
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 2, x + 1))
a[y + 1][x] += 1
else:
result.append('%d %d %d %d' % (y + 1, x + 1, y + 1, x))
a[y][x - 1] += 1
x -= 1
y += 1
print(len(result))
print('\n'.join(result))
ABC096D - Five, Five Everywhere
Divide by 5 and arrange the remaining prime numbers in ascending order as you need. Any combination will be a multiple of 5.
N = int(input())
result = []
sieve = [0] * (55555 + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, 55555 + 1):
if sieve[i] != 0:
continue
if i % 5 == 1:
result.append(i)
if len(result) == N:
break
sieve[i] = i
for j in range(i * i, 55555 + 1, i):
if sieve[j] == 0:
sieve[j] = i
print(*result)
The color combination is 30 </ sub> C 3 </ sub> = 4060, so you can do a full search, but since N ≤ 500, if you do it without thinking * O * (4060 × 500) 2 </ sup> ≒ 10 10 </ sup>) and TLE is inevitable. (I + j) If you group by the remainder of% 3 and count the original colors, * O * (4060) × 30 × 3 ≒ 3.7 × 10 5 </ sup>), so it is solved.
from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
a = [[0] * C for _ in range(3)]
for y in range(N):
for x in range(N):
t = ((x + 1) + (y + 1)) % 3
a[t][c[y][x] - 1] += 1
result = float('inf')
for b in permutations(range(C), 3):
t = 0
for i in range(3):
for j in range(C):
t += a[i][j] * D[j][b[i]]
result = min(result, t)
print(result)
I had an intuition that sorting by b was a pain when I was in KEYENCE Programming Contest 2020 B --Robot Arms. It's a scheduling problem. After that, I should remove as many bridges as necessary, but at first I recorded and solved the bridges removed by Segment Tree. Well, * O * ( I can solve it with N </ i> log N </ i>), but I noticed from the explanation PDF that it was okay to remember only the last removed one.
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
result = 0
t = -1
for a, b in ab:
a, b = a - 1, b - 1
if a <= t < b:
continue
result += 1
t = b - 1
print(result)
If you decide the 1st and 2nd animals, you will have 1 choice after that, and if you make a mistake, you will know that there is a contradiction at the end. So, if you do the 1st and 2nd with 4 patterns of round robin of S, W Good. * O * (4 × 10 5 </ sup>), so there is no problem in terms of computational complexity.
from itertools import product
N = int(input())
s = input()
swap = {'S': 'W', 'W': 'S'}
for a, b in product('SW', repeat=2):
t = [None] * N
t[0] = a
t[1] = b
for i in range(1, N - 1):
if t[i] == 'S':
if s[i] == 'o':
t[i + 1] = t[i - 1]
elif s[i] == 'x':
t[i + 1] = swap[t[i - 1]]
elif t[i] == 'W':
if s[i] == 'o':
t[i + 1] = swap[t[i - 1]]
elif s[i] == 'x':
t[i + 1] = t[i - 1]
if t[N - 1] == 'S':
if s[N - 1] == 'o' and t[N - 2] != t[0]:
continue
elif s[N - 1] == 'x' and t[N - 2] == t[0]:
continue
elif t[N - 1] == 'W':
if s[N - 1] == 'o' and t[N - 2] == t[0]:
continue
elif s[N - 1] == 'x' and t[N - 2] != t[0]:
continue
if t[0] == 'S':
if s[0] == 'o' and t[N - 1] != t[1]:
continue
elif s[0] == 'x' and t[N - 1] == t[1]:
continue
elif t[0] == 'W':
if s[0] == 'o' and t[N - 1] == t[1]:
continue
elif s[0] == 'x' and t[N - 1] != t[1]:
continue
print(''.join(t))
exit()
print(-1)
Recommended Posts