Софтуерно Инженерство
Loading...
+ Нов въпрос
milenmilen avatar milenmilen 0 Точки

JA1-Task-4-Roxettes

Не знам дали е прието да си поставяме кода тук, ако не е прието обещавам да не правя повече така. Та идеята ми е къде може да се оптимизира кода по-долу защото judge гърми та трещи от 6-ти тест нататък за време и на последния за памет.

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

int main() {
    string dnaSequence {};
    vector<short int> dnas;
    unsigned short int pos;
    cin >> dnaSequence;
    unsigned int length = dnaSequence.length();
    if (length > 15) {
        string currDna{};
        for (int i = 0; i <= length; i++) {
            if (i % 5 == 0 && i > 0) {
                short int x = stoul(currDna, nullptr, 16);
                dnas.push_back(x);
                currDna = {};
            }
            currDna = currDna + dnaSequence[i];
        }
        unsigned int numDna = (length - 1)/5;
        for (int i = 0; i < numDna; i++) {
            bool isUnique{true};
            for (int j = 0; j < numDna; j++) {
                if (i != j && dnas[i] == dnas[j]) {
                    isUnique = false;
                    break;
                }
            }
            if (isUnique == true) {
                pos = i;
                break;
            }
        }
        for (int i = pos * 5; i <= pos * 5 + 4; i++) {
            cout << dnaSequence[i];
        }
    }
    else if (dnaSequence.length() == 6){
        cout << dnaSequence << endl;
    }
    return 0;
}

Тагове:
0
C++ Fundamentals
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Здравей,

Принципно не е прието (няколко други колеги също го направиха, днес ще предупредя изрично на лекцията), защото другите могат да го копират - не е болка за умиране, но предпочитам да не го правите. По-добра идея е да опишеш горе-долу какво правиш или да дадеш част от код, който те съмнява (в твоя случай няма как, защото мислиш за цялата програма).

Проверката за това дали нещо е уникално е твърде бавна (ще направиш общо N * N проверки - за всеки елемент ще провериш всички останали). Тоест като цяло подходът ти към решението не е правилен, колкото и да оптимизираш части от него, трудно ще стигнеш до пълни точки по този начин (един колега го е постигнал, защото съм забравил да сложа ограничението за памет, но тъй като вече е изкарал точки ще оставя ограничението така - неговото решение е силно оптимизирано и ползва неща от по-нататък в курса, но пак не е най-бързия вариант).

Днес в началото на лекцията ще дам подсказка за тази задача, както бях обещал миналия път да направя ако видя, че никой не е хванал правилния път за решение (защото може да се каже, че се ползва нещо, което не сме учили, или поне не сме му обръщали внимание на свойствата).

Поздрави,

Жоро

0
fantom4e avatar fantom4e 24 Точки

Здравей Георги.
В предишния курс задачата ме изяде, тогава не успях да взема 100те точки точно поради 2та мегабайта ограничение.В момента си мисля, ако използвам двумерен масив от чарове в които една Роксет ДНК ще бъде 5бита, ще ми позволи ли да се вмъкна  във времето и 2MB памет?

0
28/11/2017 23:39:28
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Здравей,

В паметта може и да се вмъкнеш (както е настроена сега за 16 МБ, вместо 2-та които пише в условието), но във времето почти със сигурност няма да се вмъкнеш само с масив - търсенето ще ти отнема твърде много време. set би бил по-добър вариант (търсенето е много по-бързо).

При всички положения това, което обясних на лекцията, е доста по-бързо и ефикасно от всички други подходи, които се мъчат да пазят самите елементи.

Поздрави,

Жоро

0
MartinBG avatar MartinBG 1154 Точки

Задачата наистина е много добра! :)

 

В предишното издание на курса успях да се вмъкна в изискването за памет като ползвах bitset (това решение може да се приложи за произволен брой уникални ентрита), но правилното решение е друго (hint - побитови операции).

0
Jovanna avatar Jovanna 184 Точки

Най-хитрото решение е да се избегнат всички//почти вс. , койнейнери за решеавне на задачата, за да няма препълване.

Дори входа може да се чете с while(true) и if (character == '.') { break; }  Това става само тук, защото са дефинирани кратни на 5

2/ четеш по 5 символа всеки път в , приметно char arr[5]

3/ пишеш си функция -converter Hexdecimal to Binary

4/ правиш си една променлива (вектор примерно с единици и нули ще е), който да ти съдържа текущия  XOR //EcsclusiveOr резултата; Той ще се променя всеки път като му подадеш новото двоично число 

5/ резултатът ти се съдърща в променливата с XOR-овете ; обратно с Converter но от binary към hexadecimal

6/ принтиш hexadecimal

Надявам се да помогне. Въпреки че и на мен ми гърмят при тая реализация 2 теста, Жоро, защо? 

0
milenmilen avatar milenmilen 0 Точки

Мисля че като е минал срока за J.A. няма проблем да си пускаме кодовете вече.

Ето ти работещ код и си намери разликите с твоя, не ти трябват конвертори.

0
05/12/2017 22:34:28