Форум программистов, компьютерный форум CyberForum.ru

1101001000 - C++

Восстановить пароль Регистрация
 
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
08.10.2013, 10:38     1101001000 #1
Всем привет! Помогите добить задачу (выскакивает превышение лимита по времени).

Ограничение времени: 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
 Аватар для Algoritmer
155 / 95 / 13
Регистрация: 07.03.2013
Сообщений: 477
Записей в блоге: 1
08.10.2013, 10:45     1101001000 #2
Цитата Сообщение от лыс Посмотреть сообщение
(выскакивает превышение лимита по времени)
Откажись от типа vector. Реализуй через динамическое выделение памяти.
И потом, эта задача скорей всего должна решаться подсчетом, вообще без использования массивов
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
08.10.2013, 10:51  [ТС]     1101001000 #3
Попробую, спасибо..
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
08.10.2013, 10:53     1101001000 #4
Будьте проще. Если нумеровать позицию с нуля то единица будет стоять на месте 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. Будет еще меньше вычислений
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
08.10.2013, 12:27  [ТС]     1101001000 #5
Всем большое спасибо, решил по вашим способам) но терзает один рабочий код...

Добавлено через 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
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
08.10.2013, 12:43     1101001000 #6
В программе проверяется является ли m = n(n + 1)/2 целым. Дескриминант считать не разучились?
p.s. Плохая программа - вещественные числа не сравниваются на равенство...
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
08.10.2013, 13:09  [ТС]     1101001000 #7
Ммм, спасибо за мысль о дискриминанте) только добавлю, что m=n(n+1)/2 +1
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
08.10.2013, 13:12     1101001000 #8
Цитата Сообщение от лыс Посмотреть сообщение
Ммм, спасибо за мысль о дискриминанте) только добавлю, что m=n(n+1)/2 +1
Ну так естественно, так как:
Цитата Сообщение от Ilot
Если нумеровать позицию с нуля...
А у нЫх с единички.
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
08.10.2013, 13:21  [ТС]     1101001000 #9
Ilot, аа...) разъяснили)
Yandex
Объявления
08.10.2013, 13:21     1101001000
Ответ Создать тему
Опции темы

Текущее время: 05:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru