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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
#1

нужна оптимизация приложения - C++

06.04.2012, 14:26. Просмотров 1804. Ответов 39
Метки нет (Все метки)

Одной ночью коту Мурзику приснилось, что он судья на математических соревнованиях крыс. Соревнования проводятся среди N команд по K крыс в каждой. Соревнования проводятся в К раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.
Технические условия
Входные данные
Первая строка содержит два целых числа N и K (0 < N ≤ 20, 0 < K ≤ 100000). Следующие К строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.
Выходные данные
Номер команды, выигравшей соревнования. Если несколько команд имеют одинаковые результаты, то побеждает та, у которой больше номер.

Лимит времени: 2 секунды
Лимит памяти: 64 MB


вот решение:
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>
#include <fstream>
 
using namespace std; 
 
int main() {
   ifstream inf("input.txt");
   ofstream outf("output.txt");
   int k, n, i, j;
   float *a, t;
   inf >> n;
   inf >> k;
   a = new float[n];
   for(i = 0; i < n; i++) *(a + i) = 1;
   
   for (j = 0; j < k; j++)
       for (i = 0; i < n; i++){
           inf >> t;
           *(a + i) *= t;
       }
   t = *a;
   j = 1;
   cout << endl;
   for (i = 0; i < n; i++) 
       if (*(a + i) >= t) {
           t = *(a + i);
           j = i+1;
        }
   inf.close();
   outf<< j <<"\n";
   outf.close();
   return 0;
}
задача проходит 16 тестов из 20
на четырех тестах не хватает времени (2 сек). как решить эту проблему?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2012, 14:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос нужна оптимизация приложения (C++):

Запустить параллельного приложения / Запуск приложения в новом консольном окне - C++
Доброго времени суток! Хотел спросить как в коде консольного приложения запустить ещё одно консольное приложение, так чтобы оно...

Разработка web-приложения, приложения под ОС Android,Windows - C++
Доброго времени суток ребят, кто узрел эту тему прошу не проходите мимо, прошу вашей помощи.Мне требуется определиться с темой для...

Проект консольного приложения из Windows приложения - C++
привет всем. В чем может быть ошибка? 1&gt;MSVCRTD.lib(crtexew.obj) : error LNK2019: ссылка на неразрешенный внешний символ _WinMain@16 в...

оптимизация - C++
какие 5 способов оптимизации?

Оптимизация - C++
Как-нибудь можно уменьшить размер кода, т.е. сократить количество строк данного кода: #include &lt;cmath&gt; #include &quot;windows.h&quot; ...

Оптимизация - C++
Мне нужно на определенную часть программы дать указание компилятору не оптимизировать эту часть. Может кто знает как это сделать???? ...

39
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:56 #16

Не по теме:

Цитата Сообщение от Nekto Посмотреть сообщение
Не будь таким агрессивным
Вот если бы я сказал, что по IP тебя вычислю и мышке провод перегрызу, то вот это была бы агрессия.)




Цитата Сообщение от Nekto Посмотреть сообщение
Если писать арифметику через стрин
Нет!
Сейчас ты считываешь ОДНО значение. А нужно считывать сразу всю строку в массив и потом уже из этого массива брать значения. Только считывать не в цикле, а при помощи read. 100000 значений это всего лишь 400 килобайт, так что в лимит памяти легко войдёт.
0
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 17:56  [ТС] #17
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
а можно по подробней?



если поставить
int a[20];
for (int i = 0; i<N; i++) a[i] = 1; // забыли))

проходит 95% тестов
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:57 #18
Стоп! Файл же текстовый, а не бинарный... Read не поможет...
0
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 18:10  [ТС] #19
со скоростью уже все норм.
осталось решить как оперировать с большимы числами.
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 18:12 #20
Цитата Сообщение от SpecBM Посмотреть сообщение
как оперировать с большимы числами.
Умножать в double.
0
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 18:17  [ТС] #21
Цитата Сообщение от Deviaphan Посмотреть сообщение
Умножать в double.
даже в long double не проходит тестов.
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 18:26 #22
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
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> lnum;
const int base = 1000*1000*1000;
 
lnum mult (lnum a, int b)
{
int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i)
 {
  if (i == a.size())
   a.push_back (0);
  long long cur = carry + a[i] * 1ll * b;
  a[i] = int (cur % base);
  carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
   a.pop_back();
return a;
}
 
