Проблема организации турнира

Дано положительное целое число N , представляющее количество игроков, играющих в игру. Игра ведется между двумя командами так, что каждая команда состоит как минимум из одного игрока, но общее количество игроков в игре должно быть N. Игра длится ровно 30 минут , задача состоит в том, чтобы проверить, будут ли все игроки играть в игру друг против друга или нет. Если в игру можно играть до T часов и разрешено играть в игру более 1 раза. Если найдено верно, выведите «Возможно» . В противном случае выведите «Невозможно» .

Примеры:

Input: N = 3, T = 1 
Output: Possible 
Explanation: 
In 1st half hours Players { p₁, p₂ } played the game against { p₃ }. 
In 2d half hours Players { p₂, P₃ } played the game against { p₁ } 
Since all players played the game against each other within T(=1) hours. Therefore, the required output is “Possible”.

Input: N = 4, T = 0.5 
Output: Not Possible 
Explanation: 
In 1st half hours Players { p₁, p₂ } played the game against { p₃, p₄ }. 
Since player p₁ did not play the game against p₂ within T(=0.5) hours. Therefore, the required output is “Not Possible”.

Подход: проблема может быть решена с помощью жадной техники. Ниже приведены наблюдения:

• In each game, if one of the two teams has only one player then the game must be played N – 1 times.
• In each game, If one of the team have N / 2 players and other team have (N + 1) / 2 then the game must be played (N + 1) / 2 times.

Выполните следующие шаги, чтобы решить проблему:

• Если общее время игры N-1 раз меньше или равно T , то выведите «Возможно» .
• Если общее время игры (N + 1) / 2 раза меньше или равно T , то выведите «Возможно» .
• В противном случае выведите «Невозможно» .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)