UVA - 10346 - Peter's Smokes

This article will explain my thought process to solve a problem called Peter's Smokes (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Recurrence Relation

Problem Summary

Given:

Total cigarettes
Total butts required to create a new cigarette

We want to:

Total cigarettes, including the recycled cigarettes

Observation

First, we know that one cigarette will produce one butt, and a certain amount of butts will produce one cigarette. We keep repeating this process until we’re running out of cigarettes. By keeping track of the number of butts and recycled cigarette at each iteration, we could find the actual total amount of cigarettes that can be smoked. We could define the recurrence relation as:

S(c, b, r) = \begin{cases} 0 & c = 1 \\ c + S((c + b) / r,\ (c + b)\mod r,\ r) & c > 1 \end{cases}

Algorithm

The equation can be implemented using a recursive function.

The time complexity for this solution is O({total cigarettes}).

Implementation

import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 10346 - Peter's Smokes
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1287
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(System.in);
        final PrintWriter out = new PrintWriter(System.out);
        final Process process = new Process();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.totalCigarettes = in.nextInt();
            input.totalButtsForNewCigarettes = in.nextInt();
            final Output output = process.process(input);
            out.println(output.totalCigarettes);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int totalCigarettes;
    public int totalButtsForNewCigarettes;
}

class Output {
    public int totalCigarettes;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.totalCigarettes = getTotalRecycledCigarettes(
            input.totalCigarettes,
            0,
            input.totalButtsForNewCigarettes
        );
        return output;
    }

    private int getTotalRecycledCigarettes(
        final int totalCigarettes,
        final int totalButts,
        final int totalButtsForNewCigarettes
    ) {
        if (totalCigarettes == 0) return 0;

        final int totalRecycledCigarettes = getTotalRecycledCigarettes(
            (totalCigarettes + totalButts) / totalButtsForNewCigarettes,
            (totalCigarettes + totalButts) % totalButtsForNewCigarettes,
            totalButtsForNewCigarettes
        );
        return totalCigarettes + totalRecycledCigarettes;
    }
}