Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
#1

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

02.11.2013, 20:10. Просмотров 1900. Ответов 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
Ответы с готовыми решениями:

Как сократить время работы программы?!
Нужно сократить время работы программы по вычислению чисел Фибоначчи: Вот мой...

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

Счастливый билет
Ув. программисты, помогите пожалуйста несчастному студенту решить задачу. (о...

счастливый билет
Вводится шестизначное число .Определить является ли билет с этим номером...

Счастливый билет
Всем привет помогите с решением задачи.Вводится шестизначное число .Определить...

30
ya_noob
_
315 / 149 / 27
Регистрация: 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
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 12:36 #23
Цитата Сообщение от FoxTails Посмотреть сообщение
Все ясно, а почему ++hcnt[ dsum( i ) ]
увеличиваем счетчик возможных сумм цифр для старшей половины числа. это очень просто. а вот с младшей половиной числа придется помучаться, т.к. числа могут повторяться, чего, как заметил ValeryS, не учитывает мое первоначальное решение. там перед вторым циклом надо сделать еще пару проверок и добавить пару циклов, а тот проблемный цикл разделить на 2.
0
Alex5
1122 / 783 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
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
_
315 / 149 / 27
Регистрация: 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
1122 / 783 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
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
_
315 / 149 / 27
Регистрация: 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
Модератор
7223 / 5485 / 683
Регистрация: 14.02.2011
Сообщений: 18,550
03.11.2013, 15:51 #30
ya_noob,
могу предложить чтобы еще убыстрить не один цикл от 0 до 9999
а четыре вложенных цикла 0 до 9( единицы десятки сотни тысячи)
количество итераций тоже но скорость увеличивается отсутствием деления, остатков от деления
внутри цикла только сумма
C++
1
arr[t+s+d+e]++;
0
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 16:03 #31
ValeryS, думаю не стоит оно того. задача явно с какого-нибудь acm или moodle. а там и текущая реализация отработает за минимальное время в 0.015 сек
0
03.11.2013, 16:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 16:03

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

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

Задача на счастливый билет
Определить , является ли заданное с клавиатуры шестизначное число четным ,...


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

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

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