VPF::Упрощение алгоритма - Форум программистов

sQu1rr

Дата 14.11.2009, 19:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Цитата(Dov @ 14.11.2009, 18:14

)

А так не пойдёт? Я особо не тестировал.

Очень даже подойдет, правда я немного переработал, взял общий смысл
Спасибо )
Мне бы решить 6ю задачу smile

Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 19:13

Любитель

Дата 15.11.2009, 00:17 (ссылка)

(нет голосов)

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

Репутация: 24
Всего: 92

Пропустил одну очень важную вещь - двойные вычисления.

Добавь у комнаты поле, означающее количество путей из этой комнаты, в начале поставь, скажем -1. И напиши как-то так:

Код


    if( pRoom->isLast )
        return 1;

    if (pRoom->waysCount != -1)
        return pRoom->waysCount;

    pRoom->isPassed = true;
    // ...

    pRoom->waysCount = iResult;
    pRoom->isPassed = false;
    return iResult;

С генератором данных я не заморачивался - в качестве следующих допустимых комнат всегда ставил все smile

В качестве передела ходов - n*(n-1)/2 (максимальное число по условию). И, даже с учётом того, что реализация на js (ща дома у родителей - ставить и качать что-то особое не хотелось) работает всё достаточно шустро (даже для тысячи элементов, на 10 тысячах виснет, правда).

--------------------

http://oryolalex.mybrute.com

sQu1rr

Дата 15.11.2009, 01:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Не получится, ведь это просто запоминания всех возможных путей из комнаты. Ав разных ситациях пути разные и запомненный вариант выдает неправельный результат. У меня к примеру ошибка была аж на 9 000 000 ))) так что я подумаю над другим алгоритмом

Если вам стало интересно - файл для проверки
http://pastebin.com/m36dd4257
Правильный ответ: 9864101
http://pastebin.com/m2e4d7338
Правильный ответ: 18
Код моей программы:
http://pastebin.com/m3d786e7d

Это сообщение отредактировал(а) sQu1rr - 15.11.2009, 01:30

Любитель

Дата 16.11.2009, 01:19 (ссылка)

(нет голосов)

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

Репутация: 24
Всего: 92

Да, был не прав. Надо думать... smile

Добавлено через 7 минут и 22 секунды
Ээ.. Если во втором случае 18, то вы считаете что путь из A в B автоматически означает наличия пути из B в A. Вроде по условию это не так. Это не влияет на задачу, но влияет на парсинг входных данных.

--------------------

http://oryolalex.mybrute.com

sQu1rr

Дата 16.11.2009, 02:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Цитата(Любитель @ 16.11.2009, 01:19

)

Ээ.. Если во втором случае 18, то вы считаете что путь из A в B автоматически означает наличия пути из B в A. Вроде по условию это не так. Это не влияет на задачу, но влияет на парсинг входных данных.

Вы правы сейчас изменб алгоритм и посмотрю что получится. Какой я невнимательный. Спасибо зааранее!
Кстати говоря, запоминание ходов сюда какраз походит ( то что вы написали что неправы ), так как здесь есть только ход вперед, не назад!

Это сообщение отредактировал(а) sQu1rr - 16.11.2009, 02:14

sQu1rr

Дата 16.11.2009, 02:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Спасибо за помощь - алгоритм правелен. Теперь на сервере, куда выкладываю задания появилось ( парвильный ответ - неправильный ответ ). Так что спасибо еще раз. Я скоро выложу еще некоторые проблемные места некоторых программ из этой же серии. У меня какаято ошибка в 3 задании ( решает один неправильно, один не укладывается в ограничение временное ), тоже саме в 4 задании. 5 я сделал полностью неправильно smile

. в послднем принял ответы от 1 до 6. 7 8 9 10 не могу решить, так как не вмещается в __int64. Обидно, придется писать цифровой класс (( Есть другой метод? ( Предпологаю что можно в нужный момент сохранять в массив переменных и начинать новую с нуля, а в конце все прибать, но чтобы их прибавить опять нужно писать свой класс, как минимум набор фнкций перевода в char и сложения буквенных выражений ((((

Любитель

Дата 16.11.2009, 13:48 (ссылка)

(нет голосов)

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

Репутация: 24
Всего: 92

Цитата(sQu1rr @ 16.11.2009, 02:25

)

Есть другой метод? (

Это самый быстрый, я думаю.

Цитата(sQu1rr @ 16.11.2009, 02:03

)

запоминание ходов сюда какраз походит ( то что вы написали что неправы ), так как здесь есть только ход вперед, не назад!

Всмысле? Мы перешли из 1 в 2, затем в 3 и посчитали, что из 3 будет 5 вариантов путей до конца. Допустим, что есть путь и из 2 в 3, и из 3 в 2 (это по условию возможно ведь?), тогда, если мы пойдём сразу из 1 в 3 можем получить другой ответ (для количества путей из 3).

Добавлено через 2 минуты и 52 секунды
Вообще условие мутное и не совсем согласуется с описанием входного формата. С двунаправленностью переходов тоже непонятно. Но, если ответы получаются правильные - значит видать решение правильное, но условие всё-таки сформулировано нечётко.

--------------------

http://oryolalex.mybrute.com

sQu1rr

Дата 16.11.2009, 16:45 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Цитата(Любитель @ 16.11.2009, 13:48

)

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

Ненавижу эстонию эстонцев и все что с ними связано. Моя мечта смыца отсюда smile

У них всегда так

Это сообщение отредактировал(а) sQu1rr - 16.11.2009, 16:50

sQu1rr

Дата 21.11.2009, 14:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Слава богу, я почти со всем справился. Остался один алгоритм, который нужно упростить.
Текст задания 4 на первой странице. Мой код

Код


#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <math.h>
#include <algorithm>
#include "cSpeedCounter.h"
using namespace std;

struct sPlace {
    size_t iMNum;
    size_t iMPos;
    size_t iPlace;
    size_t iPos;
};

class cNodeList {
    class cNode;
public:
    cNodeList();
    ~cNodeList();
    void AddNode( const sPlace & sStruct );
    void CalculatePlaces();
    size_t GetPlace( const size_t iPos );
private:
    cNode * m_pHead;
};

class cNodeList::cNode {
public:
    cNode() : m_pNext(NULL) { }
    ~cNode() { }
    void SetStruct( const sPlace & sStruct ) { m_struct = sStruct; }
    sPlace & GetStruct() { return m_struct; }
    void SetNext( cNode * pNext ) { m_pNext = pNext; }
    cNode * GetNext() const { return m_pNext; }
private:
    sPlace m_struct;
    cNode * m_pNext;
};

cNodeList::cNodeList() : m_pHead(NULL) {

}
cNodeList::~cNodeList() {
    cNode * tmpNode = NULL;
    while( m_pHead != NULL ) {
        tmpNode = m_pHead;
        m_pHead = m_pHead->GetNext();
        delete tmpNode;
    }
}
void cNodeList::AddNode( const sPlace & sStruct ) {
    bool bPrev = false;
    cNode * tmpNode = m_pHead;
    cNode * prevNode = NULL;
    cNode * newNode = new cNode;
    for( size_t iI = 1; iI < sStruct.iMNum; ++iI ) {
        if( iI == sStruct.iMNum - 1 ) {
            prevNode = tmpNode;
            bPrev = true;
        }
        tmpNode = tmpNode->GetNext();
    }
    newNode->SetStruct( sStruct );
    if( bPrev )
        prevNode->SetNext( newNode );
    newNode->SetNext( tmpNode );
    if( ( newNode->GetNext() == m_pHead ) || ( m_pHead == NULL ) )
        m_pHead = newNode;
}
size_t cNodeList::GetPlace( const size_t iPos ) {
    cNode * tmpNode = m_pHead;
    while( tmpNode->GetStruct().iPos != iPos )
        tmpNode = tmpNode->GetNext();
    return tmpNode->GetStruct().iPlace;
}

void cNodeList::CalculatePlaces() {
    cNode * tmpNode = m_pHead;
    int iI = 0;
    while( tmpNode != NULL ) {
        tmpNode->GetStruct().iPlace = ++iI;
        tmpNode = tmpNode->GetNext();
    }
}

bool mySort( const sPlace & lhs, const sPlace & rhs ) {
    return lhs.iMPos < rhs.iMPos;
}

void CalculatePlaces( sPlace * arrPlace, const int & iArrSize, cNodeList & nl );

int main() {
    // Variables
    int iArrSize;
    string strTemp;
    sPlace * arrPlace;

    // Input
    ifstream ifile("prot.sis");
    ifile >> iArrSize;
    arrPlace = new sPlace[iArrSize];
    int iI = 0;
    while( iI < iArrSize ) {
        ifile >> strTemp;
        arrPlace[iI].iPos = iI;
        arrPlace[iI].iPlace = arrPlace[iI].iMNum = arrPlace[iI].iMPos = 0;
        size_t iNPos = strTemp.find( '/' );
        for( size_t iS = 0; iS < iNPos; ++iS ) {
            size_t pw = 1, iPW = 0, tst = iNPos - iS - 1;
            while( iPW++ < tst )
                pw *= 10;
            arrPlace[iI].iMNum += ( strTemp[iS] - 48 ) * pw;
        }
        for( size_t iS = iNPos + 1; iS < strTemp.size(); ++iS ) {
            size_t pw = 1, iPW = 0, tst = strTemp.size() - iS - 1;
            while( iPW++ < tst )
                pw *= 10;
            arrPlace[iI].iMPos += ( strTemp[iS] - 48 ) * pw;
        }
        ++iI;
    }
    ifile.close();
    // Functions
    cNodeList nl;
    CalculatePlaces( arrPlace, iArrSize, nl );

    // Output
    ofstream ofile("prot.val");
    for( int iI = 0; iI < iArrSize; ++iI )
        ofile << nl.GetPlace( iI ) << endl;
    ofile.close();

    // End of code
    delete [] arrPlace;
    return 0;
}

void CalculatePlaces( sPlace * arrPlace, const int & iArrSize, cNodeList & nl ) {
    cSpeedCounter sp;
    sort( arrPlace, arrPlace + iArrSize, mySort );
    for( size_t iI = 0; iI < iArrSize; ++iI )
        nl.AddNode( arrPlace[iI] );
    nl.CalculatePlaces();
}

Ну не получается у меня решить задание за секунду... Не знаю как упростить, Сам алгоритм занимает 1/5 времени, а вод вывод почти 4/5. Прилагаю файл, который нужно посчитать за секунду. У меня тока за 1.7 выходит. А будут файлы побольше. Желательно сократить время до 0.5. Пологаю нужно както упростить функцию вывода cNodeList::GetPlace(); но алгоритм при 50000 строк вхдного файла всеравно почти 4 секунды считает
Файл:
http://pastebin.com/m5d524a54

MTWizard

Дата 22.11.2009, 14:32 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 51
Регистрация: 8.10.2007
Где: Київ

Репутация: 3
Всего: 4

Навеное таки 5-е задание, так?

Вот решение, которое отрабатывает за 0,2 секунды: Тыц

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »