Archive for the ‘Binary search’ Category

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;
}

Advertisements

Posted June 24, 2012 by epicrado in Binary search

UVA – 11262 – Weird Fence   Leave a comment


Basic idea is binary search on the max allowed distance between two poles and build a graph using this distance, and do maximum matching to see where the binary search should go.

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

public class WeirdFence {
	public static int bfs(int s, int t, int[][] res, int[] parent) {
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(s);
		Q.add(Integer.MAX_VALUE);
		while (!Q.isEmpty()) {
			int n = Q.poll();
			int flow = Q.poll();
			if (n == t)
				return flow;
			for (int j = 0; j < res[n].length; j++) {
				if (res[n][j] != 0 && parent[j] == -1) {
					Q.add(j);
					Q.add(Math.min(flow, res[n][j]));
					parent[j] = n;
				}
			}
		}
		return 0;
	}

	public static void augmentPath(int s, int t, int flow, int[] parent,
			int[][] res) {
		int cur = t;
		while (cur != s) {
			res[parent[cur]][cur] -= flow;
			res[cur][parent[cur]] += flow;
			cur = parent[cur];
		}
	}

	public static int maxFlow(int s, int t, int[][] res) {
		int[] parent = new int[res.length];
		Arrays.fill(parent, -1);
		int flow, maxflow = 0;
		while ((flow = bfs(s, t, res, parent)) != 0) {
			maxflow += flow;
			augmentPath(s, t, flow, parent, res);
			Arrays.fill(parent, -1);
		}
		return maxflow;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int n = in.nextInt();
			int k = in.nextInt();
			int[] x = new int[n];
			int[] y = new int[n];
			boolean[] col = new boolean[n];
			for (int i = 0; i < n; i++) {
				x[i] = in.nextInt();
				y[i] = in.nextInt();
				String s = in.next();
				col[i] = s.equals("red");
			}

			int l = 0;
			int h = 3000;
			boolean ok = false;
			while (h > l) {
				int mid = (l + h) / 2;
				int[][] g = new int[n + 2][n + 2];
				for (int i = 0; i < n; i++) {
					if (col[i])
						g[0][i + 1] = 1;
					else
						g[i + 1][n+1] = 1;
				}
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if (col[i]
								&& !col[j]
								&& (x[i] - x[j]) * (x[i] - x[j])
										+ (y[i] - y[j]) * (y[i] - y[j]) <= mid
										* mid) {
							g[i + 1][j + 1] = 1;
						}
					}
				}
				int max = maxFlow(0, n+1, g);
				if (max >= k) {
					h = mid;
					ok = true;
				} else
					l = mid + 1;
			}
			if (ok)
				System.out.println(h);
			else
				System.out.println("Impossible");
		}
	}

	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 13, 2012 by epicrado in Binary search, Graphs, Maxflow

UVA – 714 – Copying Books   Leave a comment


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

public class CopyingBooks {

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int books = in.nextInt();
			int writers = in.nextInt();
			int[] b = new int[books];
			for (int i = 0; i < b.length; i++)
				b[i] = in.nextInt();
			long high = 1L << 33;
			long low = 1;
			while (high > low) {
				long mid = (high + low) / 2;
				long accu = 0;
				int j = 0;
				for (int i = 0; i < books && j < writers; i++) {
					while (b[i] + accu > mid && j < writers) {
						accu = 0;
						j++;
					}
					accu += b[i];
				}
				if (j >= writers)
					low = mid + 1;
				else
					high = mid;
			}
			long copy = high;
			int[] start = new int[writers];
			Arrays.fill(start, -1);
			long accu = 0;
			int current = writers - 1;
			for (int i = books - 1; i >= 0; i--) {
				if (accu + b[i] > copy) {
					start[current] = i + 1;
					accu = 0;
					current--;
				}
				accu += b[i];
			}
			start[current] = 0;
			int top = 0;
			for (int i = 0; i < start.length; i++)
				if (start[i] == -1)
					start[i] = top++;
			for (int i = 0; i < start.length - 1; i++) {
				if (start[i] >= start[i + 1])
					start[i + 1] += (start[i] - start[i + 1] + 1);
			}
			StringBuilder out = new StringBuilder();
			for (int i = 0; i < start.length; i++) {
				int next = books;
				if (i + 1 < start.length)
					next = start[i + 1];
				for (int j = start[i]; j < next; j++) {
					out.append(b[j] + " ");
				}
				out.append("/ ");
			}
			out.deleteCharAt(out.length() - 1);
			out.deleteCharAt(out.length() - 1);
			out.deleteCharAt(out.length() - 1);
			System.out.println(out);
		}
	}

	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 May 25, 2012 by epicrado in Binary search

UVA – 11876 – N + NOD (N)   Leave a comment


