0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 59
1

Оптимизация [сокращение времени выполнения]

06.10.2016, 15:27. Показов 991. Ответов 13
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте, стояла такая задача:
У вас имеются два билета. Номер первого билета равен M, второго – N.
Лимиты M и N: 10000000 ≤ M < N ≤ 99999999.
Ваша задача определить количество "счастливых билетов" в данном диапазоне.
Билет "счастливый", если сумма первых 4 цифр равна сумме последних 4 цифр.
Ввод:
Вводятся номера двух билетов.

Вывод
Количество "счастливых билетов" в данном диапазоне.

Пример:
a: 11111110
b: 11111112
ans: 1

a: 10000000
b: 99999999
ans: 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
#include <iostream>
using namespace std;
int lucky(int a, int b)
{
    int r1 = 0,r2 = 0,i,timer = 0;
    for(int mi=a;mi<=b;mi++)
    {
        int var1 = mi;
        for (i = 0;i < 4;i++)
        {
            int temp = var1 % 10;
            var1 /= 10;
            r1 += temp;
            int temp2 = var1 % 10;
            var1 /= 10;
            r2 += temp2;
        }
        if (r1 == r2)
        {
            timer++;
        }
        r1 = 0;
        r2 = 0;
    }
    return timer;
}
int main()
{
    int a, b;
    cin >> a >> b;
    cout << lucky(a, b) << endl;
    return 0;
}
Однако существует ограничение по времени выполнения операции: не более 4000ms
В моём случае операция занимает в среднем от 7.5 до 9 секунд.
Не могли бы вы помочь с оптимизацией? Желательно с использованием указателей.

Добавлено через 1 час 58 минут
C++
1
2
3
4
        if (r1 == r2)
        {
            timer++;
        }
Проблема, я так понял, в этой части...
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.10.2016, 15:27
Ответы с готовыми решениями:

Оптимизация [сокращение времени выполнения]
Всем привет! В общем стояла такая задача: Посчитать среднее количество букв в предложении,...

Оптимизация времени выполнения
Доброго времени суток. Есть следующая задача. Задача олимпиадная, потому учитывается время...

Оптимизация времени выполнения
Здравствуйте! Спасибо что заглянули в тему :yes: Возник вопрос, который меня весьма озадачил:...

Сокращение кода и времени проверки (задача)
Однажды Вася очень долго просидел на остановке, прежде чем дождался своего автобуса. Чтобы как-то...

13
7 / 7 / 13
Регистрация: 04.10.2016
Сообщений: 52
06.10.2016, 15:46 2
у вас под переменной timer подразумевается время? если так то это не так, на самом деле это счетчик количества удовлетворенных условию (r1 == r2), как вы время измеряете?
скорость выполнения вашего кода зависит от вычислительной мощности компьютера

Добавлено через 14 минут
операции деления занимают "много процессорного времени", и проблема не в 18-21 строках вашего кода, а в 5-17
0
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 59
06.10.2016, 15:55  [ТС] 3
Хорошо, про timer знаю, просто название такое в голову полезло))
Слушайте, а альтернатива строкам 5-17 есть? Если да, то можно пример?
0
53 / 53 / 19
Регистрация: 09.12.2015
Сообщений: 215
06.10.2016, 15:58 4
Sultik_Zaka, могу посоветовать книгу: Макконнелл С. "Совершенный код". Именно "Часть V Усовершенствование кода"

