002 Jocul Flip

[•Agent_Smith]

si eu am probleme la "Jocul" asta. nushtiu cum sta treaba la voi da eu oricum as incerca nu imi iese.Eu adun elementele negative si apoi elementele pozitive de pe fiecare linie si daca |elemente negative |> elemente pozitive
comut coloana. Acelas lucru si pentru coloane. si primesc 10 p din mila  si la restu imi zice k raspuns gresit.
Va rog ajutati-ma 

[•pauldb]

Ce faci tu acolo e greedy, nu backtracking. Citeste topicul! Gasesti suficiente indicatii.

[•Agent_Smith]

pot sa il citesc k au mai multi ideea aceasta si mie mi se pare buna. Iar eu nu fac Backtrking la probleme din astea nici daca .....

[•DITzoneC]

Pai chiar nu este buna ideea ... Nu da raspuns bun pentru un caz extrem de simplu

Cod:

2 3
-4 -2

Tu te uiti la prima linie si alegi sa o intorci. Obtii

Cod:

-2 3
4 -2

A doua linie o lasi asa cum este si cand verifici pe coloane din nou nu vei face nici o modificare.
Suma in cazul tau va fi 3.
Daca pe cazul initial am fi intors doar ultima coloana obtineam

Cod:

2 3
4 2

suma 11

In cazul in care faci intai verificarea pe coloane si apoi pe linii se poate construi un exemplu asemanator.

[•Agent_Smith]

Hmmmm.... la asta nu ma-m gandit....   si atunci cum ar trebui sa procedez???
tu de exemplu cum teai gandit??

[•DITzoneC]

Daca citeai atent posturile anterioare ai fi vazut ca s-a mai discutat asta...
Solutia este backtracking...

[•radami]

Am citit tot threadul de vreo 3 ori ca sa nu-mi scape nimic. Am mers pe varianta mea initiala, prin care verific toate posibilitatile: Intorc fiecare coloana, si pe urma parcurg fiecare linie. Unde Suma_linie < 0 intorc linia. La sfarsit calculez suma intregii matrici si o compar cu suma dinainte de "flipuri". Dupa ce termin coloanele aplic acelasi algoritm pentru linii. In teorie problema este buna, si in toate exemplele din acest thread mi-a mers. Dar la evaluare iau doar 10 puncte

[•Darth_Niculus]

 Ideea e buna... ai gresit ceva la implementare. Pan' nu-ti vad sursa nush ce sa zic...... incearca sa o implementezi din nou de la zero.

[•radami]

ok.multumesc mult..asta voiam sa stiu. daca am gresit ceva in gandirea sau daca trebuie sa ma uit pe implementare:)

[•Darth_Niculus]

Intorc fiecare coloana, si pe urma parcurg fiecare linie. Unde Suma_linie < 0 intorc linia.

Sper ca aici ai vrut sa zici ca incerci toate posibiliatile de a intoarce coloane....

[•zack]

vreau sa vad o sursa , cum spuneam si in alt topic incerc sa fac trecerea de la pascal la c++ si nu stiu cum sa fac  "ceva"

[•fireatmyself]

pai posteaza aici acel "ceva" si poate reusim sa te lamurim

[•DITzoneC]

Poti sa intrebi cum se face acel "ceva". O sursa asa direct nu cred ca iti va da nimeni mai ales la modul imperativ sub care ai cerut-o. Oricum iti va fi mult mai de ajutor sa intelegi acel "ceva" si apoi sa il implementezi de unul singur.

[•wefgef]

vreau sa vad o sursa , cum spuneam si in alt topic incerc sa fac trecerea de la pascal la c++ si nu stiu cum sa fac  "ceva"

Ar fi bine ca inainte sa faci probleme pe infoArena in C++ sa iti iei o carte sau o documentatie de pe net si sa inveti bine limbajul. Implementarea acestei probleme nu este deloc greu de "tradus" din pascal in C++, asa ca nu ar trebui sa iti ia mai mult de cateva ore sa reusesti sa iei 100 de pct.

Bafta 

[•Adix]

Am facut un btrack de m(nr de coloane) si fac flip la linie daca suma e <0 :

Compilare:

Test   Timp executie   Memorie folosita   Mesaj   Punctaj
1   4ms   12kb   Ok!   10
2   0ms   8kb   Ok!   10
3   40ms   176kb   Raspuns gresit   0
4   0ms   12kb   Ok!   10
5   20ms   176kb   Ok!   10
6   24ms   176kb   Ok!   10
7   208ms   180kb   Ok!   10
8   236ms   176kb   Ok!   10
9   236ms   176kb   Ok!   10
10   252ms   172kb   Ok!   10
Punctaj total:   90

 

