# Öar

En huvudinsikt i problemet är att man snabbt kan räkna ut hur många deltagare som försvinner på en viss ö om man håller koll på hur många som försvinner på de två senaste. I Python kan det vara ett tillfälle att använda följande syntax för att tilldela flera variabler samtidigt:

last_island, this_island = this_island, last_island + this_island

Summera sedan antalet deltagare som försvann på varje ö och stanna när det talet är större eller lika med det totala antalet deltagare på IOI. I övrigt är det bara att se till att man har korrekta startvärden och hanterar de väldigt små fallen där bara typ en deltagare försvinner.

# Tebryggning

För den första testgruppen finns det bara en sorts te, vilket innebär att antalet kannor är antalet deltagare delat på 10 avrundat uppåt. Ett sätt att räkna ut detta i python utan att använda flyttalsdivision och importera en avrunda-uppåt-funktion är följande:

antal_kannor = (kannstorlek + antal_personer - 1) // kannstorlek

Försök gärna förstå ovanstående om du inte sett det förr! (Notera att ```//``` i Python är heltalsdivision, alltså dela och avrunda neråt till närmaste heltal.)

För det generella fallet är det optimalt att koka fulla kannor te så långt det går innan man tvingas börja göra delvis fyllda kannor. Om det går att få ut tillräckligt många fulla kannor för att servera alla blir lösningen som ovan. Annars kan man börja med att servera te till alla som kan från de fulla kannorna. Sen får man ta en lista med hur mycket mer te man kan få ut ur varje tepåse, sortera den, och servera dem en i taget tills alla är nöjda. Ett trevligt sätt att implementera detta är med priority queue/max heap, men detta krävs självklart inte.

# Zoo

Det här är ett problem där det kan vara värt att se vilka testgrupper som finns och anpassa sin lösning till dem om man inte kommer på den fulla lösningen direkt.

### För den första testgruppen
finns det en matematisk formel: Eftersom man kan välja fritt bland alla $k$ djur i första buren och fritt bland alla $k-1$ djur som inte finns i förra buren i alla $n-1$ burar efter det finns det $k \cdot (k-1)^{n-1}$ sätt att placera djuren i den här testgruppen.

### I den andra testgruppen
är det inget särskilt som man ska anpassa sig till, men antalet djurarter och burar kan inte vara lika stort som i det generella fallet. Det håller sig så pass litet att det går att göra en brute-force-lösning där man helt enkelt går igenom och räknar alla möjligheter. Denna lösning är smidigast att göra rekursivt, även om det nog är möjligt med en massa nästlade loopar och if-satser. En sån här lösning kommer ta tid proportionellt mot antalet sätt att placera djuren, alltså är tidskomplexiteten $O(k \cdot (k-1)^{n-1})$ enligt uttrycket från testgrupp 1.

### Den tredje testgruppen
är lite mer matematiskt komplicerad men går att lösa med en kombination av kombinatorik och programmering. Till exempel genom att först hitta alla sätt att välja vilka burar som ska innehålla ett bråkigt djur, räkna hur många sätt det finns att placera övriga djur runt de bråkiga djuren med hjälp av formeln i testgrupp ett, ta det gånger antalet sätt att fördela bråkiga djurarter i burarna för bråkiga djur, och ta summan av den produkten för alla sätt att välja bråkiga burar. Det är lite knepigare att räkna på tidskomplexitet här, men det går att se att det enda som tar betydande tid är att gå igenom alla sätt att välja vilka burar som ska ha bråkiga djur, och att det finns mindre än $15 \cdot 13 \cdot 11 \cdot 9 \cdot 7 = 135135$ sätt att göra det på. Detta gör att en Python-lösning borde kunna gå igenom med marginal.

### För en full lösning
krävs dynamisk programmering, att hålla koll på och återanvända tidigare uträknade saker på ett smart sätt. I det här fallet går det att göra genom att hålla koll på antalet sätt att fördela djur i de första $a$ burarna på ett sådant sätt att den sista av dem innehåller djur $b$. Ett exempel på resultatet av sådana uträkningar finns nedan, där man till exempel kan se att det finns nio sätt att fylla alla fyra burar på ett sådant sätt att det sista djuret är E, att det inte finns något sätt att fylla två burar så att det andra är B, och att svaret i det här fallet (summan av sista kolumnen) är 18. För att fylla i tabellen börjar man med att fylla första kolumnen med ettor (fundera gärna på varför?), sedan fylla i varje kolumn efter det med hjälp av kolumnen innan. Till exempel står det en nia i ruta 4/E eftersom E kan vara intill A, C eller D och summan av deras rutor i kolumnen innan är $3+3+3=9$. Om man räknar ut vilka djur som får vara intill vilka i förväg tar det alltså upp till $K \leq 10$ operationer att fylla i var och en av de $N \cdot K \leq 15 \cdot 10$ rutorna, vilket ger en tidskomplexitet på $O(N \cdot K^2)$ vilket är tillräckligt snabbt med god marginal ($N \cdot K^2 \leq 15 \cdot 10^2 < 10^6$).

