Count the transmissions of Go-Back-N in this round-by-round model:
- Each round, the sender sends every packet in its window: packets
basetobase + w − 1(stopping at the last packet). - A packet in the lost list is lost the first time it is sent, and arrives every time after that.
- The receiver accepts packets in order. After the first lost packet of a round, it throws away the rest of that round.
- The next round starts at the first packet lost in this round, or just after the last packet sent if none was lost.
Input
A line with n and w (1 ≤ n ≤ 100, 1 ≤ w ≤ 20): the number of packets (numbered from 0) and the window. A second line with the lost packet numbers, or none.
Output
The total number of packets sent.
Examples
Example 1 · Input
8 4 2
Expected output
10
Example 2 · Input
5 1 none
Expected output
5
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep base, the first packet not yet delivered, and a set of packets still to be lost.
Hint 2
Each round, send every packet from base to base + w - 1 (but not past n - 1), and count them.
Hint 3
Remove every lost packet of the round from the set. The next round starts at the first lost one, or after the last one sent if none was lost.
Solution
Show one correct solution (try it yourself first)
n, w = map(int, input().split())
line = input().split()
lost = set() if line == ["none"] else set(map(int, line))
base = sent = 0
while base < n:
batch = list(range(base, min(base + w, n)))
sent += len(batch)
first = None
for p in batch:
if p in lost:
lost.discard(p)
if first is None:
first = p
base = batch[-1] + 1 if first is None else first
print(sent)