All Tracks Algorithms Searching Binary Search Problem

Student Arrangement
Tag(s):

Basic Programming, Easy, approved

Problem
Editorial
Analytics

There is a classroom which has $$M$$ rows of benches in it. Also, $$N$$ students will arrive one-by-one and take a seat.

Every student has a preferred row number(rows are numbered $$1$$ to $$M$$ and all rows have a maximum capacity $$K$$. Now, the students come one by one starting from $$1$$ to $$N$$ and follow these rules for seating arrangements:

  • Every student will sit in his/her preferred row(if the row is not full).
  • If the preferred row is fully occupied, the student will sit in the next vacant row. (Next row for N will be 1)
  • If all the seats are occupied, the student will not be able to sit anywhere.

Monk wants to know the total number of students who didn't get to sit in their preferred row. (This includes the students that did not get a seat at all)

Input

  • First line contains 3 integers $$N$$, $$M$$ and $$K$$. $$N$$ - Number of students and $$M$$ - Number of rows and $$K$$ - maximum capacity of a row.
  • Next line contains $$N$$ space seperated integers $$A_{i}$$. $$A_{i}$$ - preferred row of $$i^{th}$$ student.

Output

Output the total number of students who didn't get to sit in their preferred row.

Constraints

  • $$1 ≤N, M ≤ 10^{5} $$
  • $$1 ≤ K ≤ 500$$
  • $$1 ≤ A_{i} ≤ M$$
SAMPLE INPUT
5 2 2
1 1 2 1 1
SAMPLE OUTPUT
2
Explanation

Student 4 and student 5 did not get their preferred seats.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

BuyHatke

Challenge Name

Buyhatke Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications