[Timus] 1149 Sinus Dances

Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1149

A pretty straightforward problem which can be solved by brute force. There are basically two ways to solve the problem:

1. Simulate what you will do:

public class Task1149 {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.nextInt();
        // Store the result here:
        StringBuffer result = new StringBuffer();

        for (int i = 1; i <= n; i++) {
            // For base case.
            if (i == 1) {
                result.append(getAn(1) + "+" + (n - i + 1));
            } else {
                // Wrap the existing Si-1 within () and then append Ai +
                // (n-i+1).
                result.insert(0, "(");
                result.append(")");
                result.append(getAn(i) + "+" + (n - i + 1));
            }
        }
        out.println(result.toString());
    }

    String getAn(int n) {
        StringBuffer result = new StringBuffer();
        for (int start = 1; start <= n; start++) {
            // Base case.
            if (start == 1) {
                result.append("sin(1)");
            } else {
                // Remove the last brackets.
                StringBuffer sb = new StringBuffer(result.substring(0,
                                                                    result.length() -
                                                                    start + 1));
                // Then append '-' if start is even, otherwise '+'.
                if (start % 2 == 0) {
                    sb.append("-");
                } else {
                    sb.append("+");
                }
                // Then append sin(start).
                sb.append("sin(" + start);
                // Then add back all the brackets.
                for (int j = 0; j < start; j++) {
                    sb.append(")");
                }
                result = sb;
            }
        }
        return result.toString();
    }
}

2. Identify the recursive formula and then use recursion:

public class Task1149 {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        out.println(getSn(in.nextInt()));
    }

    String getAn(int step, int n) {
        // At the last step print sin(n).
        if (step == n) {
            return "sin(" + n + ")";
        }

        // Recursion is sin(`step`+`-|+`+`Astep`) .
        return "sin(" + step + ((step % 2 == 1) ? "-" : "+") + getAn(step + 1,
                                                                     n) + ")";
    }

    String getAn(int n) {
        return getAn(1, n);
    }

    String getSn(int step, int n) {
        // Last case.
        if (step == n) {
            return "sin(1)+" + n + "";
        }
        // Recursion is (Si)An+1-i+i
        return "(" + getSn(step + 1, n) + ")" + getAn(n + 1 - step) + "+" + step;
    }

    String getSn(int n) {
        return getSn(1, n);
    }
}