Определить, какая цифра находится в заданном месте в последовательности цифр составленных из степеней десятки

@лыс · Регистрация: 04.11.2012

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

Всем привет! Помогите добить задачу (выскакивает превышение лимита по времени).

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.

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

исходные данные 4 3 14 7 6
выход 0 0 1 0

Мой код:

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> 
#include <vector> 
#include <algorithm>
 
using namespace std;
 
int main()
{
    vector<int> v;
    int N, k, a=0, b=0;
    while(a>=0)
    {       
        v.push_back(a+1);
        b++;
        a+=b;
    }   
    scanf("%d", N);
    while(N>0)
    {
        cin>>k;
        if(find(v.begin(), v.end(), k)==v.end())
            printf("%d", 0);
        else
            printf("%d", 1);
    }    
  return 0;
}

@Algoritmer · 08.10.2013, 10:45

Сообщение от лыс

(выскакивает превышение лимита по времени)

Откажись от типа vector. Реализуй через динамическое выделение памяти.
И потом, эта задача скорей всего должна решаться подсчетом, вообще без использования массивов

@лыс · 08.10.2013, 10:51 **[ТС]**

Попробую, спасибо..

Ilot · 08.10.2013, 10:53

Будьте проще. Если нумеровать позицию с нуля то единица будет стоять на месте n(n +1)/2. Очевидно делаем цикл по n пока n(n +1)/2 меньше заданного числа.

C++
1
2
3
4
5
6
7
8
9
10
11
bool func (int numer)
{
    int n = 0;
    while((n * (n + 1))/2 <= numer)
    {
        if ((n * (n + 1))/2 == numer)
            return true;
        n++;
    }
    return false;
}

На чистоту кода не претендую накидал за пару минут.
p.s.Коль есть ограничение по времени используйте побитовое смещение вместо деления на два. Говорят оно швытче работает

p.s.s.Можно еще ввести переменную temp = (n(n +1)) >> 1. Будет еще меньше вычислений

@лыс · 08.10.2013, 12:27 **[ТС]**

Всем большое спасибо, решил по вашим способам) но терзает один рабочий код...

Добавлено через 46 минут

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

Тут все понятно, кроме формулы , как её вообще получить? Прога рабочая.

XML
1
n=(1+sqrt(8*m-7))/2;

Ilot · 08.10.2013, 12:43

В программе проверяется является ли m = n(n + 1)/2 целым. Дескриминант считать не разучились?

p.s. Плохая программа - вещественные числа не сравниваются на равенство...

@лыс · 08.10.2013, 13:09 **[ТС]**

Ммм, спасибо за мысль о дискриминанте) только добавлю, что m=n(n+1)/2 +1

Ilot · 08.10.2013, 13:12

Сообщение от лыс

Ммм, спасибо за мысль о дискриминанте) только добавлю, что m=n(n+1)/2 +1

Ну так естественно, так как:

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

Если нумеровать позицию с нуля...

А у нЫх с единички.

@лыс · 08.10.2013, 13:21 **[ТС]**

Ilot, аа...) разъяснили)

@84633 · 25.05.2020, 11:14

помогите с задачей

Полный балл: 10
Ограничение времени: 1 с
Ограничение памяти: 512M
Ограничение размера стека: 64M
Задача 7: Ремонт забора
Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ..., в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.

Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какое наименьшее число щитов необходимо приобрести, чтобы починить весь забор.

Входные данные
Первая строка входных данных содержит целое число L (L > 0) – максимальный размер щита. Во второй строке входных данных записано целое число N (N > 0) – количество досок в заборе. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 – что доска может быть сохранена.

Выходные данные
Программа должна вывести одно целое число – минимальное число щитов, которое необходимо приобрести для ремонта всего забора.

Система оценивания
Решение, правильно работающее только для случаев, когда числа L и N не превосходят 1000, будет оцениваться в 6 баллов.

В 10 баллов будет оцениваться решение, правильно работающее, когда числа L и N не превосходят 105.

Пример
Ввод Вывод Пояснение
3
8
0
0
1
0
1
0
1
0
2
Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов, например, одним щитом меняем доски с номерами 3, 4, 5, а другим щитом меняем доску с номером 7.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@лыс 1 / 1 / 0 Регистрация: 04.11.2012 Сообщений: 50
	08.10.2013, 10:51 [ТС]
	Попробую, спасибо.. 0

Ilot $Эксперт по математике/физике$ 2222 / 1424 / 419 Регистрация: 16.05.2013 Сообщений: 3,640 Записей в блоге: 6
	08.10.2013, 12:43
	В программе проверяется является ли m = n(n + 1)/2 целым. Дескриминант считать не разучились? p.s. Плохая программа - вещественные числа не сравниваются на равенство... 0

@лыс 1 / 1 / 0 Регистрация: 04.11.2012 Сообщений: 50
	08.10.2013, 13:09 [ТС]
	Ммм, спасибо за мысль о дискриминанте) только добавлю, что m=n(n+1)/2 +1 0

@лыс 1 / 1 / 0 Регистрация: 04.11.2012 Сообщений: 50
	08.10.2013, 13:21 [ТС]
	Ilot, аа...) разъяснили) 0

@84633 0 / 0 / 0 Регистрация: 25.05.2020 Сообщений: 1
	25.05.2020, 11:14
	помогите с задачей Полный балл: 10 Ограничение времени: 1 с Ограничение памяти: 512M Ограничение размера стека: 64M Задача 7: Ремонт забора Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ..., в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие. Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какое наименьшее число щитов необходимо приобрести, чтобы починить весь забор. Входные данные Первая строка входных данных содержит целое число L (L > 0) – максимальный размер щита. Во второй строке входных данных записано целое число N (N > 0) – количество досок в заборе. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 – что доска может быть сохранена. Выходные данные Программа должна вывести одно целое число – минимальное число щитов, которое необходимо приобрести для ремонта всего забора. Система оценивания Решение, правильно работающее только для случаев, когда числа L и N не превосходят 1000, будет оцениваться в 6 баллов. В 10 баллов будет оцениваться решение, правильно работающее, когда числа L и N не превосходят 105. Пример Ввод Вывод Пояснение 3 8 0 0 1 0 1 0 1 0 2 Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов, например, одним щитом меняем доски с номерами 3, 4, 5, а другим щитом меняем доску с номером 7. 0