Consider the number of beans Alice has in base 5. Note that $2008=31013_{5}, 42=132_{5}$, and $100=400_{5}$. Now, suppose Alice has $d_{k} \cdots d_{2} d_{1}$ beans when she wins; the conditions for winning mean that these digits must satisfy $d_{2} d_{1}=32, d_{k} \cdots d_{3} \geq 310$, and $d_{k} \cdots d_{3}=4i+1$ for some $i$. To gain these $d_{k} \cdots d_{2} d_{1}$ beans, Alice must spend at least $5\left(d_{1}+d_{2}+\cdots+d_{k}\right)+k-1$ cents (5 cents to get each bean in the "units digit" and $k-1$ cents to promote all the beans). We now must have $k \geq 5$ because $d_{k} \cdots d_{2} d_{1}>2008$. If $k=5$, then $d_{k} \geq 3$ since $d_{k} \cdots d_{3} \geq 3100$; otherwise, we have $d_{k} \geq 1$. Therefore, if $k=5$, we have $5\left(d_{1}+d_{2}+\cdots+d_{k}\right)+k-1 \geq 44>36$; if $k>5$, we have $5\left(d_{1}+d_{2}+\cdots+d_{k}\right)+k-1 \geq 30+k-1 \geq 35$. But we can attain 36 cents by taking $d_{k} \cdots d_{3}=1000$, so this is indeed the minimum.
Alice and the Cheshire Cat play a game. At each step, Alice either (1) gives the cat a penny, which causes the cat to change the number of (magic) beans that Alice has from $n$ to $5n$ or (2) gives the cat a nickel, which causes the cat to give Alice another bean. Alice wins (and the cat disappears) as soon as the number of beans Alice has is greater than 2008 and has last two digits 42. What is the minimum number of cents Alice can spend to win the game, assuming she starts with 0 beans?