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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
wejustfun
1 / 1 / 0
Регистрация: 20.12.2010
Сообщений: 15
14.04.2011, 13:07     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки #1
Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ

Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 231 − 1).
Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.04.2011, 13:07     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки
Посмотрите здесь:

C++ Определить, какая цифра в заданном числе встречается чаще других
Определить, какая цифра в числе есть большей – первая или последняя C++
C++ Задано трицифровое число. Определить, какая цифра в нем...
C++ Дано целое k от 1 до 180. Определить, какая цифра находится в k-ой позиции последовательности
Определить, на какой позиции слева находится первая встреченная четная цифра C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 469
14.04.2011, 13:20     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки #2
wejustfun, смотри в сторону умножения длинных чисел. Умножаешь и объединяешь в одну строку, а потом просто ищешь в этой строке.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
14.04.2011, 13:53     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки #3
From_Tula, тут всё намного элементарнее. Если единица находится в n-й позиции, то следующая единица будет через (n + 1)-у позицию от предыдущей. Поэтому достаточно вычислить пару позиций соседних единиц Pi и Pi+1, для которых Pi <= Ki <= Pi+1. Если Ki равняется одной из границ отрезка - то это 1, иначе 0.
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 469
14.04.2011, 14:18     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки #4
Согласен так проще)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
14.04.2011, 14:27     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки #5
From_Tula, суть даже не в простоте. Представьте, сколько времени уйдёт на операции с длинными числами такого размера. Уж никак не 1 секунда, которая в ограничении.
wejustfun
1 / 1 / 0
Регистрация: 20.12.2010
Сообщений: 15
18.04.2011, 15:20  [ТС]     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки #6
Вот что у меня получилось.....время 1.015 которое к сожелению нас не устраивает....
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
#include<iostream>
#include<conio.h>
#include<windows.h>
#include<stdio.h>
using namespace std;
 int main(int argc,char *argv[])
{
     int n,f, M[65535]; long a,s;
     char str[10]="Введите N";
     char buf[10];
     CharToOem(str,buf);
     cout<<buf<<endl;
     cin>>n;
     for(int j=0;j<n;j++){
     cin>>a;
     f=0;
     s=1;
     if (a == 1) f=1; else 
     for (int i=1; i<=a;i++)
        {
            s=s+i;
            if (a == s) f=1;
   }
 M[j]=f;}
 for(int j=0;j<n;j++) cout<<M[j]<<' ';
 getch();
 return 0;
 }
Yandex
Объявления
18.04.2011, 15:20     Определить, какая цифра находится в заданной позиции в последовательности степеней десятки
Ответ Создать тему
Опции темы

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