# Block Town

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by kerry.

 Sorter: kerry CEOI 1999 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);
}

```