014. Короткая последовательность

(Время - 1 сек., память - 16 Мб)

Дано целое число N. Рассмотрим последовательность S1S2S3...Sk..., где каждая группа цифр Sk состоит из записанных одно за другим чисел от 1 до k. Например, первые 75 цифр последовательности выглядят так:

112123123412345123456123456712345678123456789123456789101234567891011123456.

Требуется написать программу, которая определит какая цифра находится на N-ой позиции в построенной последовательности.

Входные данные

В единственной строке входного файла input.txt записано одно число N (0 < N < 32768).

Выходные данные

В единственную строку выходного файла output.txt нужно вывести цифру, которая стоит на N-ой позиции в последовательности.

Примеры

input.txt

output.txt

1

3

2

2

20

5

Разбор

.

Программа на Паскале

var

  n, k, l, m : integer;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(n);

  l:=0; k:=0;

  while n>l+m do

  begin

    k:=k+1;

    if k<10 then m:=1 else

      if k<100 then m:=2 else m:=3;

    l:=l+m;

    n:=n-l

  end;

  if n<10 then write(n) else

    if n<190 then

    begin

      n:=n-10; l:=n div 2+10;

      if n mod 2=0 then write(l div 10) else write(l mod 10)

    end

    else

    begin

      n:=n-190; l:=n div 3+100;

      case n mod 3 of

        0 : write(l div 100);

        1 : write(l div 10 mod 10);

        2 : write(l mod 10)

      end

    end

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2008-2009 уч. год, 2-й тур

Тематика

Сортировка и последовательности

Примерная сложность

28%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=482

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 22.05.2012