CSES - Datatähti 2020 alku - Results
Submission details
Task:Mastot
Sender:The_Anthony
Submission time:2019-10-12 15:09:25 +0300
Language:CPython3
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED11
#2ACCEPTED34
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2ACCEPTED0.02 s1, 2, 3details
#3ACCEPTED0.02 s1, 2, 3details
#4ACCEPTED0.02 s1, 2, 3details
#5ACCEPTED0.02 s1, 2, 3details
#6ACCEPTED0.02 s1, 2, 3details
#7ACCEPTED0.02 s1, 2, 3details
#8ACCEPTED0.02 s1, 2, 3details
#9ACCEPTED0.02 s1, 2, 3details
#10ACCEPTED0.02 s1, 2, 3details
#11ACCEPTED0.02 s1, 2, 3details
#12ACCEPTED0.02 s1, 2, 3details
#13ACCEPTED0.02 s1, 2, 3details
#14ACCEPTED0.02 s1, 2, 3details
#15ACCEPTED0.02 s1, 2, 3details
#16ACCEPTED0.02 s1, 2, 3details
#17ACCEPTED0.02 s1, 2, 3details
#18ACCEPTED0.02 s1, 2, 3details
#19ACCEPTED0.02 s1, 2, 3details
#20ACCEPTED0.02 s1, 2, 3details
#21ACCEPTED0.40 s2, 3details
#22ACCEPTED0.03 s2, 3details
#23ACCEPTED0.04 s2, 3details
#24ACCEPTED0.06 s2, 3details
#25ACCEPTED0.07 s2, 3details
#26ACCEPTED0.24 s2, 3details
#27ACCEPTED0.41 s2, 3details
#28ACCEPTED0.07 s2, 3details
#29ACCEPTED0.07 s2, 3details
#30ACCEPTED0.07 s2, 3details
#31ACCEPTED0.07 s2, 3details
#32ACCEPTED0.07 s2, 3details
#33ACCEPTED0.07 s2, 3details
#34--3details
#35ACCEPTED0.24 s3details
#36ACCEPTED0.48 s3details
#37--3details
#38--3details
#39--3details
#40--3details
#41--3details
#42--3details
#43--3details
#44--3details
#45--3details
#46--3details

Code

from sys import setrecursionlimit
setrecursionlimit(10**6)


def syöttö():
    etäisyys = int(input())
    kantamasyöte = input().split()
    kantamat = map(int, kantamasyöte)
    hintasyöte = input().split()
    hinnat = map(int, hintasyöte)

    # Lähetin + Mastot
    mastot = {0: {"kantama": next(kantamat), "hinta": 0}}
    for i in range(etäisyys-1):
        kantama, hinta = next(kantamat), next(hinnat)
        mastot[i+1] = {"kantama": kantama, "hinta": hinta}

    return mastot, etäisyys


def pienin_hinta(mastot, etäisyys):
    """
    :param mastot: dic
    :param etäisyys: int
    :return:
    """
    mastotuple = tuple(mastot)
    hinnatmuisti = {}

    def seuraavat_mastot(nyt_masto, mastot, etäisyys, hinnatmuisti):
        """
        done: Laita nyt_masto:n hinta muistiin.
        done: Laskee hinnat mukaan
        :param nyt_masto: n:nnes masto
        :param mastot: dic
        :param etäisyys: int
        :param hinnatmuisti: Annetun tolpan halvin hinta siitä eteenpäin.
        :return:
        """
        # Onko muistissa?
        if nyt_masto in hinnatmuisti:
            return hinnatmuisti[nyt_masto]

        # Nykyisen maston kantama
        kantama = mastot[nyt_masto]["kantama"]

        # Jos kantamaa riittää vastaanottimeen, palautetaan hinta
        if nyt_masto + kantama >= etäisyys:
            hinnatmuisti[nyt_masto] = mastot[nyt_masto]["hinta"]
            return mastot[nyt_masto]["hinta"]

        # Tarkista seuraavat mastot
        seuraavista_pienimmät_hinnat = []
        for seuraava_masto in mastotuple[mastotuple.index(nyt_masto) + 1:]:
            # Masto menee kantaman yli
            if nyt_masto + kantama < seuraava_masto:
                break

            seuraavista_pienimmät_hinnat.append(
                seuraavat_mastot(seuraava_masto, mastot, etäisyys, hinnatmuisti)
            )
        # min-funktio ottaa kahden tai useamman parametrin
        if len(seuraavista_pienimmät_hinnat) > 1:
            seuraavista_pienin_hinta = min(seuraavista_pienimmät_hinnat)
        # Mastosta ei pääse minnekään
        elif len(seuraavista_pienimmät_hinnat) == 0:
            # Palautetaan jotain tyhmää
            return float("inf")
        else:
            seuraavista_pienin_hinta = seuraavista_pienimmät_hinnat[0]

        # Siis nykyisen maston kohdalla hinta on
        # nykyisen_maston_hinta = seuraavista_pienin_hinta + mastot[nyt_masto]["hinta"]
        hinnatmuisti[nyt_masto] = seuraavista_pienin_hinta + mastot[nyt_masto]["hinta"]

        return seuraavista_pienin_hinta + mastot[nyt_masto]["hinta"]

        # hinnatmuisti[nyt_masto] = min(seuraavista_pienimmät_hinnat) + mastot[nyt_masto]["hinta"]
        # return min(seuraavista_pienimmät_hinnat) + mastot[nyt_masto]["hinta"]

    mastojenhinnat = []
    for läheinen_masto in mastotuple[1:]:
        # Masto menee kantaman yli
        if mastot[0]["kantama"] < läheinen_masto:
            break
        mastojenhinnat.append(seuraavat_mastot(läheinen_masto, mastot, etäisyys, hinnatmuisti))

    # if len(mastojenhinnat) > 1:
    return min(mastojenhinnat)
    # else:
    #     return mastojenhinnat[0]


