Решение в лоб вряд ли пройдет.
Мой алгоритм решения:
1. Легко заметить что сумма цифр от 1 до N может быть вычислена по формуле арифметической прогрессий.
2. Первая цифра всегда один.
3. Нужно найти самую меньшую или равную сумму к нашему К, её легко можно найти использую пункт 1.
4. Если найденная сумма минус К ровно одному то ответ один, иначе ноль.

Edited by author 04.05.2012 21:02

Почему вы не можете объяснять внятно, такое ощущение что вы не сами решаете свои задачи! Объясните мне пожалуйста, Как вычислить сумму от 1 до N Если нам только известен an То есть место положения N, но не известен сам N. Ведь формула такова: Sn = a1+an/2*N; Как найти Sn Если нам не известно N ?????...

Можно положить все возможные позиции в Set, а потом проверять есть ли эта позиция в Set'e.

Как заполняется Set: Постепенно суммируем числа начиная от 0 и заканчивая суммой не больше 2^31-1, промежуточные суммы кладем в Set, прибавив перед этим единицу.

Будьте внимательны при задании ограничения 2^31-1.

Сперва я указал так: 1<<31-1
Но это неправильно, т.к. приоритет у вычитания, а потом у сдвига.
Можно указать так (1<<31)-1 или еще проще Integer.MAX_VALUE (оба варианта равнозначны).
Я решал задачу с Long, но достаточно и Integer.

Edited by author 26.03.2014 01:14

package acm.timus.ru;

import java.util.Scanner;

public class N_1209 {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int i=1,a=0,k=0;
    for (int j=1; j<=n; j++) {
       a=sc.nextInt();
       if (i<a) {
           while(i<a){ k++; i+=k; }
       }else{
           while(i>a){ i-=k; k--; }
       }
       if (i==a) { System.out.print("1"+" "); }
       else{System.out.print("0"+" ");}

    }
  }
}

Time limit exceeded(