Maximum Frogs Saved-CodePudding

There are N frogs, a snake, and a hole in a straight line. The snake is present at 0 and the hole is present at X. All the N frogs are present between the snake and the hole. The value of X and the positions of N frogs are passed as the input to the 13the program. Every second, a frog can move exactly 1 position to the right, but the snake always moves 1 position to the right after the frog's movement. If a frog reaches the hole, then it is safe from the snake. If the snake reaches any frog's position, then it eats all the frogs in that position. The program must print the maximum number of frogs that can be saved from the snake as the output. Note: The snake never enters into the hole.

This is my code:

n=int(input())
a=[int(i) for i in input().split()]
b=int(input())

ak=[''] *(b 1)
ak[0]='S'
ak[b]='H'

for i in range(len(a)):
    ak[a[i]] ='F'

for j in range(len(ak)):
    if ak[j]=='':
        ak[j]='*'

print(ak)

My output:

[S,*,*,*,FF,F,*,F,F,F,H]

But I need this Output

Input:

6
4 7 5 8 4 9
10

Output:

3

Explanation:

Here N=6, X=10, and the given 6 integers are 4 7 5 8 4 9. 
The maximum number of frogs that can be saved from the snake is 3.

One of the possible ways to save 3 frogs is given below.

At T=0, [S,*,*,*,FF,F,*,F,F,F,H]
At T=1, [*,S,*,*,FF,F,*,F,F,*,HF]
At T=2, [*,*,S,*,FF,F,*,F,*,F,HF]
At T=3, [*,*,*,S,FF,F,*,F,*,*,HFF]
At T=4, [*,*,*,*,S,F,*,*,F,*,HFF]
At T=5, [*,*,*,*,*,S,*,*,*,F,HFF]
At T=6, [*,*,*,*,*,*,S,*,*,*,HFFF]

S- Snake
H- Hole
F- Frog
*- Empty Space

I don't know how to iterate and replace that *, S, F. Please explain to me the logic behind this problem.

CodePudding user response：

First of all I sorted the list of frogs positions in a descending order, after that I iterate over the sorted list and check if the distance between the hole and the frog is smaller than the distance between the snake and the hole, if that's the case I add 1 to ans and add the distance between the frog and the hole to the snake value.

Code:

n=int(input())
a=[int(i) for i in input().split()]
x=int(input())

a.sort(reverse=True)

snake = 0
ans = 0

for frog in a:
    if x-frog < x-snake:
        ans  =1
        snake  = (x-frog)
        
print(ans)

Input:

6
4 7 5 8 4 9
10

Output:

3

Explanation:

sorted list  = [9,8,7,5,4,4]

for the first frog 10-9 < 10-0 so ans = 1 and snake = (10-9) = 1

for the second frog 10-8 < 10-1 so ans = 1 and snake = (10-8) = 3

for the third frog 10-7 < 10-3 so ans = 1 and snake = (10-7) = 6

Now you can see that the snake is already at position 6 and the frogs at position 4 and 5 didn't move so they will not be saved.

so finally ans = 3