def binäärihaku(lista, haettava):
    """
    Etsii listasta alkion, jonka luku on juuri haettavaa alempi.

    :param lista: Lista lukuja
    :param haettava: Kokonaislukuna haettava kohde
    :return: Haettavan kokonaisluvun alkio
    """
    # Suoritetaan binäärihaku välillä [a,b], missä a ja b ovat listan
    # alkioita
    a = 0
    b = len(lista) - 1

    # Varmistetaan, että haettava on edes listan keskellä
    if haettava <= lista[0]:
        return 0
    if lista[-1] < haettava:
        return len(lista)

    while True:
        keski = (a + b) // 2

        # Onko haettavan ympärillä vain kaksi indeksiä
        if b - a <= 1:
            return b

        # Haettava on välillä [a,keski[
        if haettava <= lista[keski]:
            b = keski
            # print("<-")
        # Haettava on välillä ]keski,b]
        elif lista[keski] < haettava:
            a = keski
            # print("->")


def poista_turhat_mastot(mastot):
    """
    Poistaa turhat mastot.
    Masto on turha, jos
    1. on olemassa taaempana masto, joka kantaa samaan kohtaan tai pidemmälle
       kuin turha
    2. takana oleva masto ei ole kalliimpi kuin tämä masto
    """
    # for masto in mastot:
    masto = 0
    mastoja = len(mastot)
    tarkistettavat_mastot = [(masto + mastot[masto]["kantama"], masto)]
    # Tulee olemaan muotoa [(kantama, masto), (kantama, masto), ...]
    while mastoja - 2 != masto:
        # Seuraava masto
        masto += 1

        kantama = masto + mastot[masto]["kantama"]
        # Ei tarkastella mastoja, joiden kantama ei riitä
        while tarkistettavat_mastot[0][0] <= masto:
            del tarkistettavat_mastot[0]
            # Ei tarkistettavia mastoja
            if len(tarkistettavat_mastot) == 0:
                break

        if tarkistettavat_mastot:
            # Haetaan indeksi
            indeksi = binäärihaku(next(zip(*tarkistettavat_mastot)), kantama)

            # Tarkistetaan, onko tämä masto turha.
            # 1) Maston kantama ei ole paras
            turha = False
            if len(tarkistettavat_mastot) - 1 != indeksi:
                for _, tarkistus_masto in tarkistettavat_mastot[indeksi+1:]:
                    # 2) Maston hinta on korkeampi
                    tämä_masto_hinta = mastot[masto]["hinta"]
                    toinen_masto_hinta = mastot[tarkistus_masto]["hinta"]
                    if tämä_masto_hinta >= toinen_masto_hinta:
                        # Masto on täysin turha
                        del mastot[masto]
                        turha = True
                        break
            if turha:
                continue
        else:
            indeksi = 0

        # Tallennetaan nykyisen maston kantama
        if indeksi == len(tarkistettavat_mastot):
            tarkistettavat_mastot.append((kantama, masto))
        else:
            tarkistettavat_mastot.insert(indeksi, (kantama, masto))


def main():
    mastot, etäisyys = syöttö()
    # Lähettimen kantama riittää
    if mastot[0]["kantama"] >= etäisyys:
        print(0)
    else:
        poista_turhat_mastot(mastot)
        hinta = pienin_hinta(mastot, etäisyys)
        print(hinta)


main()

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
6
2 2 3 1 2 4
4 1 3 4 2

correct output
3

user output
3

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 1
1

correct output
1

user output
1

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
2 1
1

correct output
0

user output
0

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 2 1
1 2

correct output
1

user output
1

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 2 1
2 1

correct output
1

user output
1

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
4
1 1 1 1
1000000000 1000000000 10000000...

correct output
3000000000

user output
3000000000

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
19000000000

user output
19000000000

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
1 1 2 1 1 1 2 1 1 2 1 1 1 2 1 ...

correct output
4609157377

user output
4609157377

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
20 20 20 20 20 20 20 20 20 20 ...

correct output
0

user output
0

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
19
16 10 9 17 1 16 19 4 18 13 5 3...

correct output
8424700

user output
8424700

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
2 4 3 4 4 4 4 1 1 3 4 2 1 3 3 ...

