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

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

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

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

06.04.2012, 14:26. Просмотров 1779. Ответов 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
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 14:31 #2
через файл надо?
0
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 14:39  [ТС] #3
Цитата Сообщение от Nekto Посмотреть сообщение
через файл надо?
да...
0
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;
}
1
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 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
Не говоря о том, что достаточно трёх умножений, чтобы произошло переполнение даже такого большого числа.
0
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 15:20 #6
Цитата Сообщение от Deviaphan Посмотреть сообщение
При N > 20 расчёт не верен.
Первая строка содержит два целых числа N и K (0 < N ≤ 20, ...
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 15:20 #7
Цитата Сообщение от SpecBM Посмотреть сообщение
N ≤ 20
Это я видел, но для количества всё-таки про константу упомянул.)
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
06.04.2012, 15:47 #8
попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
в среднем это не изменит победителя. максимальное произведение получит погрешность, но останется максимальным

правда тут про знаки надо помнить. знаки всё очень сильно портят.
Ну как? Разве не финт ушами?
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 16:00 #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
При j > 0 расчёт не верен.
Почему?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2012, 16:14 #10
Можно просто С-шное чтение использовать, потоки долговато работают.
0
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
нужно попробовать)
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:19 #12
Цитата Сообщение от SpecBM Посмотреть сообщение
нужно попробовать)
Не нужно. Считывай не по одному значению, а блоками. У тебя тормоза именно из-за обращения к диску.

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

Не по теме:

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

Если писать арифметику через стринг, разве это будет быстрее 2 секунд для почти 2 миллионов умножений?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2012, 17:32
Привет! Вот еще темы с ответами:

Оптимизация программы - 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 ...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
06.04.2012, 17:32
Ответ Создать тему
Опции темы

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