5 kyu

Knights

22 of 62Djacon

Description:

Knights

In the kingdom of Logres, knights gather around a round table. Each knight is proud of his victories, so he makes scratches on his armor according to the number of defeated opponents. The knight's rank is determined by the number of scratches. Knights are very proud and the one, whose rank is lower, must pay homage to the one, whose rank is higher. If suddenly there is a situation when knights with the same rank sit in a row, then they arrange a tournament between them, according to the results of which one winner is determined. He puts new scratches on his armor (if k knights participated in the tournament, the winner will put k-1 new scratch) and returns to his place at the table. The rest of the tournament participants go away to heal their wounds and bruised ego. If after that a similar situation arises again, a new tournament is held, and so on.

There were n knights gathered at the round table, and they prudently arranged so that the ranks of their neighbors were different. But a late Galahad spoiled everything. He sat down on a randomly chosen place, and the merry-go-round of tournaments started again.

The ranks of all n knights originally seated at the table are known. Also know the rank of Galahad and the seat he sat on. Write a program to determine the number of knights that will remain at the table after all the tournaments are over.

Input:

Three parameters will be given as input:

  • ranks - array with ranks of knights (except Galahad)
  • p - position in which Galahad sat
  • r - rank of Galahad

Examples:

knights([1,2,3,4,5], 0, 1) # 1
knights([1,3,5,7,9], 0, 1) # 5
knights([9,7,5,3,1], 0, 1) # 5
knights([6,4,2,1,2,4,8], 3, 1) # 2
knights([7,5,6,8,9,10,12,10,8], 2, 5) # 4
knights([1,2,3,4,5], 0, 1) // 1
knights([1,3,5,7,9], 0, 1) // 5
knights([9,7,5,3,1], 0, 1) // 5
knights([6,4,2,1,2,4,8], 3, 1) // 2
knights([7,5,6,8,9,10,12,10,8], 2, 5) // 4

Short Explanation:

  1. After Galahad sits at the table after the 2nd knight, the ranks of knights at the table will be [7 5 5 6 8 9 10 12 10 8].
  2. Two knights with rank 5 will hold a tournament, one of them will remain, whose rank will increase to 6 [7 6 6 8 9 10 12 10 8].
  3. Two knights of Rank 6 will again leave 1 with Rank 7 [7 7 8 9 10 12 10 8].
  4. After the next tournament we get [8 8 9 10 12 10 8].
  5. Keeping in mind that the table is round, we see 3 Knights of Rank 8 sitting in a row. One of them will remain with rank 10 [10 9 10 12 10].
  6. There will be one more tournament, after which the remaining 4 knights will not have neighbors with the same rank [11 9 10 12]

P.s. The number of ranks in an array can reach up to 300,000

Algorithms
Logic
Puzzles

More By Author:

Check out these other kata created by Djacon

Stats:

CreatedOct 19, 2021
PublishedOct 28, 2021
Warriors Trained474
Total Skips13
Total Code Submissions969
Total Times Completed62
JavaScript Completions22
Python Completions47
Total Stars26
% of votes with a positive feedback rating96% of 26
Total "Very Satisfied" Votes24
Total "Somewhat Satisfied" Votes2
Total "Not Satisfied" Votes0
Total Rank Assessments7
Average Assessed Rank
5 kyu
Highest Assessed Rank
5 kyu
Lowest Assessed Rank
6 kyu
Ad
Contributors
  • Djacon Avatar
  • Blind4Basics Avatar
Ad