De ce nu merge pt testu 3 ? (

Later edit :

Nvm.. am rezolvat problema  .. nu mergea daca aveam mai multe coloane decat linii 

[•Darth_Niculus]

Am facut un btrack de m(nr de coloane) si fac flip la linie daca suma e <0 :

..................................

De ce nu merge pt testu 3 ? (

  Asta cred ca numai tu poti sa afli....    vezi si tu prin codul daca ai..... greseli

[•alexandru_busu]

prieteni am inceput si eu sa invatz de unul singur c++ si sunt la inceput pana acum n`am mai folosit martirci iar in cartile mele din care invatz nu am exemple concrete asa ca va rog mult sa imi dati si mie o solutie la aceasta problema daca nu se poate aici pe forum la email: [email protected]
va multumesc !

[•cos_min]

Nu cred ca vei primi ceva sursa la problema asta...

Legat de matrici :

int a[101][101]; // declararea unei matrici

// Sper ex ai aici afisarea unei matrici cu n linii si m coloane.
for(int i = 1; i <= n; i++ )
{
   for (int j = 1; j <= m; j++ )
   {
        fout << a[i,j] << " ";
   }
   fout << "\n";
}

[•Darth_Niculus]

 Sursa corecta sigur nu primesti.... dar daca citesti mai sus pe forum gasesti destule idei.... 
 Daca vrei surse cu matrici.... asta se rezolva      desi ce a scris cosmin mai sus pare a fi arhisuficient pentru a intelege..... 

[•Tabara]

prieteni am inceput si eu sa invatz de unul singur c++ si sunt la inceput pana acum n`am mai folosit martirci iar in cartile mele din care invatz nu am exemple concrete asa ca va rog mult sa imi dati si mie o solutie la aceasta problema daca nu se poate aici pe forum la email: [email protected]
va multumesc !

Depinde din ce manuale inveti.Eu te-as sfatui sa iti faci rost de niste carti care te pun pe picioare cu baza din C++. Aici as recomanda Tudor Sorin de a IX-a.

( sunt si exemple cu siruri, matrici, algoritmi mai mici etc ) 

 

[•smith_s9]

Pai... am incercat si eu sa rezolv problema asta (mi-a aratat-o unul de a X-a). Nu am facut inca backtracking (sunt a IX-a) fiindca nu prea m-a atras, afland defectele metodei. Eu am mers pe idea (postata anterior) ca verific, pe fiecare coloana, daca suma numerelor negative (transformate in numere pozitive cand le adaug) este mai mare decat cele pozitive. Daca da, pastrez coloana. Apoi din toate coloanele o aleg pe cea la care diferenta e cea mai mare. La fel pentru linii. Apoi fac flip la cea care are diferenta mai mare, coloana sau linia. Si repet procesul. Am facut programul (in Pascal) si merge perfect cu toate datele de intrare pe care le incerc. Totusi, evaluatorul mi-a dat 0 puncte pentru fiecare test, pentru raspuns gresit. Ma poate lamuri careva care ar fi problema? Ms mult.

Folosesc Borland Pascal, apropo, ar putea asta reprezenta vreo problema?

[•Adix]

Folosesc Borland Pascal, apropo, ar putea asta reprezenta vreo problema?

Nu cred ca asta ar putea reprezenta o problema .. s-au mai discutat ideile tale pe threadul asta ... ideea e pe scurt ca daca se foloseste metoda ta, nu vei gasi suma optima doar pentru unele cazuri .. de ce ? citeste mai sus ca este explicat mai bine decat pot eu ... solutia este sa faci un btracking pe coloane/linii si apoi sa faci flipurile necesare pe linii/coloane

[•smith_s9]

Meh... atunci ma bag sa invat si metoda asta . Oricum, solutia mea mi se pare foarte logica (lol) si nu pricep de ce nu merge deoarece am obtinut rezultate bune la testele mele. Ms de ajutor!

EDIT: Daca te refereai la explicatia asta, atunci sa stii ca este o diferenta intre solutia la care se adresa explicatia aia si solutia mea. A mea ar solutiona cu succes datele alea de intrare .

[•alexandru_busu]

Cod:

Restrictii si precizari

    * 1 ≤ N, M ≤ 16
    * Tabla de joc contine numere intregi din intervalul [-1.000.000,1.000.000]

deci zice ca n e minim 1 iar m e maxim 16 deci la matrice la m voi pune 16 si la n?
adik matrice [ x ][16] //fara spatii

x=?

[•smith_s9]

* 1 ≤ N, M ≤ 16

=

1≤N≤16, 1≤M≤16