Archive for the ‘Problem solving paradigms’ Category

UVa – 10714 – Ants   1 comment


The problem here is asking us to calculate the minimum,maximum time it would take all ants to fall off from the stick, lets focus on the maximum time first
That maximum time would be the maximum time that would take the last ant to fall from the stick.
So how do we make this time maximum if we had one ant at position x, simply the time would be max(x,L-x) where L is the length of the stick.
What makes the problem harder is the collision, so lets focus on what happens when 2 ants collide

Assume we have 2 ants A,B in those directions —A—><—B— and they collided at point z, what happens that
before collision B should walk distance z, A should walk distance L-z
after collision A should walk distance z, B should walk distance L-z
so they just exchanged roles here, i.e before collision we were going to wait max(z,L-z) for both ants to fall (if they didn't collide and just shook hands 🙂 )
after collision we're also going to wait max(z,L-z), so collision doesn't change the result.
Knowing this the problem becomes direct, here's solution.

#include <stdio.h>
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int main()
{
	int tc,i,n,c,l,h;
	scanf("%d",&tc);
	while(tc--){
		scanf("%d %d",&c,&n);
		l = h = 0;
		while(n--){
			scanf("%d",&i);
			l = max(l,min(c-i,i));
			h = max(h,max(c-i,i));
		}
		printf("%d %d\n",l,h);
	}
	return 0;
}

Posted May 21, 2013 by epicrado in Greedy

UVA – 11103 – WFF ‘N PROOF   Leave a comment


and another boring problem 😀

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class WFF {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			char[] s = in.readLine().toCharArray();
			if (s.length == 1 && s[0] == '0')
				return;
			String res = "";

			int cnt = 0;
			for (int i = 0; i < s.length; i++) {
				if (Character.isLowerCase(s[i])) {
					res = s[i] + res;
					s[i] = 0;
					cnt++;
					break;
				}
			}
			for (int i = 0; i < s.length; i++)
				if (s[i] == 'N') {
					res = 'N' + res;
					s[i] = 0;
				}
			while (true) {
				boolean flag = true;

				for (int i = 0; i < s.length; i++) {
					if (Character.isLowerCase(s[i]) && cnt < 2) {
						res = s[i] + res;
						s[i] = 0;
						cnt++;
						flag = false;
					} else if (Character.isUpperCase(s[i])) {
						if (s[i] == 'N' && cnt == 1) {
							res = s[i] + res;
							s[i] = 0;
							flag = false;
						} else if (cnt == 2 && s[i] != 'N') {
							res = s[i] + res;
							s[i] = 0;
							flag = false;
							cnt = 1;
						}
					}
				}
				if (flag)
					break;
			}
			if (cnt == 2) {
				System.out.println(res.substring(1, res.length()));
			} else if (res.length() > 0 && cnt == 1)
				System.out.println(res);
			else
				System.out.println("no WFF possible");
		}
	}
}

Posted July 5, 2012 by epicrado in Greedy

UVA – 11108 – Tautology   Leave a comment


Just another boring problem

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Tautology {
	public static int map(char c) {
		if (c == 'p')
			return 0;
		if (c == 'q')
			return 1;
		if (c == 'r')
			return 2;
		if (c == 's')
			return 3;
		if (c == 't')
			return 4;
		return -1;
	}

	public static boolean evaluate(int mask, char[] arr) {
		Stack<Boolean> res = new Stack<Boolean>();
		for (int i = arr.length - 1; i >= 0; i--) {
			if (map(arr[i]) != -1)
				res.push((1 << map(arr[i]) & mask) != 0);
			else {
				if (arr[i] == 'K') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(a && b);
				}
				if (arr[i] == 'A') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(a || b);
				}
				if (arr[i] == 'N')
					res.push(!res.pop());
				if (arr[i] == 'C') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(!a || b);
				}
				if (arr[i] == 'E') {
					boolean a = res.pop();
					boolean b = res.pop();
					res.push(a == b);
				}
			}
		}
		return res.pop();
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			char[] s = in.readLine().toCharArray();
			if (s.length == 1 && s[0] == '0')
				return;
			boolean ok = true;
			for (int i = 0; i < 1 << 5; i++) {
				ok = ok && evaluate(i, s);
			}
			if (ok)
				System.out.println("tautology");
			else
				System.out.println("not");
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted July 5, 2012 by epicrado in Iterative

