[c++]pomoc w uproszczeniu programu

[errorplus 22]

Witam mam pewien problem, napisałem program do tego zadania: http://main.edu.pl/pl/user.phtml?op=showtask&task=koz&con=PAS

Tylko jest jeden problem. Program oczywiście działa poprawnie i wszystko liczy dobrze. Tylko, że program ma zajmować max 64MB pamięci a mi przy ostatnim teście podaje problem, iż program jest wywłaszczony, gdyż wykonuje zbyt dużo przebiegów pętli. ( w tym linku http://main.edu.pl/pl/user.phtml?op=zasoby jest zasób tego programu (co na wejściu i na wyjściu przy testach na stronie jest wykorzystywane) ) tak jak powiedziałem w trzecim teście program jest wywłaszczony i nie wiem jak temu zapobiec. Jeżeli ktoś z forumowiczów byłby w stanie mi pomóć byłbym bardzo wdzięczny

 

I od razu mówię, że nie jestem jakiś programistą czy coś jestem na etapie nauki dlatego nie dam sobie sam z tym rady.

 

Oto mój kod:

#include <iostream>
#include <cstdlib>
#include <utility>
#include <algorithm>

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {

int n, w;
cin>>n>>w;
pair <int,string> para[w];
int tab2[w];


for(int i=0;i<w;i++)
{
tab2[i]=1;
cin>>para[i].first;
cin>>para[i].second;
}


for(int i=0;i<w;i++)
{
for(int j=0;j<w;j++)
{
if(i!=j)if(para[i].first==para[j].first && para[i].second==para[j].second) 
{
tab2[i]++;
tab2[j]--;
para[j].first=0;
para[j].second="b";
}
}
}


int suma=0;
for(int i=0;i<w;i++)
{
if(tab2[i]%2!=0)suma++;
}
cout<<suma;

return 0;
}

Edytowane 31 Marca 2013 przez errorplus

[szatkus 282]

Po pierwsze primo, rób chociaż wcięcia, bo się tego czytać nie da

 

Po drugie primo, do głowy by mi nie przyszło, że można to zadanie zrobić tak niewydajnie

Dwie pętle, każda obiega w razy, gdzie w może wynosić 100 000, daje w najgorszym wypadku 10 000 000 000 iteracji. Lampka ostrzegawcza w głowie powinna się zapalać, gdy rozwiązanie może przekroczyć 10 000 000 iteracji

 

Ok, to zeby nie psuć zabawy parę podpowiedzi:

- Poczytaj o "Programowaniu Dynamicznym"

- Do rozwiązania tego problemu wystarczy spokojnie jedna tablica długości n.

- Jeśli chodzi o złożoność czasową to bez problemu da się to zrobić w O(w + n).

- Na oko powinny wystarczy dwie pętle (nie zagnieżdżone w sobie, tylko obok siebie).

[errorplus 22]

Mówiłem, że w programowaniu jestem na etapie nauki, a tak wyszło, że muszę wykonać to zadanie. Starałem się zrobić to już drugi dzień, aż w końcu wyszło Ale ok posiedzę jeszcze trochę, zastosuję się do wskazówek i może wyjdzie.

 

A co do wcięć to robię zawsze, tylko coś przy kopiowaniu sie rozjechało

Jednak nie mam na to pomysłu za duży laik ze mnie.

Ale dzięki bardzo za próbę pomocy.

Edytowane 31 Marca 2013 przez errorplus

[waszak 4]

int n, w;
cin>>n>>w;
pair <int,string> para[w];
int tab2[w];

 

Z takim deklarowaniem tablic daleko nie zajdziesz xD.

Zadanie jest proste napisałem program, który ma kilka linii.(100 pktów dostałem pisząc kod bez kompilacji xD)  Nie potrzebujesz dynamika. Pomyśl o pstryczkach, bo algorym moim zdaniem masz zbyt udziwniony. Rozwiązanie wynika z treści i danych.

Edytowane 31 Marca 2013 przez waszak

[errorplus 22]

a mógłbyś podać kod którym mógłbym przyjąć w tym zadaniu dane od użytkownika?

zrobiłem już 28 zadań z 32, a muszę mieć 30 i kurcze już nic nie mogę wymyśleć

Edytowane 31 Marca 2013 przez errorplus

[waszak 4]

Polecam używanie scanf-ów albo wyłączonej synchronizacji w zadaniach algorytmicznych mi się nie chciało tego dodawać.

 

#include<iostream>
using namespace std;
 
int wyn[1005];
 
int main(){
    int n, m, p, wynik = 0; char z;
    cin>>n>>m;
    for(int i=0; i < m; i++){
        cin>>p>>z;
        wyn[p] ^= ((z =='c')?(1<<1)(z =='z')?(1<<2):(1<<3)));
    }
    for( int i=1; i<=n; i++){
        wynik += (!!(wyn[i]&(1<<1)))+(!!(wyn[i]&(1<<2)))+(!!(wyn[i]&(1<<3)));
    }
    cout<<wynik<<endl;
}

Edytowane 31 Marca 2013 przez waszak

[errorplus 22]

Jeju jesteś wielki. Bardzo Ci dziękuję. Twoje rozwiązanie nie tylko roziąwuje mi to konkretne zadanie, ale także ułatwi mi pisanie kolejnych programów, gdyż wzorowanie się na dobrze napisanych przykładach strasznie ułatwia mi naukę programowania.

 

I z każdym dniem c++ mnie zaskakuje

[waszak 4]

trochę leniwy byłem, bo chciałem szybko napisać.  W produkcyjnym kodzie bym tego nie napisał tak tylko dłużej, bo kod jest mniej czytelny, ale na konkursy algorytmiczne jest w sam raz.

[errorplus 22]

Potrzebuję to do szkoły, dużą część udało mi się napisać samemu, a to co napisałeś jest w sam raz Chodzi o to aby program został spunktowany na 100% i abym rozumiał kolejne kroki w nim wykonywane. I dzięki Twojemu kodowi znów się czegoś nauczyłem, chociażby szerzej o operacjach bitowych. Dziękuję Ci jeszcze raz