Tennis tournament algorithm
algorithm, java
Solution
Not sure if it works 100%, i would go like:
- Sort input
for each element going from right to left in array (bigger to smaller)
- based on value n of element at index i decrease n left elements by 1
- return fail if cant decrease because you reached end of list or value 0
return success.
This logic (if correct) can lead whit some modifications to O(N*log(N)) solution, but I currently think that that would be just too much for novice programmer.
EDIT:
This does not work correct on input 2 2 1 1
All steps are then (whitout sorting):
while any element in list L not 0:
- find largest element N in list L
- decrease N other values in list L by 1 if value >= 1 (do not decrease this largest element)
- return fail if failure at this step
- set this element N on 0
return OK
Problem
After a tennis tournament each player was asked how many matches he had. An athlete can't play more than one match with another athlete. As an input the only thing you have is the number of athletes and the matches each athlete had. As an output you will have 1 if the tournament was possible to be done according to the athletes answers or 0 if not. For example: ``` Input: 4 3 3 3 3 Output: 1 Input: 6 2 4 5 5 2 1 Output: 0 Input: 2 1 1 Output: 1 Input: 1 0 Output: 0 Input: 3 1 1 1 Output: 0 Input: 3 2 2 0 Output: 0 Input: 3 4 3 2 Output: 0 ``` the first number of the input is not part of the athletes answer it's the number of athletes that took part in the tournament for example in 6 2 4 5 5 2 1 we have 6 athletes that took part and their answers were 2 4 5 5 2 1. So far this is what we wrote but didn't work that great: ``` import java.util.Scanner; import java.util.Arrays; public class Tennis { public static void main(String[] args) { Scanner input = new Scanner(System.in); String N; int count; int sum = 0; int max; int activeAthletes; int flag; System.out.printf("Give: "); N = input.nextLine(); String[] arr = N.split(" "); int[] array = new int[arr.length]; for (count = 0; count < arr.length; count++) { array[count] = Integer.parseInt(arr[count]); //System.out.print(arr[count] + " "); } for (count = 1; count < arr.length; count++) { sum += array[count]; } //System.out.println("\n" + sum); activeAthletes = array[0]; for (count = 1; count < array.length; count++) { if (array[count] == 0) { activeAthletes--; } } max = array[1]; for (count = 2; count < array.length; count++) { if (array[count] > max) { max = array[count]; } } // System.out.println(max); if ((sum % 2 == 0) && (max < activeAthletes)) { flag = 1; } else{ flag = 0; } System.out.println(flag); } } ``` I do not want a straight solution just maybe some tips and hints because we really have no idea what else to do and I repeat even though I'll tag it as a homework (because I feel the moderators will close it again) it is not, it's just something my brother found and we are trying to solve. Well many of you have answered and I'm really grateful but as I have work tomorrow I need to go to sleep, so I'll probably read the rest of the answers tomorrow and see what works