Задача C

Задача С. N-та цифра

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 1с.

Дано початковий рядок 1, над яким застосовують наступну операцію: приписують праворуч такий же рядок, але з заміною нулів на одиниці, а одиниць на нулі. Цю операцію повторюють нескінченну кількість разів. Ваше завдання полягає в знаходженні N-тої цифри в отриманому рядку.

Вхідні дані

В першому рядку записано кількість тестів K. В наступних K рядках записано число N, номер цифри в K-му рядку (1≤K≤100, 1≤N≤1000000000).

Вихідні дані

В результаті вивести K рядків, в кожному з яких N-та цифра, відповідного рядка.

Приклади

іnput.txt	output.txt
1 7	1
2 1 2	1 0

Ідея.

Задача потребує побудови числа, щоб в ньому відшукати потрібну цифру. Однак, будувати числа для кожного тесту – це суттєве уповільнення програми. Тому краще знайти серед заданих номерів для цифр – найбільший номер, і побудувати для нього число.  За умовою задачі  числа конструюються так, що всі цифри після свого створення, які мають менші номери, - позицій не змінюють. Отже, побудувавши число - в ньому можна знайти позиції цифр для кожного тесту.

Алгоритм:

1. Прочитати кількість тестів.

2. Записати номери цифр у масив nom_digits.

3. Знайти максимальний номер серед номерів цифр (знайти максимальний елемент масиву nom_digits).

4. Поки довжина числа (масиву)  v менша за максимальний номер цифри:

            дописати цифри в кінець масиву v, інвертуючи їх (1 на 0, 0 на 1).

5. З побудованого масиву  v вивести лише ті цифри, номери, яких знаходяться в nom_digits:

            printf( "%d\n", v[ nom_digits[i]-1 ] )

Особливості реалізації:

1) для інвертування цифр використовується формула нова_цифра=1-стар_цифра. де стара_цифра це 1 або 0;

2) nom_digits[i]-1 – потрібно віднімати 1, бо індекси масива починаються з 0, а номери цифр в умові задачі розглядаються починаючи від 1;

3) індексом масива може бути значення елемента іншого масива: v[ nom_digits[i]-1 ] – тобто у числі v номер цифри nom_digits[i]-1.

  

#include <stdio.h>

#include <vector>

using namespace std;

vector<int> v;

vector<int> nom_digits;

int main()

{

       freopen("input.txt", "r", stdin);

       freopen("output.txt", "w", stdout);

       int k;

       scanf("%d", &k);

       nom_digits.assign(k,0);

       for(int test=0; test<k; ++test){

             int n;

             scanf("%d", &n);

             nom_digits[test]=n;

       }

       int max_n_ndx = 0;

       for(int i=0; i<(int)nom_digits.size(); ++i)

             if(nom_digits[i]>nom_digits[max_n_ndx])

                    max_n_ndx = i;

       v.push_back(1);

       while((int)v.size()<nom_digits[max_n_ndx])

       {

             int size = (int)v.size();

             for (int i = 0; i < size; ++i)

                           v.push_back(1 - v[i]);

       }

      

       for(int i=0; i<(int)nom_digits.size(); ++i)

             printf("%d\n", v[nom_digits[i]-1]);

      

       return 0;

}