Python Forum
I want to solve the following problem
Thread Rating:
  • 1 Vote(s) - 1 Average
  • 1
  • 2
  • 3
  • 4
  • 5
I want to solve the following problem
#1
Quote:There are N people on a street (numbered 1 through N). For simplicity, we'll view them as points on a line. For each valid i, the position of the i-th person is Xi.

It turns out that exactly one of these people is infected with the virus COVID-19, but we do not know which one. The virus will spread from an infected person to a non-infected person whenever the distance between them is at most 2. If we wait long enough, a specific set of people (depending on the person that was infected initially) will become infected; let's call the size of this set the final number of infected people.

Your task is to find the smallest and largest value of the final number of infected people, i.e. this number in the best and in the worst possible scenario.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-seperated integers X1,X2,…,XN.
Output
For each test case, print a single line containing two space-separated integers ― the minimum and maximum possible final number of infected people.

Constraints
1≤T≤2,000
2≤N≤8
0≤Xi≤10 for each valid i
X1<X2<…<XN
Subtasks
Subtask #1 (10 points): N≤3
Subtask #2 (90 points): original constraints

Example Input
3
2
3 6
3
1 3 5
5
1 2 5 6 7
Example Output
1 1
3 3
2 3
Explanation:
Example case 1: The distance between the two people is 3, so the virus cannot spread and at the end, there will always be only one infected person.

Example case 2: The distance between each two adjacent people is 2, so all of them will eventually get infected.

Example case 3:

In one of the best possible scenarios, the person at the position 1 is infected initially and the virus will also infect the person at the position 2.
In one of the worst possible scenarios, the person at the position 5 is infected initially and the virus will also infect the people at the positions 6 and 7.

for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    (m,c)=(1,1)
    for i in range(1,len(arr)):
        if(arr[i]-arr[i-1]<=2):
            c+=1
    m=c        
    print(m,c)    
        
        
Quote:this is the code i've written can anybody help in solving this problem
Reply
#2
Get the input first, then process. I would write a separate function for getting the input and processing the test cases. This makes it easy to dummy in data while testing the processing.
def input_testcases():
    """Input testcase data
    Input
    The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
    The first line of each test case contains a single integer N.
    The second line contains N space-seperated integers X1,X2,…,XN.
    """
    return [[3, 6], [1, 3, 5], [1, 2, 5, 6, 7]]  # For initial testing
    test_cases = []
    for _ in range(int(input())):
        n=int(input())
        test_cases.append(list(map(int,input().split())))
    return test_cases

def infection_range(test_case, min_space):
    """Assuming one random individual is infected, determine the
    minimum and maximum number of people to be infected given
    the spacing information in the test case and the infection
    envelope minspace.
    """
    return [1, 1] # Replace with real code

test_cases = input_testcases()
print(test_cases) # Only use when verifying input_testcases
for test_case in test_cases:
    print(*infection_range(test_case, 2))
The processing for each test case is to find the minimum infection group and the maximum infection group. I would start by finding the size of each infection group.
What is the logic for finding the size of an infection group?
Reply
#3
deanhystad -- This is a homework assignment.
please read following forum rule: https://python-forum.io/misc.php?action=help&hid=52
Reply
#4
I added that the program should be broken into two functions. That is all. Initial post already provided the code that reads in the input (input_testcases). Docstrings are copied from original post. No code was provided that shows how to find the infection numbers or how to return the minimum and maximum numbers.
Reply
#5
Ok
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Can someone help me solve this programming problem? SuchUmami 6 896 Nov-20-2023, 10:01 AM
Last Post: EdwardMatthew
  A simple problem, how best to solve it? SuchUmami 2 720 Sep-01-2023, 05:36 AM
Last Post: Pedroski55
  How to solve this simple problem? Check if cvs first element is the same in each row? thesquid 2 1,231 Jun-14-2022, 08:35 PM
Last Post: thesquid
  How do I solve the second problem? Cranberry 1 1,129 May-16-2022, 11:56 AM
Last Post: Larz60+
  Try to solve GTG multiplication table problem. Frankduc 6 2,007 Jan-18-2022, 08:26 PM
Last Post: Frankduc
  Sudoku Solver, please help to solve a problem. AdithyaR 5 2,111 Oct-28-2021, 03:15 PM
Last Post: deanhystad
  General list size question to solve problem Milfredo 3 2,357 Sep-27-2020, 08:42 AM
Last Post: Milfredo
  Solve Pynput Problem when changing language? ppel123 0 2,277 Feb-19-2020, 03:38 PM
Last Post: ppel123
  Hakkerank problem I can't solve ayo 1 2,096 Aug-29-2019, 11:18 AM
Last Post: ThomasL
  Formulae to solve problem BigDisAok 3 2,993 Jun-26-2018, 03:07 PM
Last Post: nilamo

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020