Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
02.11.2013, 20:12     Счастливый билет. Надо сократить время работы программы #2
Программы с бинарной арифметикой лучше всего писать на ассемблере.
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
02.11.2013, 20:16  [ТС]     Счастливый билет. Надо сократить время работы программы #3
Цитата Сообщение от zitxbit Посмотреть сообщение
Программы с бинарной арифметикой лучше всего писать на ассемблере.
Ассемблер - это другой язык программирования? Мне именно в с++ надо
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.11.2013, 20:53     Счастливый билет. Надо сократить время работы программы #4
FoxTails, у вас цикл слишком долго считает (100 млн. итераций). ваше решение задачи "в лоб" не годится. задачу можно решить за 20 тыс. итераций. попробуйте разбить задачу на меньшие подзадачи.
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
02.11.2013, 22:24  [ТС]     Счастливый билет. Надо сократить время работы программы #5
Цитата Сообщение от ya_noob Посмотреть сообщение
FoxTails, у вас цикл слишком долго считает (100 млн. итераций). ваше решение задачи "в лоб" не годится. задачу можно решить за 20 тыс. итераций. попробуйте разбить задачу на меньшие подзадачи.
можете написать, что то не получается
Хулиган
 Аватар для Хулиган
85 / 80 / 12
Регистрация: 08.08.2012
Сообщений: 737
02.11.2013, 22:35     Счастливый билет. Надо сократить время работы программы #6
что такое счастливый билет?
Alex5
881 / 616 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
02.11.2013, 22:43     Счастливый билет. Надо сократить время работы программы #7
Вместо того, чтобы вычислять A, B, C, D, E, F, G, H на каждом шаге цикла, можно сделать это только один раз - перед входом в цикл.
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
void func2(unsigned long *a, unsigned long *b)
{
    unsigned long counter=0;
    unsigned long A, B, C, D, E, F, G, H, X, Y;
 
    unsigned long i=*a;
    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;
 
    for( ; i<=*b; i++)
    {
        X=A+B+C+D;
        Y=E+F+G+H;
 
        if (X==Y)
        {
            counter++;
        }
        Next( A, B, C, D,   E, F, G, H );
    }
 
    cout<<counter;
 
}
А в функции Next() реализовать "сложение столбиком" - к числу ABCDEFGH прибавить 1.
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
02.11.2013, 22:51     Счастливый билет. Надо сократить время работы программы #8
Цитата Сообщение от zitxbit Посмотреть сообщение
Программы с бинарной арифметикой лучше всего писать на ассемблере.
во первых где ты увидел в этой задаче бинарную арифметику
во вторых чтобы соревноваться современными оптимизаторами, надо знать процессор "на зубок", распараллеливание команд, порядок доступа к кэшу, и много еще чего,как ты напишешь деление на 10?
в третьих программа на ассемблере не переносима

FoxTails,
раздели цикл на 2 по 10000
старшая часть и младшая
вторая подсказка сумма четырех цифр от 1 до 36
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.11.2013, 22:56     Счастливый билет. Надо сократить время работы программы #9
Цитата Сообщение от ValeryS Посмотреть сообщение
вторая подсказка сумма четырех цифр от 1 до 36
а 0 куда делся?
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
02.11.2013, 22:59     Счастливый билет. Надо сократить время работы программы #10
Цитата Сообщение от Tulosba Посмотреть сообщение
а 0 куда делся?
ты где нибудь видел билет
0000ХХХХ?????
в любом случае если билет 8 значный начинается с 1 в старшем разряде
может где нибудь и есть билеты с незначащими 0, но я не встречал
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.11.2013, 23:12     Счастливый билет. Надо сократить время работы программы #11
Цитата Сообщение от ValeryS Посмотреть сообщение
ты где нибудь видел билет
0000ХХХХ?????
в классических трамваях билеты вообще 6 значные. И да, они могут начинаться с нуля. Правда по условию задачи ТС начинаются с 1. Однако же из фразы
Цитата Сообщение от ValeryS Посмотреть сообщение
вторая подсказка сумма четырех цифр от 1 до 36
не ясно про какие цифры идет речь (первые, последние или еще какие).
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
02.11.2013, 23:21     Счастливый билет. Надо сократить время работы программы #12
Цитата Сообщение от Tulosba Посмотреть сообщение
И да, они могут начинаться с нуля.
хорошо принимается
Цитата Сообщение от Tulosba Посмотреть сообщение
не ясно про какие цифры идет речь (первые, последние или еще какие).
ладно расшифровываю
создаем массив на 37 элементов 0-36 обнуляем его
крутим чикл от 0 до 9999 это старшие 4 числа
подсчитываем сумму
ячейку массива с индексом равным сумме увеличиваем на 1
C++
1
arr[summ]++;
крутим цикл от 0 до 9999 это младшие 4 числа
подсчитываем сумму
обращаемся к ячейке с индексом равным сумме
если она равна 0 ничего не делаем
если нет уменьшаем значение на 1
количество билетов увеличиваем на 1
C++
1
2
3
4
5
if(arr[summ])
 {
  arr[summ]--;
  count++;
 }
