# Gröntkort
https://po2punkt0.kattis.com/problems/grontkort

import math

N = int(input())
M = int(input())

svar = 2
if N %2 == 1:
  #tar bort (N-2)
  #tar bort 2
  M -= N
  svar += 1
  if M <= 0:
    print(svar*10)
    exit()

print(10*(svar + math.ceil(M/N)))

## Den trötte målaren
https://po2punkt0.kattis.com/problems/dentrottemalaren

n = int(input())
karta = []
for i in range(n):
  karta.append(list(input()))

svarpos = ""
svarfarg = ""

while('V' in [s for l in karta for s in l] or 'S' in [s for l in karta for s in l]):
  for i in range(n):
    rad = karta[i]
    if 'V' in rad:
      k = 'V'
    else:
      k = 'S'
    if all((x == k or x == 'j') for x in rad) and k in rad:
      svarpos += str(i + 1)
      svarfarg += k
      for y in range(n):
        karta[i][y] = 'j'
  
  for i in range(n):
    kolumn = list(zip(*karta))[i]
    if 'V' in kolumn:
      k = 'V'
    else:
      k = 'S'
    if all((x == k or x == 'j') for x in kolumn) and k in kolumn:
      svarpos += chr(i + 65)
      svarfarg += k
      for y in range(n):
        karta[y][i] = 'j'
  
print(svarpos[::-1])
print(svarfarg[::-1])

# Korta vokaler
https://po2punkt0.kattis.com/problems/kortavokaler
Det relevanta för varje karaktär x i ordet är:
* **Fall 0** Antal kombinationer från och med x till slutet av ordet där vår senaste bokstav inte är en konsonant.
* **Fall 1** Antal kombinationer från och med x till slutet av ordet där vår senaste bokstav (kan vara x, eller en annan karaktär för kombinationer då vi inte inkluderar x) är en konsonant, men den innan det är inte en konsonant.
* **Fall 2+** Antal kombinationer från och med x till slutet av ordet där våra 2+ senaste bokstav är konsonanter.

Det här är våra olika states - det vi sparar i vår dp! Karaktär kolumnen är för tydlighet. Exempel för ordet "and".

| Index | (karaktär) | Fall 0 | Fall 1 | Fall 2+ |
| ----- |:---------- | ------ | ------ |:------ |
| 0 | a | 3 | 2 | 1 |
| 1 | n | 1 | 2 | 1 |
| 2 | d | 1 | 1 | 0 |

### Falluppdelning
Vi funderar på en karaktär på index i. Vi antar att vi, för alla karaktärer längre bak i ordet, vet alla kombinationer för **fall 0**, **fall 1** och fall **2+**.

**Vad händer om vår karaktär är en vokal?**
* Möjlighet: vi använder vokalen.
* Alla kombinationer kommer hamna i kategorin **(index i: fall 0)** eftersom vår sista bokstav då kommer vara en vokal.
* Vi kan inte använda vokalen för tidigare (alltså fallen för index i+1) där de två senaste bokstäverna är konsonanter. I så fall skulle det vara en vokal framför 2 konsonanter vilket inte är tillåtet.
* För varje kombination i **(index i+1: fall 0)** kan vi använda vokalen.
* För varje kombination i **(index i+1: fall 1)** kan vi använda vokalen.
* Vi får alltså: **(index i: fall 0)** += **(index i+1: fall 0)** + **(index i+1: fall 1)**
* Möjlighet: vi använder inte vokalen.
* Alla kombinationer för **(index i+1: fall 0)** kommer hamna i **(index i: fall 0)**. Alltså: **(index i: fall 0)** += **(index i+1: fall 0)**
* Alla kombinationer för **(index i+1: fall 1)** kommer hamna i **(index i: fall 1)**. Alltså: **(index i: fall 1)** += **(index i+1: fall 1)**
* Alla kombinationer för **(index i+1: fall 2+)** kommer hamna i **(index i: fall 2+)**. Alltså: **(index i: fall 2+)** += **(index i+1: fall 2+)**

Vi får alltså:

| Index | (karaktär) | Fall 0 | Fall 1 | Fall 2+ |
| ----- |:---------- |:------------------------------------------------- | ------ |:------- |
| i | vokal | 2 * **(index i+1: fall 0)** + **(index i+1: fall 1)** | **(index i+1: fall 1)** | **(index i+1: fall 2+)** |

