２つ以上残っている景品がもともと無い場合は不可能です。それ以外の場合を考えます。 考え得る最悪のケースは、残っている景品を全種類1つずつ出るケースです。この場合、次に出る景品は既に出た景品のいずれかになります。よって、答えは品切れでない景品の種類の数+1回となります。
参考文献：4つの言語で解ける 実践プログラミング問題集