There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.
You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets[i].
Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.
Return the time taken for the person at position k (0-indexed) to finish buying tickets.
Example 1:
Input: tickets = [2,3,2], k = 2 Output: 6 Explanation: - In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1]. - In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0]. The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.
Example 2:
Input: tickets = [5,1,1,1], k = 0 Output: 8 Explanation: - In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0]. - In the next 4 passes, only the person in position 0 is buying tickets. The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.
Constraints:
n == tickets.length1 <= n <= 1001 <= tickets[i] <= 1000 <= k < nprogram main
implicit none
integer :: n, k
integer, dimension(:), allocatable :: tickets
integer :: i, j
real :: start_time, end_time
! read input
read(*,*) n
allocate(tickets(n))
do i = 1, n
read(*,*) tickets(i)
end do
read(*,*) k
! solve problem
start_time = omp_get_wtime()
call solve(tickets, n, k)
end_time = omp_get_wtime()
! print output
write(*,*) "Time taken: ", end_time - start_time
contains
subroutine solve(tickets, n, k)
implicit none
integer, intent(in) :: n, k
integer, dimension(:), intent(inout) :: tickets
integer :: i, j
! loop through each person in the line
do i = 0, n - 1
! if this person has no more tickets left to buy, they leave the line
if (tickets(i) == 0) then
exit
end if
! this person buys one ticket
tickets(i) = tickets(i) - 1
! if this person has no more tickets left to buy, they leave the line
if (tickets(i) == 0) then
exit
end if
! this person goes back to the end of the line (which happens instantaneously)
! so they become the last person in the line
tickets(n - 1) = tickets(i)
tickets(i) = 0
end do
end subroutine solve
end program maintemp.f95:18:17:
18 | start_time = omp_get_wtime()
| 1
Error: Function ‘omp_get_wtime’ at (1) has no IMPLICIT type
temp.f95:20:15:
20 | end_time = omp_get_wtime()
| 1
Error: Function ‘omp_get_wtime’ at (1) has no IMPLICIT type
module TicketLine
implicit none
contains
function solve(tickets, k) result(time)
integer, intent(in) :: tickets(:), k
integer :: time, i, j
! Initialize the time taken by the person at position k
time = 0
! Loop through the tickets and update the time taken by the person at position k
do i = 1, size(tickets)
if (i == k) then
! The person at position k buys a ticket
time = time + 1
! If the person has no more tickets left to buy, they leave the line
if (tickets(k) == 0) then
exit
end if
! The person goes back to the end of the line (instantaneously)
j = size(tickets)
! The person buys more tickets until they have no more left to buy
do while (tickets(k) > 0)
time = time + 1
tickets(k) = tickets(k) - 1
end do
else
! The person at position k does not buy a ticket
time = time + 1
end if
end do
end function solve
end module TicketLine
program test
use TicketLine
implicit none
integer :: tickets(3) = [2, 3, 2]
integer :: k = 2
integer :: time
! Run the solve function with the given inputs and print the output
time = solve(tickets, k)
print *, "Time taken for person at position ", k, " to finish buying tickets: ", time
! Run the solve function with the given inputs and print the output
tickets = [5, 1, 1, 1]
k = 0
time = solve(tickets, k)
print *, "Time taken for person at position ", k, " to finish buying tickets: ", time
end program test
temp.f95:28:10:
28 | tickets(k) = tickets(k) - 1
| 1
Error: Dummy argument ‘tickets’ with INTENT(IN) in variable definition context (assignment) at (1)
temp.f95:39:7:
39 | use TicketLine
| 1
Fatal Error: Cannot open module file ‘ticketline.mod’ for reading at (1): No such file or directory
compilation terminated.
def time_to_buy_tickets(tickets, k):
time = 0
while tickets[k] > 0:
for i in range(len(tickets)):
if tickets[i] > 0:
tickets[i] -= 1
time += 1
if i == k and tickets[k] == 0:
break
return time
The algorithm starts with a variable time set to 0. It then enters into a loop that will continue until the person at position k has bought all their tickets (tickets[k] > 0).
Inside the loop, we iterate through each person in the queue. If the person has remaining tickets to buy, we decrement the number of tickets they need to buy (tickets[i]), increment the time variable, and check if the person is the one at position k and has finished buying all their tickets. If so, we break out of the inner loop.
After the person at position k has bought all their tickets, the algorithm will exit the outer loop and return the time variable.
int time_to_buy_tickets(vector<int>& tickets, int k) {
int time = 0;
while (tickets[k] > 0) {
for (int i = 0; i < tickets.size(); ++i) {
if (tickets[i] > 0) {
--tickets[i];
++time;
if (i == k && tickets[k] == 0) {
break;
}
}
}
}
return time;
}
The algorithm starts with a variable time set to 0. It then enters into a loop that will continue until the person at position k has bought all their tickets (tickets[k] > 0).
Inside the loop, we iterate through each person in the queue. If the person has remaining tickets to buy, we decrement the number of tickets they need to buy (tickets[i]), increment the time variable, and check if the person is the one at position k and has finished buying all their tickets. If so, we break out of the inner loop.
After the person at position k has bought all their tickets, the algorithm will exit the outer loop and return the time variable.