**Vad händer om vår karaktär är en konsonant?**
* Möjlighet: vi använder konsonanten.
* Vi kan lägga till en konsonant framför oavsett hur det tidigare kombinationen ser ut.
* Om vi lägger till en konsonant framför kombinationer där vi hade 0 konsonanter i rad så får vi nu 1 konsonant i rad:
**(index i: fall 1)** += **(index i+1: fall 0)**.
* Om vi lägger till en konsonant framför kombinationer där vi hade 1 konsonant i rad så får vi nu 2+ konsonant i rad:
**(index i: fall 2+)** += **(index i+1: fall 1)**.
* Om vi lägger till en konsonant framför kombinationer där vi hade 2+ konsonanter i rad så får vi nu 2+ konsonant i rad:
**(index i: fall 2+)** += **(index i+1: fall 2+)**.

* Möjlighet: vi använder inte konsonanten.
* Alla kombinationer för **(index i+1: fall 0)** kommer hamna i **(index i: fall 0)**. Alltså: **(index i: fall 0)** += **(index i+1: fall 0)**
* Alla kombinationer för **(index i+1: fall 1)** kommer hamna i **(index i: fall 1)**. Alltså: **(index i: fall 1)** += **(index i+1: fall 1)**
* Alla kombinationer för **(index i+1: fall 2+)** kommer hamna i **(index i: fall 2+)**. Alltså: **(index i: fall 2+)** += **(index i+1: fall 2+)**

Vi får alltså:

| Index | Fall 2+ | (karaktär) | Fall 0 | Fall 1 |
| ----- |:------------------------------------------------------- |:---------- |:----------------------- | ------------------------------------------------- |
| i | 2 * **(index i+1: fall 2+)** + **(index i+1: fall 2+)** | konsonant | **(index i+1: fall 0)** | **(index i+1: fall 1)** + **(index i+1: fall 0)** |

Rekursiv lösning:

ord = input()

dp = [[-1 for i in range(len(ord))], [-1 for i in range(len(ord))], [-1 for i in range(len(ord))]]

dp[0][len(ord)-1] = 1
dp[1][len(ord)-1] = 0
dp[2][len(ord)-1] = 0

if ord[-1] not in "aeiouy":
  dp[1][len(ord)-1] += 1
else:
  dp[0][len(ord)-1] += 1



def rek(fall, i):
  if dp[fall][i] != -1:
    return dp[fall][i]

  #Vad händer om vår karaktär är en vokal?
  if ord[i] in "aeiouy":
    if fall == 0:      
      dp[fall][i] = 2*rek(0, i+1) + rek(1, i+1)
    if fall == 1:      
      dp[fall][i] = rek(1, i+1)
    if fall == 2:      
      dp[fall][i] = rek(2, i+1)
    return dp[fall][i]

  #Vad händer om vår karaktär är en konsonant?
  if fall == 0:      
    dp[fall][i] = rek(0, i+1)
  if fall == 1:   
    dp[fall][i] = rek(0, i+1) + rek(1, i+1)
  if fall == 2:      
    dp[fall][i] = 2*rek(2, i+1) + rek(1, i+1)
  return dp[fall][i]

print(rek(0, 0) + rek(1, 0) + rek(2, 0) -1)

Gammal iterativ lösning:

a = input()

dp0 = [0 for i in range(len(a))]
dp1 = [0 for i in range(len(a))]
dp2 = [0 for i in range(len(a))]

dp0[-1] = 1
svar = 0
for i in range(len(a))[::-1]:
  if i == 0:
    if a[i] in "aeiouy":
      svar = dp0[i] + dp1[i] + dp2[i] + dp0[i] + dp1[i]
    else:
      svar = 2*(dp0[i] + dp1[i] + dp2[i])
    
    break
  if a[i] in "aeiouy":
    dp0[i-1] += dp0[i] + dp1[i]
  else:
    dp1[i-1] += dp0[i]
    dp2[i-1] += dp1[i] + dp2[i]
  dp0[i-1] += dp0[i]
  dp1[i-1] += dp1[i]
  dp2[i-1] += dp2[i]

print(svar -1)

# Bergskedja
https://po2punkt0.kattis.com/problems/bergskedja2