int main()
{
 FILE *f=fopen("input.txt","r");
 int N, K;
 fscanf(f,"%d%d",&N,&K);
 lnum* a=new lnum[N];
 for (int i=0;i<N;i++)
  a[i].push_back(1);
 int temp;
 for (int i=0;i<K;i++)
  {
   for (int j=0;j<N;j++)
    {
     fscanf(f,"%d",&temp);
     a[j]=mult(a[j],temp);
    }
  }
 fclose(f);
 int max_i=0;
 lnum max=a[0];
 for (int i=1;i<N;i++)
  if (a[i]>=max) { max=a[i]; max_i=i; }
 f=fopen("output.txt","w");
 fprintf(f,"%d\n",max_i+1);
 fclose(f);
 return 0;
}
70%, по времени не успеваю
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 18:29 #23
Цитата Сообщение от SpecBM Посмотреть сообщение
даже в long double не проходит тестов.
Тогда попробуй, как тебе уже советовали, считать не по честному. Сделай для каждого загруженного целого сдвиг на 24 бита вправо и умножай получившиеся числа. Они будут не больше 255. Может и хватит даблов.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2012, 19:08 #24
Ну там тема на длинную арифметику, так что придется ее написать.
Я за 2 минуты накидал решение с double, максимальное время работы - 0.6 секунд, но на 6 тестах валится где-то.
Тут длинную арифметику нужно неплохо так реализовать, если хранить 9 знаков в одном элементе массива, то все равно будет не особо быстро. Вроде можно по 17-18 хранить, но тогда нужно будет контролировать переполнение через asm-вставки. Где-то читал про такое, но не уверен, что даже на ассемблере можно умножить 2 64битных числа.
0
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 19:16  [ТС] #25
нужна оптимизация приложения

хз что не так
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 20:51 #26
быдлокод :)
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
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> lnum;
const int base = 1000*1000*1000;
 
