Verkefnalýsing

Gefnar eru jákvæðar heiltölur $X$ og $N$.

Í upphafi er heiltalan $X$ skrifuð á töfluna.

JOI-kun endurtekur eftirfarandi aðgerð:

Aðgerð: Látum $x$ vera töluna sem nú er skrifuð á töfluna. Reiknaðu afganginn þegar $x$ er deilt með $3$ og látum hann vera $r$. Eftir því hvert gildi $r$ er skaltu endurskrifa töluna á töflunni á eftirfarandi hátt:

• Þegar $r=0$, endurskrifaðu töluna á töflunni sem töluna sem fæst með því að leggja $1$ við $x$.
• Þegar $r=1$, endurskrifaðu töluna á töflunni sem töluna sem fæst með því að margfalda $x$ með $2$.
• Þegar $r=2$, endurskrifaðu töluna á töflunni sem töluna sem fæst með því að margfalda $x$ með $3$.

Finndu fjölda aðgerða sem þarf þar til talan sem skrifuð er á töfluna verður $N$ eða stærri.

Skorður

• $1 \le X < N \le 100\,000$.
• Öll inntaksgildi eru heiltölur.

Inntak

Inntakið er gefið á eftirfarandi sniði:

X
N

Úttak

Prentaðu fjölda aðgerða sem þarf þar til talan sem skrifuð er á töfluna verður $N$ eða stærri.

Ekki prenta neitt annað en svarið. (Ekki prenta setningar sem biðja um inntak o.s.frv.)

Varðandi snið svarsins má einnig skoða æfingadæmin og sýnilausnir þeirra.

Dæmi 1

Inntaksdæmi 1

2
40

Úttaksdæmi 1

4

• Í upphafi er talan sem skrifuð er á töfluna $2$.
• Í $1$. aðgerðinni er talan $x$ sem skrifuð er á töfluna í upphafi aðgerðarinnar $2$. Þar sem afgangurinn $r$ þegar $x$ er deilt með $3$ er $2$ er talan á töflunni endurskrifuð sem $6$, sem er talan sem fæst með því að margfalda $x=2$ með $3$.
• Í $2$. aðgerðinni er talan $x$ sem skrifuð er á töfluna í upphafi aðgerðarinnar $6$. Þar sem afgangurinn $r$ þegar $x$ er deilt með $3$ er $0$ er talan á töflunni endurskrifuð sem $7$, sem er talan sem fæst með því að leggja $1$ við $x=6$.
• Í $3$. aðgerðinni er talan $x$ sem skrifuð er á töfluna í upphafi aðgerðarinnar $7$. Þar sem afgangurinn $r$ þegar $x$ er deilt með $3$ er $1$ er talan á töflunni endurskrifuð sem $14$, sem er talan sem fæst með því að margfalda $x=7$ með $2$.
• Í $4$. aðgerðinni er talan $x$ sem skrifuð er á töfluna í upphafi aðgerðarinnar $14$. Þar sem afgangurinn $r$ þegar $x$ er deilt með $3$ er $2$ er talan á töflunni endurskrifuð sem $42$, sem er talan sem fæst með því að margfalda $x=14$ með $3$.
• Þar sem talan á töflunni verður $40$ eða stærri í fyrsta sinn eftir $4$ aðgerðir er prentað $4$.

Dæmi 2

Inntaksdæmi 2

3
4

Úttaksdæmi 2

1

Dæmi 3

Inntaksdæmi 3

20
62

Úttaksdæmi 3

3

Dæmi 4

Inntaksdæmi 4

1
100000

Úttaksdæmi 4

19