180962025-09-29 16:33:12algoproDNS szakaszok száma (75 pont)pypy3Elfogadva 75/7564ms23616 KiB
# UUID: 9f683df9-23eb-4c6e-b6b0-897382d598c5
n = int(input())
dns = input()

a_db = [0] * (n+1)
for i in range(n):
    a_db[i+1] = a_db[i] + (1 if dns[i] == 'A' else 0)

utolso_g = [-1] * n
utolso = -1
for i in range(n):
    if dns[i] == 'G':
        utolso = i
    utolso_g[i] = utolso

szamlalo = 0
for i in range(n):
    if dns[i] == 'T' and utolso_g[i] != -1:
        szamlalo += a_db[utolso_g[i]]

print(szamlalo)


# Ezen lehet gyorsítani.
# Kell egy A lista, amiben minden indexre  megtudjuk, hogy előtte hány A van
# Ehhez 1x kell végigmenni a stringen.
#
# És kell egy G lista is, ami minden indexre megmondja az előtte lévő G helyet.
# (Ha nincs, akkor -1). Ez is megcsinalhato 1x vegigmenve a stringen.
#
# És végül a megoldás:
#
# Vegigmesz a stringen, és ahol T-t találsz, ott a G listából megtudjuk,
# hogy hol van előtte G, majd az A listából, hogy hány darab van.
RészfeladatÖsszpontTesztVerdiktIdőMemória
base75/75
1Elfogadva0/039ms19300 KiB
2Elfogadva0/057ms23328 KiB
3Elfogadva3/343ms19416 KiB
4Elfogadva4/443ms19396 KiB
5Elfogadva4/445ms19432 KiB
6Elfogadva4/439ms19452 KiB
7Elfogadva4/441ms19524 KiB
8Elfogadva3/339ms19508 KiB
9Elfogadva3/345ms19428 KiB
10Elfogadva4/439ms19696 KiB
11Elfogadva4/439ms19940 KiB
12Elfogadva4/443ms19772 KiB
13Elfogadva4/443ms19960 KiB
14Elfogadva4/446ms19944 KiB
15Elfogadva3/357ms23012 KiB
16Elfogadva4/456ms23016 KiB
17Elfogadva4/454ms23044 KiB
18Elfogadva4/464ms23208 KiB
19Elfogadva4/457ms23524 KiB
20Elfogadva4/464ms23520 KiB
21Elfogadva3/356ms23272 KiB
22Elfogadva4/464ms23616 KiB