correct output
2817777553

user output
2817777553

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
4 4 4 4 3 4 1 3 4 1 1 4 1 3 1 ...

correct output
3020673750

user output
3020673750

Test 13

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
5 1 3 4 2 4 2 2 5 1 3 3 2 4 1 ...

correct output
2064735712

user output
2064735712

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
8 1 2 6 8 6 9 1 4 9 9 8 6 3 3 ...

correct output
378551508

user output
378551508

Test 15

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
5 2 8 9 4 10 1 8 9 9 8 1 7 8 9...

correct output
457149308

user output
457149308

Test 16

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
7 6 2 6 1 3 10 4 6 3 5 2 2 10 ...

correct output
471575451

user output
471575451

Test 17

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
6 2 2 3 8 7 2 10 8 9 6 3 10 5 ...

correct output
620685913

user output
620685913

Test 18

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
4 5 3 8 2 8 5 9 6 3 7 5 1 6 9 ...

correct output
1132427688

user output
1132427688

Test 19

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
15 9 7 18 3 20 19 20 17 16 16 ...

correct output
333300698

user output
333300698

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

input
20
19 18 17 16 15 14 13 12 11 10 ...

correct output
660514815

user output
660514815

Test 21

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4999000000000

user output
4999000000000

Test 22

Group: 2, 3

Verdict: ACCEPTED

input
5000
5000 5000 5000 5000 5000 5000 ...

correct output
0

user output
0

Test 23

Group: 2, 3

Verdict: ACCEPTED

input
5000
4999 4998 4997 4996 4995 4994 ...

correct output
576616581

user output
576616581

Test 24

Group: 2, 3

Verdict: ACCEPTED

input
5000
3343 3711 2568 137 2621 3850 4...

correct output
671570

user output
671570

Test 25

Group: 2, 3

Verdict: ACCEPTED

input
5000
119 203 420 133 175 334 461 10...

correct output
85700253

user output
85700253

Test 26

Group: 2, 3

Verdict: ACCEPTED

input
5000
8 6 2 1 4 5 7 3 4 2 1 10 3 6 6...

correct output
193210576015

user output
193210576015

Test 27

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 1 2 2 1 2 2 1 1 1 2 1 2 2 ...

correct output
1576581428593

user output
1576581428593

Test 28

Group: 2, 3

Verdict: ACCEPTED

input
5000
300 1937 2136 770 429 2388 197...

correct output
3584707

user output
3584707

Test 29

Group: 2, 3

Verdict: ACCEPTED

input
5000
949 46 29 2237 2413 36 42 1162...

correct output
3210354

user output
3210354

Test 30

Group: 2, 3

Verdict: ACCEPTED

input
5000
1557 1727 1787 360 1698 2423 1...

correct output
3177107

user output
3177107

Test 31

Group: 2, 3

Verdict: ACCEPTED

input
5000
484 1991 2309 1326 1901 2426 8...

correct output
4863018

user output
4863018

Test 32

Group: 2, 3

Verdict: ACCEPTED

input
5000
1833 459 1994 2050 272 31 708 ...

correct output
2876923

user output
2876923

Test 33

Group: 2, 3

Verdict: ACCEPTED

input
4999
530 2248 1916 859 2394 1403 24...

correct output
5194452

user output
5194452

Test 34

Group: 3

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
199999000000000

user output
(empty)

Test 35

Group: 3

Verdict: ACCEPTED

input
200000
200000 200000 200000 200000 20...

correct output
0

user output
0

Test 36

Group: 3

Verdict: ACCEPTED

input
200000
199999 199998 199997 199996 19...

correct output
819945000

user output
819945000

Test 37

Group: 3

Verdict:

input
200000
9036 179861 197509 187949 9444...

correct output
59563

user output
(empty)

Test 38

Group: 3

Verdict:

input
200000
357 1516 141 399 860 1591 544 ...

correct output
247414000

user output
(empty)

Test 39

Group: 3

Verdict:

input
200000
10 4 1 7 1 8 8 4 8 2 2 4 2 4 8...

correct output
7789595210075

user output
(empty)

Test 40

Group: 3

Verdict:

input
200000
1 2 1 1 1 1 2 1 2 2 1 2 2 2 2 ...

correct output
62777824801872

user output
(empty)

Test 41

Group: 3

Verdict:

input
200000
9473 42975 69773 60909 9354 20...

correct output
76814

user output
(empty)

Test 42

Group: 3

Verdict:

input
200000
31087 18493 14158 65333 95850 ...

correct output
180614

user output
(empty)

Test 43

Group: 3

Verdict:

input
200000
66563 17340 2293 5101 35636 96...

correct output
56642

user output
(empty)

Test 44

Group: 3

Verdict:

input
200000
4005 35201 22254 56956 49098 7...

correct output
287201

user output
(empty)

Test 45

Group: 3

Verdict:

input
200000
99266 91407 53419 70750 93505 ...

correct output
54045

user output
(empty)

Test 46

Group: 3

Verdict:

input
199999
23098 95019 27998 22880 40713 ...

correct output
184595

user output
(empty)