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

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

Looks tough. Help appreciated.


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(;
	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);
			System.out.println("No Solution.");
	public static boolean isLegal(int K, int L, int[] side, int[] front){
		if(side[0] == front[0] && side[K-1] == front[L-1]){
			return true;
			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;

	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.
			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.
		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.
			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].
	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)
	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