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

токены - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
08.09.2011, 13:58     токены #1
здравствуйте! нужны идеи по решению этой задачи. у меня никаких кроме как поделить их на токены...

Однажды Азиз заметил, что номер его телефона 321321 и номер его дома 111 обладают интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. Азиз назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 является од- новременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать программу, находящую количество k-чисел, не превосходящих заданное число n.
Формат входных данных:
На первой строке стандартного потока ввода задано число k, на второй — число n (2 <= k <= 100, 1 <= n <= 10100).
Формат выходных данных:
Первая строка стандартного потока вывода должна содержать одно число — количество k-чисел, не превышающих n.

Вход: 2 3140
Выход: 31
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2011, 13:58     токены
Посмотрите здесь:

Visual C++ Разбить СString на токены
Разделение большого текста из файла на токены Python
C# Разбить математическое выражение на токены и занести их в массив строк
C++ Как редактировать токены функции strtok?

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.09.2011, 14:04     токены #2
Просто перебрать все числа до n, если длина числа не кратна k, то сразу отметать, иначе сравнивать все подстроки. Хотя можно и динамику найти, но с такими ограничениями и перебор сойдет.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
08.09.2011, 15:43     токены #3
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
53
54
55
56
57
58
59
60
61
62
63
64
65
/////////////////////////////////////////////////////////////////////////////////////////
// Однажды Азиз заметил, что номер его телефона 321321 и номер его дома 111 обладают 
// интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. 
// Азиз назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, 
// число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 
// является од- новременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). 
// Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать 
// программу, находящую количество k-чисел, не превосходящих заданное число n.
//
// Формат входных данных:
// На первой строке стандартного потока ввода задано число k, 
// на второй — число n (2 <= k <= 100, 1 <= n <= 10100).
//
// Формат выходных данных:
// Первая строка стандартного потока вывода должна содержать одно число — количество k-чисел, 
// не превышающих n.
//
// Вход: 2 3140
// Выход: 31 
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int  count_k_numbers_not_great_n
    (
        int  k,
        int  n
    )
{
    int  res = 0;
    for(int  factor_degree = 10; ; factor_degree *= 10)
    {
        int  factor = 1;
        for(int  i = 0; i < k - 1; ++i)
        {
            factor *= factor_degree;
            factor += 1;
        }
        int  mult_min       = factor_degree / 10;
        int  mult_max_real  = n / factor;
        if(mult_max_real < mult_min)  return res;
        res += std::min(mult_max_real, factor_degree - 1) - mult_min + 1;   
    }    
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "k = ";
    int  k = 0;
    std::cin >> k;
 
    std::cout << "n = ";
    int  n = 0;
    std::cin >> n;
    std::cout << "Количество "
              << k
              << "-чисел, не превосходящих "
              << n
              << ", равно "
              << count_k_numbers_not_great_n(k, n)
              << "."
              << std::endl;
}
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
08.09.2011, 15:54  [ТС]     токены #4
Цитата Сообщение от diagon Посмотреть сообщение
если длина числа не кратна k
а как узнать та длину перебираемого числа?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.09.2011, 15:58     токены #5
Цитата Сообщение от jambas92 Посмотреть сообщение
а как узнать та длину перебираемого числа?
C++
1
2
3
#include <cmath>
//...
log10(n) + 1
Только для натуральных чисел.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
08.09.2011, 22:24  [ТС]     токены #6
вот к чему я пришел, где -то считает правильно но на больших числах ошибается сильно. найдите пожалуйста в чем я не прав.

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
#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    int k, n;
    int dlina;
    int yaya1, yaya2;
    unsigned long long int x = 1;
    int count = 0;
 
    cin >> k >> n;
 
    for (double i=10; i<=n; i++)
    {
        dlina = log10(i) + 1;
        if (dlina % k == 0)
        {
            for (int j=0; j<dlina-1; j++)
            {
                x = 10 * x;
            }
            yaya1 = i / x;
            yaya2 = (int)i % x;
            if (yaya1==yaya2)
            {
                count++;
            }
            x=1;
        }
    }
    cout << count;
}
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
09.09.2011, 13:34     токены #7

Не по теме:

Большие числа - это сколько десятичных разрядов? double не может гарантировать сохранность более 16 разрядов: подробнее о double.

Добавлено через 14 минут
Прочитав внимательнее заметил, что это к делу не должно относиться. Сорри.



Добавлено через 11 минут
хм... условие смущает. Если у n максимум 10100, то k ведь никак больше 4 в принципе быть не может?
Не прав в том, что при k=3 нужно сверять 3 значения, при k=4 - уже 4. Лучше написать отдельно процедурку разбиения числа на части в массив, переданный по ссылке.
villu
202 / 202 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
09.09.2011, 14:38     токены #8
Цитата Сообщение от jambas92 Посмотреть сообщение
Вход: 2 3140
Выход: 31
почему 31?

3131 3030
2929 2828 2727 2626 2525 2424 2323 2222 2121 2020
1919 1818 1717 1616 1515 1414 1313 1212 1111 1010

итого 22.

909 на сколько понимаю уже не подходит.