В гугле сразу первые две ссылки - документ.
0
7 / 7 / 13
Регистрация: 04.10.2016
Сообщений: 52
06.10.2016, 15:59 5
в том то и дело, вам необходимо разработать более быстрый алгоритм сэкономив на делениях
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.10.2016, 16:23 6
Sultik_Zaka, Ваш алгоритм, конечно, чудовищен. Нужен совсем другой подход. Надо выяснить, сколько четырехзначных чисел (от 0 до 9999) дают суммы цифр S = 0, 1, 2 ... 36. Пусть это будем S[i] - количество 4-х значных чисел, дающих сумму i. Затем просто сложить квадраты S[i]. Это будет количество всех счастливых билетов. Потом из них нужно будет отсечь не удовлетворяющие условию a <= N <= b. Как это сделать - вопрос не простой, но решаемый. Во всяком случае задача будет решаться за разумное время.
1
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
06.10.2016, 16:35 7
Байт, но всегда надо начинать с алгоритма в лоб и потом еще оптимизировать делая замеры )
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.10.2016, 16:46 8
Цитата Сообщение от rikimaru2013 Посмотреть сообщение
всегда надо начинать с алгоритма в лоб
Не уверен. Лобовое решение данной задачи уже показывает, что придется иметь дело с перебором 108. Это уже должно настораживать. А для 10-значных чисел (1010) и вообще не имеет смысла браться.
Да и замеров никаких не надо. Ясно, что 104 много меньше 108
1
553 / 361 / 206
Регистрация: 27.11.2014
Сообщений: 1,049
06.10.2016, 17:50 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
#include <iostream>
 
int lucky(int a, int b) {
    /*максимальное количество сочетаний из 4 цифр, для каждой суммы (можно сразу их в массив забить)*/
    int m[37] = {0};
    for(int i = 0; i <= 9999; ++i) {
        int val = i, sum = 0;
        while(val) {
            sum += val % 10;
            val /= 10;
        }
        m[sum] += 1;
    }
    /*исключаем из суммы те, что меньше порога*/
    for(int i = 0, l = a % 10000; i < l; ++i) {
        int val = i, sum = 0;
        while(val) {
            sum += val % 10;
            val /= 10;
        }
        m[sum] -= 1;
    }
    /*исключаем из суммы те, что больше порога*/
    for(int i = 1 + (b % 10000); i <= 9999; ++i) {
        int val = i, sum = 0;
        while(val) {
            sum += val % 10;
            val /= 10;
        }
        m[sum] -= 1;
    }
    /*считаем сумму левой части и добавляем количество возможных чисел с той же суммой из правой*/
    int cnt = 0;
    for(int i = a / 10000, l = b / 10000; i <= l; ++i) {
        int val = i, sum=0;
        while(val) {
            sum += val % 10;
            val /= 10;
        }
        cnt+=m[sum];
    }       
            
    return cnt;
}
 
int main() {
    int a, b;
    std::cin >> a >> b;
    
    std::cout << "нессыпрорвёмся" << lucky(a, b) << std::endl;
 
    return 0;
}
Добавлено через 16 минут
Если не заморачиваться на строгом следование комментам, то можно сразу так:
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
int lucky(int a, int b) {
    
    int m[37] = {0};        
    for(int i = a % 10000, l = b % 10000; i <= l; ++i) {
        int val = i, sum = 0;
        while(val) {
            sum += val % 10;
            val /= 10;
        }
        m[sum] += 1;
    }
    
    /*считаем сумму левой части и добавляем количество возможных чисел с той же суммой из правой*/
    int cnt = 0;
    for(int i = a / 10000, l = b / 10000; i <= l; ++i) {
        int val = i, sum=0;
        while(val) {
            sum += val % 10;
            val /= 10;
        }
        cnt+=m[sum];
    }       
            
    return cnt;
}
1
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 59
06.10.2016, 18:10  [ТС] 10
Спасибо, однако само задание требует к тому же и использование указателей, в противном случае контестер считает код неправильным.
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
06.10.2016, 19:25 11
Цитата Сообщение от ture Посмотреть сообщение
"нессыпрорвёмся"

10005000
20001000
-214141

Цитата Сообщение от ture Посмотреть сообщение
Если не заморачиваться
10005000
20001000
0

Мой вариант:
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
///////////////////////////////////////////////////////////////////////////////
//1.
///////////////////////////////////////////////////////////////////////////////
//У вас имеются два билета. Номер первого билета равен M, второго – N.
//Лимиты M и N: 10000000 ? M < N ? 99999999.
//Ваша задача определить количество "счастливых билетов" в данном диапазоне.
//Билет "счастливый", если сумма первых 4 цифр равна сумме последних 4 цифр.
//Ввод:
//Вводятся номера двух билетов.
 