lnum mult (lnum a, int b)  //ÓìГ*îæåГ*ГЁГҐ äëèГ*Г*îãî Г*Г* êîðîòêîå
//ÓìГ*îæГ*ГҐГІ äëèГ*Г*îå a Г*Г* êîðîòêîå b (b < (base)) 
//ГЁ ñîõðГ*Г*ГїГҐГІ ðåçóëüòГ*ГІ Гў a:
{
 int carry = 0;
 for (size_t i=0; i<a.size() || carry; ++i) 
  {
   if (i == a.size())
    a.push_back (0);
   long long cur = carry + a[i] * 1ll * b;
   a[i] = int (cur % base);
   carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();
return a;
}
 
bool checks(lnum a, lnum b)  // a>=b 
{
 if (a.size()>b.size()) return true;
 if (a.size()<b.size()) return false;
 for (size_t i=a.size()-1;i>=0;--i)
  {
   if (a[i]>b[i]) return true;
   if (a[i]<b[i]) return false;
  }
 return true;
} 
 
int main()
{
  FILE *f=fopen("input.txt","r");
  int N, K;
  fscanf(f,"%d%d",&N,&K);
  lnum* a=new lnum[N];
  bool* sign=new bool[N]; //Г¬Г*Г±Г±ГЁГў õðГ*Г*ГҐГ*ГЁГї Г§Г*Г*ГЄГ*
  int **inp=new int*[N];
  for (int i=0;i<N;i++)
   inp[i]=new int[K];
  int temp;
  for (int i=0;i<N;i++)
   {
    a[i].push_back(1); //äëÿ ГіГ¬Г*îæåГ*ГЁГї
    sign[i]=true;      //+
   }
  for (int i=0;i<K;i++)
   {
    for (int j=0;j<N;j++)
     {
      fscanf(f,"%d",&temp);
      if (temp<0) { sign[j]=!sign[j]; inp[j][i]=-temp; } //åñëè "-", ГІГ® ìåГ*ГїГҐГ¬ Г§Г*Г*ГЄ
       else inp[j][i]=temp;
     }
   }
  fclose(f);
  int max_i=0;
  bool all_minus=true; //ïðîâåðêГ* ГҐГ±ГІГј ëè ïîëîæèòåëüГ*ûå Г·ГЁГ±Г«Г*
  for (int i=0;i<N;i++)
   if (!sign[i]) { all_minus=false; break; } 
  if (!all_minus)
   {
    for (int i=0;i<N;i++)
     {
      if (sign[i]) //åñëè ïëþñ
       {
        for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
         a[i]=mult(a[i],inp[j][i]);
        max_i=i; //Г§Г*ïîìèГ*Г*ГҐГ¬ ГЁГ*äåêñ äëÿ Г¬Г*êñèìóìГ*
       }
     }
    lnum max=a[max_i];  
    for (int i=0;i<N;i++)
     {
      if (sign[i]) //åñëè ïëþñ
       {
        if (i!=max_i) //åñëè Г*ГҐ òîò æå ýëåìåГ*ГІ
        if (checks(a[i],max)) //Г*[i]>=max
         { 
          max_i=i; 
          max=a[i]; 
         }
       }
     }    
   } 
  else
   {
    for (int i=0;i<N;i++)
     {
      if (!sign[i])
       {
        for (int j=0;j<K;j++)
         a[i]=mult(a[i],inp[j][i]);
        max_i=i;
       }
     }
    lnum max=a[max_i]; 
    for (int i=0;i<N;i++)
     {
      if (!sign[i])
       {
        if (i!=max_i)
        if (!checks(a[i],max)) 
         { 
          max_i=i; 
          max=a[i]; 
         }
       }
     }    
   } 
  f=fopen("output.txt","w");
  fprintf(f,"%d\n",max_i+1);
  fclose(f);
  delete [] a;
  delete [] sign;
  return 0;
}
Подскажите, а в моём быдло-коде что не так? Процедурку умножения стырил, там по идее всё правильно должно быть.

Добавлено через 49 минут
С умножением что-то не так... Проверил - в конце выводит то, что задал в начале (пробовал другие числа любой длины кроме 1 начальным значением).
0
castaway
Эксперт С++
4915 / 3023 / 370
Регистрация: 10.11.2010
Сообщений: 11,080
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 21:18 #27
Nekto, нужна оптимизация по скорости - не используй С++, используй Си.
Любой алгоритм на С++ можно переписать на Си, который будет выполняться быстрее. Классы, STL и т.д. и т.п. только замедляют выполнение программы.
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 21:19 #28
Цитата Сообщение от lazybiz Посмотреть сообщение
Nekto, нужна оптимизация по скорости - не используй С++, используй Си.
Любой алгоритм на С++ можно переписать на Си, который будет выполняться быстрее. Классы, STL и т.д. и т.п. только замедляют выполнение программы.
В последнем коде надо найти ошибку Он ошибочные результаты выдаёт
0
castaway
Эксперт С++
4915 / 3023 / 370
Регистрация: 10.11.2010
Сообщений: 11,080
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 21:21 #29
Цитата Сообщение от Nekto Посмотреть сообщение
В последнем коде надо найти ошибку Он ошибочные результаты выдаёт
Это не решит твоей проблемы. Я сильно сомневаюсь что программа пройдет все тесты.
0
Kuzia domovenok
1950 / 1803 / 138
Регистрация: 25.03.2012
Сообщений: 6,245
Записей в блоге: 1
06.04.2012, 22:45 #30
Да ладно вам, считайте приближённо, складывая только порядки величин.
Вот: как вам это? Не уверен, правда, что будет быстрее.

а можно по подробней?
Вот: набросал поподробней. Сплошные битовые операции, ни одного умножения. Правда, не уверен, что операция
C++
1
while(!(num&mask)){mask=mask>>1;cnt--;}
быстрее умножения. Совсем не уверен. Зато оптимизация! И никаких крестопроблем, характерных для ООП и крестоплюсов.
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
#include <iostream>
#include <fstream>
#include <limits>
using namespace std;
//MAXINT32=1<<31-1
int main(){
    ifstream inf("input.txt");
    ofstream outf("output.txt");
    int n, k, num;
    int i, j;
    const int hbit=1<<30;
    int mask;
    int result, cnt;
    int sign;
    int max, max_i;
    inf >> n;
    inf >> k;
    max=1<<31;//MIN_INT32
    max_i=-1;
    sign=1;//positive
    for (i=0; i<k; i++){
        result=0;//резалт хранит сумму порядков всех чисел, сами числа не хранятся.
        for (j=0; j<n; j++){
            mask=hbit;
            inf>>num;
            if (num<0){
                cnt=30;
                while(!(num&mask)){mask=mask>>1;cnt--;}//число положительное, подсчитываем число нулевых битов в 
//начале, чтобы определить ближайшую степень двойки
                if (num&(mask>>1))result+=cnt+1;//если второй по старшинству бит - единица, округляем в большую сторону
                else
                result+=cnt;
            }
            else{
                sign=sign^1; //if (sign==0) sign=1; else sign=0;
                cnt=30;
                while(num&mask){mask=mask>>1; cnt--;}//число отрицательное, подсчитываем число единичных битов в 
//начале, чтобы определить ближайшую степень двойки
                if (num&(mask>>1))result+=cnt;//если второй по старшинству бит - единица, округляем в большую сторону
                else 
                result+=(cnt+1);
            }
        }
        if ((result>max)&&(sign)){//работает если хоть одно произведение положительно. и если нет крайне близких по значению произведений
            result=max;
            max_i=i;
        }
        //else if result==max && sign , то считаем вручную оба произведения.
        //и всё равно все расчёты были приблизительными, но зато сверх быстрыми.
    }
    inf.close();
    outf<< max_i <<"\n";
    outf.close();
    return 0;
}
0
06.04.2012, 22:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2012, 22:45
Привет! Вот еще темы с ответами:

Оптимизация программы - C++
#include&lt;std_lib_facilities.h&gt; #include&lt;conio.h&gt; void moveHorse(int &amp;, int , int , int, int &amp;, int &amp;, int &amp;);//переставляет коня ...

Оптимизация памяти - C++
Доброго времени суток. У меня есть класс(код показывать не буду, он не нужен), в приватном поле есть переменная типа int *, то есть класс...

Оптимизация кода - C++
В общем дело такое, мне нужно 2 одинаковые программы(небольшие), только одна программа должна быть неоптимизированная, а другая, точно...

Оптимизация у компилятора С++ - C++
Добрый день! Начал изучать С++ и случайно заглянул в дизассемблированный код. Лучше бы этого не делал! &gt;8- 01352984 mov ...


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

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

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