Concours AtCoder pour débutants Défi des questions passées 6

Concours AtCoder pour débutants Défi des questions passées 6

ABC090D - Remainder Reminder

Si le reste de la division de a par b est égal ou supérieur à K, il est confirmé que b est égal ou supérieur à K + 1. Le reste de la division par b est égal à 0..b-1, et le nombre de K ou plus apparaissant dans ce cycle est b. - K. Puisque a est N ou moins, le nombre de cycles est N / b. Après cela, il faut penser au reste du cycle, mais puisque N commence à 1, le cycle est 1, 2, ..., Notez que l'ordre est b --1, 0. Autrement dit, si N% b est n, alors 1, 2, ..., n et le nombre de K = 0 et K = 1 est le même.

N, K = map(int, input().split())

result = 0
for b in range(K + 1, N + 1):
    result += (N // b) * (b - K) + max(N % b - max(K - 1, 0), 0)
print(result)

ABC115D - Christmas

Le nombre de couches du hamburger de niveau L et le nombre de galettes qu'il contient sont N ≤ 50, il peut donc être calculé facilement (et la formule à calculer peut être facilement dérivée sans tourner la boucle). Après cela, se répète jusqu'à ce que X soit épuisé. Si vous rencontrez un hamburger de niveau L et que le X restant est supérieur au hamburger de niveau L, réduisez X de ce nombre de couches, ajoutez ce nombre de galettes au comptoir et, s'il est plus petit, le hamburger de niveau L -1. Allez à l'intérieur.

N, X = map(int, input().split())


def f(N, X):
    result = 0

    if X >= 1:
        X -= 1
    else:
        return result

    if X >= 2 ** ((N - 1) + 2) - 3:
        X -= 2 ** ((N - 1) + 2) - 3
        result += 2 ** ((N - 1) + 1) - 1
    else:
        return result + f(N - 1, X)

    if X >= 1:
        X -= 1
        result += 1
    else:
        return result

    if X >= 2 ** ((N - 1) + 2) - 3:
        X -= 2 ** ((N - 1) + 2) - 3
        result += 2 ** ((N - 1) + 1) - 1
    else:
        return result + f(N - 1, X)

    if X >= 1:
        X -= 1
    else:
        return result

    return result


print(f(N, X))

ABC053D - Card Eater

Si vous avez 3 cartes de duplication ou plus, vous pouvez réduire 2 duplications sans réduire le nombre de types de cartes quel que soit votre choix 3. Si vous avez 2 cartes de duplication, vous pouvez acheter 2 cartes de duplication d'un côté. Une carte de duplication peut réduire la duplication à 0 sans réduire le nombre de types de cartes. S'il existe une carte de duplication, deux cartes de duplication et une autre carte peuvent réduire le nombre de types de cartes. Peut être décrémenté de 1, mais la duplication peut être réduite à 0. Après tout, la réponse est le nombre de types de cartes moins 1 si le nombre de duplications est impair et 0 s'il est pair.

N = int(input())
A = list(map(int, input().split()))

t = len(set(A))
if (len(A) - t) % 2 == 0:
    print(t)
else:
    print(t - 1)

ABC072D - Derangement

Si p i </ sub> = i, échangez simplement avec p i </ sub> et p i + 1 </ sub> et comptez le nombre de fois. P Échangez avec le p N-1 </ sub> précédent uniquement lorsque N </ sub> = N. Puisque p i </ sub> est une séquence de 1..N, Si vous échangez, ce sera toujours p i </ sub>! = I, et bien sûr p i + 1 </ sub>! = I, donc p i + 1 </ sub> est toujours correct. Il est clair qu'il est préférable de le faire dans l'ordre pour que les p i </ sub> = i consécutifs qui peuvent être traités en une fois ne soient pas traités en deux fois.

N = int(input())
p = list(map(int, input().split()))

result = 0
for i in range(N - 1):
    if p[i] != i + 1:
        continue
    result += 1
    p[i], p[i + 1] = p[i + 1], p[i]
if p[N - 1] == N:
    result += 1
print(result)

ABC040D - À propos des mesures contre le vieillissement des routes

Il est évident d'utiliser une taille UnionFind par tous les moyens, puis il suffit de trier par année et d'ajouter des routes dans l'ordre pour voir combien de villes les gens peuvent aller et venir.

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[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 5)

N, M = map(int, input().split())
roads = []
for _ in range(M):
    a, b, y = map(int, input().split())
    roads.append((y, a - 1, b - 1))
Q = int(input())
citizen = []
for i in range(Q):
    v, w = map(int, input().split())
    citizen.append((w, v - 1, i))

parent = [-1] * N

roads.sort(reverse=True)

results = [None] * Q
t = 0
for c in sorted(citizen, reverse=True):
    while t < M and roads[t][0] > c[0]:
        unite(parent, find(parent, roads[t][1]), find(parent, roads[t][2]))
        t += 1
    results[c[2]] = -parent[find(parent, c[1])]
print(*results, sep='\n')

ABC129E - Sum Equals Xor

Lorsque L = XXXX, le nombre de paires satisfaisant la condition est n. Lorsque L = 1XXXX, le nombre de paires satisfaisant la condition est compris entre 0 et 1111 et le nombre de paires satisfaisant la condition et le nombre de paires satisfaisant entre 10 000 et 1XXXX. À propos, si YYYY + ZZZZ = YYYY x ou ZZZZ, alors 1YYYY + ZZZZ = 1YYYY x ou ZZZZ est valable, et YYYY + 1ZZZZ = YYYY xor 1ZZZZ est également valable. 2 * n.

Le nombre de paires qui satisfont la condition lorsque L = 1 est (0,0), (0,1), (1,0), qui est de 3. Le nombre de paires qui satisfont la condition lorsque L = 11 est comme décrit ci-dessus. La somme de 0 à 1 = 3 et de 10 à 11 = 2 * 3 donne 3 * 3 = 9. De même, L = 111 devient 9 * 3 = 27 et L = 1111 devient 3 4 </ sup>. = 81. En conséquence, le nombre de paires qui satisfont la condition lorsque L = 1XXXX est 2 * n + 3 4 </ sup>.

À ce stade, vous pouvez calculer la réponse un chiffre à la fois à partir du dernier chiffre.

L = input()

result = 1
t = 1
for c in L[::-1]:
    if c == '1':
        result = result * 2 + t
        result %= 1000000007
    t *= 3
    t %= 1000000007
print(result)

Recommended Posts

Concours AtCoder pour débutants Défi des questions passées 6
Concours AtCoder pour débutants Défi des questions passées 4
Concours AtCoder pour débutants Défi des questions passées 9
Concours AtCoder pour débutants Défi des questions passées 7
Concours AtCoder pour débutants Défi des questions passées 10
Concours AtCoder Débutants Défi des questions passées 5
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Défi des questions passées 1
Examen des questions passées d'AtCoder (12 / 6,7)
Examen des questions passées d'AtCoder (12/5)
Défiez AtCoder
AtCoder Beginner Contest 066 Revoir les questions précédentes
# 2 Les débutants en Python défient AtCoder! ABC085C --Otoshidama
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes