game_changer007's blog

Div1-B
By game_changer007, 9 years ago, In English

how to solve this question.I tried to understand the russian version of editorial by googlle translator,but it wasnt clear to me

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Just solved it, basically some (n) animals will come and you need to attend them, once you attend one of them, they go to the back of the queue, finally you need to print the queue of animals you will have after attending k animals. Let's see an example test case is solved:

3 3 1 2 1

That means that you have 3 animals, lets call them 1,2,3 You will have 3 appointments available. Current queue: 1 2 3 (with 1 2 1 appointments respectively)

Appointment 1: First animal 1 is attended and since now it doesn't have any more appointments it doesn't go to the back of the queue. Current queue: 2 3 (with 2 1 appointments respectively)

Appointment 2: Then animal 2 is attended and it has still one more appointment to go, so it goes to the back of the queue. Current queue: 3 2 (with 1 1 appointments respectively)

Appointment 3: Animal 3 is attended and since it has no more appointments it won't go back to the queue. Current queue: 2 (with just 1 appointment left)

So you need to print 2 because you have animal number 2 with exactly one appointment left.

In case 2 you print -1 because you end all your appointments before reaching the k appointments you were supposed to have.

In case 3 you will atend the animals in the following order: 1 2 3 4 5 6 7 2 3 5 (Note that since animals 1,4 and 7 have just 1 appointment they wont go back to the queue, neither will 5, because it has fulfilled its 2 appointments) So that means that the queue you end up with is 6 2 3 (with 2 1 1 appointments respectively)

Hope that helps!!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now my solution :D

    So basically I did a sort of the animals (used a set of type animal, actually an unordered set of int will also work), and then took the one with the lowest appointments and checked if I could attend it ai times, I had several variables:

    1. rounds = how many times I have gone through the entire queue

    2. animalsLeft= how many animals I have left

    Check if I can attend the animal with lowest ai, ai-rounds times (that means if animalsLeft*(ai-rounds)<=k), if I could attend it then I update rounds and k (k-=animalsLeft*(ai-rounds)), then delete all animals which have ai or less and update animalsLeft for everyone I delete.

    Once I couldn't attend an animal ai-rounds times then I attend the whole queue as many times as I can floor(k/animalsLeft), then I go through the queue one last time to identify which animal would be the next one in the queue, and I simply print those animals who are still in the queue.

    Here is my solution 9957483

    Let me know what you think!

    → Reply