Category Archives: UVA

UVA – 10679 – I Love Strings!! – [Suffix Array nlgn]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int find(char * p) {
	int l = 0, sz = strlen(p), h = strlen(str) - 1;

	while (l <= h) {
		int mid = l + (h - l) / 2;
		char * tmp = (char*)malloc(sz+1);
		strncpy(tmp, str + pos[mid], sz);
		tmp[sz] = 0;
		int cmp = strcmp(p, tmp);
		if (cmp < 0)
			h = mid - 1;
		if (cmp > 0)
			l = mid + 1;
		if (!cmp)
			return mid;
	}
	return -1;
}

int main() {
	freopen("input.txt", "r", stdin);
	string s;
	int T, q;
	char p[2000], tmp[200];
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		scanf("%d", &q);
		gets(tmp);
		long long len = 0LL + strlen(str);
		suffixSort(len);
		while (q--) {
			gets(p);
			if (find(p) != -1)
				puts("y");
			else
				puts("n");
		}

	}
}

UVa – 1225 – Digit Counting

#include <iostream>
#include <string>
#include <string.h>
#include <sstream>
using namespace std;

int main() {
	int T, N, n[10];
	cin >> T;
	while (T-- && cin >> N) {
		stringstream s;
		while (N--) s << (N + 1);
		memset(n, 0, sizeof n);
		for (size_t c = 0; c < s.str().length(); c++)
			n[s.str()[c] - '0']++;
		for (int i = 0; i < 10; i++) {
			cout << n[i];
			if (i!=9) cout << " ";
		}
		cout << endl;
	}
	return 0;
}

UVa – 12403 – Save Setu



#include <iostream>
#include <string>

using namespace std;

int main() {
	int T, donations=0, N;
	string s;
	cin >> T;
	while(T-- && cin>> s){
		if(!s.compare("donate")){
			cin >> N;
			donations+=N;
		}
		else
			cout << donations << endl;
	}
	return 0;
}

UVa – 11282 – Mixing Invitations

#include <iostream>

#include <cstdio>
using namespace std;

typedef  long long int LONG;

int main() {
	LONG nck[21][21],der[21]; int N, M;

	for (int i = 0; i < 21; ++i)
		der[i] = i < 2 ? 1 - i : (i - 1) * (der[i - 2] + der[i - 1]);

	for (int n = 0, nCk = 1; n < 21; n++, nCk = 1)
		for (int k = 0; k <= n; k++)
			nck[n][k] = nCk, nCk = nCk * (n - k) / (k + 1);

	while (scanf("%d %d\n", &N, &M) == 2) {
		LONG total = 0;
		for (int i = 0; i <= M; i++)
			total += nck[N][i] * der[N - i];
		printf("%lld\n", total);
	}
	return 0;
}

UVa – 10926 – How Many Dependencies?


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

int dist[101][101];

int main() {

	for (int N, max_deps = 0, max_i = 0; scanf("%d", &N) && N; max_deps = 0, max_i = 0) {
		memset(dist, 0, sizeof dist);
		
		for (int T, n = 1; n <= N && scanf("%d", &T); n++)
			for (int t = 1, o; t <= T && scanf("%d", &o); t++)
				dist[n][o] = 1;

		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					if ((dist[i][k] * dist[k][j] != 0) && (i != j) && dist[i][k] + dist[k][j] >= dist[i][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						if (dist[i][j] > max_deps || (dist[i][j] == max_deps && i < max_i))
							max_i = i, max_deps = dist[i][j];
					}

		printf("%d\n", max_i);
	}
	return 0;
}

UVa – 11549 – Calculator Conundrum

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long int Long;
#define d(i) (i > 0 ? int (log10(i)) + 1 : 1)
#define f(k,n) (d(k*k) < n ? (k * k) : ((k * k) / int (pow(10, d(k*k) - n))))

int main() {
	Long k, T, n;
	scanf("%lld", &T);
	while (T-- && scanf("%lld %lld", &n, &k)) {
		Long m = k, tortoise = k, hare = k;
		do {
			m = max((tortoise = f(tortoise, n)), m);
			m = max((hare = f(hare, n)), m);
			m = max((hare = f(hare, n)), m);
		} while (tortoise != hare);
		printf("%lld\n", m);
	}
	return 0;
}

UVa – 846 – Steps

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

int main() {
	int T;
	cin >> T;
	for (int a, b; T-- && cin >> a >> b;) {
		int c = (int) round(sqrt(b - a));
		cout << 2 * c - (c && c * c >= b - a) << endl;
	}
	return 0;
}

UVa – 637 – Booklet Printing



#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <sstream>
using namespace std;

string to_s(int a) {stringstream ss; ss << a; return ss.str();}

int main() {
	for (int a, b, p, P, N = 0; (scanf("%d", &N) == 1) && N;) {
		a = 1, p = 1, P = (N / 4 + 1 - ((N % 4) ? 0 : 1)), b = P * 4;
		printf("Printing order for %d pages:\n", N);
		while (b > a) {
			printf("Sheet %d, front: %s, %d\n", p, (b-- > N) ? string("Blank").c_str() : to_s(b+1).c_str(), a++);
			if (N > 1)
				printf("Sheet %d, back : %d, %s\n", p, a, (b > N) ? string("Blank").c_str() : to_s(b).c_str());
			b--, a++, p++;
		}
	}
	return 0;
}

UVa – 10931 – Parity

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

char s[33];
int main() {
	for (int N = 0; (scanf("%d", &N) == 1) && N && itoa(N, s, 2);) {
		printf("The parity of %s is %d (mod 2).\n", s, __builtin_popcount(N));
	}
	return 0;
}

UVa – 10420 – List of Conquests

#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
int main() {
	int n;
	char country[80], mara_momes[80];
	map<string, int> m;
	scanf("%d\n", &n);

	while (n-- && scanf("%s", country) == 1 && gets(mara_momes))
		m[string(country)] = m[string(country)] + 1;

	for (map<string, int>::iterator it = m.begin(); it != m.end(); it++)
		printf("%s %d\n", it->first.c_str(), it->second);

	return 0;
}