public class TPZSGfp {

    // Fictitious play for two-person, zero-sum game
    // See p. 744 of Raghavan, T.E.S., Handbook of Game Theory 2, 1994, "Zero-Sum Two-Person Games".

    private static void test(String description, double[][] payoff, double epsilon, int iterations) {
        StdOut.println();
        StdOut.println(description);
        StdOut.println("------------------------------------");
        int m = payoff.length;
        int n = payoff[0].length;

        double[] x=new double[n];
        double[] y=new double[m];

        int[] colCount=new int[n];
        int[] rowCount=new int[m];

        int minCol,maxRow;
        double minVal,maxVal,work;

        double gameValue=999999999,oldGameValue;

        // Uses "alternating" vs. "simultaneous" updating.
        // See Berger, U., J. Economic Theory 135 (1), 2007, 572-578, "Brown's Original Fictitious Play".  berger.pdf
        for (int k=0; k<iterations; k++) {
            minVal=999999999;
            minCol=999999999;
            for (int j=0; j<n; j++) {
                work=0.0;
                for (int i=0; i<m; i++)
                    work+=rowCount[i]*payoff[i][j];
                if (work<minVal) {
                    minVal=work;
                    minCol=j;
                    }
                }
            colCount[minCol]++;

            maxVal=(-999999999);
            maxRow=999999999;
            for (int i=0; i<m; i++) {
                work=0.0;
                for (int j=0; j<n; j++)
                    work+=colCount[j]*payoff[i][j];
                if (work>maxVal) {
                    maxVal=work;
                    maxRow=i;
                    }
                }
            rowCount[maxRow]++;

            if (k%1000==999 || k==iterations-1) {
                oldGameValue=gameValue;
                for (int i=0; i<m; i++)
                    y[i]=Double.valueOf(rowCount[i])/(k+1);

                for (int i=0; i<n; i++)
                    x[i]=Double.valueOf(colCount[i])/(k+1);

                gameValue=0.0;
                for (int i=0; i<m; i++)
                    for (int j=0; j<n; j++)
                gameValue+=y[i]*x[j]*payoff[i][j];

//StdOut.println("oldGameValue "+oldGameValue+" gameValue "+gameValue);

                if (Math.abs(gameValue-oldGameValue)<epsilon || k==iterations-1) {
                    iterations=k+1;
                    break;
                    }
                }
            }

        StdOut.println("actual iterations = "+iterations);


        StdOut.print("y[] = [");
        for (int i = 0; i < m-1; i++)
            StdOut.printf("%10.6f, ", y[i]);
        StdOut.printf("%10.6f]\n", y[m-1]);

        StdOut.print("x[] = [");
        for (int j = 0; j < n-1; j++)
            StdOut.printf("%10.6f, ", x[j]);
        StdOut.printf("%10.6f]\n", x[n-1]);

        StdOut.println("game value =  " + gameValue);
        
    }

    public static void main(String[] args) {
        int m = StdIn.readInt();
        int n = StdIn.readInt();
        double epsilon = StdIn.readDouble();
        int iterations = StdIn.readInt();
        double[][] payoff = new double[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                payoff[i][j] = StdIn.readDouble();
        test("game " + m + "-by-" + n, payoff, epsilon, iterations);
    }

}