Block Town

From Progteam

Revision as of 22:17, 11 March 2008 by Mlc413 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by kerry.


FBlock Town
Problem Number 1736
Sorter: kerry
Source: CEOI 1999
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1736



Block Town is problem number 1736 on the Peking University ACM site.

Looks tough. Help appreciated.

n


Here's my solution so far, it gets wrong answer on PKU.


import java.util.*;

public class Main{
	
	public static Scanner in;
	
	public static void main(String[] args){
		in=new Scanner(System.in);
		
		doStuff();
	}
	
	public static void doStuff(){
		int K=in.nextInt();
		int L=in.nextInt();
		int side[] = new int[K];
		int front[] = new int[L];
		for(int i = 0; i < K; i++){
			side[i] = in.nextInt();
		}
		for(int j = 0; j < L; j++){
			front[j] = in.nextInt();
		}
		
		if( isLegal( K, L, side, front)){
			int x = getMax( K, L, side, front);
			int y = getMin( K,  L, side, front);
		
			System.out.println(y + " " + x);
		}
		else{
			System.out.println("No Solution.");
		}
	}
	
	public static boolean isLegal(int K, int L, int[] side, int[] front){
		Arrays.sort(side);
		Arrays.sort(front);
		
		if(side[0] == front[0] && side[K-1] == front[L-1]){
			return true;
		}
		else
			return false;
		
	}
		
		public static int getMax(int K, int L, int[] side, int[] front){
			int maxBlox = 0;
			
			for(int j = 0; j < L; j++){
				for(int m = 0; m < K; m++){
					maxBlox += Math.min(side[m], front[j]);
				}
			}
      return maxBlox;
			
		}
	
	public static int getMin(int K, int L, int[] side, int[] front){
		int minBlox = 0;
		
		for(int j = 0; j < K; j++){
			int r = side[j];
			for(int m = 0; m < L; m++){
				if(front[m] >= r){
					minBlox += r;
					side[j] = 0;
					front[m] = 0;
					m = L;
				}
			}
		}
		
		for(int p = 0; p < L; p++){
			if(front[p]  != 0){
				minBlox += front[p];
			}
		}
		
		for(int q = 0; q < K; q++){
				if(side[q]  != 0){
					minBlox += side[q];
				}
		}
		return minBlox;
	}
	
	
	
}


This works, and should be NlogN (limit is the quicksort, everything else is linear. Radix sort makes the whole thing linear).

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

int compare(const void * a, const void * b);

int main() {
long long int max=0, min=0, tot=0;
int i,j,cmp, *width, *height;
unsigned int w, h;


	scanf("%d %d", &w, &h);
	
	width=(int *)malloc(sizeof(int)*w);
	height=(int *)malloc(sizeof(int)*h);	


	for(i=0;i<w;i++) { 
		scanf("%d", &width[i]);
	}

	for(i=0;i<h;i++) { 
		scanf("%d", &height[i]);
	}
	qsort(width, w, sizeof(int), compare);    // Sort input into 2 lists.
	qsort(height, h, sizeof(int), compare);

	if(width[w-1]!=height[h-1]) {            // Largest values must match, or no solution. Smaller can hide in the shadow of larger for all 
		printf("No solution.\n");        // other cases.
		return 0;
	}

	i=j=0;
	while ((i<w) || (h<j)) {                               //Start at the beginning of both lists.
		if (!(cmp=compare(&width[i],&height[j]))) {    //If they're the same, advance in both lists and increment min.
			min+=width[i]; 
			max+=(width[i]*(h-j)+tot);             // tot holds the total of previous values on the left(as seen from the front).
			tot+=height[j];                        // Because of the sorting, this is the only value that can be on the left.
			j++;                                   
			i++;
			
		}
		else {
			if (cmp>0) {                          // If width[i] is greater, then add height[j] to both min and tot, but not max.
				min+=height[j];               // Max will pick up those values via tot when height[j]>=width[i] later.
				tot+=height[j];
				j++;
			}
			else {
				max+=(width[i]*(h-j)+tot);   // The multiplication is to take into account the spaces ahead that, due to the sort, 
				min+=width[i];               // can accommodate but not exceed width[i].
				i++;
			}
		}
			
	}
	while (i<w)                          // This bit is for tables with uneven sides to pick up the leftovers if there are 
		min+=width[i++];             // multiple copies of the max value.
	while (j<h)
		min+=height[j++];
	printf("%lld %lld\n", min, max);     // On PKU you have to change %lld to %I64d. I wish they made that more clear :( 
		
return 0;
}	



int compare(const void * a, const void * b) {  // The casting is needed for the qsort() library routine. LSD radix sort is a little faster, but I'm lazy.
	return(*(int *)a - *(int *)b);
}

Personal tools