UVA – 10718 – Bit Mask   1 comment


#include <stdio.h>
typedef long long int ll;
ll solve(ll L, ll U, ll N) {
	ll res = 0;
	int gt = 0;
	int i;
	for (i = 31; i >= 0; i--) {
		if (gt) {
			if ((U & (1LL << i)) && !(N & (1LL << i)))
				res |= 1LL << i;
			else if ((U & (1LL << i)))
				U |= (1LL << i) - 1;
		} else {
			if ((U & (1LL << i)) && (L & (1L << i)))
				res |= 1LL << i;
			else if ((U & (1LL << i)) && !(N & (1LL << i))) {
				res |= 1LL << i;
				gt = 1;
			} else if ((U & (1LL << i)))
				U |= (1LL << i) - 1;
		}
	}
	return res;
}
int main() {
	ll N, L, U;
	while (scanf("%lld %lld %lld", &N, &L, &U) == 3)
		printf("%lld\n", solve(L, U, N));
	return 0;
}

Posted July 5, 2012 by epicrado in Greedy

UVA – 11567 – Moliu Number Generator   Leave a comment


#include <stdio.h>
int min(int a,int b)
{
	return (a<b)?a:b;
}
int calc(long long int n)
{
	if(n==0)
		return 0;
	else if(n==1)
		return 1;
	else if(n&1)
		return 1 + min(calc(n+1),calc(n-1));
	else
		return 1+calc(n/2);
}
int main()
{
	long long int n;
	while(scanf("%lld",&n)==1)
		printf("%d\n",calc(n));
	return 0;
}

Posted July 4, 2012 by epicrado in Greedy

UVA – 11516 – WiFi   Leave a comment


Binary search the answer, a good note is that the minimum distance is always on the form x.0 or x.5 nothing else.

#include <stdio.h>
int loc[100005];
int compare(const void *a,const void *b)
{
	int* ia = (int*)a;
	int* ib = (int*)b;
	return ((*ia)<(*ib)) ? -1 : 1;
}
int main()
{
	int tc;
	scanf("%d",&tc);
	while(tc-->0)
	{
		int s,h,i,j,lo,hi,mid;
		scanf("%d %d",&s,&h);	
		for(i=0;i<h;i++)
			scanf("%d",loc+i);
		qsort(loc,h,sizeof(int),compare);
		lo = 0;
		hi = 2*(loc[h-1]-loc[0]+1);
		while(hi>lo)
		{
			mid = (lo+hi)/2;
			int start = loc[0];
			int needed = 1;
			for(i = 1;i<h;i++)
				if(loc[i]>start+mid)
				{
					start = loc[i];
					needed++;
				}
			if(needed>s)
				lo = mid+1;
			else
				hi = mid;
		}
		printf("%.1f\n",hi/2.00);
	}
	return 0;
}

Posted June 24, 2012 by epicrado in Binary search

UVA – 165 – Stamps   Leave a comment


Simple backtracking + dp to find n for a given coin domination

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Stamps {
	static int optimal;
	static Stack<Integer> best;

	public static int func(Stack<Integer> s, int h) {
		int max = s.peek() * h + 1;
		int[] count = new int[max];
		Arrays.fill(count, Integer.MAX_VALUE);
		count[0] = 0;
		for (int i = 0; i < max; i++) {
			if (count[i] > h) {
				return i - 1;
			}
			for (int j : s)
				if (i + j < max)
					count[i + j] = Math.min(count[i + j], 1 + count[i]);
		}
		return max - 1;
	}

	public static void n(int h, int k, Stack<Integer> s) {
		if (k == 0) {
			int current = func(s, h);
			if (current > optimal) {
				optimal = current;
				best = (Stack<Integer>) s.clone();
			}

		} else {
			int current = func(s, h);
			for (int j = s.peek() + 1; j <= current + 1; j++) {
				s.push(j);
				n(h, k - 1, s);
				s.pop();
			}
		}
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		while (true) {
			int h = in.nextInt(), k = in.nextInt();
			if (h == 0 && k == 0)
				break;
			Stack<Integer> S = new Stack<Integer>();
			S.push(1);
			optimal = 1;
			n(h, k - 1, S);
			for (int i : best)
				System.out.printf("%3d", i);
			System.out.printf(" ->%3d\n", optimal);

		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted June 20, 2012 by epicrado in Recursive Backtracking