Solution:

Answer: $35$

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.