[Timus] 1, 10, 100, 1000…

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());
    }
}