Commits

littledot5566 committed dbae8ae

srm560 div2 lvl2 TomekPhone complete.

Comments (0)

Files changed (1)

src/srm560/TomekPhone.java

+package srm560;
+
+import java.util.Arrays;
+
+public class TomekPhone {
+	public int minKeystrokes(int[] frequencies, int[] keySizes) {
+		Arrays.sort(frequencies);
+		Arrays.sort(keySizes);
+
+		int[] used = new int[keySizes.length];
+		int f = frequencies.length - 1, k = 0, strokes = 0;
+
+		// fill the first row first
+		while (k < keySizes.length) {
+			if (used[k] < keySizes[k]) {
+				// with keys with highest frequency
+				used[k]++;
+				strokes += frequencies[f] * used[k];
+				f--;
+
+				// all keys have been assigned
+				if (f < 0)
+					break;
+			}
+
+			k++;
+			if (k == keySizes.length) {
+				// TomekPhone is full, yet keys still remain: no solution
+				if (used[k - 1] == keySizes[k - 1])
+					return -1;
+				k = 0;
+			}
+		}
+
+		return strokes;
+	}
+
+}