4 5 2
BE
BADC

|$b$ \\ $a$|1|2|3|4($=n$)|
|----------|-|-|-|-------|
|A |1|1|3|3 |
|B |1|0|0|0 |
|C |1|1|3|3 |
|D |1|1|3|3 |
|E |1|3|3|9 |

# Planet X
Exakt vilken information får vi från kända rutor? Vi tar ett exempel: ruta $K$ är känd och ruta $O$ är okänd. Låt dist($K$, $O$)=kortaste vägen mellan $K$ och $O$. I rutnät är avstånd så-kallat manhattanavstånd, vilket kan beräknas med dist($K$, $O$)=$|K_x-O_x|+|K_y-O_y|$. Varje gång vi tar ett steg från ruta $K$ kommer höjden att förändras med $\pm$ 1. Om ruta $K$ har höjd $h$ och $d$=dist($K$,$O$), så betyder det att höjden av $O$ är inom $[h-d, h+d]$.

Detta känns rätt i fallet om vi går kortaste vägen från $K \rightarrow O$, men kan vi inte ta en längre väg och få ett större intervall? Nej! Varje kortaste väg ger oss info som är "optimal"- om vi använder informationen från en väg som inte är kortaste, så kan denna motsäga en kortaste väg, och alla vägars info måste respekteras. Därför duger det att bara betrakta kortaste vägar.

Vi försöker nu fylla i de okända rutorna. Låt oss för varje okänd ruta $O$ beräkna intervallet som alla andra kända rutor ger. Vi har nu ett flertal intervall för värdet på $O$. Alla höjder $0 \leq h \leq 9$ som ligger innanför alla intervall är en möjlig höjd för $O$. Om det finns exakt ett möjligt $h$ har vi bestämt höjden för den rutan. Om det finns mer än en är det omöjligt att bestämma höjden entydigt.

Blir något i stilen med $O(10N^2M^2)$, vilket är snabbt nog eftersom $N$ och $M$ är jättesmå.

# Planetbacke
Detta problemet är välkänt som "longest path". I allmänhet är det svårt att lösa snabbare än $O(2^NN^2)$.

Vi vet därmed att en vanlig algoritm för longest path är för långsam. Då måste vi leta efter en särskild begräsning som gör det lösbart. I detta problemet är begränsningen som gör det lösbart att "Det finns aldrig fler än $7$ rutor i rutnätet som har samma höjd".

Detta gör att en DP kör snabbt nog. Mer exakt så behöver vi inte längre hålla koll på *alla* möjliga rutor vi kan ha besökt, utan bara de med samma höjd som rutan vi befinner oss på. Mer exakt håller vi koll på:

- x
- y
- Om vi vet x och y, så vet vi höjden av rutan vi befinner oss på. Då räcker det att hålla koll på vilka av dom upp till 7 rutorna av samma höjd som vi har besökt.

Så,
$$\text{DP[x][y][vis]=max längd}$$

Här är en implementation. Den använder ganska många trick. Vi representerar vilka rutor vi besökt (vis) som ett binärt tal. Om vi har $N$ möjliga besökta rutor finns det $2^N$ möjliga delmängder av besökta rutor. Vanligtvis hade vi velat representera detta med ett tal i intervallet $[0, 2^N-1]$. I detta fallet är vi lata: vi använder en dictionary och har ett tal mellan 0 och $2^{NM-1}$. Vi vet dock att det inte kan finnas mer än $2^7$ möjliga värden på $vis$ för ett givet par $(x,y)$. Det kanske även ser långsamt ut när vi anropar best många gånger i botten. Det går fortfarande snabbt eftersom DP:n gör att varje tillstånd kan besökas som mest en gång. Eftersom det finns $NM \cdot 2^7$ kör på programmet i $O(2^7NM)$.

n,m=[int(i) for i in input().split()]
# Change '1' to 1
grid = [[ord(c)-ord('0') for c in input()] for i in range(n)]

memo = {}

dirs = ((0,1),(1,0),(0,-1),(-1,0),(1,1),(-1,1),(1,-1),(-1,-1))
def best(r, c, vis):
    if (r,c,vis) in memo:
        return memo[(r,c,vis)]
    h = grid[r][c]

    ret = 0
    for dir in dirs:
        nr = r + dir[0]
        nc = c + dir[1]

        # We can't go outside of grid or to a higher cell
        if nr < 0 or nc < 0 or nr >= n or nc >= m or grid[nr][nc]>h:
            continue

        # Transform 2D coordinate into 1D coordinate
        ind = nr*m+nc
        # If we remain at same height
        if grid[nr][nc]==h:
            if vis & (1<<ind): # If already visited, skip
                continue
            newvis = vis | (1<<ind) # Otherwise, add that it is visited
        else:
            newvis = 1<<ind # If new height, remove old visited
        ret = max(ret, 1+best(nr,nc,newvis))
    memo[(r,c,vis)] = ret
    return ret

