473,326 Members | 2,133 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

I want to solve the following problem

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.


Here is my code


Expand|Select|Wrap|Line Numbers
  1. for _ in range(int(input())):
  2.     n=int(input())
  3.     arr=list(map(int,input().split()))
  4.     (m,c)=(1,1)
  5.     for i in range(1,len(arr)):
  6.         if(arr[i]-arr[i-1]<=2):
  7.             c+=1
  8.     m=c        
  9.     print(m,c)    
  10.  
  11.  
May 8 '20 #1
3 2626
Rabbit
12,516 Expert Mod 8TB
And what issue are you having?
May 8 '20 #2
I want to now how to code the following problem
May 9 '20 #3
Rabbit
12,516 Expert Mod 8TB
Count and track all blocks of people within 2 distance of each other. Keep track of the size of those blocks. Three smallest and largest blocks are the answer.
May 9 '20 #4

Sign in to post your reply or Sign up for a free account.

Similar topics

1
by: BVM | last post by:
Hi, All: I have this error. It seems execution time is too long. Actually the execution time is about 30 seconds(I tested in Query analyzer). How do I solve this problem? ...
9
by: David. E. Goble | last post by:
Arrrh! some buttons work while others don't, but I can't see why. I have tried comparing the files that do work, with the ones that don't. But to no help. The funny thing is the parts that work...
9
by: Papiya | last post by:
The proble is how can i include any picture, let it be any bitmap file to my c program..... i want to display a bitmap file using C/C++ Hope somebody will help me Please reply if u know solution...
0
by: Mamatha | last post by:
Hi I have one VB.NET application and i declare a thread as a public variable in the form.I want to declare this same thread as a public variable according to my flexibility,so i have to declare...
16
by: Hooyoo | last post by:
Following are similar codes of my project: At first I define two classes in two files: //ClassA.h #pragma once #include "ClassB.h" class ClassA { public: ClassA(void){};
2
by: davidson1 | last post by:
Hai friends..for menu to use in my website..i found in one website....pl look below website.... http://www.dynamicdrive.com/dynamicindex1/omnislide/index.htm i downloaded 2 files.... ...
1
by: Ryan Liu | last post by:
Hi, I have a 100 clients/ one server application, use ugly one thread pre client approach. And both side user sync I/O. I frequently see the error on server side(client side code is same, but...
0
by: ppel123 | last post by:
Hi everyone, I am working on a project (just started) in PYTHON and I want to create a keylogger for 2 languages english and greek. For this I have created the below (it is under "construction")...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.