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

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

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

C++ Найти элемент с заданым условием
C++ В каждой строке матрицы найти и вывести минимальный элемент и его номер в строке
Определить, какая цифра в числе есть большей – первая или последняя C++
C++ Задано трицифровое число. Определить, какая цифра в нем...
Вывести члены арифметической прогрессии, которые не превышают 100, с заданым начальным членом и шагом C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 21:01     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #2

Не по теме:

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



Сейчас решу

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

Добавлено через 3 минуты
упс забыл) 1<=N<=100000, 1<=K<=10^15
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 22:03     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #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
И всётаки проверьте, потестируйте

прошу лайк
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.05.2012, 22:20     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #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;
}
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 22:33  [ТС]     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #6
valeriikozlov, на тесте 11 3 неверно, должно быть 1, а выводит 9
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.05.2012, 22:42     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #7
Jeron95, Должно быть 9! всё верно у него
PS посмотрите лучше моё решение, оно более наглядно. Его легко изменить для больших ограничений. Стоит отметить, что преждевременная оптимизация - корень всех 3ол
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 22:54  [ТС]     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #8
Ternsip, Нет! десятая строка начинается с числа 10, 11 строка с числа 11 и добавляется предыдущая, то есть 10

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

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

Не по теме:

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

Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
30.05.2012, 23:07  [ТС]     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #12
Ternsip, да ничего) бывает)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.05.2012, 08:34     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её
Еще ссылки по теме:

C++ На вход подается дата. Нужно вывести на экран, какая дата будет через 29 дней 12 часов и 44 минуты
Какая цифра в строке встречается чаще всего (выполнить с помощью указателей) C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
31.05.2012, 08:34     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её #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 и примеры тестов (если они есть).
Yandex
Объявления
31.05.2012, 08:34     По заданым N и K найти какая цифра будет стоять N-ой строке на K-ом месте и вывести её
Ответ Создать тему
Опции темы

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