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

Серьезная оптимизация - C++

Восстановить пароль Регистрация
 
rus_phantom
6 / 6 / 1
Регистрация: 31.03.2011
Сообщений: 69
16.11.2012, 22:58     Серьезная оптимизация #1
Участвую в олимпиаде, уже придумал алгоритм который обязан работать, но к сожалению вылетаю по тайм_лимит. Алгоритм линейный, я уже не знаю как программу оптимизировать. Вот код:

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
#include <vector>
#include <iostream>
//#include <cstdlib>
//#include <cstdio>
 
using namespace std;
 
typedef struct {
    int a,b;
}   mpair;
 
 
int main()
{
    //Читаем число
    int count;
    //scanf("%d",&count);   //C-style
    cin>>count;
 
    int max = (count+2)/3;
    //Отдельное условие на 1, если это не сделать то получу WA
    if (count==1) {
        cout<<0;
        //printf("0");      //C-Style
        return 0;
    }
 
    //mpair* res = (mpair*) malloc(20);//(sizeof(mpair)*max+19)/20);    //C-Style
    //size_t point=0;
    vector<mpair> v;
    for (int m=1;m<=max;m++){
        unsigned int to_del= 2*m-1;
        unsigned int a_a = count-m;
        unsigned int b_b = count+m-1;
        
        if (a_a%to_del==0) {
            mpair temp;
            temp.a=m; temp.b=a_a/to_del;
            if (temp.a>temp.b)
                //res[point++] = temp;                      //C_style
                v.push_back(temp);
        }
 
        to_del+=2;
        if (b_b%to_del==0) {
            mpair temp;
            temp.a=m; temp.b=b_b/to_del;
            if (temp.a<=temp.b)
                //res[point++] = temp;                      //C_style
                v.push_back(temp);
        }
    }
 
    size_t size = v.size();
    //cout<<point<<endl;                                //C-Style
    //printf("%d\n",size);
    //printf("%d\n",point);
    cout<<size<<endl;
 
    for (size_t i=0;i<size;i++) {
    //for (size_t i=0;i<point;i++) {
        //cout<<res[i].b<<" "<<res[i].a<<endl;
        //printf("%d %d\n",v[i].b,v[i].a);
        //printf("%d %d\n",res[i].b,res[i].a);
        cout<<v[i].b<<" "<<v[i].a<<endl;
    }
 
 
    return 0;
}
Можно ли это как нибудь оптимизировать?
Я уже и С ввод юзал и от векторов отказывался, не помогает, падает на числах больших
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2012, 22:58     Серьезная оптимизация
Посмотрите здесь:

Оптимизация C++
C++ Оптимизация вычислений
Оптимизация кода C++
C++ Оптимизация кода
C++ Оптимизация кода (C++)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
16.11.2012, 23:06     Серьезная оптимизация #2
телепаты в отпуске
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
16.11.2012, 23:07     Серьезная оптимизация #3
rus_phantom, было бы клево, если бы вы еще и задание написали
rus_phantom
6 / 6 / 1
Регистрация: 31.03.2011
Сообщений: 69
16.11.2012, 23:21  [ТС]     Серьезная оптимизация #4
Простите, вот условие (вторая задача):
https://dl.dropbox.com/u/32625075/pr...%20%281%29.pdf
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.11.2012, 23:28     Серьезная оптимизация #5
Цитата Сообщение от rus_phantom Посмотреть сообщение
Алгоритм линейный
Проблема именно в нем. Линия уместна на ограничениях примерно до 10^6.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.11.2012, 23:55     Серьезная оптимизация #6
Решение выкладывать не буду, просто опишу как решил эту задачу.
Делал также:
Цитата Сообщение от rus_phantom Посмотреть сообщение
C++
1
for (int m=1;m<=max;m++){
Но в самом цикле считал сначало что кол-во строк равно числу m, затем считал что кол-во столбцов m. Проверял с помощью выведенной формулы, может ли существовать ферма с кол-вом строк или столбцов равным m. Если да, то заносил данные в массив. Из цикла выходил когда невыполнялось условие m<=max или еще в двух случаях:
- если m кол-во строк фермы и кол-во столбцов становилось равным или больше m (причем вариант когда равны проверял на возможность существования)
- если m кол-во столбцов фермы и кол-во строк становилось равным или больше m
Yandex
Объявления
16.11.2012, 23:55     Серьезная оптимизация
Ответ Создать тему
Опции темы

Текущее время: 22:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru