The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.
The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.
You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the ith sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.
Example 1:
Input: students = [1,1,0,0], sandwiches = [0,1,0,1] Output: 0 Explanation: - Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1]. - Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0]. - Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [0,1]. - Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1]. - Front student takes the top sandwich and leaves the line making students = [] and sandwiches = []. Hence all students are able to eat.
Example 2:
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] Output: 3
Constraints:
1 <= students.length, sandwiches.length <= 100students.length == sandwiches.lengthsandwiches[i] is 0 or 1.students[i] is 0 or 1.program main
implicit none
integer :: n_students, n_sandwiches
integer, dimension(:), allocatable :: students, sandwiches
integer :: i, j, k, l
! read input
read(*,*) n_students, n_sandwiches
allocate(students(n_students))
allocate(sandwiches(n_sandwiches))
do i = 1, n_students
read(*,*) students(i)
end do
do i = 1, n_sandwiches
read(*,*) sandwiches(i)
end do
! solve problem
do while (any(students /= 0))
if (students(1) == sandwiches(1)) then
! student at front of queue prefers top sandwich
students(1) = 0
sandwiches(1) = 0
else
! student at front of queue does not prefer top sandwich
! move them to the back of the queue
do i = 1, n_students - 1
students(i) = students(i + 1)
end do
students(n_students) = 0
end if
end do
! print output
write(*,*) "Number of students that are unable to eat: ", count(students /= 0)
end program mainAt line 9 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7c5afd764960 in ??? #1 0x7c5afd7654d9 in ??? #2 0x7c5afd9b917b in ??? #3 0x7c5afd9b2684 in ??? #4 0x7c5afd9b32aa in ??? #5 0x5c940e4992bc in MAIN__ #6 0x5c940e499913 in main
program main
implicit none
integer, parameter :: MAX_STUDENTS = 100
integer, parameter :: MAX_SANDWICHES = 100
integer :: students(MAX_STUDENTS)
integer :: sandwiches(MAX_SANDWICHES)
integer :: num_students, num_sandwiches
integer :: i, j
read (*,*) num_students, num_sandwiches
do i = 1, num_students
read (*,*) students(i)
end do
do i = 1, num_sandwiches
read (*,*) sandwiches(i)
end do
do i = 1, num_students
if (students(i) == sandwiches(1)) then
write (*,*) "Student ", i, " takes the top sandwich"
students(i) = 0
sandwiches(1) = 0
else
write (*,*) "Student ", i, " leaves the top sandwich"
students(i) = 0
end if
end do
do i = 1, num_sandwiches
if (sandwiches(i) == 1) then
write (*,*) "Sandwich ", i, " is taken"
else
write (*,*) "Sandwich ", i, " is left"
end if
end do
do i = 1, num_students
if (students(i) == 1) then
write (*,*) "Student ", i, " is unable to eat"
end if
end do
end program main
At line 12 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7f7c89905960 in ??? #1 0x7f7c899064d9 in ??? #2 0x7f7c89b5a17b in ??? #3 0x7f7c89b53684 in ??? #4 0x7f7c89b542aa in ??? #5 0x566e9f0f021a in MAIN__ #6 0x566e9f0f0803 in main
def min_time_to_remove_balloons(colors, neededTime):
n = len(colors)
INF = 10**9
dp = [[INF] * 26 for _ in range(n)]
for color in range(26):
if colors[0] != chr(ord('A') + color):
dp[0][color] = neededTime[0]
for i in range(1, n):
for color1 in range(26):
for color2 in range(26):
if color1 != color2 and colors[i] != chr(ord('A') + color1):
dp[i][color1] = min(dp[i][color1], dp[i-1][color2] + neededTime[i])
ans = INF
for color in range(26):
ans = min(ans, dp[n-1][color])
return ans
The algorithm uses dynamic programming. We maintain a 2D table dp[i][j] that represents the minimum time Bob needs to make the rope colorful up to (and including) the i-th balloon, with the assumption that the i-th balloon's color is changed to color j. Initially, we fill the table with a large value (here, 1e9).
We then loop through each balloon, and for each balloon, we loop through all pairs of colors (26^2 possibilities). For each pair of colors, if the colors are different and the i-th balloon is not of color1, we update dp[i][color1] by taking the minimum between its current value and dp[i - 1][color2] + the time needed to remove the i-th balloon.
After iterating over all balloons and color pairs, we search for the minimum value in the last row of the dp table, as this represents the minimum time needed to make the whole rope colorful.
The time complexity of this algorithm is O(n * 26^2), where n is the length of the string colors, since the algorithm needs to loop through each balloon and all possible color pairs. This complexity is acceptable for the problem's constraints.
#include <vector>
#include <string>
int min_time_to_remove_balloons(const std::string& colors, const std::vector<int>& neededTime) {
int n = colors.size();
int dp[n][26];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 26; j++) {
dp[i][j] = 1e9;
}
}
for (int color = 0; color < 26; color++) {
if (colors[0] != 'A' + color) dp[0][color] = neededTime[0];
}
for (int i = 1; i < n; i++) {
for (int color1 = 0; color1 < 26; color1++) {
for (int color2 = 0; color2 < 26; color2++) {
if (color1 != color2 && colors[i] != 'A' + color1) {
dp[i][color1] = std::min(dp[i][color1], dp[i-1][color2] + neededTime[i]);
}
}
}
}
int ans = 1e9;
for (int color = 0; color < 26; color++) {
ans = std::min(ans, dp[n-1][color]);
}
return ans;
}
The algorithm uses dynamic programming. We maintain a 2D table dp[i][j] that represents the minimum time Bob needs to make the rope colorful up to (and including) the i-th balloon, with the assumption that the i-th balloon's color is changed to color j. Initially, we fill the table with a large value (here, 1e9).
We then loop through each balloon, and for each balloon, we loop through all pairs of colors (26^2 possibilities). For each pair of colors, if the colors are different and the i-th balloon is not of color1, we update dp[i][color1] by taking the minimum between its current value and dp[i - 1][color2] + the time needed to remove the i-th balloon.
After iterating over all balloons and color pairs, we search for the minimum value in the last row of the dp table, as this represents the minimum time needed to make the whole rope colorful.
The time complexity of this algorithm is O(n * 26^2), where n is the length of the string colors, since the algorithm needs to loop through each balloon and all possible color pairs. This complexity is acceptable for the problem's constraints.