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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
#1

По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её - C++

30.05.2012, 21:00. Просмотров 725. Ответов 12
Метки нет (Все метки)

Ограничения по времени: 2 секунды
Ограничения по памяти: 256 megabytes
Строки (цепочки цифр) создаются по следующему правилу.
Первая строка из одного символа - "1". Каждая следующая задается так: записывается номер строки потом 2 раза предыдущая.
Примет
1. 1
2. 211
3. 3211211
4. 432112113211211
По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её. Если длина строки меньше K, вывести -1.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2012, 21:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её (C++):

Определить, какая цифра стоит на заданном месте в последовательности - C++
всем вечер добрый. интересует алгоритм решения к двум задачам. честно говоря, довольно долго думал, но ничего дельного я не придумал. ...

Для заданного N, определить, какая цифра стоит на N-ом месте в этой последовательности - Информатика
Выпишем подряд все натуральные числа: 1234567891011121314… Для заданного N, определить, какая цифра стоит на N-ом месте в этой...

Будет ли быстрея работать компьютер, если оперативка будет стоять в двух разьёмах? - Компьютерное железо
Будет ли быстрея работать комп если оперативка быдет стоять в двух разьёмах

Вывести в одной строке символы, стоящие на нечетном месте, а в другой – стоящие на четном месте - Assembler
Здрасте.Подскажите пожалуйста.Есть задание: Ввести строку символов. Вывести на одной строке символы, стоящие на нечетном месте, а на...

Определите, какие кегли остались стоять на месте - Turbo Pascal
N кеглей выставили в один ряд, занумеровав их слева направо числами от 1 до N. Затем по этому ряду бросили K шаров, при этом i-й шар сбил...

Какая цифра в строке встречается чаще всего (выполнить с помощью указателей) - C++
написать программу, которая до введенного с клавиатуры строки (максимальная длина строки - 80 символов) сообщает, какая цифра в ней...

12
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 21:01 #2

Не по теме:

Jeron95, ЕГЭ полезло



Сейчас решу

Ну вы смешной.. А где же ограничения на N и K ?!??!
0
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 21:05  [ТС] #3
Ternsip, задача действительно из ЕГЭ, но я взял её с одного сайта для онлайн контестов

Добавлено через 3 минуты
упс забыл) 1<=N<=100000, 1<=K<=10^15
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 22:03 #4
Jeron95, Для n=61 в строке уже 9223372036854775807 символов, а это больше чем 10^15. И это проигнорирвоать ?

Добавлено через 2 минуты
Либо К увеличьте либо N уменьшйате

Добавлено через 18 минут
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
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <conio.h>
#include <vector>
using namespace std;
 
vector <long long> mas;
 
int calc(long long n,long long k){
    if (k==1) return n;
    if (k>mas[n-1]) return -1;
    if (k<=mas[n-1]/2 + 1) return calc(n-1,k-1);
    return calc(n-1,k-mas[n-1]/2-1);
};
 
int main(){
    long long n,k;
    cin>>n>>k;
    mas.push_back(1);
    for (int i=1;i<n;i++)
        mas.push_back(mas[i-1]*2+1);
    cout<<calc(n,k);
    getch();
};
Вот для 1<=n<=62 и 1<=k<=10^16
И всётаки проверьте, потестируйте

прошу лайк
1
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.05.2012, 22:20 #5
Проверяйте для значений:
Цитата Сообщение от Jeron95 Посмотреть сообщение
1<=N<=100000, 1<=K<=10^15
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
 
int main () 
{
    int n, i;
    long long a[100000], k;
    cin>>n>>k;
    n--;
    
    a[0]=1;
    for(i=1; i<100000; i++)
    {
        a[i]=a[i-1]*2+1;
        if(a[i]>1000000000000000)
            break;
    }
    while(true)
    {
        if(n<0)
        {
            n=-2;
            break;
        }
        if(k==1)
            break;
        if(n<=i)
        {
            if(a[n]/2<k-1)
                k-=1+a[n]/2;
            else
                k--;
            n--;
        }
        else
        {
            k--; n--;
        }
    }
    cout<<n+1<<endl;
    return 0;
}
1
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 22:33  [ТС] #6
valeriikozlov, на тесте 11 3 неверно, должно быть 1, а выводит 9
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 22:42 #7
Jeron95, Должно быть 9! всё верно у него
PS посмотрите лучше моё решение, оно более наглядно. Его легко изменить для больших ограничений. Стоит отметить, что преждевременная оптимизация - корень всех 3ол
0
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 22:54  [ТС] #8
Ternsip, Нет! десятая строка начинается с числа 10, 11 строка с числа 11 и добавляется предыдущая, то есть 10

Добавлено через 1 минуту
и начало 11 строки будет 1110987 и третья цифра единица!
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 22:57 #9
Jeron95,
пшш
0
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 22:59  [ТС] #10
ну да, как я и говорил
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 23:04 #11
Jeron95, хахаха простите! я не заметил что "цифра" я подумал число =)

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

Не по теме:

Врятли успею переделать сёдня уже баиньки пора

0
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 23:07  [ТС] #12
Ternsip, да ничего) бывает)
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
31.05.2012, 08:34 #13
Jeron95, проверяйте:
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;
 
int main () 
{
    int n, i, t;
    long long a[1000], k;
    cin>>n>>k;    
    a[1]=1; i=2;
    while(i<10){a[i]=a[i-1]*2+1; i++;}
    while(i<100){a[i]=a[i-1]*2+2; i++;}
    while(i<1000){a[i]=a[i-1]*2+3; i++; if(a[i]>1000000000000000) break;}
 
    while(true)
    {
        if(n<1)
        {
            n=-1;
            break;
        }
        if(n==100000) t=6;
        if(n<100000 && n>=10000) t=5;   
        if(n<10000 && n>=1000) t=4;
        if(n<1000 && n>=100) t=3;
        if(n<100 && n>=10) t=2;
        if(n<10) t=1;
        if(k<=t)
        {
            while(k<t)
            {
                n/=10;
                t--;
            }
            n%=10;
            break;
        }
        if(n<=i)
        {
            if((a[n]-t)/2+t<k)
                k-=(a[n]-t)/2+t;
            else
                k-=t;
            n--;
        }
        else
        {
            k-=t; n--;
        }
    }
    cout<<n<<endl;
    return 0;
}
и на будущее: не стесняйтесь, сразу пишите ограничения на N и K и примеры тестов (если они есть).
1
31.05.2012, 08:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.05.2012, 08:34
Привет! Вот еще темы с ответами:

Составить матрицу, на месте симметричных элементов которой будут стоять 0 - C (СИ)
Составить матрицу,на месте симметричных элементов которой будут стоять 0 (Си)! Хэлп,плиз,заранее спасибо! Добавлено через 16...

Определить, какая площадь и квадратных метрах будет покрашена и какая будет побелена - Pascal ABC
Длина класса L метров, ширина - b метров, высота класса – h метров. В классе имеется дверь размером dl x dh и три окна размером ol x oh см....

Найти и вывести сумму всех хороших (цифра десятков больше, чем цифра единиц) элементов массива - Информатика
Задание 25 № 5289. Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 1000. Элемент массива...

Будет ли поезд стоять на платформе - C++
1) Поезд прибывает на станцию в a часов b минут и отправляется в c часов d минут. Пассажир пришел на платформу в n часов m минут. Будет...


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

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

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