import java.util.Arrays;
import java.util.Random;

class LogisticsOptimizer {

    public static void main(String[] args) {
        // Randomly generated problem data
        String[] factories = {"Seattle", "Portland", "Denver"};
        String[] stores = {"Los_Angeles", "Phoenix", "Dallas", "Chicago"};
        
        Random rand = new Random();
        int[] production = {
            rand.nextInt(100) + 50,  // 50-150 units
            rand.nextInt(120) + 60,  // 60-180 units
            rand.nextInt(80) + 70    // 70-150 units
        };
        
        int[] requirements = {
            rand.nextInt(90) + 40,   // 40-130 units
            rand.nextInt(70) + 50,   // 50-120 units
            rand.nextInt(110) + 30,  // 30-140 units
            rand.nextInt(60) + 60    // 60-120 units
        };
        
        // Balance demand if needed
        int totalSupply = Arrays.stream(production).sum();
        int totalDemand = Arrays.stream(requirements).sum();
        if (totalSupply != totalDemand) {
            requirements[0] += totalSupply - totalDemand;
        }

        // Randomized cost matrix (per unit)
        int[][] shippingCosts = new int[factories.length][stores.length];
        for (int i = 0; i < factories.length; i++) {
            for (int j = 0; j < stores.length; j++) {
                shippingCosts[i][j] = rand.nextInt(500) + 200; // $200-$700
            }
        }

        // Solve using Northwest Corner Method
        int[][] allocations = solveNorthwestCorner(production, requirements);
        
        // Display results
        printSolution(factories, stores, production, requirements, 
                     shippingCosts, allocations);
    }

    private static int[][] solveNorthwestCorner(int[] supply, int[] demand) {
        int[][] solution = new int[supply.length][demand.length];
        int[] remainingSupply = Arrays.copyOf(supply, supply.length);
        int[] remainingDemand = Arrays.copyOf(demand, demand.length);
        
        int i = 0, j = 0;
        while (i < supply.length && j < demand.length) {
            int amount = Math.min(remainingSupply[i], remainingDemand[j]);
            solution[i][j] = amount;
            remainingSupply[i] -= amount;
            remainingDemand[j] -= amount;
            
            if (remainingSupply[i] == 0) i++;
            if (remainingDemand[j] == 0) j++;
        }
        return solution;
    }

    private static void printSolution(String[] sources, String[] destinations,
                                    int[] supply, int[] demand,
                                    int[][] costs, int[][] solution) {
        System.out.println("=== Logistics Optimization Report ===");
        System.out.println("\nSources:");
        for (int i = 0; i < sources.length; i++) {
            System.out.printf("- %-10s: %d units%n", sources[i], supply[i]);
        }
        
        System.out.println("\nDestinations:");
        for (int j = 0; j < destinations.length; j++) {
            System.out.printf("- %-10s: %d units%n", destinations[j], demand[j]);
        }
        
        System.out.println("\nOptimal Allocation Plan:");
        int totalCost = 0;
        for (int i = 0; i < solution.length; i++) {
            for (int j = 0; j < solution[0].length; j++) {
                if (solution[i][j] > 0) {
                    int cost = solution[i][j] * costs[i][j];
                    System.out.printf("%-10s → %-10s: %4d units x $%3d = $%6d%n",
                            sources[i], destinations[j],
                            solution[i][j], costs[i][j], cost);
                    totalCost += cost;
                }
            }
        }
        System.out.printf("%nTotal Transportation Cost: $%,d%n", totalCost);
    }
}