Задачи
May 8

Задача. Школьная столовая

В школьной столовой есть круглые и квадратные булочки (0 и 1 соответственно). Ученики стоят в очереди и у каждого ученика есть свои предпочтения по выбору булочки.

Количество булочек равно количеству учеников. Булочки уложены стопкой.

Если ученик в начале очереди предпочитает булочку сверху стопки, то он может взять ее и выйти из очереди. В противном случае он снова переходит в конец очереди. Это продолжается до тех пор, пока ни один из учеников очереди не сможет взять свою любимую булочку.

Входные данные:

  • массив students, где students[i] - это предпочтение iго студента в типе булочки (students[0] - 1й ученик в очереди).
  • массив buns, где buns[i] - тип булочки в стопке (buns[0] - это верхняя булочка в стопке).

Необходимо вернуть количество учеников, которые так и не смогут взять свою булочку из стопки.

Пример

students = [1,1,0,0]
buns     = [0,1,0,1]
Output: 0

Пояснение:

1. students = [1,1,0,0]
   buns     = [0,1,0,1]

2. students = [1,0,0,1]
   buns     = [0,1,0,1]

3. students = [0,0,1,1]
   buns     = [0,1,0,1]
ученик забирает булочку

4. students = [0,1,1]
   buns     = [1,0,1]

5. students = [1,1,0]
   buns     = [1,0,1]
ученик забирает булочку

6. students = [1,0]
   buns     = [0,1]

7. students = [0,1]
   buns     = [0,1]
последние 2 ученика забирают последние булочки

Разбор

Предоставим не самое оптимальное, но самое очевидное решение. Так как в задаче фигурируют 2 очереди, очередь учеников и очередь из булочек. Далее мы просто смоделируем сам процесс.

Создадим цикл по количеству учеников, в цикле проверим совпадение предпочтений, если нашли совпадение, то удаляем соотв.элементы из обоих очередей, в противном случае, обновляем очередь учеников и увеличиваем наш счетчик.

Реализация

Test

https://dotnetfiddle.net/YsTXXE