Tasks Details
hard
1.
Refueling
Given the locations of cities and the amount of fuel at each of them, compute the maximum number of cities that can be visited.
Task Score
100%
Correctness
100%
Performance
100%
There are N cities arranged in a row (numbered from 0 to N−1). The K-th city is located at position X[K] and contains A[K] liters of fuel. Getting from city J to city K requires |X[J] − X[K]| liters of fuel.
Tom is planning a trip. He wants to visit as many cities as possible. Unfortunately, he is limited by the available fuel. To be precise, at the departure time from city J, leaving for city K, the tank should contain at least |X[J] − X[K]| liters of fuel. When Tom visits a city, he refuels his car with all the available fuel at this city. He can refuel at each city just once at most. The fuel tank has an infinite capacity.
Tom can arbitrarily choose the city from which to start his trip. Tom begins with an empty tank and immediately refuels his car at the starting city. He wants to know how many cities he can visit.
Write a function:
def solution(A, X)
that, given two arrays A, X consisting of N integers each, returns the maximum number of different cities that Tom can visit.
Examples:
1. Given A = [4, 1, 4, 3, 3], X = [8, 10, 11, 13, 100], the function should return 4. One of the possible trips is: 1 → 2 → 0 → 3.
- Tom starts his trip in city number 1 and refuels 1 liter of fuel.
- Then he drives to city number 2 (it costs |10 − 11| = 1 liter of fuel) and refuels 4 liters of fuel.
- Next he drives to city number 0 (it costs |11 − 8| = 3 liters of fuel) and refuels 4 liters of fuel.
- Finally he drives to city number 3 (it costs |8 − 13| = 5 liters of fuel) and refuels 3 liters of fuel.
- Tom has insufficient fuel to reach city number 4.
2. Given A = [0, 10, 0], X = [1, 2, 3], the function should return 3. Tom can start his trip in city number 1. Then he can visit city number 0 followed by city number 2 (or vice versa). It costs 3 liters of fuel in total.
3. Given A = [0, 1, 0, 1, 1, 1, 0], X = [1, 2, 3, 4, 5, 6, 7], the function should return 4. Tom can start his trip in city number 3. Then he visits cities 4, 5 and 6, respectively.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..700];
- each element of array A is an integer within the range [0..1,000,000];
- each element of array X is an integer within the range [1..1,000,000];
- X[K] < X[K + 1] for each K within the range [0..N−2].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 1 minutes
Notes
not defined yet
Code: 02:27:12 UTC,
java,
autosave
Code: 02:27:22 UTC,
py,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, X):
Max_Cities_Covered = 0
for Starting_City in range(len(A)):
#Get furthest possible uni-directional
Current_Fuel = A[Starting_City]
Furthest_City_Up = Starting_City
for Next_City_Up in range(Starting_City+1,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Furthest_City_Up = Next_City_Up-1
break #Travel in this direction is over
else:
Furthest_City_Up=Next_City_Up
Current_Fuel= Current_Fuel - (X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
Current_Fuel = A[Starting_City]
Furthest_City_Down = Starting_City
for Next_City_Down in reversed(range(0,Starting_City)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Furthest_City_Down = Next_City_Down+1
break #Travel in this direction is over
else:
Furthest_City_Down=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#print(Starting_City,Furthest_City_Up,Furthest_City_Down)
#Initially up
for Turn_Around_City_Up in range(Starting_City+1,Furthest_City_Up+1):
#State at turn-around
Current_Fuel = sum(A[Starting_City:(Turn_Around_City_Up+1)]) - (X[Turn_Around_City_Up] - X[Starting_City])
#Check how far we can get on other side
Lowest_City_Reached = Starting_City
if Starting_City>0: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Turn_Around_City_Up] - X[Starting_City-1] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - (X[Turn_Around_City_Up] - X[Starting_City-1]) + A[Starting_City-1]
Lowest_City_Reached = Starting_City-1
#Check how much further I can then still travel
for Next_City_Down in reversed(range(0,Starting_City-1)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Lowest_City_Reached = Next_City_Down+1
break #Travel in this direction is over
else:
Lowest_City_Reached=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#Record covered cities
Total_Cities_Covered = Turn_Around_City_Up - Lowest_City_Reached +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
#Initially down
if Max_Cities_Covered== len(A): #save us useless further investigation
break
for Turn_Around_City_Down in reversed(range(Furthest_City_Down,Starting_City)):
#State at turn-around
Current_Fuel = sum(A[Turn_Around_City_Down:(Starting_City+1)]) - (X[Starting_City] - X[Turn_Around_City_Down])
#Check how far we can get on other side
Highest_City_Reached = Starting_City
if Starting_City<len(A)-1: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Starting_City+1] - X[Turn_Around_City_Down] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - ( X[Starting_City+1] - X[Turn_Around_City_Down]) + A[Starting_City+1]
Highest_City_Reached = Starting_City+1
#Check how much further I can then still travel
for Next_City_Up in range( Starting_City+2,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Highest_City_Reached = Next_City_Up-1
break #Travel in this direction is over
else:
Highest_City_Reached=Next_City_Up
Current_Fuel= Current_Fuel - ( X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
#Record covered cities
Total_Cities_Covered = Highest_City_Reached - Turn_Around_City_Down +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
if Max_Cities_Covered== len(A): #save us useless further investigation
break
return Max_Cities_Covered
Code: 02:27:32 UTC,
py,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, X):
Max_Cities_Covered = 1
for Starting_City in range(len(A)):
#Get furthest possible uni-directional
Current_Fuel = A[Starting_City]
Furthest_City_Up = Starting_City
for Next_City_Up in range(Starting_City+1,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Furthest_City_Up = Next_City_Up-1
break #Travel in this direction is over
else:
Furthest_City_Up=Next_City_Up
Current_Fuel= Current_Fuel - (X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
Current_Fuel = A[Starting_City]
Furthest_City_Down = Starting_City
for Next_City_Down in reversed(range(0,Starting_City)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Furthest_City_Down = Next_City_Down+1
break #Travel in this direction is over
else:
Furthest_City_Down=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#print(Starting_City,Furthest_City_Up,Furthest_City_Down)
#Initially up
for Turn_Around_City_Up in range(Starting_City+1,Furthest_City_Up+1):
#State at turn-around
Current_Fuel = sum(A[Starting_City:(Turn_Around_City_Up+1)]) - (X[Turn_Around_City_Up] - X[Starting_City])
#Check how far we can get on other side
Lowest_City_Reached = Starting_City
if Starting_City>0: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Turn_Around_City_Up] - X[Starting_City-1] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - (X[Turn_Around_City_Up] - X[Starting_City-1]) + A[Starting_City-1]
Lowest_City_Reached = Starting_City-1
#Check how much further I can then still travel
for Next_City_Down in reversed(range(0,Starting_City-1)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Lowest_City_Reached = Next_City_Down+1
break #Travel in this direction is over
else:
Lowest_City_Reached=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#Record covered cities
Total_Cities_Covered = Turn_Around_City_Up - Lowest_City_Reached +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
#Initially down
if Max_Cities_Covered== len(A): #save us useless further investigation
break
for Turn_Around_City_Down in reversed(range(Furthest_City_Down,Starting_City)):
#State at turn-around
Current_Fuel = sum(A[Turn_Around_City_Down:(Starting_City+1)]) - (X[Starting_City] - X[Turn_Around_City_Down])
#Check how far we can get on other side
Highest_City_Reached = Starting_City
if Starting_City<len(A)-1: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Starting_City+1] - X[Turn_Around_City_Down] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - ( X[Starting_City+1] - X[Turn_Around_City_Down]) + A[Starting_City+1]
Highest_City_Reached = Starting_City+1
#Check how much further I can then still travel
for Next_City_Up in range( Starting_City+2,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Highest_City_Reached = Next_City_Up-1
break #Travel in this direction is over
else:
Highest_City_Reached=Next_City_Up
Current_Fuel= Current_Fuel - ( X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
#Record covered cities
Total_Cities_Covered = Highest_City_Reached - Turn_Around_City_Down +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
if Max_Cities_Covered== len(A): #save us useless further investigation
break
return Max_Cities_Covered
Code: 02:27:38 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, X):
Max_Cities_Covered = 1
for Starting_City in range(len(A)):
#Get furthest possible uni-directional
Current_Fuel = A[Starting_City]
Furthest_City_Up = Starting_City
for Next_City_Up in range(Starting_City+1,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Furthest_City_Up = Next_City_Up-1
break #Travel in this direction is over
else:
Furthest_City_Up=Next_City_Up
Current_Fuel= Current_Fuel - (X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
Current_Fuel = A[Starting_City]
Furthest_City_Down = Starting_City
for Next_City_Down in reversed(range(0,Starting_City)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Furthest_City_Down = Next_City_Down+1
break #Travel in this direction is over
else:
Furthest_City_Down=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#print(Starting_City,Furthest_City_Up,Furthest_City_Down)
#Initially up
for Turn_Around_City_Up in range(Starting_City+1,Furthest_City_Up+1):
#State at turn-around
Current_Fuel = sum(A[Starting_City:(Turn_Around_City_Up+1)]) - (X[Turn_Around_City_Up] - X[Starting_City])
#Check how far we can get on other side
Lowest_City_Reached = Starting_City
if Starting_City>0: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Turn_Around_City_Up] - X[Starting_City-1] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - (X[Turn_Around_City_Up] - X[Starting_City-1]) + A[Starting_City-1]
Lowest_City_Reached = Starting_City-1
#Check how much further I can then still travel
for Next_City_Down in reversed(range(0,Starting_City-1)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Lowest_City_Reached = Next_City_Down+1
break #Travel in this direction is over
else:
Lowest_City_Reached=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#Record covered cities
Total_Cities_Covered = Turn_Around_City_Up - Lowest_City_Reached +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
#Initially down
if Max_Cities_Covered== len(A): #save us useless further investigation
break
for Turn_Around_City_Down in reversed(range(Furthest_City_Down,Starting_City)):
#State at turn-around
Current_Fuel = sum(A[Turn_Around_City_Down:(Starting_City+1)]) - (X[Starting_City] - X[Turn_Around_City_Down])
#Check how far we can get on other side
Highest_City_Reached = Starting_City
if Starting_City<len(A)-1: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Starting_City+1] - X[Turn_Around_City_Down] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - ( X[Starting_City+1] - X[Turn_Around_City_Down]) + A[Starting_City+1]
Highest_City_Reached = Starting_City+1
#Check how much further I can then still travel
for Next_City_Up in range( Starting_City+2,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Highest_City_Reached = Next_City_Up-1
break #Travel in this direction is over
else:
Highest_City_Reached=Next_City_Up
Current_Fuel= Current_Fuel - ( X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
#Record covered cities
Total_Cities_Covered = Highest_City_Reached - Turn_Around_City_Down +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
if Max_Cities_Covered== len(A): #save us useless further investigation
break
return Max_Cities_Covered
Analysis
Code: 02:27:43 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, X):
Max_Cities_Covered = 1
for Starting_City in range(len(A)):
#Get furthest possible uni-directional
Current_Fuel = A[Starting_City]
Furthest_City_Up = Starting_City
for Next_City_Up in range(Starting_City+1,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Furthest_City_Up = Next_City_Up-1
break #Travel in this direction is over
else:
Furthest_City_Up=Next_City_Up
Current_Fuel= Current_Fuel - (X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
Current_Fuel = A[Starting_City]
Furthest_City_Down = Starting_City
for Next_City_Down in reversed(range(0,Starting_City)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Furthest_City_Down = Next_City_Down+1
break #Travel in this direction is over
else:
Furthest_City_Down=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#print(Starting_City,Furthest_City_Up,Furthest_City_Down)
#Initially up
for Turn_Around_City_Up in range(Starting_City+1,Furthest_City_Up+1):
#State at turn-around
Current_Fuel = sum(A[Starting_City:(Turn_Around_City_Up+1)]) - (X[Turn_Around_City_Up] - X[Starting_City])
#Check how far we can get on other side
Lowest_City_Reached = Starting_City
if Starting_City>0: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Turn_Around_City_Up] - X[Starting_City-1] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - (X[Turn_Around_City_Up] - X[Starting_City-1]) + A[Starting_City-1]
Lowest_City_Reached = Starting_City-1
#Check how much further I can then still travel
for Next_City_Down in reversed(range(0,Starting_City-1)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Lowest_City_Reached = Next_City_Down+1
break #Travel in this direction is over
else:
Lowest_City_Reached=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#Record covered cities
Total_Cities_Covered = Turn_Around_City_Up - Lowest_City_Reached +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
#Initially down
if Max_Cities_Covered== len(A): #save us useless further investigation
break
for Turn_Around_City_Down in reversed(range(Furthest_City_Down,Starting_City)):
#State at turn-around
Current_Fuel = sum(A[Turn_Around_City_Down:(Starting_City+1)]) - (X[Starting_City] - X[Turn_Around_City_Down])
#Check how far we can get on other side
Highest_City_Reached = Starting_City
if Starting_City<len(A)-1: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Starting_City+1] - X[Turn_Around_City_Down] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - ( X[Starting_City+1] - X[Turn_Around_City_Down]) + A[Starting_City+1]
Highest_City_Reached = Starting_City+1
#Check how much further I can then still travel
for Next_City_Up in range( Starting_City+2,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Highest_City_Reached = Next_City_Up-1
break #Travel in this direction is over
else:
Highest_City_Reached=Next_City_Up
Current_Fuel= Current_Fuel - ( X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
#Record covered cities
Total_Cities_Covered = Highest_City_Reached - Turn_Around_City_Down +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
if Max_Cities_Covered== len(A): #save us useless further investigation
break
return Max_Cities_Covered
Analysis
Code: 02:27:45 UTC,
py,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, X):
Max_Cities_Covered = 1
for Starting_City in range(len(A)):
#Get furthest possible uni-directional
Current_Fuel = A[Starting_City]
Furthest_City_Up = Starting_City
for Next_City_Up in range(Starting_City+1,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Furthest_City_Up = Next_City_Up-1
break #Travel in this direction is over
else:
Furthest_City_Up=Next_City_Up
Current_Fuel= Current_Fuel - (X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
Current_Fuel = A[Starting_City]
Furthest_City_Down = Starting_City
for Next_City_Down in reversed(range(0,Starting_City)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Furthest_City_Down = Next_City_Down+1
break #Travel in this direction is over
else:
Furthest_City_Down=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#print(Starting_City,Furthest_City_Up,Furthest_City_Down)
#Initially up
for Turn_Around_City_Up in range(Starting_City+1,Furthest_City_Up+1):
#State at turn-around
Current_Fuel = sum(A[Starting_City:(Turn_Around_City_Up+1)]) - (X[Turn_Around_City_Up] - X[Starting_City])
#Check how far we can get on other side
Lowest_City_Reached = Starting_City
if Starting_City>0: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Turn_Around_City_Up] - X[Starting_City-1] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - (X[Turn_Around_City_Up] - X[Starting_City-1]) + A[Starting_City-1]
Lowest_City_Reached = Starting_City-1
#Check how much further I can then still travel
for Next_City_Down in reversed(range(0,Starting_City-1)):
if X[Next_City_Down+1]-X[Next_City_Down] > Current_Fuel:
Lowest_City_Reached = Next_City_Down+1
break #Travel in this direction is over
else:
Lowest_City_Reached=Next_City_Down
Current_Fuel= Current_Fuel - ( X[Next_City_Down+1]-X[Next_City_Down] )+A[Next_City_Down]
#Record covered cities
Total_Cities_Covered = Turn_Around_City_Up - Lowest_City_Reached +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
#Initially down
if Max_Cities_Covered== len(A): #save us useless further investigation
break
for Turn_Around_City_Down in reversed(range(Furthest_City_Down,Starting_City)):
#State at turn-around
Current_Fuel = sum(A[Turn_Around_City_Down:(Starting_City+1)]) - (X[Starting_City] - X[Turn_Around_City_Down])
#Check how far we can get on other side
Highest_City_Reached = Starting_City
if Starting_City<len(A)-1: #Check that there were cities on the other side at all
#Can I at all get to other side
if X[Starting_City+1] - X[Turn_Around_City_Down] <= Current_Fuel: #Can traverse back
Current_Fuel = Current_Fuel - ( X[Starting_City+1] - X[Turn_Around_City_Down]) + A[Starting_City+1]
Highest_City_Reached = Starting_City+1
#Check how much further I can then still travel
for Next_City_Up in range( Starting_City+2,len(A)):
if X[Next_City_Up]-X[Next_City_Up-1] > Current_Fuel:
Highest_City_Reached = Next_City_Up-1
break #Travel in this direction is over
else:
Highest_City_Reached=Next_City_Up
Current_Fuel= Current_Fuel - ( X[Next_City_Up]-X[Next_City_Up-1] )+A[Next_City_Up]
#Record covered cities
Total_Cities_Covered = Highest_City_Reached - Turn_Around_City_Down +1
if Total_Cities_Covered>Max_Cities_Covered:
Max_Cities_Covered=Total_Cities_Covered
if Max_Cities_Covered==len(A): #save us useless further investigation
break
if Max_Cities_Covered== len(A): #save us useless further investigation
break
return Max_Cities_Covered
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N**2) or O(N**2*log(N))
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.040 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.040 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.040 s
OK
1.
0.040 s
OK
2.
0.040 s
OK
small_each_group_needs_change_direction
N <= 50, many groups of cities are unreachable to each other. There is only one group with optimal solution.
N <= 50, many groups of cities are unreachable to each other. There is only one group with optimal solution.
✔
OK
1.
0.040 s
OK
2.
0.040 s
OK
expand all
Performance tests
1.
0.040 s
OK
2.
0.044 s
OK
3.
0.044 s
OK
1.
0.040 s
OK
2.
0.044 s
OK
large_one_big
Maximal N, exactly one city has significantly more available fuel than other cities.
Maximal N, exactly one city has significantly more available fuel than other cities.
✔
OK
1.
0.072 s
OK
2.
0.044 s
OK
1.
0.044 s
OK
2.
0.044 s
OK
1.
0.044 s
OK
2.
0.052 s
OK
large_each_group_needs_change_direction
Maximal N, many groups of cities are unreachable to each other. There is only one group with optimal solution.
Maximal N, many groups of cities are unreachable to each other. There is only one group with optimal solution.
✔
OK
1.
0.040 s
OK
2.
0.040 s
OK