Homework 6: Searching
- State for each question, whether the statements are True or False, and the reason why.
a. Linear searching does not need to usean ordered list, but abinary search does.
b. The maximum number of values examined in a binary search of 40.000 items is the same asthat for 60,000 items.
对于40,000个项目，最大的查找次数是 log2(40000)。而对于60,000个项目，最大的查找次数是 log2(60000)。这两个值是不同的，所以对40,000和60,000个项目的二分搜索所需的最大查找次数并不相同。
c. Of the two searchc methods, linear and binary, a binary search is the fastest way to search a list of values.
d. Another name for a inear search is a sequential search
- Suppose you have a list of names:
Andrew, Bob, Cathy, Debra, Kasim, Maisie, Noah, Paul, Sue, Tim, Verity
In a binary search of the list to find the name Kasim, which names would be examined? 
def binary_search(names, target): left = 0 right = len(names) - 1 examined_names =  while left <= right: mid = (left + right) // 2 mid_name = names[mid] examined_names.append(mid_name) if mid_name == target: return examined_names elif mid_name < target: left = mid + 1 else: right = mid - 1 return None names = ["Andrew", "Bob", "Cathy", "Debra", "Kasim", "Maisie", "Noah", "Paul", "Sue", "Tim", "Verity"] target_name = "Kasim" examined = binary_search(names, target_name) print(examined)
3 Check the Access Records (40 Points)
With the city’s streets now considerably less congested, there’s a sense of relief in the air. However, the calm is about to be interrupted as the mayor of Liberty City prepares to lead a delegation on a visit to the Los Santos area. Their accommodations? The prestigious Garden Bank Hotel.
To ensure their safety and maintain the security of the event, the LSPD has reached out for as- sistance in designing a robust license plate registration system. This system will serve as the gate- keeper, allowing only authorized vehicles to enter the premises while keeping uninvolved members of the community at bay.
It’s essential to understand that some criminal syndicates have been known to engage in the illegal practice of duplicating license plates for nefarious purposes. As a result, each license plate must be registered only once, granting a vehicle one entry into the hotel grounds. The goal is clear: to guarantee a safe and secure environment for the mayor and the visiting delegation during their stay.
3.2 Input Format
The first line, an integer n, represents the license plate of the vehicle registered in the system’s records. The next n lines, each line is a string indicating one license plate.
Line n + 2, an integer m, represents the number of license plates captured by surveillance.
The next m lines, one string per line, represent the license plate captured by the monitor.
3.3 Output Format
For each recorded license plate, output one line, which means you always have to output m lines.
Output OK if the license plate is correct (in the registered database) and is the first occurrence, WRONG if the license plate is incorrect, REPEAT if the license plate is correct but not the first occurrence, and INVALID if the license plate does not meet the federal requirement.
3.4 Sample Input 1
1 AA−AAAAA−1 1 AA−AAAAA−1
3.5 Sample Output 1
3.6 Sample Input 2
3 AA−AAAAA−A NY−QU0TE−0 NY−LRU0M−0 4 NY−LRU0M−0 NY−LRU0M−0 AA−AAAAA−C A&*
3.7 Sample Output 2
OK REPEAT WRONG INVALID
3.8 Data Constraints
This problem might need you to consider 3 parts: whether a plate is valid, whether it has registered, and, whether it has repeated in the monitor. However, some test cases don’t require you to finish all these functions. We promise that:
For the 1st test case, i.e. 1.in,
- No invalid/repeated plates appeared;
- If you don’t assert whether a plate is valid or it has appeared more than once,you can still pass this case.
- No repeated plates appeared;
- If you don’t assert whether a plate has appeared more than once, you can still pass these two cases.
For all test cases, 1 ≤ n, m ≤ 10000.
One should note that all registered license plates are valid.
4 The Real GTA: Grand Theft Auto (Bonus, 20 Points)
I can’t take anymore! You know what I am saying? This is bllsht! Those cops should write those dumb codes themselves.
Franklin said to himself. He attempted to break out of the LSPD holding cell the old-fashioned way - knocking out the guards and grabbing the keys. Just walking to the door, he was knocked down and sent back to the dim cell by the backup police officers who heard the sirens.
He suddenly remembers Leslie, the cripple he used to work with. He finds a way to get in touch with Leslie. Leslie says he can get Franklin out, but he needs Franklin to do what he says.
One day, Franklin finds a note in his lunch bread. The note tells him to rob the escort vehicle and escape on his way back to his cell from the office. Sure enough, in the afternoon Franklin got into the escort vehicle. On the way, the guard said he wanted a burger from McDonald’s, so he put a hook on Franklin’s head and cuffed his hands to the steering wheel.
To Franklin’s surprise, Leslie’s voice came over the radio. He told Franklin to drive the car right now.
I got mad respect for you man. But I can’t see anything, bro. I can’t even take off this dumb hood. Franklin said.
If you are still eager for freedom, do as I say! Stupid! Leslie roared.
Franklin has to drive to the safe house within the time limit. Since Franklin’s head is covered by a hood and his hands are tied up, all he can do is step on the gas, hit the brakes and change the direction. Not only that, he doesn’t know the location of the safe house so he has to follow Leslie’s directions. Luckily, the main roads in Los Santos were basically straight, so with Franklin’s excellent driving skills he could estimate the distance of a block.
Leslie knows the size of the map, which is rectangular in shape, Leslie also creates a simple coordinate system. The point at the bottom left corner is the origin point (0, 0). He also knows Franklin’s initial location and the location of the safe house. Hearing the siren, Leslie tells Franklin there must be some obstacle on the road, Franklin should avoid hitting the obstacle if he does not want to be arrested again.
The following definitions are given for clarity.
4.2.1 Direction and Speed:
Franklin has an excellent sense of direction and can sense whether he is facing east or south or west or north. Note that speed is a non-negative integer. Note that before receiving the first instruction, Franklin’s speed is always 0.
- Facing north: (in the absence of obstacles) the next time step Franklin’s vertical coordinate increases by the current speed.
- Facing south: (in the absence of obstacles) the next time step Franklin’s vertical coordinate decreases by the current speed.
- Facing east: (in the absence of obstacles) the next time step Franklin’s horizontal coordinate increases by the current speed.
- Facing west: (in the absence of obstacles) the next time step Franklin’s horizontal coordinate decreases by the current speed.
4.2.2 Time and Instructions:
for a time limit t, the process has t time steps. Franklin always receives t instructions. Some instructions may lead to Franklin’s attributes (direction and speed) change. Instructions contain:
North: May change the direction and the speed.
South: May change the direction and the speed.
East: May change the direction and the speed.
West: May change the direction and the speed.
Park: Keep the direction and reset the speed.
Keep: Keep the direction and the speed.
4.2.3 Rules for the Game:
- Rules for Franklin’s Actions:
- Speed Adjustment Rules
- When the command direction matches Franklin’s current direction, his speed increases by 1.
- When the command direction and Franklin’s current direction are at 180-degree angles from each other, his speed decreases by 1 and his direction stays still.
- Direction Adjustment Rule
- When the command direction and Franklin’s current direction are at 90-degree angles from each other, his speed remains the same, but his direction changes to the command direction.
- Zero Speed Rule
- If Franklin’s speed reaches zero, his direction always changes to the command direction, and his speed is set to 1.
- Speed Adjustment Rules
- Attribute Precedence
- Franklin’s attribute changes take precedence over coordinate changes. He first receives instruc- tions that may change his attributes (speed or direction), and then he moves according to the present direction and speed.
- Obstacles and Border Rules:
- When Franklin encounters police-imposed obstacles on the road, he cannot drive through them. These obstacles keep Franklin one block away from the obstacle and change his speed to 0.
- Franklin cannot pass the borders of the map. If he reaches or attempts to pass the borders, his speed will change to 0.
- End of Driving
- Franklin’sdriveendseitherafteraspecifiednumberoftimesteps(ttimesteps)orwhenhiscoordi- nate is the same as the coordinate of the safe house. In the latter case, the safe house’s coordinates may either match Franklin’s new coordinates after following the instructions or be situated on the path between Franklin’s old and new coordinates.
- If Franklin’s drive ends, he will disregard all subsequent instructions.
4.3 Input Format
The input contains 5 lines.
The first line contains three positive integers n, m and t representing the size of the mapping matrix and time limit, where n is the length in the horizontal direction and m is the length in the vertical direction. The integers are separated by one space. The origin point is (0, 0).
The second line is one coordinate of the form (x, y), which is the coordinate of the safe house.
The third line is one coordinate of the form (x, y), which is Franklin’s initial coordinate.
The fourth line is k coordinates of the form (x, y). These coordinates are the coordinates of the obstacle. If there is no obstacle, the input is (−1, −1).
The fifth line is a series of Franklin’s actions including t capital letters: N, E, S, W, P, and K for north, east, south, west, park and keep, respectively.
4.4 Output Format
The output contains only one integer, indicating the Manhattan Distance between Franklin’s final coordi- nates and the safe house.
4.5 Sample Input 1
3 1 8 (0,2) (0,0) (−1,−1) EEEEKKKK
4.6 Sample Output 1
4.7 Sample Input 2
3 3 4 (2,2) (0,0) (1,1) ENEN
4.8 Sample Output 2
4.9 Sample Input 3
3 3 10 (2,2) (0,0) (1,1) EKNKPKEEPP
4.10 Sample Output 3
4.11 Data Constraints
To solve this problem you have to consider a lot of constraints and read the problem thoroughly. However, it is promised that some test cases are easier to handle. The test cases are given as follows:
- The game map is a single row, i.e. the car can’t move vertically.
- You may simply ignore all the instructions asking you to move N/S.
- Note that the car can still face North or South. This may affect it’s speed.
- No obstacles are given;
- You can assume that the car won’t hit obstacles;
- But, be careful to handle it if the car hits the wall!
- They are corner cases;
- If you get the Wrong Answer on these two test cases, check your code carefully if it works correctly in special cases.
For all test cases, 1 ≤ n, m ≤ 64; 1 ≤ t ≤ 32; Let o be 12 (m + n), then 1 ≤ k ≤ o log o.
- MAKE SURE YOU UNDERSTAND EVERY SENTENCE ABOVE BEFORE YOU WRITE ANY CODE!
- PLEASE NOTE THAT THE ORIGIN POINT IS (0, 0).
- Note that there are some police-imposed obstacles on the road. When Franklin encounters these obstacles he cannot drive through them.
- Note that Franklin can not pass the borders of the map.
- You do NOT have to figure out why k is constrained as this.
AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh