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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
#1

Счастливый билет. Надо сократить время работы программы - C++

02.11.2013, 20:10. Просмотров 1819. Ответов 30
Метки нет (Все метки)

Написал 2 программы обе работают очень долго первая 19сек вторая 15сек
А надо: Лимит времени 2000/4000/4000/4000 мс.

Условие: Надо ввести число в диапазоне 10000000 ≤ M < N ≤ 99999999. Посчитать количество счастливых билетов
Примеры:
Input: 11111110 11111112
Output: 1
Input: 10000000 99999999
Output: 4379055

Вот код первой задачи:
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
#include <iostream>
using namespace std;
void func(unsigned long *a, unsigned long *b)
{
    unsigned long counter=0;
    unsigned long A, B, C, D, E, F, G, H, X, Y;
    for(unsigned long i=*a; i<=*b; i++)
    {
        A=i/10000000;
        B=(i/1000000)%10;
        C=(i/100000)%10;
        D=(i/10000)%10;
        E=(i/1000)%10;
        F=(i/100)%10;
        G=(i/10)%10;
        H=i%10;
 
        X=A+B+C+D;
        Y=E+F+G+H;
 
        if (X==Y)
            {
                counter++;
            }
    }
 
    cout<<counter;
}
int main()
{
    unsigned long a, b;
    cin>>a>>b;
    func(&a, &b);
    return 0;
}
Вот код второй задачи:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
void func(unsigned long *a, unsigned long *b)
{
    unsigned long counter=0;
    for(unsigned long i=*a;i<=*b; i++)
    {
        if(((i/10000000)+((i/1000000)%10)+((i/100000)%10)+((i/10000)%10))==(((i/1000)%10)+((i/100)%10)+((i/10)%10)+(i%10)))
            counter++;
    }
 
    cout<<counter;
}
int main()
{
    unsigned long a, b;
    cin>>a>>b;
    func(&a, &b);
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2013, 20:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Счастливый билет. Надо сократить время работы программы (C++):

Как сократить время работы программы?! - C++
Нужно сократить время работы программы по вычислению чисел Фибоначчи: Вот мой код: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include...

Счастливый билет - C++
Ув. программисты, помогите пожалуйста несчастному студенту решить задачу. (о вознаграждении договоримся) Дан массив из 6 целых чисел от...

Счастливый билет! - C++
билет с шестизначным номером считается счастливым если сумма трех старших цифр совпадает с суммой трех младших. допустим что в билетной...

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

счастливый билет - C++
Вводится шестизначное число .Определить является ли билет с этим номером счастливым ?с оптимизацией времени решения на турбо си!прошу...

Счастливый билет - C++
Всем привет помогите с решением задачи.Вводится шестизначное число .Определить является ли билет с этим номером счастливым ?Нужно...

30
ValeryS
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,233
03.11.2013, 00:34 #16
Alex5,
все понял
тогда все таки
C++
1
arr[summ]++;
в arr[2] будет 3
и три раза сложим итого 9
осталось разобраться с условиями цикла
предлагаю такой вариант
если старшая часть не различается
подсчитываем сумму и заносим в массив
а в младшей крутим цикл от начального до конечного
если различается то старший от начального до конечного
а младший так
вычитаем из конечного начальное если больше 10000 крутим от 0 до 9999
если меньше
то делаем такой хитрый цикл
C++
1
for(int i=n;i!=f;i=(i+1)%10000)
или так
C++
1
for(int i=f;i!=n;i--)
нам ведб направление без разницы
0
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 08:21 #17
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
#include <cstdio>
using namespace std;
 
int dsum( int x )
{
    return x % 10 + x / 10 % 10 + x / 100 % 10 + x / 1000;
}
 
int calc( int m, int n )
{
    int hcnt[ 37 ] = { 0 };
    int lcnt[ 37 ] = { 0 };
    int r = 0;
 
    for ( int i = m / 10000, max = n / 10000; i <= max; ++i )
        ++hcnt[ dsum( i ) ];
    for ( int i = m % 10000, max = n % 10000; i <= max; ++i )
        ++lcnt[ dsum( i ) ];
    for ( int i = 1; i < 37; ++i )
        r += hcnt[ i ] * lcnt[ i ];
 
    return r;
}
 
int main()
{
    int m, n;
 
    scanf( "%d%d", &m, &n );
    printf( "%d\n", calc( m, n ) );
 
    return 0;
}
0
ValeryS
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,233
03.11.2013, 10:16 #18
ya_noob,
число 19999998 и 20000000
как поведет себя второй цикл???
0
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 11:54  [ТС] #19
почему массив размера 37?
0
ValeryS
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,233
03.11.2013, 11:59 #20
Цитата Сообщение от FoxTails Посмотреть сообщение
почему массив размера 37?
ты обсуждение то читаешь?
за ходом мысли следишь?
или только готовые коды просматриваешь?
Цитата Сообщение от ValeryS Посмотреть сообщение
вторая подсказка сумма четырех цифр от 1 до 36
Цитата Сообщение от Tulosba Посмотреть сообщение
а 0 куда делся?
Цитата Сообщение от ValeryS Посмотреть сообщение
создаем массив на 37 элементов 0-36 обнуляем его
0
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 12:06 #21
Цитата Сообщение от ValeryS Посмотреть сообщение
как поведет себя второй цикл???
упс, не доглядел. но всё равно идея решения ясна
0
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 12:09  [ТС] #22
Все ясно, а почему ++hcnt[ dsum( i ) ]
0
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 12:36 #23
Цитата Сообщение от FoxTails Посмотреть сообщение
Все ясно, а почему ++hcnt[ dsum( i ) ]
увеличиваем счетчик возможных сумм цифр для старшей половины числа. это очень просто. а вот с младшей половиной числа придется помучаться, т.к. числа могут повторяться, чего, как заметил ValeryS, не учитывает мое первоначальное решение. там перед вторым циклом надо сделать еще пару проверок и добавить пару циклов, а тот проблемный цикл разделить на 2.
0
Alex5
1102 / 763 / 119
Регистрация: 12.04.2010
Сообщений: 1,933
03.11.2013, 12:57 #24
ya_noob,
Цитата Сообщение от ya_noob Посмотреть сообщение
for ( int i = m % 10000, max = n % 10000; i <= max; ++i )
++lcnt[ dsum( i ) ];
Вот ещё пример. m == 10004444; n == 99993333
Какой результат вернёт calc( m, n )?
0
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 12:59  [ТС] #25
и еще можете объяснить эту строчку
r += hcnt[ i ] * lcnt[ i ];
0
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 13:58 #26
Цитата Сообщение от Alex5 Посмотреть сообщение
Какой результат вернёт
не тормозите, я же признал эту ошибку 3 поста назад.
Цитата Сообщение от FoxTails Посмотреть сообщение
и еще можете объяснить эту строчку
r += hcnt[ i ] * lcnt[ i ];
Цитата Сообщение от FoxTails Посмотреть сообщение
Все ясно
мне кажется вам ничего не ясно.
0
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 14:13  [ТС] #27
все ясно это насчет этой строчки ++lcnt[ dsum( i ) ];
а эту я не понял r += hcnt[ i ] * lcnt[ i ];
0
Alex5
1102 / 763 / 119
Регистрация: 12.04.2010
Сообщений: 1,933
03.11.2013, 15:17 #28
Операции деления и взятия остатка занимают больше времени, чем сложение. Поэтому имеет смысл не пользоваться / и % внутри цикла.
См. сообщение #7
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
    // ... 
    // перед входом в цикл вычисляем начальные значения A, B, C, D, E, F, G, H 
    for( i = ... ; i<= ... ; i++)
    {
        // ...
        Next( A, B, C, D,   E, F, G, H );
    }
    // ... 
 
void Next( unsigned long & A, unsigned long & B, unsigned long & C, unsigned long & D, 
     unsigned long & E, unsigned long & F, unsigned long & G, unsigned long & H )
{
    ++H;
    if( H < 10 ) return;
    H = 0;
 
    ++G;
    if( G < 10 ) return;
    G = 0;
 
    ++F;
    if( F < 10 ) return; 
    F = 0;
 
    ++E;
    if( E < 10 ) return; 
    E = 0;
 
 
 
    ++D;
    if( D < 10 ) return; 
    D = 0;
 
    ++C;
    if( C < 10 ) return; 
    C = 0;
 
    ++B;
    if( B < 10 ) return; 
    B = 0;
 
    ++A;
 
    return;
}
0
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 15:47 #29
v2. теперь попробуйте ее сломать
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
#include <cstdio>
using namespace std;
 
int dsum( int x )
{
    return x % 10 + x / 10 % 10 + x / 100 % 10 + x / 1000 % 10;
}
 
// считаем кол-во счастливых билетов с фиксированным значением старшей четверки чисел (hi) и диапазоном младшей четверки [a, b]
int calc_lo( int hi, int a, int b )
{
    int r = 0;
    int hi_sum = dsum( hi );
 
    for ( ; a <= b; ++a )
        if ( dsum( a ) == hi_sum )
            ++r;
    return r;
}
 
// считаем кол-во счастливых билетов в диапазоне [a0000, b9999], где a и b определяют диапазон значений старшей четверки чисел
int calc_hi( int a, int b )
{
    int hcnt[ 37 ] = { 0 };
    int lcnt[ 37 ] = { 0 };
    int r = 0;
 
    for ( ; a <= b; ++a ) ++hcnt[ dsum( a ) ];
    for ( int i = 0; i < 10000; ++i ) ++lcnt[ dsum( i ) ];
    for ( int i = 1; i < 37; ++i ) r += hcnt[ i ] * lcnt[ i ];
 
    return r;
}
 
int calc( int m, int n )
{
    int m_lo = m % 10000, m_hi = m / 10000;
    int n_lo = n % 10000, n_hi = n / 10000;
    int t;
 
    if ( n_hi - m_hi == 0 )
        return calc_lo( m_hi, m_lo, n_lo );
 
    t = calc_lo( m_hi, m_lo, 9999 ) + calc_lo( n_hi, 0, n_lo );
    if ( n_hi - m_hi == 1 )
        return t;
    return calc_hi( m_hi + 1, n_hi - 1 ) + t;
}
 
int main()
{
    int m, n;
 
    scanf( "%d%d", &m, &n );
    printf( "%d\n", calc( m, n ) );
 
    return 0;
}
0
ValeryS
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,233
03.11.2013, 15:51 #30
ya_noob,
могу предложить чтобы еще убыстрить не один цикл от 0 до 9999
а четыре вложенных цикла 0 до 9( единицы десятки сотни тысячи)
количество итераций тоже но скорость увеличивается отсутствием деления, остатков от деления
внутри цикла только сумма
C++
1
arr[t+s+d+e]++;
0
03.11.2013, 15:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 15:51
Привет! Вот еще темы с ответами:

Почти счастливый билет - C++
В гугле полно задач про &quot;Счастливые билеты&quot;, а у меня возникла проблема с &quot;Почти счастливыми билетами. Вот задача - Назовем “почти...

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

Счастливый билет (Лимит Времени) - C++
Всем привет! Контестер пишет Time Limit. Подскажите что можно сделать чтоб моя программа работала быстрее. Что можно изменить или добавить?...

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


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

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

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