Först så skapar vi två ritkade grafer där rutorna är noder, och det går en kant från a till b om:
* **Graf 1:** b är högre upp än a (och man kan gå från b till a i rutnätet).
* **Graf 2:** b är lägre än a (och man kan gå från b till a i rutnätet).

Jag använder dictionaries för detta som jag namnger "upp" (graf 1) och "ner" (graf2). Vi har
* upp[nod1] = [nod2, nod3, nod4]

om nod2, nod3 och nod4 är högre upp än nod1, och är närliggande till nod1 (ligger bredvid). Jag sparar varje nod i en tuple, som (rad, kolumn).

#### Hur hittar jag vilka noder som är högre än de närliggande noderna?
Om ett hus har 0 närliggande hus som är lägre så vet jag att det huset är högre än alla närligande hus. Nu kan jag "ta bort" det huset från grafen. Jag sätter rutan att få värde -1 i min 2D lista jag kallar karta. Jag tar -=1 på alla närliggande hus - de är högre än en nod färre pga noden jag "tog bort". Så länge det finns noder jag inte tagit bort så kommer minst en nod ha 0 närliggande hus som är lägre. På det här sättet kan jag hitta riktningarna av alla kanterna.

#### Vad kan jag inse nu?
* Jag börjar på startpositionen mitt hus. Alla hus jag kan gå till i den riktade grafen "upp", kommer att vara högre än mitt hus (om a är högre än b som är högre än mitt hus så kommer a vara högre än mitt hus). Om jag har x noder som är högre än mitt hus så kan mitt hus som högst vara det x+1 högsta.
* Man kan visa att det alltid kommer gå för mig att ha det x+1 högsta grafen! Hur? Lite komplicerat:
1. Vi säger att alla noder som måste vara högre än mitt hus är en mängd M. Vi vet att från ett hus "a" i M till ett närliggande hus "b" som inte är i m så kommer "a" vara högre än "b". Varför? Eftersom om "b" var högre än "a", och "a" är som vi vet högre än mitt hus så skulle "b" vara en del av mängden M. Men "b" var inte i mängd M. Motsägelsebevis!
2. Vi testar att låta mitt hus vara det x+1 högsta huset. Då kommer alla hus i mängd m vara på en högre höjd än alla hus som inte är i mängd m. Detta gör att oavsett vilket hus som har vilket av de resterande höjderna av husen-som-inte-är-i-mängd-m (hus i icke-M) så kommer alla kanter mellan M och icke-M att stämma. Alla hus i M kommer vara högre än husen i icke-M. Nu är frågan, finns det en kombination av tal som uppfyller alla inbördes relationer i icke-M? Ja! Vi kan välja siffrorna hur vi vill - minst ett sätt kommer att funka!
3. Vi för samma argument för hur vilken den lägsta höjden mitt hus kan ha!

#### En sista fråga:
Hur hittar vi antalet hus i mängden M? Vi väljer en graf i taget, antingen "upp" eller "ner" och så gör vi en BFS! Observera att kanterna i grafen kommer att vara riktade.

import copy
from queue import Queue
r, k = [int(i) for i in input().split()]

q = Queue()
karta = []
for i in range(r):
  karta.append([int(a) for a in list(input())])
  for b in range(k):
    if karta[i][b] == 0:
      q.put((i, b))

#Adjacency lists med hjälpa av dictionary
upp = {}
ner = {}
for a in range(r):
  for b in range(k):
    upp[(a,b)] = []
    ner[(a,b)] = []


#Hittar riktningarna som kanterna har och lägger till dem i mina adjacency lists
while(not q.empty()):
  curr = q.get()
  #print(curr)
  for i in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
    new = (curr[0] + i[0], curr[1] + i[1])
    if new[0] >= 0 and new[0] < r and new[1] >= 0 and new[1] < k and karta[new[0]][new[1]] != -1:
      #print("new",new)
      upp[curr].append(new)
      ner[new].append(curr)
      karta[new[0]][new[1]] -= 1
      if karta[new[0]][new[1]] == 0:
        q.put(new)
    karta[curr[0]][curr[1]] = -1


def bfs(lista):
  qu = Queue()
  v = [(0,0)]
  qu.put((0,0))

  while not qu.empty():
    curr = qu.get()
    for i in lista[curr]:
      if not i in v:
        qu.put(i)
        v.append(i)
  return len(v)


print(bfs(ner), r*k - bfs(upp) + 1)