Cod sursa(job #233264)

Utilizator ste_fanusGheorghe Stefan ste_fanus Data 17 decembrie 2008 11:57:22
Problema Tablete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
// Runda 1 - Tablete

#include <stdio.h>
#include <string.h>

#define FILE_INPUT	"tablete.in"
#define FILE_OUTPUT	"tablete.out"

int N, K;
char Flag[1000001];
long M[1024][1024];


void Validate()
{
	int i, j;

	memset(Flag, 0, sizeof(Flag));

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			Flag[M[i][j]] = 1;

	for (i = 1; i <= N * N; i++)
		if (!Flag[i])
		{
			printf("EROARE: numarul %d nu apare in matrice!\n", i);
		}

	for (i = 1; i <= N; i++)
		for (j = 2; j <= N; j++)
			if (M[i][j] < M[i][j - 1])
			{
				printf("EROARE: pe linia %d apar numere descrescatoare la indicele %d\n", i, j);
			};

	for (i = 1; i <= N; i++)
		if (M[i][K] & 1)
		{
			printf("EROARE: pe coloana K, la linia %d nu este element par!\n", i);
		}
}


int main()
{
	freopen(FILE_INPUT, "rt", stdin);
	scanf("%d %d", &N, &K);
	fclose(stdin);

	memset(M, 0, sizeof(M));
	memset(Flag, 0, sizeof(Flag));

	int i, j;
	// daca K e par, completam cu 1..N*N, secvential

	if (N % 2 == 0)
	{
		if (K % 2 == 0)
		{
			for (i = 1; i <= N; i++)
				for (j = 1; j <= N; j++)
					M[i][j] = (i - 1) * N + j;
		} else
		{
			// K impar, avem coloana cu cele pare: K + 1, 2K, 3K + 1, 4K... completam initial indicii pana la col K din toata partea stanga, apoi coloana K, apoi cu ce ramane completam restul matrice
			// la fiecare atribuire, bifez si in Flag numarul respectiv

			for (i = 1; i <= N; i++)		// linia
				for (j = 1; j <= K; j++)
				{
					int nr = -1;

					if (j == K)					// col K -> pun ce trebuie
						nr = (i & 1) ? (i * K + 1) : (i * K);
					else
					if (i & 1)						// i impar
					{
						nr = K * (i - 1) + j;
					} else						// i par
					{
						if (j == 1)
							nr = (i - 1) * K;
						else
							nr = (i - 1) * K + j;
					}

					if (nr != -1)
					{
						M[i][j] = nr;
						Flag[nr] = 1;
					}
				}

			// gata cu stanga, inclusiv coloana K

			int x = K * N + 1;
			for (i = 1; i <= N; i++)
				for (j = K + 1; j <= N; j++)
				{
					for (; x <= N * N; x++)
						if (Flag[x] == 0) break;

					M[i][j] = x;
					Flag[x] = 1;
				}
		}
	} else										// N impar
	{
		int nr, index;

		// compunem coloana K
		// idee noua, bazata pe faptul ca (i, K) trebuie sa fie cel putin cat cele (i - 1) * N + K - 1 elem din partea stanga si sus
		for (i = 1; i <= N; i++)
		{
			nr = (i - 1) * N + K - 1;
			index = nr + 1;

			if (index & 1)
				index++;

			if (i == N)
			{
				if (N * N - index < N - K)
					index -= 2;
			}

			M[i][K] = index;
			Flag[index] = 1;
		}


		// partea stanga, col 1..K - 1
		int x = 1;
		for (i = 1; i <= N; i++)
			for (j = 1; j < K; j++)
			{
				for (; x <= N * N; x++)
					if (Flag[x] == 0) break;
				M[i][j] = x;
				Flag[x] = 1;
			}

		// partea dreapta, col K + 1..N
		for (i = 1; i <= N; i++)
			for (j = K + 1; j <= N; j++)
			{
				for (; x <= N * N; x++)
					if (Flag[x] == 0) break;
				M[i][j] = x;
				Flag[x] = 1;
			}
	}

	

	// afisare
	freopen(FILE_OUTPUT, "wt", stdout);
	Validate();
	for (i = 1; i <= N; i++, printf("\n"))
		for (j = 1; j <= N; j++)
			printf("%ld ", M[i][j]);
	fclose(stdout);


	return 0;
}