//Вывод
//Количество "счастливых билетов" в данном диапазоне.
 
//Пример:
//a: 11111110
//b: 11111112
//ans: 1
 
//a: 10000000
//b: 99999999
//ans: 4379055
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <string>
///////////////////////////////////////////////////////////////////////////////
typedef long long                           T_int;
typedef std::map    < T_int,    T_int   >   T_count_of_sum;
///////////////////////////////////////////////////////////////////////////////
T_int   sum_digits( T_int   n )
{
    T_int   res{};
 
    do
    {
        res     +=  n % 10;
        n       /=  10;
    }
    while(n);
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
void    fill_count_of_tail_dig_sum
    (
        T_int               min,
        T_int               max,
        T_int               mod,
        T_count_of_sum  &   count_of_sum
    )
{
    for( T_int  n{min}; n <= max; ++n )
    {
        ++count_of_sum  [
                            sum_digits( n % mod )
                        ];
    }
}
///////////////////////////////////////////////////////////////////////////////
T_int   winning_tickets_count_in_segment
    (
        T_int   min,
        T_int   max
    )
{
    T_count_of_sum  count_of_sum_L;
    T_count_of_sum  count_of_sum_R;
    T_int           num_len     =   std::to_string( max ).size();
    T_int           mod         =   std::pow( 10,   num_len / 2 );
 
    fill_count_of_tail_dig_sum
        (
            min /   mod,
            max /   mod,
            mod,
            count_of_sum_L
        );
 
    fill_count_of_tail_dig_sum
        (
            min,
            std::min    (
                            min + mod - 1,
                            max
                        ),
            mod,
            count_of_sum_R
        );
 
    T_int   res{};
 
    for( T_int  sum{}; sum <= 9 * num_len / 2; ++sum )
    {
        res +=      count_of_sum_L[ sum ]
                *   count_of_sum_R[ sum ];
    }//for
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_int     a{};
    T_int     b{};
 
    std::cin    >>  a   >>  b;
 
    std::cout   <<  winning_tickets_count_in_segment( a, b )
                <<  std::endl;
}
0
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 59
08.10.2016, 06:45  [ТС] 12
Ваш вариант как-то не хочет принимать компилятор
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
08.10.2016, 06:51 13
Цитата Сообщение от Sultik_Zaka Посмотреть сообщение
Ваш вариант как-то не хочет принимать компилятор
С++11 надо подключить.
0
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 59
09.10.2016, 16:56  [ТС] 14
Проблема решена!
Держите код, может кому пригодится:
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
#include <iostream>
using namespace std;
int lucky(int *a,int *b,char *sum)
{
  int count3 = 0;
  for (int i = 0;i <= 99;i++) sum[i] = i / 10 + i % 10;
  int h = 0, h_sum;
  for (int i = *a;i <= *b;i++)
  {
    int l = i % 10000;
    if (l == 0 || h == 0) {
      h = i / 10000;
      h_sum = *(sum + h / 100) + *(sum + h % 100);
    }
    count3 += (sum[l / 100] + sum[l % 100] == h_sum);
  }
  return count3;
}
int main()
{
  int a, b;
  char sum[100];
  cin >> a >> b;
  cout << lucky(&a,&b,sum) << endl;
  return 0;
}
0
09.10.2016, 16:56
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.10.2016, 16:56
Помогаю со студенческими работами здесь

Полиморфизм времени выполнения/времени компиляции
Здравствуйте, подскажите, пожалуйста, литературу, где мне внятно можно узнать что такое полиморфизм...

Ошибка времени выполнения
Я пишу проэкт в Visual Studia 2008 на C++. У меня есть несколько проблем. Во-первых, когда я...

Измерение времени выполнения
Подскажите пожалуйста как измерить время выполнения чего-то с наносекундной точностью. ...

Ошибка времени выполнения.
Вот код: void Add_Kod ( _kod*&amp; KodBuf, int a, char* buf, char* buf2) { if(a==1) { KodBuf...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru