Задача 1, 10, 100, 1000

@HardLogin · Регистрация: 20.01.2013

Студворк — интернет-сервис помощи студентам

Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 231 − 1).
Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.

Не могу понять как её решить

Подскажите.

valeriikozlov · 05.03.2013, 06:14

Сообщение от HardLogin

Подскажите.

берете массив типа int (мне хватило размера 65536). Заполняете его числами: 1, 2, 4, 7 и т.д. Т.е. значениями на каких местах в последовательности находятся единицы. Потом для каждого Ki двоичный поиск. Если число Ki найдено, то выводите 1, если нет, то выводите 0.

Байт · 05.03.2013, 07:24

А можно без всяких массивов.
Единицы стоят на местах n*(n-1)/2 + 1

C
1
2
3
4
5
6
 int F(int k)
{ int s, i; 
  for(s=i=1; s<k; i++) s+=i;
  if (s==k) return 1;
  else return 0;
}

@HardLogin · 05.03.2013, 09:27 **[ТС]**

выдает Time limit exceeded вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
 
int F(int k)
{ int s, i; 
  for(s=i=1; s<k; i++) s+=i;
  if (s==k) return 1;
  else return 0;
}
 
int main()
{
int n;
cin >> n;
 
int *k = new int[ n ];
for( int i = 0; i < n; i++ )
cin >> k[ i ];
 
int s;
for( int i = 0; i < n; i++ )
{
 cout << F( k[ i ] ) << (( i == n - 1 )? "" : " ");
}
 
return 0;
}

@pontakrin · 05.03.2013, 13:15

не знаю понял ли вопрос но вот

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using namespace std;
 
 
int main(void){
    char * ch = "110100100010000";
    char buf[255];
    int pos = 0; // позиция
    int bi = 1;
 
    for (int i = 0; i < strlen(ch); i++){   // ищем цыфры
        
        if (ch[i] == '1'){
            ++pos;
            cout << pos << ". ";
            
            for (int j = i; j < strlen(ch); j++){
                if (ch[j] == '1'){
                    buf[bi] = 0;
                    memcpy(buf, &ch[j], bi++);
                    cout << buf << endl;
                    break;      
                }
            }
        }
    }
   
   return 0;
}

@HardLogin · 05.03.2013, 14:12 **[ТС]**

не работает(

Добавлено через 2 минуты
вобщем я там нашел решение но я не понимаю как оно работает(

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long float m,n;
int N;
    cin>>N;
    for  (int i=1; i<=N; i++)
    {
    cin>>m;
    n=(1+sqrt(8*m-7))/2;
 if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))
   cout<<1<<" ";
    else
    cout<<0<<" ";
     }
    cin>>N;
    return 0;
    }

и то медленно: 0.25 сек.

@pontakrin · 05.03.2013, 14:13

у меня нормально собралось.

C++
1
2
3
4
5
6
1. 1
2. 10
3. 100
4. 1000
5. 10000
Для продолжения нажмите любую клавишу . . .

какая у вас ОС и компилятор?

@HardLogin · 05.03.2013, 15:59 **[ТС]**

не там нужно вывести только одну n цифр 0 или 1

valeriikozlov · 05.03.2013, 19:50

Сообщение от HardLogin

и то медленно: 0.25 сек.

Почему же медленно? Там ограничения 1 сек.
Правда мой вариант (пост №2) отработал за 0.062 сек. Если есть желание реализуйте его. Не получится покажите свой код, помогу.

@HardLogin · 05.03.2013, 22:12 **[ТС]**

ну вот же

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
 
int F(int k)
{ int s, i; 
  for(s=i=1; s<k; i++) s+=i;
  if (s==k) return 1;
  else return 0;
}
 
int main()
{
int n;
cin >> n;
 
int *k = new int[ n ];
for( int i = 0; i < n; i++ )
cin >> k[ i ];
 
int s;
for( int i = 0; i < n; i++ )
{
 cout << F( k[ i ] ) << (( i == n - 1 )? "" : " ");
}
 
return 0;
}

valeriikozlov · 06.03.2013, 06:43

Сообщение от HardLogin

ну вот же

это совсем не то )

Сообщение от valeriikozlov

берете массив типа int (мне хватило размера 65536). Заполняете его числами: 1, 2, 4, 7 и т.д. Т.е. значениями на каких местах в последовательности находятся единицы. Потом для каждого Ki двоичный поиск. Если число Ki найдено, то выводите 1, если нет, то выводите 0.

Нужно создать массив L[] размером 65536.
Затем нужно заполнить массив L[] числами: 1, 2, 4, 7, 11, 16 и т.д.
Потом уже считывая очередное ki искать его значение в массиве L[] (с помощью двоичного поиска). Если нашли это значение, то выводите 1, если не нашли, то выводите 0.
Снова считываете очередное ki и опять ищите его в массиве L[]...

@HardLogin · 06.03.2013, 09:34 **[ТС]**

ну понимаете это всем известный прием) но его можно получить, только написав программу которая может вычислить, без готовых решений, как я там писал:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long float m,n;
int N;
    cin>>N;
    for  (int i=1; i<=N; i++)
    {
    cin>>m;
    n=(1+sqrt(8*m-7))/2;
 if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))
   cout<<1<<" ";
    else
    cout<<0<<" ";
     }
    cin>>N;
    return 0;
    }

этот код выложил какой то англичанин там на обсуждении задачи, он работает, но почему в чем подкол этой формулы:

C++
1
if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))

@ya_noob · 06.03.2013, 11:21

Сообщение от HardLogin

но почему в чем подкол этой формулы:

Вам же написали как можно вычислить местонахождение единиц:

Сообщение от Байт

Единицы стоят на местах n*(n-1)/2 + 1

8*m-7 - дискриминант квадратного уравнения, полученного из вышеприведенной формулы,
1+sqrt(8*m-7) - один из его корней
а эта штука

C++
1
if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))

проверяет является ли корень целым числом. Элементарно! Внимательней читайте сообщения и вникайте

@HardLogin · 06.03.2013, 20:22 **[ТС]**

как отсюда n*(n-1)/2 + 1 может выйти такое 8*m-7 ? причем тут 8 и 7?

Новые блоги и статьи Все статьи Все блоги /
1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .
Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .

@HardLogin 54 / 54 / 2 Регистрация: 20.01.2013 Сообщений: 832 Записей в блоге: 1

	Задача 1, 10, 100, 1000 05.03.2013, 00:02. Показов 6578. Ответов 13 Метки нет (Все метки) Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте. Исходные данные В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 231 − 1). Результат Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki. Не могу понять как её решить Подскажите. 0

@HardLogin 54 / 54 / 2 Регистрация: 20.01.2013 Сообщений: 832 Записей в блоге: 1
	05.03.2013, 15:59 [ТС]
	не там нужно вывести только одну n цифр 0 или 1 0

@HardLogin 54 / 54 / 2 Регистрация: 20.01.2013 Сообщений: 832 Записей в блоге: 1
	06.03.2013, 20:22 [ТС]
	как отсюда n(n-1)/2 + 1 может выйти такое 8m-7 ? причем тут 8 и 7? 0