ans = 0
# Try every starting position
# O(NM2^7) amortized
for i in range(n):
    for j in range(m):
        ans = max(ans, best(i,j,1<<(i*m+j)))
print(ans+1)

# Cykeltävling
Problemet känns väldigt komplext. För att göra det mer angripbart behövs lite insikter. Låt R[i]=springshastigheten av person i, och C[i]=cykelhastigheten av person i.
### Insikt 1:
I en optimal lösning hoppar varje person på cykeln och sedan av som mest en gång. Intuitivt beror detta på att cykelbyten är ineffektiva, eftersom det leder till att man behöver vänta mer.
### Insikt 2:
Som en följd av insikt 1, så kommer varje person att vilja springa ett visst tag och cykla ett visst tag i en optimal lösning.
### Insikt 3:
Vi kan binärsöka över svaret. Vi kan föreställa oss att varje person börjar med en att springa, vilekt tar en viss tid. Vi kan sedan skära ner tider genom att låta de cykla istället, och vi vill minimera den största tiden. Alltså vill vi minimera den största, något som är klassiskt binärsökbart.

Hur hjälper binärsökning oss? Låt säga att vi vill kolla om svaret är $\leq mid$. Vi får en klassificering av 3 sorters personer:
1. De som hinner springa i mål. Dessa ignorerar vi
2. De som inte hinner springa i mål, och har C[i] $\leq$ R[i]. För dessa är det omöjligt att hinna i mål på $mid$ sekunder, så vi vet direkt att det inte går.
3. De som inte hinner springa i mål, och har C[i] $>$ R[i]. Vi kan nu använda matte för att beräkna hur mycket de behöver använda cykeln.

Det är nu det blir knivigt. Vad händer om någon springar springer förbi den som cyklar? Då behöver personen stanna och vänta, vilket känns väldigt ineffektivt. (Vi kommer att prata om att folk behöver springa ikapp cykeln senare). Vi kan undvika detta med följande schema:
- Personen som cyklar snabbast börjar med cykeln. Då kan ingen springa ikapp cykeln. Varför? Låt oss anta att personen som börjar cykla är person nr $1$ och personen som springar förbi är person nr $2$. För att springa förbi måste $R[2] > C[1]$ hålla. Eftersom person nr $2$ är i tredje gruppen (snabbare att cykla än att springa), så håller $C[2] \geq R[2]$. Men då håller också $C[2] > C[1]$, vilket motsäger antagandet att snabbaste cyklisten börjar cykla.
- När person nr 1 är färdig med cykeln kan den lämna den. Vi kan nu ignorera person nr 1, den har cyklat färdigt. Första personen att springa fram till cykeln kommer också att vara den snabbaste cyklisten av kvarvarande i laget (kan finnas flera som är lika snabba, spelar ingen roll då). Ingen har då en chans att springa förbi. Detta fortsätter.

Då är det enda som är kvar att beräkna hur mycket varje person behöver använda cykeln. Det är frestande att räkna ut detta i sekunder. Tyvärr kommer detta ge fel svar; det räknar inte in att folk kommer behöva springa ikapp cykeln. Istället kommer beräkningen att anta att person 1 använder x sekunder, direkt efter byts det till person 2 osv., vilket uppenbarligen inte stämmer. Detta går att fixa nu när vi vet den optimala ordningen, men är onödigt pilligt.

För att lösa detta kan vi istället beräkna hur långt varje person behöver cykla. Varför fixar det problemet? Innan var det problematiska att vi inte nödvändigtvis kan göra direkta byten inom tidsskalan, utan det finns stunder när personer springer ikapp cykeln. Inom avståndsskalan behöver vi däremot inte oroa oss om det längre; vi har redan räknat in både tiden varje person springer respektive cyklar. Vi kan däremot få lite problem även här; ibland säger vår lösning att vi behöver cykla en total längd längre än $l$. Vi använder detta för att avgöra om ett visst $mid$ funkar eller inte.

n, l = [int(i) for i in input().split()]
run = [0] * n
bike = [0] * n
for i in range(n):
    run[i], bike[i] = [int(i) for i in input().split()]

lo = 0
hi = l+1
# När vi binärsöker över flyttal är det frestande att göra
# while hi-lo>1e-5
# Gör inte detta! Det kan hamna i en oändlig loop pga flyttals-avrundningar
# TRO MIG, GÖR ALDRIG DET
for _ in range(100):
    mid = (lo+hi)/2

    total_biking_length = 0
    for i in range(n):
        # We can run to goal
        if run[i] * mid >= l:
            continue
        # Completely impossible
        if bike[i] <= run[i]:
            bike_length += 100000000
            break
        distance_decrease_needed = l - run[i] * mid # How much distance must we save
        speed_increase = bike[i] - run[i] # How much faster is biking over running
        seconds_biking = distance_decrease_needed / speed_increase
        length_biked = seconds_biking * bike[i]
        total_biking_length += length_biked
    
    if bike_length <= l:
        hi = mid
    else:
        lo = mid
print(lo)