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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
02.11.2013, 20:10     Счастливый билет. Надо сократить время работы программы #1
Написал 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2013, 20:10     Счастливый билет. Надо сократить время работы программы
Посмотрите здесь:

Счастливый билет C++
Счастливый билет! C++
C++ Счастливый билет
C++ счастливый билет
счастливый билет C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 12:06     Счастливый билет. Надо сократить время работы программы #21
Цитата Сообщение от ValeryS Посмотреть сообщение
как поведет себя второй цикл???
упс, не доглядел. но всё равно идея решения ясна
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 12:09  [ТС]     Счастливый билет. Надо сократить время работы программы #22
Все ясно, а почему ++hcnt[ dsum( i ) ]
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 12:36     Счастливый билет. Надо сократить время работы программы #23
Цитата Сообщение от FoxTails Посмотреть сообщение
Все ясно, а почему ++hcnt[ dsum( i ) ]
увеличиваем счетчик возможных сумм цифр для старшей половины числа. это очень просто. а вот с младшей половиной числа придется помучаться, т.к. числа могут повторяться, чего, как заметил ValeryS, не учитывает мое первоначальное решение. там перед вторым циклом надо сделать еще пару проверок и добавить пару циклов, а тот проблемный цикл разделить на 2.
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
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 )?
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 12:59  [ТС]     Счастливый билет. Надо сократить время работы программы #25
и еще можете объяснить эту строчку
r += hcnt[ i ] * lcnt[ i ];
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 13:58     Счастливый билет. Надо сократить время работы программы #26
Цитата Сообщение от Alex5 Посмотреть сообщение
Какой результат вернёт
не тормозите, я же признал эту ошибку 3 поста назад.
Цитата Сообщение от FoxTails Посмотреть сообщение
и еще можете объяснить эту строчку
r += hcnt[ i ] * lcnt[ i ];
Цитата Сообщение от FoxTails Посмотреть сообщение
Все ясно
мне кажется вам ничего не ясно.
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 14:13  [ТС]     Счастливый билет. Надо сократить время работы программы #27
все ясно это насчет этой строчки ++lcnt[ dsum( i ) ];
а эту я не понял r += hcnt[ i ] * lcnt[ i ];
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
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;
}
ya_noob
_
200 / 144 / 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;
}
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,048
03.11.2013, 15:51     Счастливый билет. Надо сократить время работы программы #30
ya_noob,
могу предложить чтобы еще убыстрить не один цикл от 0 до 9999
а четыре вложенных цикла 0 до 9( единицы десятки сотни тысячи)
количество итераций тоже но скорость увеличивается отсутствием деления, остатков от деления
внутри цикла только сумма
C++
1
arr[t+s+d+e]++;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 16:03     Счастливый билет. Надо сократить время работы программы
Еще ссылки по теме:

Как сократить время работы программы?! C++
Почти счастливый билет C++

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

Или воспользуйтесь поиском по форуму:
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 16:03     Счастливый билет. Надо сократить время работы программы #31
ValeryS, думаю не стоит оно того. задача явно с какого-нибудь acm или moodle. а там и текущая реализация отработает за минимальное время в 0.015 сек
Yandex
Объявления
03.11.2013, 16:03     Счастливый билет. Надо сократить время работы программы
Ответ Создать тему
Опции темы

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