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

Задача 1, 10, 100, 1000 - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
05.03.2013, 00:02     Задача 1, 10, 100, 1000 #1
Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 231 − 1).
Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.

Не могу понять как её решить Подскажите.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.03.2013, 00:02     Задача 1, 10, 100, 1000
Посмотрите здесь:

Массив размерностью 30 заполнить случайными числами, лежащими в диапозоне от -100 до 100 C++
Вывести на экран таблицу стоимости яблок в диапозоне от 100 г. до 1 кг. с шагом 100 г C++
C++ Нужно вычислить факториал 33, 100 и 1000 как можно проще
Найти все простые числа из интервала от 100 до 1000, используя логическую функцию C++
Задача (язык С + +). Найти сумму целых положительных чисел, кратных 4 и меньших 100 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.03.2013, 06:14     Задача 1, 10, 100, 1000 #2
Цитата Сообщение от HardLogin Посмотреть сообщение
Подскажите.
берете массив типа int (мне хватило размера 65536). Заполняете его числами: 1, 2, 4, 7 и т.д. Т.е. значениями на каких местах в последовательности находятся единицы. Потом для каждого Ki двоичный поиск. Если число Ki найдено, то выводите 1, если нет, то выводите 0.
Байт
 Аватар для Байт
13994 / 8825 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
05.03.2013, 07:24     Задача 1, 10, 100, 1000 #3
А можно без всяких массивов.
Единицы стоят на местах 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
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
05.03.2013, 09:27  [ТС]     Задача 1, 10, 100, 1000 #4
выдает 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
1 / 1 / 0
Регистрация: 22.03.2010
Сообщений: 71
05.03.2013, 13:15     Задача 1, 10, 100, 1000 #5
не знаю понял ли вопрос но вот

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
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
05.03.2013, 14:12  [ТС]     Задача 1, 10, 100, 1000 #6
не работает(

Добавлено через 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
1 / 1 / 0
Регистрация: 22.03.2010
Сообщений: 71
05.03.2013, 14:13     Задача 1, 10, 100, 1000 #7
у меня нормально собралось.

C++
1
2
3
4
5
6
1. 1
2. 10
3. 100
4. 1000
5. 10000
Для продолжения нажмите любую клавишу . . .
какая у вас ОС и компилятор?
Миниатюры
Задача 1, 10, 100, 1000  
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
05.03.2013, 15:59  [ТС]     Задача 1, 10, 100, 1000 #8
не там нужно вывести только одну n цифр 0 или 1
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.03.2013, 19:50     Задача 1, 10, 100, 1000 #9
Цитата Сообщение от HardLogin Посмотреть сообщение
и то медленно: 0.25 сек.
Почему же медленно? Там ограничения 1 сек.
Правда мой вариант (пост №2) отработал за 0.062 сек. Если есть желание реализуйте его. Не получится покажите свой код, помогу.
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
05.03.2013, 22:12  [ТС]     Задача 1, 10, 100, 1000 #10
ну вот же
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
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.03.2013, 06:43     Задача 1, 10, 100, 1000 #11
Цитата Сообщение от 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
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
06.03.2013, 09:34  [ТС]     Задача 1, 10, 100, 1000 #12
ну понимаете это всем известный прием) но его можно получить, только написав программу которая может вычислить, без готовых решений, как я там писал:
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
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.03.2013, 11:21     Задача 1, 10, 100, 1000 #13
Цитата Сообщение от 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))
проверяет является ли корень целым числом. Элементарно! Внимательней читайте сообщения и вникайте
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.03.2013, 20:22     Задача 1, 10, 100, 1000
Еще ссылки по теме:

C++ Составить таблицу стоимости порций сыра весом 50, 100, 150, … 1000 г. Стоимость сыра — вводимая величина.
Генерировать и вывести на экран массив с целого числа n случайных чисел от -100 до 100 C++
Покупатель должен заплатить в кассу 5 руб. У него имеются купюры по 1, 5, 10, 50, 100, 500, 1000 и 10000 руб C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
06.03.2013, 20:22  [ТС]     Задача 1, 10, 100, 1000 #14
как отсюда n*(n-1)/2 + 1 может выйти такое 8*m-7 ? причем тут 8 и 7?
Yandex
Объявления
06.03.2013, 20:22     Задача 1, 10, 100, 1000
Ответ Создать тему
Опции темы

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