$30.00

Category: COMP 281

Description

5/5 - (4 votes)

Problem 1046

Title: Sum of Adjacent Numbers

Description

In the 3×3 grid below, the greatest sum of two adjacent numbers in any direction (up, down, left, right, or

diagonally) is 22+23=45.

21 22 23

20 10 11

17 16 15

Input n and m. 1<=n<=100. 1<=m<=n. Then input a n x n grid. All integers in the grid are from 0 to 1000.

Output the greatest sum of m adjacent numbers in any direction (along straight line only).

You are required to use malloc to dynamically allocate just enough space for storing the grid.

Input

n, m, and then followed by a n x n grid

Output

The greatest sum of m adjacent numbers in any direction

Sample Input

3 2

21 22 23

20 00 11

17 06 15

Sample Output

45

Problem 1048

Title: Sort and Search for Dates

Description

Input n (1<=n<=10000) and then followed by n lines. Each line corresponds to a valid date, consisting of

one string (“January”, “February”, …, or “December”), one integer between 1 and 31, and one two digit

integer representing the year (from 90 to 99, and then from 00 to 12). You do not have to worry about date

validation. All dates in the input are valid dates.

Please use structures to store the dates. Please use malloc to dynamically allocate just enough space for n

structures. You are asked to sort the dates chronologically using the built-in qsort function. Please output the

sorted list, one date per line, from most recent to oldest date. Please also use the built-in bsearch function to

allow for a user query to check whether a specific date is in the list, and output either “Yes” or “No”.

Input

n and then followed by n dates.

Output

sorted list of dates, and whether a date input by the user (e.g. January 1 00) is in the list

Sample Input

10

January 1 01

January 1 00

February 28 99

July 17 12

September 10 12

July 1 00

June 30 90

August 25 06

May 27 08

October 1 03

January 1 00

Sample Output

September 10 12

July 17 12

May 27 08

August 25 06

October 1 03

January 1 01

July 1 00

January 1 00

February 28 99

June 30 90

Yes

Problem 1049

Title: Priority Queue

Description

A priority queue is an abstract data type, which is like a regular queue, but additionally, each element is

associated with a “priority value”. In this problem, the queue elements are integers from 10000 to 19999, the

priority values are integers from 1 to 10 (10 corresponds to the highest priority).

The input consists of a list of operations, one operation per line. A sample input looks like the following:

Insert 10000 2

Insert 10000 2

Insert 10000 3

Insert 19444 9

Pop

Insert 10331 3

Pop

Pop

Pop

Pop

Pop

The operations are defined as follows:

• Insert x y: Add element x (10000<=x<=19999) to the queue with an associated priority value y

(1<=y<=10). The queue allows duplicate elements. In the above example, we inserted 10000 three

times. After these three insertions, there are two elements of value 10000 and priority 2 in the queue,

and there is one element of value 10000 and priority 3 in the queue. You don’t need to check the

validity of the input. That is, if an input line says “Insert x y”, then x is guaranteed to be between

10000 and 19999, and y is guaranteed to be between 1 and 10.

• Pop: Identify the element with the highest priority from the queue, output the element, and remove it

from the queue. If the queue is empty, then output -1 (the queue remains empty). If there are multiple

queue elements sharing the same highest priority value, then we remove and output the element that

has the highest priority value and joined the queue the earliest.

For the above sample input, the sample output should be:

19444

10000

10331

10000

10000

-1

Explanation of the example: At the moment of the first “Pop”, 19444 has the highest priority value 9. At the

moment of the second “Pop”, both 10331 and 10000 share the highest priority value 3. We remove and

output 10000 because it joined the queue earlier. At the moment of the third “Pop”, 10331 has the highest

priority value 3. Finally, at the moment of the sixth “Pop”, the queue is empty.

A priority queue can be implemented using a variety of methods. Your mark for this problem depends on the

efficiency of your implementation.

Time efficiency: The time efficiency of your implementation is judged based on the speed of insert and pop

when there are a huge number of elements in the queue.

Memory efficiency: The memory consumption of your queue should be dynamically adjusted based on the

number of elements in it.

Input

A list of operations, one per line

Output

Corresponding output

Sample Input

Insert 10000 2

Insert 10000 2

Insert 10000 3

Insert 19444 9

Pop

Insert 10331 3

Pop

Pop

Pop

Pop

Pop

Sample Output

19444

10000

10331

10000

10000

-1

Problem 1050

Title: Flight Travel Planner

Description

You are working for a travel agency and are asked to write a computer program that can provide travel

advice between cities based on a given map. The first line of the input of the program contains one integer n.

n (2<=n<=10000) is the number of cities on the map. The second line of the input also contains an integer,

m, (2<=m<=10000), which indicates the number of connections that will follow in the input below. Then,

starting from the third line of the input, each line contains two integers from 1 to n, i.e. the connections

between the cities. If a line says “a b”, then it means that there is direct flight between city a and city b.

There will be m of such connections. The last line also contains a pair of cities, say “c d”, which will

represent a query: “is there a connecting flight between c and d?”

Here is one sample input:

6

7

6 4

3 4

5 4

3 2

5 2

5 1

2 1

1 6

For this flight network, there exists at least one route between every pair of cities. For example, between city

5 and 6, there exists a route with 1 stop at city 4.

Given the input and the query, answer whether there is a route between cities c and d (note that this

connection can be indirect). The output should be “Yes” or “No”.

Let x be the total number of lines of the input. We know for sure that x is much smaller than n square. Your

implementation should take this into consideration (for the purpose of saving memory).

For example, let us consider the case with n=10000 and x=10000 (so x is much less than n square). One easy

way to represent a graph in memory is to use a n by n matrix. If the element in the i-th row and the j-th

column equals 1, then that means node i and j are directly connected (0 means not directly connected). The

memory consumption of the matrix representation is at least n square over 2 bits (each element only needs 1

bit; also, we only need to store half of the matrix due to symmetry). When n=10000, n square over 2 bits is

just too much. You should find better ways to represent graphs in memory.

Input

Flight network

Output

Yes or No

Sample Input

6

7

6 4

3 4

5 4

3 2

5 2

5 1

2 1

1 6

Sample Output

Yes

Sample Input 2

5

3

4 3

3 2

5 1

1 4

Sample Output 2

No

WhatsApp us