002 Jocul Flip

[•SebiSebi]

Din cate vad eu tu găsești linia și coloana cu suma minima și le înmulțești cu -1, ceea ce nu e corect. Poți schimba starea mai multor linii si a mai multor coloane. Ca sa rezolvi problema trebuie sa înveți backtracking.

[•IuliaCristianaM]

@Pirtoaca George Sebastian
Multumesc pentru raspuns.

[•ChrystianSandu]

Buna ziua,
Nu inteleg ce ar putea sa fie gresit...

[•ChrystianSandu]

Cod:

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("flip.in");
ofstream fout ("flip.out");

int n, m, i, j, a[20][20], s;
int main()
{
    fin >> n >> m;

    for (i=0; i<n; i++)
    {
        for (j=0; j<m; j++)
        {
            fin >> a[i][j];
        }
    }
    for (j=0; j<m; j++)
    {
        s = 0;
        for (i=0; i<n; i++)
        {
            s = s + a[i][j];
        }
        if (s<0)
        {
            for (i=0; i<n; i++)
            {
                a[i][j] = a[i][j] * (-1);
            }
        }
    }
    for (i=0; i<m; i++)
    {
        s = 0;
        for (j=0; j<n; j++)
        {
            s = s + a[i][j];
        }
        if (s<0)
        {
            for (j=0; j<m; j++)
            {
                a[i][j] = a[i][j]*(-1);
            }
        }
    }
    s = 0;
    for (i=0; i<n; i++)
    {
        for (j=0; j<m; j++)
        {
            s = s + a[i][j];
        }
    }
    fout << s;
    return 0;
}

Nu inteleg de ce primesc doar 20 de puncte, am incercat cu mai multe numere si imi iese chiar BINE pe PC, dar pe site...

[•PlayLikeNeverB4]

Nu am testat, dar probabil iti da gresit pe un test de genul asta.

2 2
-2 3
3 -2

Raspuns: 10

[•ChrystianSandu]

Gata, m-am prins cum trebuie facut.  Multumesc. 

[•geaninmihai]

@Sandu Cristian, ce ai modificat in codul tau? Primesc doar 10 puncte, desi in PC merg toate exemplele

[•robertforyou]

Am incercat sa fac ceva, dar mi se afiseaza 12, nu reusesc sa imi dau seama ce am gresit.

Cod:

#include <iostream>
#include <fstream>
using namespace std;


int main()
{
	int N, M, s1, s2;
	ifstream in;
	ofstream out;
	in.open("flip.in");
	in >> N >> M;
	in.close();
	int tabel[16][16];
	for (int i = 0; i < N; i++) //atribuie valorile
	{
		for (int j = 0; j < M; j++)
		{
			in >> tabel[i][j];
		}
	}
	for (int i = 0; i < N; i++)// verifica daca liniile sunt <0, iar daca da schimba semnul la fiecare numar de pe linie
	{
		s1 = 0;
		for (int j = 0; j < M; j++)
		{
			s1 = s1 + tabel[i][j]; // ia fiecare termen de pe coloanele din acea linie si fa suma termenilor
		}
		if (s1 < 0) // daca suma termenilior <0 atunci schimba semnul tuturor termenilor implicati
		{
			for (int j = 0; j < M; j++)
			{
				tabel[i][j] = 0 - tabel[i][j];
			}
		}
	}
	for (int j = 0; j < M; j++)// verifica daca coloanele sunt <0, iar daca da schimba semnul la fiecare numar de pe coloana
	{
		s2 = 0;
		for (int i = 0; i < N; i++)
		{
			s2 = s2 + tabel[i][j]; // ia fiecare termen de pe liniile din acea coloana si fa suma termenilor
		}
		if (s2 < 0) // daca suma termenilor <0 atunci schimba semnul tuturor termenilor implicati
		{
			for (int i = 0; i < N; i++)
			{
				tabel[i][j] = 0 - tabel[i][j];
			}
		}
	}
	int s3 = 0;
	for (int i = 0; i < N; i++) // calculare suma finala
	{
		for (int j = 0; j < M; j++)
		{
			s3 = s3 + tabel[i][j];
		}
	}
	out.open("flip.out");
	out << s3;
	out.close();
	return 0;
}

[•superstar1998]

Ok, am incercat o metoda liniara si am obtinut 28 pe testul dat, dar evaluatorul mi-a dat 30 puncte, restul testelor fiind gresite. Apoi am incercat o varianta cu backtracking, iar pe testul dat exemplu obtin suma maxima 29, inversand (de exemplu), linia 3 si coloana 2. Pe solutia asta am primit 40 puncte, iar pe celelalte cazuri depaseste timpul.

[•superstar1998]

Ok, obtineam 29 din cauza fisierului de intrare (schimbasem pe metoda liniara ca sa testez si alte cazuri, ups), insa as fi curios sa vad sursa originala.

[•Mr.Ionut]

Stie cineva daca pot vedea ce date de intrare introduce evaluatorul pentru fiecare test? Am gasit niste date de intrare in comentarii pentr ucare nu functioneaza codul meu (si multumesc pentru asta ) si as vrea sa vad si altele pe care nu ar merge codul meu. Mersi!

[•dinicaandrei]

Vre-un sfat pentru optimizare?

https://infoarena.ro/job_detail/2259180