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

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

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

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

06.04.2012, 14:26. Просмотров 1724. Ответов 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 сек). как решить эту проблему?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2012, 14:26     нужна оптимизация приложения
Посмотрите здесь:

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

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

Оптимизация алгоритма - C++
Условие: Дана выборка (X_i, Y_i)_{i=1}^N. Предполагается, что она была построена по следующему закону: \begin{cases} Y=\beta \xi...

Оптимизация кода - C++
Как сравнить 2 строки. Вот как их задавал в ходе программы string h,b; ... char * text = NULL; if ( OpenClipboard(0) ) { ...

Циклы и их оптимизация - C++
Доброго времени суток! Имеется код программы, необходимо оптимизировать вложенный цикл чтобы время потраченное на выполнение программы...

Оптимизация программы - C++
Здравствуйте,задали задачку :Напишите программу, которая будет выполнять последовательность запросов вида ADD num, PRESENT num и COUNT (без...

Оптимизация алгоритма - C++
#include&lt;iostream&gt; #include&lt;stdlib.h&gt; #include&lt;time.h&gt; #include&lt;iomanip&gt; using namespace std; #define jaba for(i=0; i&lt;k; i++)...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 14:31     нужна оптимизация приложения #2
через файл надо?
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 14:39  [ТС]     нужна оптимизация приложения #3
Цитата Сообщение от Nekto Посмотреть сообщение
через файл надо?
да...
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 14:45     нужна оптимизация приложения #4
Цитата Сообщение от SpecBM Посмотреть сообщение
да...
Это на сайте каком-то?
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 <cstdio>
int main() 
{
   FILE *f=fopen("input.txt","r");
   int N, K;
   fscanf(f,"%d%d",&N,&K);
   long long a[20]={1};
   int temp;
   for (int i=0;i<K;i++)
    {
     for (int j=0;j<N;j++)
      {
       fscanf(f,"%d",&temp);
       a[j]*=temp;
      }
    }
   fclose(f);
   int max_i=0;
   long long 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",max_i+1);
   fclose(f);
   return 0;
}
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 15:20     нужна оптимизация приложения #5
Цитата Сообщение от Nekto Посмотреть сообщение
a[j]*=temp;
При j > 0 расчёт не верен.

Добавлено через 58 секунд
Цитата Сообщение от Nekto Посмотреть сообщение
a[20]
При N > 20 расчёт не верен.

Добавлено через 2 минуты
Цитата Сообщение от Nekto Посмотреть сообщение
long long a
Не говоря о том, что достаточно трёх умножений, чтобы произошло переполнение даже такого большого числа.
castaway
Эксперт С++
4880 / 3016 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 15:20     нужна оптимизация приложения #6
Цитата Сообщение от Deviaphan Посмотреть сообщение
При N > 20 расчёт не верен.
Первая строка содержит два целых числа N и K (0 < N ≤ 20, ...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 15:20     нужна оптимизация приложения #7
Цитата Сообщение от SpecBM Посмотреть сообщение
N ≤ 20
Это я видел, но для количества всё-таки про константу упомянул.)
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
06.04.2012, 15:47     нужна оптимизация приложения #8
попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
в среднем это не изменит победителя. максимальное произведение получит погрешность, но останется максимальным

правда тут про знаки надо помнить. знаки всё очень сильно портят.
Ну как? Разве не финт ушами?
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 16:00     нужна оптимизация приложения #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
При j > 0 расчёт не верен.
Почему?
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2012, 16:14     нужна оптимизация приложения #10
Можно просто С-шное чтение использовать, потоки долговато работают.
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 16:32  [ТС]     нужна оптимизация приложения #11
Цитата Сообщение от Nekto Посмотреть сообщение
Это на сайте каком-то?
e-olimp.com.ua

Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
нужно попробовать)
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:19     нужна оптимизация приложения #12
Цитата Сообщение от SpecBM Посмотреть сообщение
нужно попробовать)
Не нужно. Считывай не по одному значению, а блоками. У тебя тормоза именно из-за обращения к диску.

Добавлено через 51 секунду
Цитата Сообщение от Nekto Посмотреть сообщение
Почему?
a[0] == 1, все последующие равны нулю.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 17:20     нужна оптимизация приложения #13
Цитата Сообщение от Deviaphan Посмотреть сообщение
При j > 0 расчёт не верен.
Мой код прошел 50% тестов Добавил только \n при выводе.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:30     нужна оптимизация приложения #14
Цитата Сообщение от Nekto Посмотреть сообщение
Мой код прошел 50% тестов
Не заданные явно элементы инициализируются конструктором по умолчанию. Для чисел это 0. Если твой компилятор поступает иначе - удали его, отформатируй винт и сожги монитор. С мышью тоже что-нибудь можешь сделать, она тоже в этом замешана.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 17:32     нужна оптимизация приложения #15
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не заданные явно элементы инициализируются конструктором по умолчанию. Для чисел это 0. Если твой компилятор поступает иначе - удали его, отформатируй винт и сожги монитор. С мышью тоже что-нибудь можешь сделать, она тоже в этом замешана.
да, с конструктором ты прав, исправил ту строчку, уже 85% тестов проходит

Не по теме:

Не будь таким агрессивным

Если писать арифметику через стринг, разве это будет быстрее 2 секунд для почти 2 миллионов умножений?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:56     нужна оптимизация приложения #16

Не по теме:

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




Цитата Сообщение от Nekto Посмотреть сообщение
Если писать арифметику через стрин
Нет!
Сейчас ты считываешь ОДНО значение. А нужно считывать сразу всю строку в массив и потом уже из этого массива брать значения. Только считывать не в цикле, а при помощи read. 100000 значений это всего лишь 400 килобайт, так что в лимит памяти легко войдёт.
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% тестов
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:57     нужна оптимизация приложения #18
Стоп! Файл же текстовый, а не бинарный... Read не поможет...
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 18:10  [ТС]     нужна оптимизация приложения #19
со скоростью уже все норм.
осталось решить как оперировать с большимы числами.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2012, 18:12     нужна оптимизация приложения
Еще ссылки по теме:

Оптимизация программы на С++ - C++
Помогите оптимизировать программу на С++, я не представляю, что в ней можно изменить. Хотя бы намек на функцию, в которой нужна...

Оптимизация функции - C++
Здравствуйте, каким образом(кроме switch) можно оптимизировать эту функцию(Нужен самый оптимизированный вариант): void blabla() { ...

Оптимизация программы - 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++
Программа ищет одинаковые файлы в папке где сама находится(по маске или расширению), по хэшу, и перемещает все копии в отдельную папку. ...

Оптимизация робота - C++
Написал вот эту задачу: Робот Имя входного файла: robot.in Имя выходного файла: robot.out Ограничение по времени: 2 секунды ...


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

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 18:12     нужна оптимизация приложения #20
Цитата Сообщение от SpecBM Посмотреть сообщение
как оперировать с большимы числами.
Умножать в double.
Yandex
Объявления
06.04.2012, 18:12     нужна оптимизация приложения
Ответ Создать тему
Опции темы

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