Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1209
One should note here is that ones are located at location that depends on location of previous one.
1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 …
First one is located at 1st position, second one is (1+1 = 2) position, the third one is (2+2 = 4) position, fifth one is (4+3 = 7) position and so on.
We can easily pre calculate the location of ones. This makes the problem easy to code. Here is the solution:
package codes; import FastIO.InputReader; import FastIO.OutputWriter; import java.util.HashSet; import java.util.Set; public class Task1209 { private Set<Long> ones = new HashSet<>(); /** * Populate the {@code ones} set with the position of ones. */ public Task1209() { long pos = 0; long step = 1; while (pos <= Integer.MAX_VALUE) { ones.add(pos); pos += step; step++; } } public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.nextInt(); StringBuilder result = new StringBuilder(); while (n-- > 0) { int pos = in.nextInt(); // Check if the pos - 1 is in ones set, if it is then print 1 // else 0. if (ones.contains(new Long(pos - 1))) { result.append("1 "); } else { result.append("0 "); } } out.println(result.toString().trim()); } }