Messages posted by: petarsor

VlatkoSh wrote:Probav dinamicko ama dobiva Runtime Error na povekje testovi (izgleda bara premnogu memorija?): https://pastebin.com/S4TG5782
Isto taka probav Meet In The Middle, sto e pobrzo ama dobiva Runtime Error na istite testovi: https://pastebin.com/34V0q9GH
Moze da mi pomogne nekoj?

Мислам дека си во право, дека со твојот код ќе имаш проблем со меморија.
Ова е лесно и да го провериш (пробав јас кај мене, стварно користи доста повеќе од 64 мегабајти на пример на 5-тиот пример). Само додади едно system("pause") на крајот и отвори Task Manager (претпоставувам користиш Windows), ќе видиш колку меморија се користи.

boolTrue wrote:Проблемот е што имам точен резултат но погрешен пат, бидејќи ги има повеќе патишта. Како да знам кој е оптималниот пат во задачата?

Тргни од крајот.

VlatkoSh wrote:Pretpostavuvam deka ne mora nesto kako BigInt da se koristi?

Во моето решение имам имплементирано (многу е едноставно, исто како што сме учеле на школо) собирање на големи броеви (ги чувам како string), и множење со едноцифрен број (во случајов, со 9).
Тоа е се што ми требаше за решението за задачава.

VlatkoSh wrote:Ne razbiram zosto pagja na vreme. Zarem ne e O(n*log2(sum a))? Toa e najvekje 200000*log2(200000*1000000) < 8000000 operacii.

Пишувам од телефон, така да неможам баш добро да го видам кодот или да тестирам на компјутер, али операции со реални броеви се некогаш поприлично бавни.
Друго, провери да не пристапуваш до некоја неиницијализирана променлива (место во некоја низа), или надвор од низата.

Сепак, прво нешто што јас би пробал е да го заменам ова

со нешто како

Може си видел дека може така со реални броеви, оти целта е да се намали грешката, па нема потреба да користиш EPS на тој начин таму. Со менување на вредноста (50) се движиш од помала прецизност (но побрзо решение) до поголема (но побавно решение).
Истестирај прво тоа да видиш дали е грешка со сложеноста, или имаш некој друг проблем.

VlatkoSh wrote:Go smeniv redot (k > 0 && k < K) i tocno e sega.

VlatkoSh wrote:Mislam deka odgovoruvas na gresniot covek

Да да. На BATIR му/и пишував.

Ако некој натпреварувач ќе прати 3 решенија, а сите други по 10, тој што ќе прати 3 прв ќе престане со праќање на решенија.
Можеш да користиш нешто како priority_queue за следење на тоа кој натпреварувачи први ќе "испаѓаат".

Не мораш еден по еден да одземаш од секој натпреварувач, што ако имаме некоја променлива "subtracted" која ќе води сметка за тоа колку имаме одземано од сите натпреварувачи?
Ако ова не е доволно, еве едно решение на задачава.

#include <vector>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {

int N, K;
    cin >> N >> K;

vector<int> R(N);
    priority_queue<pair<int, int> > pq;
    for (int i=0; i<N; i++) {
        cin >> R[i];
        pq.push(make_pair(-R[i], i));
    }

int left = N;
    int subtracted = 0;

while (K > 2*left && left > 0) {

pair<int, int> current = pq.top();
        pq.pop();

//odzemi 1 od site
        subtracted++;
        K -= left;

int value = -current.first;
        int index = current.second;

if (value - subtracted == 0) {
            //ovoj natprevaruvach e gotov so isprakjanje
            //pa ne go dodavame nazad vo priority_queue-to
            left--; //eden pomalku natprevaruvach

//ako ima i drugi natprevaruvachi koi imaat isto reshenija
            //izbrishi gi i niv
            while (!pq.empty() && (-pq.top().first - subtracted == 0)) {
                pq.pop();
                left--;
            }
        } else {

//dodadi go nazad vo priority_queue-to
            pq.push(make_pair(-R[index], index));
        }
    }

while (K > 0 && left > 0) {

for (int i=0; i<N && K > 0; i++) {

if (R[i] - subtracted > 0) {
                R[i]--;
                K--;

if (R[i] - subtracted == 0) {
                    left--;
                }
            }

}

cout << left << endl;
    return 0;
}

Всушност, најголема грешка ти е што не го прочита мојот одговор соодветно.

Дури имав напишано точно што треба

која треба да биде map<string,int> mapa; итн.

Исто и при крајот каде што имаш пак s1[i]... Не можеш s1[i] бидејќи s1 иницијално има 0 елементи. Може s1.push_back(...)

BATIR wrote:Brute force ne moze vo ovaa zadaca. Kako bi se resavala?

Не сакам многу да откривам, оти е сложена задача, ама генерално
1) имаш работа со големи броеви (собирање, множење), бидејќи не можеш во променлива од тип int (на пример) да чуваш број со 100 цифри итн.
2) користење на степените на бројот 9 (9, 81, ...) во пресметките.

