# Lösningar skolkval 2018
Skicka in era lösningar till vår träningstävling! 👇👇
https://po2punkt0.kattis.com/contests/h26nju

I dokumentet så länkar jag även till problemen på po kattis, du kan skicka in lösningar till problemen där även om vår träningstävling tagit slut.

## Tunnelbanan
https://po2punkt0.kattis.com/problems/tunnelbaneplatser

Vi kallar deltagarnas gruppstorlekarna för a1, a2, a3, a4 utifrån problembeskrivningen. Vi kan se vissa saker:
1. Alla a4 grupper måste ha sin egna sätesgrupp.
2. Alla a3 grupper måste ha en sätesgrupp, men en a1 grupp kan sitta med.
3. Alla a2 grupper kan antingen dela en sätesgrupp med en a2 grupp eller två a1 grupper. Vi vet att a1 grupper är mer flexibla så vi låter a2 grupper sitta med a2 grupper så länge det går. Om det är ett udda antal a2 grupper låter vi två a1 grupper sitta med den sista
4. Om det finns a1 grupper kvar efter detta så låter vi dem ta upp så många sätesgrupper de behöver.

import math

a1, a2, a3, a4 = [int(i) for i in input().split()]

#Här gör vi (1)
ans = a4

#Här gör vi (2)
ans += a3
a1 = max(a1-a3, 0)

#Här gör vi (3)
ans += a2//2
#Fallet om det finns ett udda antal a2 grupper
if a2 % 2 == 1:
    ans += 1
    a1 = max(a1 - 2, 0)

#Här gör vi (4)
ans += math.ceil(a1/4)

#Och så måste man skriva ut sitt svar :)
print(ans)

#### Tidskomplexitet
Vi gör ∼fyra beräkningar, det blir konstant tid, alltså O(1).

## Köpa matta
https://po2punkt0.kattis.com/problems/kopamatta

Ett matte-igt problem!

#### Testfallsgrupp 1:
När $M, N < 1000$ så kan vi ha en lösning med kvadratisk tidskomplexitet. Alltså, vi kan prova alla kombinationer av tal som är mellan $1-1000$. För varje par kollar vi om produkten (alltså antalet rutor) är inom rätt räckvidd. För alla som är det så sparar vi paret med minst differens.

M, N = [int(i) for i in input().split()]

ans = (1, M)

for a in range(1, M + 1):
    for b in range(1, N+1):
        if a*b >= M and a*b <= N:
            if abs(a-b) < abs(ans[0] - ans[1]):
                ans = (a, b)


print(min(ans[0], ans[1]), max(ans[0], ans[1]))

#### Testfallsgrupp 2
Nu har vi $10^{11} \leq M < 10^{12}$ och $M = N$. Vi inser att $\sqrt{M}$ är inte så stort, som max en miljon. Vi kan alltså kolla på alla tal från $1$ till $\sqrt{M}$.

Vi vet dessutom att för ett par av tal $a,b$ där $a \cdot b = M$ så har vi att antingen $a$ eller $b$ måste vara mindre (eller lika med) $\sqrt{M}$.

Jag börjar bakifrån, och räknar från $\sqrt{M}$ till $1$. Det första talet ($x$) jag hittar som delar $M$ kommer att vara svaret! Mina två tal blir då alltså $x$ och $M/x$. När jag räknar bakifrån så börjar jag med talen som har så liten differens som möjligt.

import math

M, N = [int(i) for i in input().split()]
for i in reversed(range(math.floor(math.sqrt(N))+1)):
    if N % i == 0:
        print(min(i, N//i), max(i, N//i))
        exit()

#### Full lösning
Lösningen är liknande som i **testfallsgrupp 2**. Problemet är att nu har vi en räckvidd av antal rutor som är acceptabla. Det vi gör är:
* Tittar på varje tal mellan $1$ och $\sqrt{M}$ (kallar vårt nuvarande tal för $i$)
* Vi kollar:
* Finns det något tal inom rätt räckvidd som är delbart med $i$? Om nej så skippar vi $i$ för $i$ kan inte vara en sidlängd på mattan. (Hur vet vi om detta är fallet? Jo om $N//i < M$).

**Annars har vi tre möjliga fall (se bild nedan):**
1. **$i$:s kvadrat är inom rätt räckvidd**, alltså, $N \leq i^2 \leq M$. Då vet vi att vi kan skapa en kvadratisk matta med sidlängd $i$! Detta är svaret, för inget kan vara mer kvadratiskt än en kvadrat!
2. **$i$:s kvadrat är större än vår räckvidd**. Vi vill ha ett tal $x$ så att $i \cdot x$ är inom vår räckvidd och differensen är så liten som möjligt. Vi vet att $x <i$ (eftersom $i^2$ är för stort). Vi vill alltså välja det största möjliga $x$:et som funkar. Detta kommer att vara $N//i$.
3. **$i$:s kvadrat är mindre än vår räckvidd.** Vi vill ha ett tal $x$ så att $i \cdot x$ är inom vår räckvidd och differensen är så liten som möjligt. Vi vet att $i < x$. Vi vill alltså välja det minsta möjliga $x$:et som funkar. Detta kommer att vara $ceil(M/x)$.

Exempel där $i = 3$. vi ser att $i^2 = 9$. De röda rutorna är alla rutor som är delbara med $3$ (alltså alla tal som kan vara vår mattstorlek när en sida har längd $3$). I fall 1 väljer vi kvadraten. I fall 2 väljer vi den röda rutan som är längst till höger inom rätt räckvidd. I fall 3 väljer vi den röda rutan längst till vänster inom rätt räckvidd.

#### Så vad är vår lösning?
Om det finns röda rutor inom rätt räckvidd så kollar vi om kvadraten är inom räckvidden, kollar på den högraste röda rutan inom rätt räckvidd och den vänstraste röda rutan inom rätt räckvidd. Ett av dessa tre fall kommer innehålla den bästa lösningen där en av sidlängderna är $i$. Vi jämför alla fall med vår tidigare bästa lösning, och sparar den bästa. Vi gör detta för alla $i$:n!

import math

M, N = [int(i) for i in input().split()]

ans = (1, M)
for i in range(1, math.ceil(math.sqrt(N))):
    hi = N//i
    lo = math.ceil(M/i)
    if hi*i < M and lo*i > N:
        continue

    if i*i >= M and i*i <= N:
        print(i, i)
        exit()

    if abs(i- hi) < abs(ans[0]-ans[1]):
        ans = (i, hi)
    if abs(i- lo) < abs(ans[0]-ans[1]):
        ans = (i, lo)

print(min(ans[0], ans[1]), max(ans[0], ans[1]))

## Brickor lösning 1
https://po2punkt0.kattis.com/problems/brickor

Det kluriga här är att hitta optimala drag: "i den här positionen vill vi alltid göra så här...". Sen är programmeringsbiten ganska lätt!

#### Huvudidé
Vi kan se:
1. Om vi har två svarta brickor på rad kan vi göra dem båda vita i ett drag.
2. Om vi har en enskild svart bricka med vita brickor runt om så kan vi fortfarande göra den vit! Vi hittar en till svart bricka med vita brickor runt omkring (t ex fallet"VSVVSV"):
* Ett drag att plocka svarta bricka nr 1 (och en närliggande vit bricka) till kanten (så att den nya svarta brickan ligger ytterst)
* Ett drag att plocka svarta bricka nr 2 (och en närliggande vit bricka) till kanten så att den nya svarta brickan nr 2 ligger brevid den nya svarta brickan nr 1.
* Ett drag för att plocka ut de två svarta brickorna, göra dem båda vita och lägga dem på kanten.

Alltså för att göra två närliggande svarta brickor vita (**1.**) tar 1 drag. Att göra två ej närliggande svarta brickor vita (**2.**) tar 3 drag.

Vi gör:
* (**1.**) så länge vi kan. Vi kan göra (**1.**) lika många gånger som vi har par av 'S' brevid varandra (där varje 'S' ingår i max ett par).
* (**2.**) för resterande 'S'. Alla resterande 'S' kommer att ha vita brickor runt sig. Detta kommer ta $3 \cdot {antalSkvar} / 2$ det vill säga $1.5 * antalSkvar$.

Vi kallar antaler par av 'S' vi har för $p$ och antalet enkla 'S' vi har för $e$. Detta kommer ta $p + 1.5 \cdot e$ antal drag!

#### Specialfall!
Huvudidén antar att vi börjar med vita brickor på kanterna. Tänk att vi har situation "SVSV"! Detta är situation (**2.**) men det tar inte tre drag! Detta kan vi göra på två drag eftersom ett av våra drag som var att få en svart bricka till kanten är redan klart! Så efter att vi har tagit bort så många par av svarta brickor vi kan (**1.**) så kollar vi:
* Har vi en svart bricka på vänster kanten? Då blir svaret ett drag mindre!
* Har vi en svart bricka på högerkanten? Då blir svaret ett drag mindre!
* Annars? Då är svaret detsamma!

Meen... vi har ett specialfall för specialfallen! Tänk fallet "SVVVS". Vi kan inte lösa detta på ett drag! Om vi har svarta brickor på kanterna och alla i mitten är vita (det finns minst en vit bricka i mitten), så kommer detta ta ett drag mer än förväntat!

#### Tidskomplexitet
Vi kan se att `count()` har tidskomplexitet O(N) och `replace()` har tidskomplexitet O(N+M)där N är längden på den långa strängen och M är längden på substrängen som man vill byta ut (i vårt fall så har vi M = 2). Sedan gör vi några operationer med konstant tidskomplexitet. Vår totala tidskomplexitet blir alltså linjär till antalet brickor!

s = input()

ans = s.count("SS")
s = s.replace("SS","")
ans += int(s.count('S')*1.5)

if s[0] == 'S':
    ans -= 1
if s[-1] == 'S':
    ans -= 1
if  s[0] == 'S' and s[-1] == 'S' and s.count('S') == 2:
    ans += 1

print(ans)

## Brickor lösning 2
Vi gör en BFS (breadth first search)! Lättare idé men jobbigare kod :)

På varje position finns antingen en vit eller svart bricka. Vi kan se att det finns som mest $2^{15} \approx 30000$ olika sätt vårt spelbräde kan se ut på. Det är inte så mycket!

Vi säger att våra noder är alla unika sätt vårt spelbräde kan se ut. Om vi börjar med spelbrädet `"SVS"` så skulle våra noder vara: `"SVS"`, `"VSS"`, `"SSV"` och `"VVV"`. Vi säger att det finns en kant från nod a till nod b om vi kan gå från a till b genom att göra ett drag.


Nu gör vi en BFS för att hitta den kortaste vägen (alltså färst antal drag) från vår startposition till positionen då alla brickor är vita.

#### Tidskomplexitet
Låt $n$ vara längden på strängen. Vi har ungefär $2^n$ noder och ungefär $2^n \cdot n$ kanter. Tidskomplexiteten för en BFS är O(antalkanter + antalnoder). I koden under använder jag en dictionary vilket gör tidskomplexiteten till O($2^n \cdot n \cdot log(n)$). För $n = 15$ blir detta ungefär $500$ $000$ operationer.

from queue import Queue

inp = input()

def change(x):
    if x == 'S':
        return 'V'
    return 'S'

def move(s, a, left_or_right):
    s = list(s)
    if left_or_right == 0:
        s.insert(0, change(s[a]))
        #Eftersom vi har lagt till ett element längst fram i listan kommer vårt element på index a+1 nu ha index a+2
        s.insert(1, change(s[a+2]))
        s.pop(a+3)
        s.pop(a+2)
    else:
        s.append(change(s[a]))
        s.append(change(s[a+1]))
        s.pop(a+1)
        s.pop(a)
    s = "".join(s)
    return s


q = Queue()
q.put(inp)
dp = {inp: 0}

while not q.empty():
    curr = q.get()
    for i in range(len(inp)-1):
        for lr in range(2):
            nasta = move(curr, i, lr)
            if nasta not in dp:
                dp[nasta] = dp[curr] +1
                q.put(nasta)

end_pos = "".join(["V" for i in inp])
print(dp[end_pos])

## MeTube
https://po2punkt0.kattis.com/problems/dutub

Ett DP (dynamisk programmerings) problem!

#### Huvudidé
Vi ser att det finns få kategorier, som flest 10! Alla kombinationer av kategorier blir $2^{10} \approx 1000$. Det är inte så mycket!

Vi börjar med att vår enda kategorikombination är att vi inte har sett något och att detta tar 0 minuter. Sedan kan vi tänka att vi funderar på varje film en i taget. Vad händer om vi inte ser på film $i$? Jo då har vi exakt samma kategorikombinationer som innan. För varje kategorikombination ($k$) som vi har skaffat kan vi nu ställa oss frågan, vad händer om vi ser dessa filmer och film $i$?
* Vi kommer då att ha sett alla kategorier i $k$ och alla kategorier som $i$ har!
* Detta kommer ta tiden att se på $k$ plus tiden att se på film $i$.
* Om vi inte har sparat denna nya kategorikombination så sparar vi den nu!
* Om vi redan har sparat en sådan så upptaderar vi tiden den tar till den tid som är kortast!

#### Tidskompexitet
För $n$ antal filmer och $k$ kategorier får detta tidskomplexitet $O(2^k \cdot n)$.

#a är en sträng med kategorier vi sett.
#Om vi ser en video med kategorierna b så har vi nu sett kategorierna: sammanfoga(a,b)
#Dessa kategorier kommer vara i bokstavsordning
def sammanfoga(a, b):
    for i in b:
        if i not in a:
            a += i
    return "".join(sorted(a))

n = int(input())
#lista: en lista av listor som sparar inputen.
#Varje element i lista kommer innehålla [tid, kategorier] för en video
lista = []
#bokstaver: en sträng som innehåller alla kategorier i bokstavsordning
bokstaver = ""

for i in range(n):
    lista.append(input().split())
    lista[i][0] = int(lista[i][0])
    for i in lista[i][1]:
        bokstaver = sammanfoga(bokstaver, i)

#dp: en dictionary där vi sparar alla kombinationer vi har hittills
#dp[sträng_med_kategorier_i_bokstavsordning] = minsta_minuter_att_ha_sett_dessa_kategorier
#Börjar med att lägga in möjligheterna vi har efter första filmen från "lista"
#Vi har 2 möjligheter, antingen så har vi sett filmen, eller så har vi inte sett filmen
dp= {"": 0, "".join(sorted(lista[0][1])): lista[0][0]}

#Vi går igenom filmerna i "lista" var för sig. 
#För varje kategorikombination som vi redan har  i "dp", så kan vi kombinera det med att se vår nuvarande film.
#Vi lägger till den nya katerogikombinationen och antal minuter vi använt i "to_add"

for i in range(1, n):
    to_add = []
    for curr in dp:
        curr_time = dp[curr]
        nasta = ''.join(sammanfoga(curr, lista[i][1]))
        nastatid = lista[i][0] + curr_time
        to_add.append((nasta, nastatid))

    #Nu kollar vi om dessa kombinationer är bättre än de vi redan har! Om de är bättre så uppdaterar vi "dp"!
    for x in to_add:
        if x[0] not in dp:
            dp[x[0]] = x[1]
        elif dp[x[0]] > x[1]:
            dp[x[0]] = x[1]

print(dp[bokstaver])