правда необходимо "доработать напильником" для условий ТС
Alex5
881 / 616 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
02.11.2013, 23:43     Счастливый билет. Надо сократить время работы программы #13
Цитата Сообщение от ValeryS Посмотреть сообщение
крутим цикл от 0 до 9999
А если задан диапазон значений a == 12345678, b == 34566543, то в каких пределах крутить циклы?
Цитата Сообщение от ValeryS Посмотреть сообщение
если нет уменьшаем значение на 1
Например, 11114000, 11110400, 11110040, 11110004. Эти билеты счастливые. А если мы сразу уменьшаем на 1, то мы не досчитаемся многих билетов.

Добавлено через 3 минуты
Цитата Сообщение от ValeryS Посмотреть сообщение
ладно расшифровываю
создаем массив на 37 элементов 0-36 обнуляем его
крутим чикл от 0 до 9999 это старшие 4 числа
подсчитываем сумму
ячейку массива с индексом равным сумме увеличиваем на 1
Код C++
1
arr[summ]++;
Что же касается диапазона от 00000000 до 99999999, то дальше не нужны никакие циклы. Число счастливых билетов равно сумме квадратов элементов массива arr[].
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
02.11.2013, 23:47     Счастливый билет. Надо сократить время работы программы #14
Alex5,
ну я же сказал
Цитата Сообщение от ValeryS Посмотреть сообщение
"доработать напильником"
это же просто идея, возражения принимаются
Цитата Сообщение от Alex5 Посмотреть сообщение
Например, 11114000, 11110400, 11110040, 11110004.
хорошо давай не будем вычитать
нашим проще
уйдет ветвление

тогда в первом цикле
C++
1
arr[summ]=1;
во втором
C++
1
count+=arr[summ];
Добавлено через 1 минуту
Цитата Сообщение от Alex5 Посмотреть сообщение
Что же касается диапазона от 00000000 до 99999999, то дальше не нужны никакие циклы. Число счастливых билетов равно сумме квадратов элементов массива arr[].
не понял
переведи
Alex5
881 / 616 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
03.11.2013, 00:20     Счастливый билет. Надо сократить время работы программы #15
ValeryS,
Цитата Сообщение от ValeryS Посмотреть сообщение
не понял
переведи
Так вот, ты сам написал:
Цитата Сообщение от ValeryS Посмотреть сообщение
Код C++
1
count+=arr[summ];
В случае диапазона билетов от 00000000 до 99999999 эта операция будет выполнена arr[summ] раз. ( Сколько раз во втором цикле встретится билет с суммой summ? arr[summ] раз. )

Рассмотрим билеты с 4 цифрами ( от 0000 до 9999 ).
Сколько случаев, когда сумма старших цифр равна 2?
02 11 20 arr[2] == 3
Сколько счастливых билетов, у которых сумма старших цифр равна сумме младших цифр и равна 2?
0202
0211
0220
1102
1111
1120
2002
2011
2020
9 билетов == arr[2]*arr[2]

Добавлено через 6 минут
ValeryS,
Цитата Сообщение от ValeryS Посмотреть сообщение
не понял
переведи
Так вот, ты сам написал:
Цитата Сообщение от ValeryS Посмотреть сообщение
Код C++
1
count+=arr[summ];
В случае диапазона билетов от 00000000 до 99999999 эта операция будет выполнена arr[summ] раз. ( Сколько раз во втором цикле встретится билет с суммой summ? arr[summ] раз. )

Рассмотрим билеты с 4 цифрами ( от 0000 до 9999 ).
Сколько билетов, у которых сумма старших цифр равна 2 ? 02 11 20 arr[2] == 3
Сколько счастливых билетов, у которых сумма старших цифр равна сумме младших цифр и равна 2?
0202
0211
0220
1102
1111
1120
2002
2011
2020
9 билетов == arr[2]*arr[2]
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
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--)
нам ведб направление без разницы
ya_noob
_
200 / 144 / 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;
}
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
03.11.2013, 10:16     Счастливый билет. Надо сократить время работы программы #18
ya_noob,
число 19999998 и 20000000
как поведет себя второй цикл???
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
03.11.2013, 11:54  [ТС]     Счастливый билет. Надо сократить время работы программы #19
почему массив размера 37?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 11:59     Счастливый билет. Надо сократить время работы программы
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
03.11.2013, 11:59     Счастливый билет. Надо сократить время работы программы #20
Цитата Сообщение от FoxTails Посмотреть сообщение
почему массив размера 37?
ты обсуждение то читаешь?
за ходом мысли следишь?
или только готовые коды просматриваешь?
Цитата Сообщение от ValeryS Посмотреть сообщение
вторая подсказка сумма четырех цифр от 1 до 36
Цитата Сообщение от Tulosba Посмотреть сообщение
а 0 куда делся?
Цитата Сообщение от ValeryS Посмотреть сообщение
создаем массив на 37 элементов 0-36 обнуляем его
Yandex
Объявления
03.11.2013, 11:59     Счастливый билет. Надо сократить время работы программы
Ответ Создать тему
Опции темы

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