[PYTHON] yukicoder contest 249 Participation record

yukicoder contest 249 Participation record

A 1057 Nice day

The first day cannot be a wonderful day because there is no cake I ate the day before. So if the number of shortcakes and chocolate cakes is different, eat the larger one on the first day. After that, you can eat alternately.

A, B = map(int, input().split())

if A == B:
    print(2 * A - 1)
else:
    print(min(A, B) * 2)

B 1058 Nice Number

Since the number to be calculated is not a prime number and does not have a divisor of 2 or more and 10 ^{5 </ sup> or less, in short, the product of two prime numbers larger than 10 5 </ sup> is in ascending order. ..}

So, find such a prime number appropriately,

>>> for i in range(10**5, 10**5+1000):
...   flag = True
...   for j in range(2, int(sqrt(i))+1):
...     if i % j == 0:
...       flag = False
...       break
...   if flag:
...     print(i)
...
100003
100019
100043
100049
100057
100069
100103
100109
100129
100151
...

Find the product in ascending order,

>>> result = []
>>> for i in [100003,100019,100043,100049,100057,100069,100103,100109,100129,100151]:
...   for j in [100003,100019,100043,100049,100057,100069,100103,100109,100129,100151]:
...     result.append(i*j)
...
>>> print(sorted(set(result))[:10])
[10000600009, 10002200057, 10003800361, 10004600129, 10005200147, 10006000171, 10006200817, 10006800931, 10007200207, 10007601083]

I've embedded it in the source code.

N = int(input())

print([1, 10000600009, 10002200057, 10003800361, 10004600129, 10005200147, 10006000171, 10006200817, 10006800931, 10007200207][N - 1])

C 1059 Nice set

I couldn't break through.

First, the cost is 0 or 1. Because the pair of i, i + 1 is cost 1. After that, if you think that it is over if you drop the one that costs 0 like the Eratosthenes sieve, it is not. For example, if there are 2, 3, and 6, the cost of the pair of 2 and 3 will be 1, but the cost of the pair of 3 and 6 will eliminate 3 and the cost of the pair of 2 and 6 will be 6 at 0. You can achieve a nice set at zero cost. In other words, you can erase things that have a common common multiple at zero cost. Then you can solve the problem with Union Find as to how many Unions there are.

from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[i] += parent[j]
    parent[j] = i


setrecursionlimit(10 ** 6)

L, R = map(int, input().split())

parent = [-1] * (R + 1)
for i in range(L, R):
    if find(parent, i) != i:
        continue
    for j in range(i * 2, R + 1, i):
        unite(parent, i, j)
print(sum(1 for i in range(L, R + 1) if find(parent, i) == i) - 1)