Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
HardLogin
53 / 53 / 2
Регистрация: 20.01.2013
Сообщений: 817
Записей в блоге: 1
1

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

05.03.2013, 00:02. Просмотров 1434. Ответов 13
Метки нет (Все метки)

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

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

Нужно вычислить факториал 33, 100 и 1000 как можно проще
Нужно вычислить фактариал 33, 100 и 1000 как можно проще

Найти все простые числа из интервала от 100 до 1000, используя логическую функцию
Нужно написать программу, буду премного благодарен) Знаю, что на самом деле тут...

Разработать программу, которая динамически выделяет 100 блоков памяти по 1000 байт каждый и освобождает их
Всем привет. Подкинули на учебе вот такое задание - Напишите программу, которая...

Даны 100 целых чисел, принадлежащих интервалу [0; 1000]. Определите количество тех из них, которые делятся на
Даны 100 целых чисел, принадлежащих интервалу . Определите количество тех из...

Составить таблицу стоимости порций сыра весом 50, 100, 150, … 1000 г. Стоимость сыра — вводимая величина.
Буду очень признателен, если поможете безрукому... 3. Составить таблицу...

13
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
05.03.2013, 06:14 2
Цитата Сообщение от HardLogin Посмотреть сообщение
Подскажите.
берете массив типа int (мне хватило размера 65536). Заполняете его числами: 1, 2, 4, 7 и т.д. Т.е. значениями на каких местах в последовательности находятся единицы. Потом для каждого Ki двоичный поиск. Если число Ki найдено, то выводите 1, если нет, то выводите 0.
1
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
05.03.2013, 07:24 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;
}
0
HardLogin
53 / 53 / 2
Регистрация: 20.01.2013
Сообщений: 817
Записей в блоге: 1
05.03.2013, 09:27  [ТС] 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;
}
0
pontakrin
1 / 1 / 1
Регистрация: 22.03.2010
Сообщений: 71
05.03.2013, 13:15 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;
}
0
HardLogin
53 / 53 / 2
Регистрация: 20.01.2013
Сообщений: 817
Записей в блоге: 1
05.03.2013, 14:12  [ТС] 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 сек.
0
pontakrin
1 / 1 / 1
Регистрация: 22.03.2010
Сообщений: 71
05.03.2013, 14:13 7
у меня нормально собралось.

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

Покупатель должен заплатить в кассу 5 руб. У него имеются купюры по 1, 5, 10, 50, 100, 500, 1000 и 10000 руб
Покупатель должен заплатить в кассу 5 руб. У него имеются купюры по 1, 5, 10,...

Задача простая Года n<=100
Дано натуральне число n(n&lt;=100), яке визначає вік людини ( в роках). Дати для...

Вывести на экран таблицу стоимости яблок в диапозоне от 100 г. до 1 кг. с шагом 100 г
Написать программу, которая выводит на экран таблицу стоимости, например, яблок...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru