Desafios de Programação no Verão de 2011 - Prova 09 - Equipe

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Relações de Equivalência (por AUHAUAH Balões Mano)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAXN 90

int n;
int b[MAXN];

int prim[2] = {13, 89};
map<int,int> memo[2];

int tcr[16][90];

int pot (int x, int y)
{
	if (!y) return 1;
	
	int a = pot(x, y/2);
	a *= a;
	
	if (y%2)
		a *= x;
	
	return a;
}

int bell (int n, int p)
{
	if (n  < 89)
		return b[n] % prim[p];
	
	if (memo[p].find(n) != memo[p].end())
		return memo[p][n];
	
	int exp = (int) (log(n)/log(prim[p]) + (1e-8));
	int dif = n - pot(prim[p], exp);
	
	return (memo[p][n] = ((exp*bell(dif, p))%prim[p] + bell(dif+1, p))%prim[p]);
}

int main (void)
{
	for (int i = 0; i < 1157; i++)
	{
		tcr[i%13][i%89] = i;
	}

	int st[90][90];
	for (int i = 0; i < 90; i++)
	{
		st[i][0] = 0;
		st[i][i] = 1;
		for (int j = 1; j < i; j++)
			st[i][j] = (st[i-1][j-1] + j*st[i-1][j]) % 1157;
	}
	
	for (int i = 0; i < 89; i++)
	{
		b[i] = 0;
		for (int j = 0; j <= i; j++)
		{
			b[i] = (b[i] + st[i][j]) % 1157;
		}
	}
	
	while (scanf ("%d", &n) == 1)
	{
		printf ("%d\n", tcr[bell(n,0)][bell(n,1)]);
	}
	
	return 0;
}

Coloring Rectangles (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<set>
#include<map>
#include<cstring>
#include<vector>
using namespace std;
#define MAX 64
struct tri{
	int a,b,c,d;
} V[MAX];
int grid[128][128],N,M;
int value[64];
int pd[64][64];

int f(int at,int k) {
	if(k == 0) return pd[at][k] = 0;
	if(at >= N) return pd[at][k] = 0;

	if(pd[at][k] != -1) return pd[at][k];

	return pd[at][k] = max(f(at+1, k), f(at+1, k-1) + value[at]);
}

int main() {
	while(scanf("%d %d", &N, &M) == 2) {
		set<int> X;
		set<int> Y;
		map<int,int> mapaX;
		map<int,int> mapaY;
		map<int,int> mapaXX;
		map<int,int> mapaYY;
		for(int i = 0;i < N; i++) {
			int a,b,c,d;
			scanf("%d %d %d %d", &a, &b, &c, &d);
			V[i] = (tri) {a,b,c,d};
			X.insert(a);
			X.insert(c);
			Y.insert(b);
			Y.insert(d);
		}
		int maxx,maxy;
		int at = 0;
		for(set<int>::iterator i = X.begin(); i != X.end(); ++i) {
			mapaXX[at] = *i;
			mapaX[*i] = at++;
			maxx = at;
		}
		at = 0;
		for(set<int>::iterator i = Y.begin(); i != Y.end(); ++i) {
			mapaYY[at] = *i;
			mapaY[*i] = at++;
			maxy = at;
		}
		memset(grid,-1,sizeof(grid));
		for(int i = 0;i < N; i++) {
			for(int j = mapaX[V[i].a]; j < mapaX[V[i].c]; j++) {
				for(int k = mapaY[V[i].b]; k < mapaY[V[i].d]; k++) {
					grid[j][k] = i;
				}
			}
		}
		memset(value, 0, sizeof(value));
		for(int k = 0; k < N; k++) {
			for(int i = 0; i < maxx; i++) {
				for(int j = 0;j < maxy; j++) {
					if(grid[i][j] == k) {
						value[k] += (mapaXX[i+1] - mapaXX[i]) * (mapaYY[j+1] - mapaYY[j]);
					}
				}
			}
		}
		/*
		for(int i = 0;i < N; i++) {
			printf("%d ", value[i]);
		}
		printf("\n");
		*/
		memset(pd,-1,sizeof(pd));
		int resp = f(0,M);
//		printf("%d\n", f(0,M));
		at = 0;
		int k = M;
		vector<int> R;
		while(resp != 0) {
			if(k > 0 && (pd[at+1][k-1] + value[at] == resp)) {
				R.push_back(at);
				resp -= value[at];
				at++;
				k--;
			} else {
				at++;
			}

			/*
			if(pd[at+1][k] == resp) {
				at++;
			} else {
				R.push_back(at);
				resp -= value[at];
				at++;
				k--;
			}
			*/
		}
		for(int i = 0; i < R.size();i++) {
			if(i) printf(" ");
			printf("%d", R[i]);
		}
		puts("");
	}
	return 0;
}

Maior Subsequência Bitônica (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 200000

int n;

int bitA[N], bitB[N], qtd[N], v[N], ord[N];

int readA(int x) {
	int r = 0;
	while(x > 0) {
		r = max(r, bitA[x]);
		x -= (x&-x);
	}
	return r;
}

void updateA(int x, int val) {
	while(x < N) {
		bitA[x] = max(bitA[x], val);
		x += (x&-x);
	}
}

int readB(int x) {
	int r = 0;
	while(x < N) {
		r = max(r, bitB[x]);
		x += (x&-x);
	}
	return r;
}

void updateB(int x, int val) {
	while(x > 0) {
		bitB[x] = max(bitB[x], val);
		x -= (x&-x);
	}
}



int tenta1() {
	for(int i = 0; i < N; i++) {
		bitA[i] = bitB[i] = qtd[i] = 0;
	}
	int r = 0;
	for(int i = 0; i < n; i++) {
		qtd[i] = readA(v[i]);
		updateA(v[i]+1, qtd[i]+1);
	}
	for(int i = 0; i < N; i++) {
		bitA[i] = bitB[i] = 0;
	}
	for(int i = n-1; i >= 0; i--) {
		int aux = readA(v[i]);
		updateA(v[i]+1, aux+1);
		r = max(r, aux + qtd[i] + 1);
	}
	return r;
}


int tenta2() {
	for(int i = 0; i < N; i++) {
		bitA[i] = bitB[i] = qtd[i] = 0;
	}
	int r = 0;
	for(int i = 0; i < n; i++) {
		qtd[i] = readB(v[i]);
		updateB(v[i]-1, qtd[i]+1);
	}
	for(int i = 0; i < N; i++) {
		bitA[i] = bitB[i] = 0;
	}
	for(int i = n-1; i >= 0; i--) {
		int aux = readB(v[i]);
		updateB(v[i]-1, aux+1);
		r = max(r, aux + qtd[i] + 1);
	}
	return r;
}

int main() {
	while(scanf("%d", &n) == 1) {
		for(int i = 0; i < n; i++) {
			scanf("%d", v+i);
			ord[i] = v[i];
		}
		sort(ord, ord+n);
		for(int i = 0 ; i < n; i++) {
			v[i] = (int) (lower_bound( ord, ord + n, v[i] ) - ord);
			v[i]+= 2;
		}
		int a = tenta1();
		int b = tenta2();
		printf("%d\n", a > b ? a : b);
	}
	return 0;
}

Cracking RSA (por SUDO)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <utility>

using namespace std;

#define EPS 1e-9

int cmp(double a, double b = 0.0) {
	return a+EPS < b ? -1 : a-EPS > b;
}

const int DIG = 4;
const int BASE = 10000; // BASE**3 < 2**51
const int TAM = 2048;
struct bigint {
int v[TAM], n;
bigint(int x = 0): n(1) {
memset(v, 0, sizeof(v));
v[n++] = x; fix();
}
bigint(char *s): n(1) {
memset(v, 0, sizeof(v));
int sign = 1;
while (*s && !isdigit(*s)) if (*s++ == '-') sign *= -1;
char *t = strdup(s), *p = t + strlen(t);
while (p > t) {
*p = 0; p = max(t, p - DIG);
sscanf(p, "%d", &v[n]);
v[n++] *= sign;
}
free(t); fix();
}
bigint& fix(int m = 0) {
n = max(m, n);
int sign = 0;
for (int i = 1, e = 0; i <= n || e && (n = i); i++) {
v[i] += e; e = v[i] / BASE; v[i] %= BASE;
if (v[i]) sign = (v[i] > 0) ? 1 : -1;
}
for (int i = n - 1; i > 0; i--)
if (v[i] * sign < 0) { v[i] += sign * BASE; v[i+1] -= sign; }
while (n && !v[n]) n--;
return *this;
}
int cmp(const bigint& x = 0) const {
int i = max(n, x.n), t = 0;
while (1) if ((t = ::cmp(v[i], x.v[i])) || i-- == 0) return t;
}
bool operator <(const bigint& x) const { return cmp(x) < 0; }
bool operator ==(const bigint& x) const { return cmp(x) == 0; }
bool operator !=(const bigint& x) const { return cmp(x) != 0; }
operator string() const {
ostringstream s; s << v[n];
for (int i = n - 1; i > 0; i--) {
s.width(DIG); s.fill('0'); s << abs(v[i]);
}
return s.str();
}
friend ostream& operator <<(ostream& o, const bigint& x) {
return o << (string) x;
}
bigint& operator +=(const bigint& x) {
for (int i = 1; i <= x.n; i++) v[i] += x.v[i];
return fix(x.n);
}
bigint operator +(const bigint& x) { return bigint(*this) += x; }
bigint& operator -=(const bigint& x) {
for (int i = 1; i <= x.n; i++) v[i] -= x.v[i];
return fix(x.n);
}
bigint operator -(const bigint& x) { return bigint(*this) -= x; }
bigint operator -() { bigint r = 0; return r -= *this; }
void ams(const bigint& x, int m, int b) { // *this += (x * m) << b;
for (int i = 1, e = 0; (i <= x.n || e) && (n = i + b); i++) {
v[i+b] += x.v[i] * m + e; e = v[i+b] / BASE; v[i+b] %= BASE;
}
}
bigint operator *(const bigint& x) const {
bigint r;
for (int i = 1; i <= n; i++) r.ams(x, v[i], i-1);
return r;
}
bigint& operator *=(const bigint& x) { return *this = *this * x; }
// cmp(x / y) == cmp(x) * cmp(y); cmp(x % y) == cmp(x);
bigint div(const bigint& x) {
if (x == 0) return 0;
bigint q; q.n = max(n - x.n + 1, 0);
int d = x.v[x.n] * BASE + x.v[x.n-1];
for (int i = q.n; i > 0; i--) {
int j = x.n + i - 1;
q.v[i] = int((v[j] * double(BASE) + v[j-1]) / d);
ams(x, -q.v[i], i-1);
if (i == 1 || j == 1) break;
v[j-1] += BASE * v[j]; v[j] = 0;
}
fix(x.n); return q.fix();
}
bigint& operator /=(const bigint& x) { return *this = div(x); }
bigint& operator %=(const bigint& x) { div(x); return *this; }
bigint operator /(const bigint& x) { return bigint(*this).div(x); }
bigint operator %(const bigint& x) { return bigint(*this) %= x; }
bigint pow(int x) {
if (x < 0) return (*this == 1 || *this == -1) ? pow(-x) : 0;
bigint r = 1;
for (int i = 0; i < x; i++) r *= *this;
return r;
}
bigint root(int x) {
if (cmp() == 0 || cmp() < 0 && x % 2 == 0) return 0;
if (*this == 1 || x == 1) return *this;
if (cmp() < 0) return -(-*this).root(x);
bigint a = 1, d = *this;
while (d != 1) {
bigint b = a + (d /= 2);
if (cmp(b.pow(x)) >= 0) { d += 1; a = b; }
}
return a;
}
};

#define MAX 105

int M[MAX][MAX];

int gaussian_elimination(int a[MAX][MAX], int n, int m) {
	int i, j, k, l;
	
	for (i=0,j=0; i < n && j < m; j++) {
		for (k=i; k < n; k++) {
			if (a[k][j] == 1) {
				break;
			}
		}
		
		if (k == n) {
			continue;
		}
		
		for (l=0; l < m; l++) {
			int aux = a[i][l]; a[i][l] = a[k][l]; a[k][l] = aux;
		}
		
		for (k=i+1; k < n; k++) if (a[k][j] != 0) {
			for (l=j; l < m; l++) {
				a[k][l] ^= a[i][l];
			}
		}
		
		i++;
	}
	
	return n - i;
}

int main () {
	vector <int> primes;
	int t, m;
	
	for (int i=2; primes.size() < 100; i++) {
		bool isprime = true;
		for (int j=2; j < i; j++) {
			if (i%j == 0) {
				isprime = false;
			}
		}
		if (isprime) primes.push_back(i);
	}
	
	while (scanf("%d %d",&t,&m) == 2) {
		
		memset(M,0,sizeof(M));
		
		for (int i=0; i < m; i++) {
			int n;
			scanf("%d",&n);
			for (int j=0; j < t; j++) {
				while (n%primes[j] == 0) {
					n /= primes[j];
					M[i][j] ^= 1;
				}
			}
		}
		
		int kernel = gaussian_elimination(M,m,t);
		
		bigint ans = bigint(2).pow(kernel) - bigint(1);
		
		cout << ((string) ans) << endl;
	}
	
	return 0;
}

Super String (por SUDO)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <utility>

using namespace std;

#define EPS 1e-9

string table[1<<12][12];
int init[12][12];

inline bool shorter(string a, string b) {
	return a.length() < b.length() || (a.length() == b.length() && a < b);
}

int main () {
	string s[15];
	
	while (cin >> s[0]) {
		vector <string> v;
		int n;
		
		for (n=1; s[n-1] != "."; n++) {
			cin >> s[n];
		} n--;
		
		vector <bool> erased(n,false);
		
		for (int i=0; i < n; i++) {
			bool good = true;
			for (int j=0; j < n; j++) {
				if (i != j && !erased[j] && s[j].find(s[i]) != -1) {
					good = false;
				}
			}
			if (good) v.push_back(s[i]);
			else erased[i] = true;
		}
		
		n = v.size();
		
		for (int i=0; i < n; i++) {
			for (int j=0; j < n; j++) if (i != j) {
				int k;
				for (k=min(v[i].length(),v[j].length())-1; k > 0; k--) {
					int l;
					for (l=0; l < k && v[i][k-l-1] == v[j][v[j].length()-l-1]; l++);
					if (l == k) {
						break;
					}
				}
				init[i][j] = k;
			}
		}
		
		for (int i=0; i < n; i++) {
			table[1<<i][i] = v[i];
		}
		
		for (int mask=1; mask < (1 << n); mask++) if (__builtin_popcount(mask) > 1) {
			for (int i=0; i < n; i++) if (mask & 1 << i) {
				table[mask][i] = "";
				for (int j=0; j < n; j++) {
					if (i != j && (mask & 1 << j)) {
						string aux = table[mask-(1<<i)][j] + v[i].substr(init[i][j]);
						if (table[mask][i] == "" || shorter(aux,table[mask][i])) {
							table[mask][i] = aux;
						}
					}
				}
			}
		}
		
		string ans = "";
		
		for (int i=0; i < n; i++) {
			if (ans == "" || shorter(table[(1<<n)-1][i],ans)) {
				ans = table[(1<<n)-1][i];
			}
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

Fork Bomb (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
	return (b == 0) ? a : gcd(b, a % b);
}

int pot(int a, int e, int m) {
	if (e == 0) {
		return 1;
	}
	long long b = pot(a, e/2, m);
	b = (b * b) % m;
	return (e % 2 == 0) ? b : (b * a) % m;
}

int main() {
	int n, m, t;
	while (scanf("%d %d %d", &n, &t, &m) != EOF) {
		int res = (pot(n, t, m*(n - 1)) + (m * (n-1)) - 1) % (m * (n - 1));
		printf("%d\n", (res / (n - 1)) % m);
	}
	return 0;
}

GCD LCM (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <map>
#include <math.h>

using namespace std;

typedef long long lld;
typedef unsigned long long llu;
typedef long double ldouble;

lld val_abs(lld a) {
	return (a >= 0) ? a : -a;
}

llu gcd(llu a, llu b) {
	return (b != 0) ? gcd(b, a % b) : a;
}

llu mul_mod(llu a, llu b, llu m) {
	llu y = (llu)((ldouble)a*(ldouble)b/m+(ldouble)1/2);
	y = y * m;
	llu x = a * b;
	llu r = x - y;
	if ((lld) r < 0) {
		r = r + m;
		y = y - 1;
	}
	return r;
}

llu exp_mod(llu a, llu e, llu mod) {
	if (e == 0) {
		return 1;
	}
	llu b = exp_mod(a, e/2, mod);
	if (e % 2 == 0) {
		return mul_mod(b, b, mod);
	} else {
		return mul_mod(mul_mod(b, b, mod), a, mod);
	}
}

int is_probably_prime(llu n) {
	if (n == 2) {
		return 1;
	}
	llu s = 0, d = n - 1;
	while (d % 2 == 0) {
		d/= 2;
		s++;
	}
	for (int k = 0; k < 32; k++) {
		llu a = (rand() % (n - 2)) + 2;
		llu x = exp_mod(a, d, n);
		if (x != 1 && x != n-1) {
			int r;
			for (r = 1; r < s; r++) {
				x = mul_mod(x, x, n);
				if (x == 1) {
					r = s;
					break;
				} else if (x == n-1) {
					r = 0;
					break;
				}
			}
			if (r != 0) {
				return 0;
			}
		}
	}
	return 1;
}

llu rho(llu n) {
	llu d;
	llu c = rand() % n;
	llu x = rand() % n;
	llu xx = x;

	if (n % 2 == 0) {
		return 2;
	}

	do {
		x = (mul_mod(x, x, n) + c) % n;
		xx = (mul_mod(xx, xx, n) + c) % n;
		xx = (mul_mod(xx, xx, n) + c) % n;
		d = gcd(val_abs(x - xx), n);
	} while (d == 1);

	return d;
}

map <llu,int> F;

void factor(llu n) {
	if (n == 1) {
		return;
	}
	if (is_probably_prime(n)) {
		F[n]++;
		return;
	}
	llu d = rho(n);
	factor(d);
	factor(n/d);
}

int main() {
	int tests;
	scanf("%d", &tests);
	for (int test = 0; test < tests; test++) {
		lld g, l;
		scanf("%lld %lld", &g, &l);
		lld raiz = sqrtl(l);
		lld ma, mb;
		lld a, b;
		int ok = 0;
		for (a = 1; a <= raiz; a++) {
			if (l % a == 0) {
				b = (l / a) * g;
				if (gcd(a, b) == g) {
					if (!ok || a < ma) {
						ma = a;
						mb = b;
						ok = 1;
					}
				}
				lld oa = l / a;
				lld ob = (l / oa) * g;
				if (gcd(oa, ob) == g) {
					if (!ok || oa < ma) {
						ma = oa;
						mb = ob;
						ok = 1;
					}
				}
			}
		}
		if (ok) {
			printf("%lld %lld\n", ma, mb);
		} else {
			printf("-1\n");
		}
	}
	return 0;
}

Discrete Logging (por AUHAUAH Balões Mano)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

ll p, b, n;

map<ll,int> m;

ll pot (ll x, int y)
{
	if (y == 0)
		return 1;
		
	ll a = pot (x, y/2);
	a = (a*a)%p;
	
	if (y % 2)
		a = (a * x)%p;
		
	return a;
}

int main (void)
{
	ll k;
	const ll d = 1<<16;
	while (scanf ("%lld %lld %lld", &p, &b, &n) == 3)
	{
//		printf ("%lld %lld %lld: ", p, b, n);
		bool achou = false;
		
		m.clear();
		
		k = 1;
		for (int i = 0; i < d; i++)
		{
			if (k == n)
			{
				printf ("%d\n", i);
				achou = true;
				break;
			}
			
			m[k] = i;
			
			k = (k*b)%p;
		}
		
		if (achou) continue;
		
		ll inv = pot(b, p-2);
//		printf ("Inverso: %lld\n", inv);
		inv = pot(inv, d);
//		printf ("Inverso^d: %lld\n", inv);
		
		k = (inv*n)%p;
//		printf ("Inverso^d * n: %lld\n", k);
		
		ll lim = p/d;
		if (p%d) lim++;
		
		for (int i = 1; i <= lim; i++)
		{
			if (m.find(k) != m.end())
			{
				achou = true;
//				printf ("(%lld,%d,%lld) ", k,m[k], pot(b, i*d + m[k]));
				printf ("%lld\n", i*d + m[k]);
				break;
			}
			
//			printf ("Não achei: %lld\n", k);
			k = (k*inv)%p;
		}
		
		if (!achou)
			printf ("no solution\n");
	}
}

Golden Tiger Claw (por SUDO)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define fori(i, n) for ( int i = 0; i < (n); ++i )
#define forr(i, a, b) for ( int i = (a); i <= (b); ++i )
#define ford(i, a, b) for ( int i = (a); i >= (b); --i )
#define tr(it, a, b) for ( typeof(a) it = (a); it != (b); ++it )
#define all(x) (x).begin(),(x).end()
#define sz size()
#define pb push_back

const int INF = 0x3F3F3F3F;
const int MAXN = 501;
int lx[MAXN], ly[MAXN], mark_t[MAXN], viz_x[MAXN][MAXN], num_viz_x[MAXN], sat_x[MAXN], sat_y[MAXN], pai_x[MAXN], pai_y[MAXN], match[MAXN], N, w[MAXN][MAXN];
vector< int > S, T;
 
int not_satured()
{
	forr(i,1,N) if ( sat_x[i] == 0 ) return i;
	return 0;
}

int choose( int * x_pai )
{
	fori(i,S.sz) fori(j,num_viz_x[S[i]]) if ( !mark_t[ viz_x[S[i]][j] ] )
	{
		*x_pai = S[i];
		return viz_x[S[i]][j];
	}
	return -1;
}

void init()
{
	forr(i,1,N)
	{
		int k = -1;
		forr(j,1,N) if ( w[i][j] > k ) k = w[i][j];
		lx[i] = k;
		ly[i] = 0;
	}
	memset( num_viz_x, 0, sizeof( num_viz_x ) );
	memset( mark_t, 0, sizeof( mark_t ) );
	memset( sat_x, 0, sizeof( sat_x ) );
	memset( sat_y, 0, sizeof( sat_y ) );
	memset( match, -1, sizeof( match ) );
	memset( pai_x, -1, sizeof( pai_x ) );
	memset( pai_y, -1, sizeof( pai_y ) );
	forr(i,1,N) forr(j,1,N) if ( lx[i] + ly[j] == w[i][j] ) viz_x[i][ num_viz_x[i]++ ] = j;
}

void calc()
{
	int best = INF;
	fori(i,S.sz) forr(j,1,N) if ( !mark_t[j] ) if ( lx[S[i]] + ly[j] - w[S[i]][j] < best ) best = lx[S[i]] + ly[j] - w[S[i]][j];
	fori(i,S.sz) lx[S[i]] -= best;
	fori(i,T.sz) ly[T[i]] += best;
	memset( num_viz_x, 0, sizeof( num_viz_x ) );
	memset( mark_t, 0, sizeof( mark_t ) );
	memset( sat_x, 0, sizeof( sat_x ) );
	memset( sat_y, 0, sizeof( sat_y ) );
	memset( match, -1, sizeof( match ) );
	memset( pai_x, -1, sizeof( pai_x ) );
	memset( pai_y, -1, sizeof( pai_y ) );
	forr(i,1,N) forr(j,1,N) if ( lx[i] + ly[j] == w[i][j] ) viz_x[i][ num_viz_x[i]++ ] = j;
}

void hungarian()
{
	int i, u, y, z, x_pai;
	init();
	while ( u = not_satured() )
	{
		S.clear();
		T.clear();
		memset( mark_t, 0, sizeof ( mark_t ) );
		S.push_back( u );
		while ( 1 )
		{
			y = choose( &x_pai );
			if ( y == -1 ) { calc(); break; }
			else
			{
				if ( sat_y[y] )
				{
					S.push_back( match[y] );
					T.push_back( y );
					mark_t[y] = 1;
					pai_x[y] = x_pai;
					pai_y[ match[y] ] = y;
				}
				else
				{
					pai_x[y] = x_pai;
					int atual = y;
					while ( atual != -1 )
					{
						match[ atual ] = pai_x[atual];
						sat_y[atual] = 1;
						sat_x[ pai_x[atual] ] = 1;
						atual = pai_y[ pai_x[atual] ];
					}
					break;
				}
			}
		}
	}
}

int main()
{
	while ( scanf( "%d", &N ) == 1 )
	{
		forr(i,1,N) forr(j,1,N) scanf( "%d", &w[i][j] );
		hungarian();
		int asw = 0;
		forr(i,1,N)
		{
			if ( i != 1 ) printf( " " );
			printf( "%d", lx[i] );
			asw += lx[i];
		}
		cout << endl;
		forr(i,1,N)
		{
			if ( i != 1 ) printf( " " );
			printf( "%d", ly[i] );
			asw += ly[i];
		}
		puts("");
		printf( "%d\n", asw );
	}
	
    return 0;
}