object FeedTheDogs {
  
  def feedTheDogs(food: List[Int], dogs: List[Int]): List[Int] = {
    val position: ArrayBuffer[Int] = ArrayBuffer()
    position.addAll(dogs)
    val foodArray: ArrayBuffer[Int] = ArrayBuffer()
    foodArray.addAll(food)
    var first: Boolean = true
    while (!checkEmpty(foodArray)) {
      for (i <- Range(0, position.length)) {
        val j = position(i)
        if (foodArray(j) > 0) foodArray(j) -= 1
        else {
          val move = moveDogs(foodArray, i, first, position)
          if (move != position(i)) {
            position(i) = move
            foodArray(move) -= 1
          }
        }
        first = false
      }
    }
    return position.toList
  }

  def closeDogs(position: ArrayBuffer[Int], dog: Int): Int = {
    var closestDog = Integer.MAX_VALUE
    var closest = Integer.MAX_VALUE
    position foreach { x =>
      val dif = Math.abs(x - dog)
      if (dif != 0 && dif < closest) {
        closest = dif
        closestDog = x
      } else if (dif != 0 && dif == closest) {
        return dog
      }
    }
    closestDog
  }

  def moveDogs(food: ArrayBuffer[Int], i: Int, first: Boolean, position: ArrayBuffer[Int]): Int = {
    var r = position(i)
    var l = position(i)

    while (r < food.length - 1 || l > 0) {
      if (r < food.length - 1) r += 1
      if (l > 0) l -= 1
      if (food(r) > 0 && food(l) == 0) return r
      if (food(r) == 0 && food(l) > 0) return l
      if (food(r) > 0 && food(l) > 0) {
        val closestDog = closeDogs(position, position(i))
        if (closestDog < position(i)) return r
        if (closestDog > position(i) || closestDog == Integer.MAX_VALUE) return l
        if (first) {
          for (j <- Range(0, i)) {
            if (position(j) > position(i)) return position(i)
          }
          return l
        }
        return position(i)
      }
    }
    position(i)
  }

  def checkEmpty(food: ArrayBuffer[Int]): Boolean = {
    food foreach (x => if (x != 0) return false)
    true
  }
  
}

def feedTheDogs(food, dogs):
    position = dogs
    first = True

    while not checkEmpty(food):
        for i in range(len(position)):
            j = position[i]
            if food[j] > 0:
                food[j] -= 1
            else:
                move = moveDog(food, i, first, position)
                if move != position[i]:
                    position[i] = move
                    food[move] -= 1
        first = False
    return position


def closeDog(position, dog):
    closestDog = 9999999999999
    closest = 9999999999999
    for i in position:
        dif = abs(i - dog)
        if dif != 0 and dif < closest:
            closest = dif
            closestDog = i
        elif dif != 0 and dif == closest:
            return dog
    return closestDog


def moveDog(food, i, first, position):
    r = position[i]
    l = position[i]

    while r < len(food) - 1 or l > 0:
        if r < len(food) - 1: r += 1
        if l > 0: l -= 1
        if food[r] > 0 and food[l] == 0: return r
        if food[r] == 0 and food[l] > 0: return l
        if food[r] > 0 and food[l] > 0:
            closestDog = closeDog(position, position[i])
            if closestDog < position[i]: return r
            if closestDog > position[i] or closestDog == 9999999999999: return l
            return position[i]
    return position[i]


def checkEmpty(food):
    for i in food:
        if i != 0: return False
    return True

def solution(food, dogs):
    position = dogs
    first = True

    while not checkEmpty(food):
        for i in range(len(position)):
            j = position[i]
            if food[j] > 0:
                food[j] -= 1
            else:
                move = moveDog(food, i, first, position)
                if move != position[i]:
                    position[i] = move
                    food[move] -= 1
        first = False
    return position


def closeDog(position, dog):
    closestDog = 9999999999999
    closest = 9999999999999
    for i in position:
        dif = abs(i - dog)
        if dif != 0 and dif < closest:
            closest = dif
            closestDog = i
        elif dif != 0 and dif == closest:
            return dog
    return closestDog


def moveDog(food, i, first, position):
    r = position[i]
    l = position[i]

    while r < len(food) - 1 or l > 0:
        if r < len(food) - 1: r += 1
        if l > 0: l -= 1
        if food[r] > 0 and food[l] == 0: return r
        if food[r] == 0 and food[l] > 0: return l
        if food[r] > 0 and food[l] > 0:
            closestDog = closeDog(position, position[i])
            if closestDog < position[i]: return r
            if closestDog > position[i] or closestDog == 9999999999999: return l
            return position[i]
    return position[i]


def checkEmpty(food):
    for i in food:
        if i != 0: return False
    return True

def solution(food: ArrayBuffer[Int], dogs: ArrayBuffer[Int]): ArrayBuffer[Int] = {
  val position: ArrayBuffer[Int] = dogs
  var first: Boolean = true

  while(!checkEmpty(food)) {
    for(i <- Range(0, position.length)) {
      val j = position(i)
      if(food(j) > 0) food(j) -= 1
      else {
        val move = moveDogs(food, i, first, position)
        if(move != position(i)) {
          position(i) = move
          food(move) -= 1
        }
      }
      first = false
    }
  }
  return dogs
}

def closeDogs(position: ArrayBuffer[Int], dog: Int): Int = {
  var closestDog = Integer.MAX_VALUE
  var closest = Integer.MAX_VALUE

  position foreach { x =>
    val dif = Math.abs(x - dog)
    if(dif != 0 && dif < closest) {
      closest = dif
      closestDog = x
    } else if (dif != 0 && dif == closest) {
      return dog
    }
  }
  closestDog
}

def moveDogs(food: ArrayBuffer[Int], i: Int, first: Boolean, position: ArrayBuffer[Int]): Int = {
  var r = position(i)
  var l = position(i)

  while ( r < food.length - 1 || l > 0) {
    if(r < food.length - 1) r += 1
    if(l > 0) l-= 1
    if(food(r) > 0 && food(l) == 0) return r
    if(food(r) == 0 && food(l) > 0) return l
    if(food(r) > 0 && food(l) > 0) {
      val closestDog = closeDogs(position, position(i))
      if(closestDog < position(i)) return r
      if(closestDog > position(i) || closestDog == Integer.MAX_VALUE) return l
      if(first) {
        for(j <- Range(0, i)) {
          if(position(j) > position(i)) return position(i)
        }
        return l
      }
      return position(i)
    }
  }
  position(i)
}

def checkEmpty(food: ArrayBuffer[Int]): Boolean = {
  food foreach( x => if(x != 0) return false)
  return true
}