BATIR wrote:Zdravo, zadacata od SPOJ - https://www.spoj.com/problems/SHPATH/ ja iskucav , ama kodot ne raboti. Kje moze celosna popravka okolu istiot

Ај вака, мислам дека е најдобро ако те насочам само во добра насока, бидејќи за време на натпревари/испити/итн ќе немаш помош некој друг да го гледа/поправа кодот.

1. Програмата што ја имаш прикачено не се ни компајлира. Имаш некои грешки како на пример во линијата mapa<string,int> mapa[ns+1]; која треба да биде map<string,int> mapa; итн.
Тоа треба прво да поправиш

2. Потоа, имаш и други грешки, некои во однос на извршување на програмата, а некои грешки и со алгоритамот.
На пример, имаш вектор "s", и потоа читаш во s[i].first и s[i].second, но тој вектор (кога се прави) има големина 0, па неможеш да читаш во s[0].first на пример (елемент s[0] не постои). Можеш да додаваш со push_back на пример, или уште на почеток да го направиш со соодветна големина.

Има и грешки со алгоритамот Dijkstra. На пример, не треба да имаш vis[sosed]=true; во for циклусот каде што ги поминуваш соседите, бидејќи можеби ќе се открие некој друг (пократок) пат од некое друго теме подоцна.

3. Има и некои делови кои што не треба да ги правиш како на пример mapa[s[i]].first]-- (ова не се ни компајлира, бидејќи има повеќе знаци ']' од '[', но тука не треба ни да има --, бидејќи индексите ти почнуваат од 0, итн.

okova wrote:Да се пресмета збирот на N цели броеви кои се внесуваат од тастатура (последователно, еден по друг).

Ова ми делува како некое домашно, ама нема врска (и така е задача од МЕНДО)
http://mendo.mk/Task.do?id=234

MODDI wrote:Кодов ми работи во 4 од 20-те дадени тест примери. Барам веќе 2 часа немозам да го најдам решението. Може малку помош??

Јас би поправил вака:

MODDI wrote:Кодов ми работи во 15 од 20те тест случаеви, може малку помош??

Ископирај ги линиите за сортирање (sort и reverse) и додади ги и на крајот од while циклусот. Тогаш ќе работи на сите тест случаи.
Размисли зошто, и пробај после да напишеш решение со подобра сложеност (иако не треба во оваа задача, оти се мали вредностите).

BATIR wrote:Hint okolku kodov, za test primerot na koj stranicata go testira pri prakjanje, ne mi dava da go vnesam pravilno inputot.

Имаш повеќе грешки за поправање. Не треба да печатиш празно место помеѓу цифрите, треба да ставиш знак за нов ред по печатењето во order(), не треба да имаш return 0 во if-овите по sort и reverse (бидејќи не треба да ти заврши програмата, туку да ги решава и другите случаи), итн

Ставам и код со неколку поправки, ако не успееш да ги најдеш сите.

#include <bits/stdc++.h>

using namespace std;

void order(vector<int> a, vector<int> b)
{
    int bs=a.size();
    int ss=b.size();
    int cnt=0;
    for(int i=0; i<bs; i++)
    {
        cout<<a[i]<<"";
        if(cnt<ss)
        {
            cout<<b[i]<<"";
            cnt++;
        }
        if(i+1 < bs && cnt==ss)
        {
            cout<<a[i+1];
            i=bs;
        }

}

cout << endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int niza[n];
        vector<int> even,odd;
        for(int i=0; i<n; i++)
        {
            cin>>niza[i];
            if(niza[i]%2==0)
            {
                even.push_back(niza[i]);
            }
            else if(niza[i]%2!=0)
            {
                odd.push_back(niza[i]);
            }
        }
        sort(even.begin(),even.end());
        sort(odd.begin(),odd.end());
        reverse(even.begin(),even.end());
        reverse(odd.begin(),odd.end());

if(even.size()==0&&odd.size() > 0)
        {
            cout<<odd[0]<<endl;
            //return 0;
        }
        else if(odd.size()==0&&even.size()> 0)
        {
            cout<<even[0]<<endl;
            //return 0;
        }
        else
        {
            if(even.size()>odd.size() && even[0] > 0)
            {
                order(even,odd);
            }
            else if(odd.size()>even.size() && odd[0] > 0)
            {
                order(odd,even);
            }
            else
            {
                if(odd[0]>even[0])
                   {
                     order(odd,even);
                   }
                else
                {
                     order(even,odd);
                }

}
        }

}
}

BATIR wrote:A kako bi bilo ako namesto priority_queue koristam obicen queue?

Што сакаш да постигнеш со тоа, за да може да ти одговориме? Не работи така алгоритамот Dijkstra, и (на тој начин) не можеш да ја постигнеш истата сложеност.