Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
HairCuts – SRM 261
import java.util.Arrays;
import java.text.DecimalFormat;
public class HairCut {
public static void main(String[] args){
HairCut cut = new HairCut();
double d;
DecimalFormat f = new DecimalFormat("0.0########");
System.out.println(f.format(cut.maxCut(new String[]{"04:22","09:00"},"05:52")));
System.out.println(f.format(cut.maxCut(new String[]{"09:00","09:22","09:22"},"10:11")));
System.out.println(f.format(cut.maxCut(new String[]{"09:00","04:00","04:02"},"04:09")));
System.out.println(f.format(cut.maxCut(new String[]{"04:40", "10:54", "12:30", "03:46", "04:48", "01:57", "04:47", "10:29", "10:39"},"05:21")));
}
void getSortedMin(String[] a, int[] s){
int i=0;
for(String m: a){
s[i++] = getMin(m);
}
Arrays.sort(s,0,s.length-1);
}
int getMin(String a){
int h,m;
String[] b = a.split(":",0);
h = Integer.parseInt(b[0]);
m = Integer.parseInt(b[1]);
if(h<9) h=h+12;
return (h-9)*60+m;
}
double maxCut(String[] enter, String lastExit){
int lastExitMin = getMin(lastExit);
int[] enterMin = new int[enter.length+1];
getSortedMin(enter,enterMin);
enterMin[enter.length] = lastExitMin;
double low,high;
high=0;
low=1<<30;
for(int i=0;i<enterMin.length-1;i++){
int t = enterMin[i+1]-enterMin[i];
if(t<low) low=t;
if(high<t) high=t;
}
while(low<high){
System.out.printf("%f,%f -> ",low,high);
double mid=low+(high-low)/2;
double t=0.0;
for(int m=0;m<enterMin.length-1;m++){
if((double)enterMin[m]<t){
t=t+mid;
}else{
t=(double)enterMin[m]+mid;
}
}
System.out.printf("%f\n",t);
if((double)lastExitMin<t) high=mid;
else low=mid+0.0000000001;
}
if(low<5.0) low=-1.0;
return low;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment