package template;

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

public class TestCase {

    private boolean isSolved;
    private Object solution;
    private Map<String, Integer> intProperties;
    private Map<String, ArrayList<Integer>> intArrayProperties;
    private Map<String, ArrayList<ArrayList<Integer>>> intArray2DProperties;
    private Map<String, Double> doubleProperties;
    private Map<String, ArrayList<Double>> doubleArrayProperties;
    private Map<String, ArrayList<ArrayList<Double>>> doubleArray2DProperties;
    private Map<String, String> stringProperties;
    private Map<String, ArrayList<String>> stringArrayProperties;
    private Map<String, ArrayList<ArrayList<String>>> stringArray2DProperties;
    private Map<String, Boolean> booleanProperties;
    private Map<String, ArrayList<Boolean>> booleanArrayProperties;
    private Map<String, ArrayList<ArrayList<Boolean>>> booleanArray2DProperties;
    private Map<String, Long> longProperties;
    private Map<String, ArrayList<Long>> longArrayProperties;
    private Map<String, ArrayList<ArrayList<Long>>> longArray2DProperties;
    private int ref;
    private double time;

    public TestCase() {
        initialise();
    }

    private void initialise() {
        isSolved = false;
        intProperties = new HashMap<>();
        intArrayProperties = new HashMap<>();
        intArray2DProperties = new HashMap<>();
        doubleProperties = new HashMap<>();
        doubleArrayProperties = new HashMap<>();
        doubleArray2DProperties = new HashMap<>();
        stringProperties = new HashMap<>();
        stringArrayProperties = new HashMap<>();
        stringArray2DProperties = new HashMap<>();
        booleanProperties = new HashMap<>();
        booleanArrayProperties = new HashMap<>();
        booleanArray2DProperties = new HashMap<>();
        longProperties = new HashMap<>();
        longArrayProperties = new HashMap<>();
        longArray2DProperties = new HashMap<>();
        ref = 0;
    }

    public void setSolution(Object o) {
        solution = o;
        isSolved = true;
    }
    
    public Object getSolution() {
        if (!isSolved) {
            Utils.die("getSolution on unsolved testcase");
        }

        return solution;
    }

    public void setRef(int i) {
        ref = i;
    }
    public int getRef() {
        return ref;
    }

    public void setTime(double d) {
        time = d;
    }
    public double getTime() {
        return time;
    }
    
    public void setInteger(String s, Integer i) {
        intProperties.put(s, i);
    }
    
    public Integer getInteger(String s) {
        return intProperties.get(s);
    }

    public void setIntegerList(String s, ArrayList<Integer> l) {
        intArrayProperties.put(s, l);
    }

    public void setIntegerMatrix(String s, ArrayList<ArrayList<Integer>> l) {
        intArray2DProperties.put(s, l);
    }

    public ArrayList<Integer> getIntegerList(String s) {
        return intArrayProperties.get(s);
    }

    public Integer getIntegerListItem(String s, int i) {
        return intArrayProperties.get(s).get(i);
    }

    public ArrayList<ArrayList<Integer>> getIntegerMatrix(String s) {
        return intArray2DProperties.get(s);
    }
    
    public ArrayList<Integer> getIntegerMatrixRow(String s, int row) {
        return intArray2DProperties.get(s).get(row);
    }
    
    public Integer getIntegerMatrixItem(String s, int row, int column) {
        return intArray2DProperties.get(s).get(row).get(column);
    }

    public ArrayList<Integer> getIntegerMatrixColumn(String s, int column) {
        ArrayList<Integer> out = new ArrayList();
        
        for(ArrayList<Integer> row : intArray2DProperties.get(s)) {
            out.add(row.get(column));
        }
        return out;
    }


    public void setDouble(String s, Double i) {
        doubleProperties.put(s, i);
    }
    
    public Double getDouble(String s) {
        return doubleProperties.get(s);
    }

    public void setDoubleList(String s, ArrayList<Double> l) {
        doubleArrayProperties.put(s, l);
    }

    public void setDoubleMatrix(String s, ArrayList<ArrayList<Double>> l) {
        doubleArray2DProperties.put(s, l);
    }

    public ArrayList<Double> getDoubleList(String s) {
        return doubleArrayProperties.get(s);
    }

    public Double getDoubleListItem(String s, int i) {
        return doubleArrayProperties.get(s).get(i);
    }

    public ArrayList<ArrayList<Double>> getDoubleMatrix(String s) {
        return doubleArray2DProperties.get(s);
    }
    
    public ArrayList<Double> getDoubleMatrixRow(String s, int row) {
        return doubleArray2DProperties.get(s).get(row);
    }
    
    public Double getDoubleMatrixItem(String s, int row, int column) {
        return doubleArray2DProperties.get(s).get(row).get(column);
    }

    public ArrayList<Double> getDoubleMatrixColumn(String s, int column) {
        ArrayList<Double> out = new ArrayList();
        
        for(ArrayList<Double> row : doubleArray2DProperties.get(s)) {
            out.add(row.get(column));
        }
        return out;
    }

    
    public void setString(String s, String t) {
        stringProperties.put(s, t);
    }
    
    public String getString(String s) {
        return stringProperties.get(s);
    }

    public void setStringList(String s, ArrayList<String> l) {
        stringArrayProperties.put(s, l);
    }

    public void setStringMatrix(String s, ArrayList<ArrayList<String>> l) {
        stringArray2DProperties.put(s, l);
    }

    public ArrayList<String> getStringList(String s) {
        return stringArrayProperties.get(s);
    }

    public String getStringListItem(String s, int i) {
        return stringArrayProperties.get(s).get(i);
    }

    public ArrayList<ArrayList<String>> getStringMatrix(String s) {
        return stringArray2DProperties.get(s);
    }
    
    public ArrayList<String> getStringMatrixRow(String s, int row) {
        return stringArray2DProperties.get(s).get(row);
    }
    
    public String getStringMatrixItem(String s, int row, int column) {
        return stringArray2DProperties.get(s).get(row).get(column);
    }

    public ArrayList<String> getStringMatrixColumn(String s, int column) {
        ArrayList<String> out = new ArrayList();
        
        for(ArrayList<String> row : stringArray2DProperties.get(s)) {
            out.add(row.get(column));
        }
        return out;
    }

    
    public void setBoolean(String s, Boolean b) {
        booleanProperties.put(s, b);
    }
    
    public Boolean getBoolean(String s) {
        return booleanProperties.get(s);
    }

    public void setBooleanList(String s, ArrayList<Boolean> l) {
        booleanArrayProperties.put(s, l);
    }

    public void setBooleanMatrix(String s, ArrayList<ArrayList<Boolean>> l) {
        booleanArray2DProperties.put(s, l);
    }

    public ArrayList<Boolean> getBooleanList(String s) {
        return booleanArrayProperties.get(s);
    }

    public Boolean getBooleanListItem(String s, int i) {
        return booleanArrayProperties.get(s).get(i);
    }

    public ArrayList<ArrayList<Boolean>> getBooleanMatrix(String s) {
        return booleanArray2DProperties.get(s);
    }
    
    public ArrayList<Boolean> getBooleanMatrixRow(String s, int row) {
        return booleanArray2DProperties.get(s).get(row);
    }
    
    public Boolean getBooleanMatrixItem(String s, int row, int column) {
        return booleanArray2DProperties.get(s).get(row).get(column);
    }

    public ArrayList<Boolean> getBooleanMatrixColumn(String s, int column) {
        ArrayList<Boolean> out = new ArrayList();
        
        for(ArrayList<Boolean> row : booleanArray2DProperties.get(s)) {
            out.add(row.get(column));
        }
        return out;
    }

    public void setLong(String s, Long b) {
        longProperties.put(s, b);
    }
    
    public Long getLong(String s) {
        return longProperties.get(s);
    }

    public void setLongList(String s, ArrayList<Long> l) {
        longArrayProperties.put(s, l);
    }

    public void setLongMatrix(String s, ArrayList<ArrayList<Long>> l) {
        longArray2DProperties.put(s, l);
    }

    public ArrayList<Long> getLongList(String s) {
        return longArrayProperties.get(s);
    }

    public Long getLongListItem(String s, int i) {
        return longArrayProperties.get(s).get(i);
    }

    public ArrayList<ArrayList<Long>> getLongMatrix(String s) {
        return longArray2DProperties.get(s);
    }
    
    public ArrayList<Long> getLongMatrixRow(String s, int row) {
        return longArray2DProperties.get(s).get(row);
    }
    
    public Long getLongMatrixItem(String s, int row, int column) {
        return longArray2DProperties.get(s).get(row).get(column);
    }

    public ArrayList<Long> getLongMatrixColumn(String s, int column) {
        ArrayList<Long> out = new ArrayList();
        
        for(ArrayList<Long> row : longArray2DProperties.get(s)) {
            out.add(row.get(column));
        }
        return out;
    }

    

    


}

package org.ivansopin.jam;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class DancingWithTheGooglers {
	final static String fileName = "DancingWithTheGooglers1";

	final static String inExtension = ".in";
	final static String outExtension = ".out";
	final static String source = fileName + inExtension;
	final static String destination = fileName + outExtension;

	static BufferedReader bufferedReader;
	static BufferedWriter bufferedWriter;
	static int counter;

	/* this is problem-specific */
	static int numOfCases;
	static int numOfPeople, tmpNumOfPeople;
	static int numOfSurp, tmpNumOfSurp;
	static int max, tmpMax;
	static int[] points, tmpPoints;

	public static void main(String[] args) throws NumberFormatException, IOException, InterruptedException {
		bufferedReader = new BufferedReader(new FileReader(new File(source)));
		bufferedWriter = new BufferedWriter(new FileWriter(new File(destination)));

		numOfCases = Integer.parseInt(bufferedReader.readLine());

		Reader reader = new Reader();
		reader.start();
		reader.join();

		for (int i = 0; i < numOfCases; i++) {
			copyData();

			reader = new Reader();
			reader.start();

			/********* this is where the real logic starts **********/
			
			Comparator<Score> comparator = new ScoreComparator();
			ArrayList<Score> scores = new ArrayList<Score>();
			int curNumOfSurp = 0;
			int curNumOfGood = 0;
			
			for (int j = 0; j < numOfPeople; j++) {
				 Score score = new Score(points[j], max);
				 scores.add(score);
				 //score.display();
				 if (score.surprising)
					 curNumOfSurp++;
				 if (score.elMax >= max)
					 curNumOfGood++;
			}
			
			System.out.println(curNumOfSurp + " surprises initially; " + numOfSurp + " expected");
			
			if (curNumOfSurp < numOfSurp) {
				Collections.sort(scores, comparator);
				
				int j = 0;
				
				while (curNumOfSurp < numOfSurp) {
					Score score = scores.get(j++);
					
					if (!score.surprising) {
						score.switchSurp();
						curNumOfSurp++;
					}
				}
				
			} else if (curNumOfSurp > numOfSurp) {
				Collections.sort(scores, comparator);
				
				int j = scores.size() - 1;
				
				while (curNumOfSurp > numOfSurp) {
					Score score = scores.get(j--);
					
					if (score.surprising) {
						boolean wasGoodScore = score.elMax >= max;
						if (score.switchSurp())
							curNumOfSurp--;
						boolean isGoodScore = score.elMax >= max;
						if (wasGoodScore && !isGoodScore)
							curNumOfGood--;
					}
				}
			}

			//for (int j = 0; j < numOfPeople; j++) {
			//	 scores.get(j).display();
			//}
			
			// at some point, the results should be printed:
			bufferedWriter.write("Case #" + (i + 1) + ": " + curNumOfGood + "\n");
			

			/********** this is where the real logic ends ***********/

			if (reader.isAlive()) {
				reader.join();
			}
		}

		bufferedWriter.close();
		bufferedReader.close();
	}

	static class ScoreComparator implements Comparator<Score>
	{
	    @Override
	    public int compare(Score x, Score y)
	    {
	        // Assume neither string is null. Real code should
	        // probably be more robust
	        if (x.total < y.total)
	        {
	            return -1;
	        }
	        if (x.total > y.total)
	        {
	            return 1;
	        }
	        return 0;
	    }
	}
	
	static class Score {
		int type;
		boolean surprising = false;
		int elMax;
		int total;
		
		Score (int total, int maxWanted) {
			this.total = total;
			int rem = total % 3;
			int maxElement;
			
			if (rem == 0) {
				if (total == 0) {
					maxElement = 0;
					type = 1;
				} else {
					maxElement = total / 3;
					
					if ((maxElement >= maxWanted) || (maxElement + 1 < maxWanted)) {
						elMax = maxElement;
						type = 1;
					} else {
						elMax = maxElement + 1;
						surprising = true;
						type = 5;
					}
				}
			} else if (rem == 1) {
				maxElement = total / 3 + 1;
				
				elMax = maxElement;
				type = 2;
			} else {
				maxElement = total / 3 + 1;
				
				if ((maxElement >= maxWanted) || (maxElement + 1 < maxWanted)) {
					elMax = maxElement;
					type = 3;
				} else {
					elMax = maxElement + 1;
					surprising = true;
					type = 4;
				}
			}
		}
	
		boolean switchSurp() {
			if (surprising) {
				if (type == 5) {
					type = 1;
					elMax -= 2;
				} else if (type == 6) {
					type = 2;
				} else {
					type = 3;
					elMax -= 1;
				}
				
				return true;
			} else {
				if (type == 1) {
					if (total != 0) {
						type = 5;
						elMax += 2;
						return true;
					}
					return false;
				} else if (type == 2) {
					type = 6;
					return true;
				} else {
					type = 4;
					elMax += 1;
					return true;
				}
			}
		}
	
		void display() {
			String triple = "\t[";
			
			if (type == 1) {
				triple += elMax + "," + elMax + "," + elMax; 
			} else if (type == 2) {
				triple += (elMax - 1) + "," + (elMax - 1) + "," + (elMax);
			} else if (type == 3) {
				triple += (elMax - 1) + "," + (elMax) + "," + (elMax);
			} else if (type == 4) {
				triple += (elMax - 2) + "," + (elMax - 2) + "," + (elMax);
			} else if (type == 5) {
				triple += (elMax - 2) + "," + (elMax - 1) + "," + (elMax);
			} else {
				triple += (elMax - 2) + "," + (elMax) + "," + (elMax);
			}
			
			System.out.println(triple + "] = " + total + " (" + surprising + ") (type " + type + ")");
		}
	}
	
	static void copyData() {
		/* this is problem-specific */
		numOfPeople = tmpNumOfPeople;
		numOfSurp = tmpNumOfSurp;
		max = tmpMax;
		points = tmpPoints;
	}

	static class Reader extends Thread {
		public Reader() {
		}

		@Override
		public void run() {
			int item;
			String line;
			StringTokenizer tokenizer;

			try {
				if (counter < numOfCases) {
					/* this is problem-specific */
					line = bufferedReader.readLine();
					tokenizer = new StringTokenizer(line);
					
					tmpNumOfPeople = Integer.parseInt(tokenizer.nextToken());
					tmpNumOfSurp = Integer.parseInt(tokenizer.nextToken());
					tmpMax = Integer.parseInt(tokenizer.nextToken());
					tmpPoints = new int[tmpNumOfPeople];

					for (int i = 0; i < tmpNumOfPeople; i++) {
						item = Integer.parseInt(tokenizer.nextToken());

						tmpPoints[i] = item;
					}

					counter++;
				}
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}