или как-то не так?
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
09.09.2011, 15:07     токены #9
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/////////////////////////////////////////////////////////////////////////////////////////
// Однажды Азиз заметил, что номер его телефона 321321 и номер его дома 111 обладают 
// интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. 
// Азиз назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, 
// число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 
// является од- новременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). 
// Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать 
// программу, находящую количество k-чисел, не превосходящих заданное число n.
//
// Формат входных данных:
// На первой строке стандартного потока ввода задано число k, 
// на второй — число n (2 <= k <= 100, 1 <= n <= 10100).
//
// Формат выходных данных:
// Первая строка стандартного потока вывода должна содержать одно число — количество k-чисел, 
// не превышающих n.
//
// Вход: 2 3140
// Выход: 31 
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int  count_k_numbers_not_great_n
    (
        int  k,
        int  n
    )
{
    int  res = 0;
    for(int  factor_degree = 10; ; factor_degree *= 10)
    {
        int  factor = 1;
        for(int  i = 0; i < k - 1; ++i)
        {
            factor *= factor_degree;
            factor += 1;
        }
        int  mult_min       = factor_degree / 10;
        int  mult_max_real  = n / factor;
        if(mult_max_real < mult_min)  return res;
        int  mult_max = std::min(mult_max_real, factor_degree - 1);
        for(int  mult = mult_min; mult <= mult_max; ++mult)
        {
            std::cout << ++res
                      << ":"
                      << '\t'
                      << mult * factor
                      << std::endl;
        }        
    }    
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "k = ";
    int  k = 0;
    std::cin >> k;
 
    std::cout << "n = ";
    int  n = 0;
    std::cin >> n;
    std::cout << std::endl;
    std::cout << std::endl
              << "Количество "
              << k
              << "-чисел, не превосходящих "
              << n
              << ", равно "
              << count_k_numbers_not_great_n(k, n)
              << "."
              << std::endl;
}
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.09.2011, 15:22  [ТС]     токены #10
villu, есть же ведь еще такие варианты:
11, 22, 33, 44, 55, 66, 77, 88, 99,
villu
202 / 202 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
09.09.2011, 15:25     токены #11
а. Задачу не так понял.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.09.2011, 15:37  [ТС]     токены #12
Mr.X, первое решение абсолютно верно, но тест не проходит из за того что n может доходить до 1 <= n <= 10^100).
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
09.09.2011, 15:48     токены #13
Теперь понятно. Коммент о дабл всё же имеет некоторую ценность.
Для таких n про перебор можно забыть, используй логику.
Интересно при k=2 и n=10^100 выходит. Для подсчёта нужно работать с очень большими числами => реализовывать такие числа будет проще в виде строки (нужна лишь операция сложения).

n считывай тоже как строку, кстати.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.09.2011, 16:48     токены #14
А задачка-то на динамику...
Можно ссылку?
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.09.2011, 16:53  [ТС]     токены #15
давай))
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.09.2011, 17:00     токены #16
Цитата Сообщение от jambas92 Посмотреть сообщение
давай))
Я у вас ссылку на задачу спрашиваю =\ Вы ее с какого-нибудь сайта по олимпиадному программированию взяли?
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
09.09.2011, 17:38     токены #17
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от jambas92 Посмотреть сообщение
Mr.X, первое решение абсолютно верно, но тест не проходит из за того что n может доходить до 1 <= n <= 10^100).
В первом сообщении у вас было написано 10100, что и ввело всех в заблуждение.
Тогда так:
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/////////////////////////////////////////////////////////////////////////////////////////
// Однажды Азиз заметил, что номер его телефона 321321 и номер его дома 111 обладают 
// интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. 
// Азиз назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, 
// число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 
// является од- новременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). 
// Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать 
// программу, находящую количество k-чисел, не превосходящих заданное число n.
//
// Формат входных данных:
// На первой строке стандартного потока ввода задано число k, 
// на второй — число n (2 <= k <= 100, 1 <= n <= 10^100).
//
// Формат выходных данных:
// Первая строка стандартного потока вывода должна содержать одно число — количество k-чисел, 
// не превышающих n.
//
// Вход: 2 3140
// Выход: 31 
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string       T_str;
typedef T_str::size_type  T_pos;
/////////////////////////////////////////////////////////////////////////////////////////
T_str  count_k_numbers_not_great_n
    (
        int           k,
        const T_str&  n_str
    )
{
    int    n_len       = n_str.size();
    int    res_len     = n_len / k;
    if(res_len == 0) return "0";
    int    head_len    = res_len + n_len % k;
    T_str  n_str_head  = n_str.substr(0, head_len);
    T_str  res         = T_str(res_len, '9');
    if(res_len == head_len)
    {
        res = n_str_head;
        T_str  max_val_str;
        for(int  i = 0; i < k; ++i)
        {
            max_val_str += res;
        }
        if(max_val_str > n_str)
        {
            for(size_t  res_pos = res_len - 1; ; --res_pos)
            {
                if(res[res_pos] > '0')
                {
                    --res[res_pos];
                    break;
                }
                else
                {
                    res[res_pos] = '9';
                }
            }
        }
    }
    if(res[0] == '0')
    {
        res.erase(0, 1);
    }
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "k = ";
    int  k = 0;
    std::cin >> k;
 
    std::cout << "n = ";
    T_str  n;
    std::cin >> n;
    std::cout << "Количество "
              << k
              << "-чисел, не превосходящих "
              << n
              << ", равно "
              << count_k_numbers_not_great_n(k, n)
              << "."
              << std::endl;
}
Yandex
Объявления
09.09.2011, 17:38     токены
Ответ Создать тему
Опции темы

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