# [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);
}
}```

This site uses Akismet to reduce spam. Learn how your comment data is processed.