#include <stdio.h>
#define N 1021650
int nod[N];
int nnod[N];
int main()
{
	int i,j,hi,lo,tc,mid,a,b,cc=1,iter;
	for(i=0;i<N;i++)
		nod[i]=0;
	for(i=1;i<N;i++)
		for(j=i;j<N;j+=i)
			nod[j]++;
	nnod[0]=1;
	nod[0]=1;
	for(i=1;i<66000;i++)
		nnod[i]=nnod[i-1]+nod[nnod[i-1]];
	scanf("%d",&tc);
	while(tc--)
	{
		scanf("%d %d",&i,&j);
		iter = 20;
		lo = 0;
		hi = 65999;
		while(iter--)
		{
			mid = (hi+lo)/2;
			if(nnod[mid]<i)
				lo = mid;
			else
				hi = mid;
		}
		a = hi;
		lo = 0;
		hi = 65999;
		iter = 20;
		while(iter--)
		{
			mid = (hi+lo)/2;
			if(nnod[mid]<=j)
				lo = mid;
			else
				hi = mid;
		}
		b = lo;
		printf("Case %d: %d\n",cc++,b-a+1);
	}
	return 0;
}

Posted September 16, 2011 by epicrado in Binary search

UVA – 11935 – Through the Desert   Leave a comment


#include <stdio.h>
char event[55];
int val[55];
int km[55];
int n;
char can(double fuel)
{
	double init = fuel;
	int cons = 0;
	int ckm = 0;
	int leek = 0;
	int i;
	for(i=0;i<n;i++)
	{
		fuel=fuel-(km[i]-ckm)*leek-(km[i]-ckm)/100.00*cons;
		if(fuel<0)
			return 0;
		if(event[i]=='F')
			cons = val[i];
		else if(event[i]=='L')
				leek++;
		else if(event[i]=='M')
				leek = 0;
		else if(event[i]=='G'&&fuel>=0)
				fuel = init;
		ckm = km[i];
	}
	return 1;
}
int main()
{
	char inp[100],s1[20],s2[20];
	int c,x,a;
	double hi,lo,mid;
	n = 0;
	while(gets(inp))
	{
		x = sscanf(inp,"%d %s %s %d",&a,s1,s2,&c);
		if(x==4&&!a&&!c)
			break;
		if(x==2&&s1[0]=='G')
		{
			km[n]=a;
			event[n]='g';
			n++;
			hi = 10000;
			lo = 0;
			while(hi-lo>1e-9)
			{
				mid = (hi+lo)/2;
				if(can(mid))
					hi = mid;
				else
					lo = mid;
			}
			printf("%.3lf\n",(hi+lo)/2);
			n = 0;
		}
		else
		{
			if(x<=3)
			{
				km[n]=a;
				event[n]=s1[0];
				n++;
			}
			if(x==4)
			{
				km[n]=a;
				event[n]=s1[0];
				val[n]=c;
				n++;
			}
		}
	}
	return 0;
}

Posted September 16, 2011 by epicrado in Binary search

UVA – 10341 – Solve It   Leave a comment


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define E 2.7182818284
int p,q,r,s,t,u;
double absolute(double d)
{
	if(d<0)
		return -d;
	return d;
}
double f(double x)
{
	return p*pow(E,-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
}
int main()
{
	double hi,lo,mid;
	while(scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)==6)
	{
		if(f(1)*f(0)>0)
			puts("No solution");
		else
		{
			hi = 1;
			lo = 0;
			if(f(1)<f(0))
			{
				hi = 0;
				lo = 1;
			}
			while(absolute(hi-lo)>1e-9)
			{
				mid = (hi+lo)/2.00;
				if(f(mid)<0)
					lo = mid;
				else
					hi = mid;
			}
			printf("%.4lf\n",(hi+lo)/2.00);fac
		}
	}
	return 0;
}

Posted September 15, 2011 by epicrado in Binary search

UVA – 10566 – Crossed Ladders   2 comments


#include <stdio.h>
#include <math.h>
double min(double a,double b)
{
	return (a<b)?a:b;
}
double func(double x,double y,double d)
{
	return 1/sqrt(x*x-d*d) + 1/sqrt(y*y-d*d);
}
int main()
{
	double recip,hi,lo,mid,x,y,c;
	while(scanf("%lf %lf %lf",&x,&y,&c)==3)
	{
		lo = 0;
		hi = min(x,y);
		recip = 1 / c;
		while(hi-lo>1e-4)
		{
			mid = (hi + lo) / 2;
			if(func(x,y,mid)<recip)
				lo = mid;
			else
				hi = mid;
		}
		printf("%.3lf\n",(hi+lo)/2);
	}
	return 0;
}

Posted August 22, 2011 by epicrado in Binary search