Archive for the ‘Greedy’ 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 – 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 – 11520 – Fill the Square   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class FillTheSquare {
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		int cc = 1;
		while (tc-- > 0) {
			int n = Integer.parseInt(in.readLine());
			char[][] map = new char[n][];
			int[][] v = new int[n][n];
			for (int i = 0; i < n; i++)
				map[i] = in.readLine().toCharArray();
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if (map[i][j] != '.') {
						for (int d = 0; d < 4; d++) {
							int ni = i + dx[d];
							int nj = j + dy[d];
							if (ni >= 0 && nj < n && ni < n && nj >= 0) {
								v[ni][nj] |= (1 << (map[i][j] - 'A'));
							}
						}
					}
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if (map[i][j] == '.') {
						int tar = 0;
						while ((v[i][j] & 1) == 1) {
							v[i][j] >>= 1;
							tar++;
						}
						map[i][j] = (char) ('A' + tar);
						if (i + 1 < n) {
							v[i + 1][j] |= (1 << tar);
						}
						if (j + 1 < n) {
							v[i][j + 1] |= (1 << tar);
						}
					}
			System.out.printf("Case %d:\n", cc++);
			for (int i = 0; i < map.length; i++)
				System.out.println(new String(map[i]));
		}
	}
}

Posted April 19, 2012 by epicrado in Greedy

UVA – 10020 – Minimal coverage   Leave a comment


import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class MinimalCoverage {

	static class Line implements Comparable<Line> {
		int start, end;

		public Line(int s, int e) {
			start = s;
			end = e;
		}

		public String toString() {
			return start + " " + end;
		}

		public int compareTo(Line arg0) {
			if (start < arg0.start || (start == arg0.start && end > arg0.end))
				return -1;
			return 1;
		}
	}

	public static void main(String[] args) {
		int c;
		Scanner in = new Scanner(System.in);
		c = in.nextInt();
		while (c-- > 0) {
			int m = in.nextInt();
			PriorityQueue<Line> Q = new PriorityQueue<Line>();
			int s = in.nextInt();
			int e = in.nextInt();
			while (s != 0 || e != 0) {
				Q.add(new Line(s, e));
				s = in.nextInt();
				e = in.nextInt();
			}
			int start = 0;
			LinkedList<Line> taken = new LinkedList<Line>();
			while (start < m) {
				Line best = null;
				while (!Q.isEmpty() && Q.peek().start <= start) {
					Line cur = Q.remove();
					if (best == null || cur.end > best.end)
						best = cur;
				}
				if (best == null)
					break;
				else {
					start = best.end;
					taken.add(best);
				}
			}
			if (start < m)
				System.out.println(0);
			else {
				System.out.println(taken.size());
				for (Line i : taken) {
					System.out.println(i);
				}
			}
			if (c != 0)
				System.out.println();
		}
	}
}

Posted August 24, 2011 by epicrado in Greedy

UVA – 10340 – All in All   Leave a comment


Greedy solution
just search for the characters in the order they appear in the first string,
And whenever one is found search for the next one after it.

#include <stdio.h>
int main()
{
	char s1[2000010],s2[2000010];
	int i,j;
	while(scanf("%s %s",s1,s2)==2)
	{
		i = 0;
		for(j=0;s2[j]&&s1[i];j++)
			if(s2[j]==s1[i])
				i++;
		if(!s1[i])
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}

Posted August 23, 2011 by epicrado in Greedy