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

@SpecBM · Регистрация: 16.01.2010

Студворк — интернет-сервис помощи студентам

Одной ночью коту Мурзику приснилось, что он судья на математических соревнованиях крыс. Соревнования проводятся среди 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 сек). как решить эту проблему?

@Nekto · 06.04.2012, 14:31

через файл надо?

@SpecBM · 06.04.2012, 14:39 **[ТС]**

Сообщение от Nekto

через файл надо?

да...

@Nekto · 06.04.2012, 14:45

Сообщение от 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 · 06.04.2012, 15:20

Сообщение от Nekto

a[j]*=temp;

При j > 0 расчёт не верен.

Добавлено через 58 секунд

Сообщение от Nekto

a[20]

При N > 20 расчёт не верен.

Добавлено через 2 минуты

Сообщение от Nekto

long long a

Не говоря о том, что достаточно трёх умножений, чтобы произошло переполнение даже такого большого числа.

@castaway · 06.04.2012, 15:20

Сообщение от Deviaphan

При N > 20 расчёт не верен.

Первая строка содержит два целых числа N и K (0 < N ≤ 20, ...

@Deviaphan · 06.04.2012, 15:20

Сообщение от SpecBM

N ≤ 20

Это я видел, но для количества всё-таки про константу упомянул.)

@Kuzia domovenok · 06.04.2012, 15:47

попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
в среднем это не изменит победителя. максимальное произведение получит погрешность, но останется максимальным

правда тут про знаки надо помнить. знаки всё очень сильно портят.
Ну как? Разве не финт ушами?

@Nekto · 06.04.2012, 16:00

Сообщение от Deviaphan

При j > 0 расчёт не верен.

Почему?

@diagon · 06.04.2012, 16:14

Можно просто С-шное чтение использовать, потоки долговато работают.

@SpecBM · 06.04.2012, 16:32 **[ТС]**

Сообщение от Nekto

Это на сайте каком-то?

e-olimp.com.ua

Сообщение от Kuzia domovenok

попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13

нужно попробовать)

@Deviaphan · 06.04.2012, 17:19

Сообщение от SpecBM

нужно попробовать)

Не нужно. Считывай не по одному значению, а блоками. У тебя тормоза именно из-за обращения к диску.

Добавлено через 51 секунду

Сообщение от Nekto

Почему?

a[0] == 1, все последующие равны нулю.

@Nekto · 06.04.2012, 17:20

Сообщение от Deviaphan

При j > 0 расчёт не верен.

Мой код прошел 50% тестов

Добавил только \n при выводе.

@Deviaphan · 06.04.2012, 17:30

Сообщение от Nekto

Мой код прошел 50% тестов

Не заданные явно элементы инициализируются конструктором по умолчанию. Для чисел это 0. Если твой компилятор поступает иначе - удали его, отформатируй винт и сожги монитор. С мышью тоже что-нибудь можешь сделать, она тоже в этом замешана.

@Nekto · 06.04.2012, 17:32

Сообщение от Deviaphan

Не заданные явно элементы инициализируются конструктором по умолчанию. Для чисел это 0. Если твой компилятор поступает иначе - удали его, отформатируй винт и сожги монитор. С мышью тоже что-нибудь можешь сделать, она тоже в этом замешана.

да, с конструктором ты прав, исправил ту строчку, уже 85% тестов проходит

Не по теме:

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

Если писать арифметику через стринг, разве это будет быстрее 2 секунд для почти 2 миллионов умножений?

@Deviaphan · 06.04.2012, 17:56

Не по теме:

Сообщение от Nekto

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

Вот если бы я сказал, что по IP тебя вычислю и мышке провод перегрызу, то вот это была бы агрессия.)

Сообщение от Nekto

Если писать арифметику через стрин

Нет!
Сейчас ты считываешь ОДНО значение. А нужно считывать сразу всю строку в массив и потом уже из этого массива брать значения. Только считывать не в цикле, а при помощи read. 100000 значений это всего лишь 400 килобайт, так что в лимит памяти легко войдёт.

@SpecBM · 06.04.2012, 17:56 **[ТС]**

Сообщение от 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 · 06.04.2012, 17:57

Стоп! Файл же текстовый, а не бинарный... Read не поможет...

@SpecBM · 06.04.2012, 18:10 **[ТС]**

со скоростью уже все норм.
осталось решить как оперировать с большимы числами.

@Deviaphan · 06.04.2012, 18:12

Сообщение от SpecBM

как оперировать с большимы числами.

Умножать в double.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Nekto 347 / 292 / 37 Регистрация: 23.03.2012 Сообщений: 838
	06.04.2012, 14:31
	через файл надо? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	06.04.2012, 15:47
	попробуй замени умножение на сложение степеней двойки попробуй округлять вводимые числа, например d00125=b01111101~=10000000=1<<7 d00070=b01000110~=01000000=1<<6 их произведение равно 1<<13 в среднем это не изменит победителя. максимальное произведение получит погрешность, но останется максимальным правда тут про знаки надо помнить. знаки всё очень сильно портят. Ну как? Разве не финт ушами? 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	06.04.2012, 16:14
	Можно просто С-шное чтение использовать, потоки долговато работают. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	06.04.2012, 17:57
	Стоп! Файл же текстовый, а не бинарный... Read не поможет... 0

@SpecBM 20 / 20 / 12 Регистрация: 16.01.2010 Сообщений: 66
	06.04.2012, 18:10 [ТС]
	со скоростью уже все норм. осталось решить как оперировать с большимы числами. 0