Diferență între revizuiri ale paginii „DSA Homework 5”
| (Nu s-au afișat 6 versiuni intermediare efectuate de același utilizator) | |||
| Linia 1: | Linia 1: | ||
= Data Centers = | = Data Centers = | ||
| − | Little John is all grown up now and working in a high tech data center. One day, as he got to work, he finds out that hackers attacked his network and managed to disable some of the servers. A disabled server can't route data in or out, so | + | Little John is all grown up now and working in a high tech data center. One day, as he got to work, he finds out that hackers attacked his network and managed to disable some of the servers. A disabled server can't route data in or out, so it behaves as all links to and from it are disabled. Some of the remaining servers are critical to data access within his company and he wants to know if there is still a route for the data between them. |
Help Little John write a program to find out if those servers are still linked. | Help Little John write a program to find out if those servers are still linked. | ||
| Linia 24: | Linia 24: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- bgcolor="#ddeeff" align="left" | |- bgcolor="#ddeeff" align="left" | ||
| − | |'''Input''' || '''Output''' | + | |'''Input''' || '''Output''' || '''Comments''' |
|- bgcolor="#ddffdd" align="left" | |- bgcolor="#ddffdd" align="left" | ||
| | | | ||
| Linia 42: | Linia 42: | ||
0 | 0 | ||
</pre> | </pre> | ||
| + | | | ||
| + | The data center has 5 nodes. There is only 1 failed node: node 2. The critical servers are 0 and 4 and since there is no route between them, the result is 0. | ||
| + | |- bgcolor="#ddffdd" align="left" | ||
| + | |<pre style="font-size:12px"> | ||
| + | 5 | ||
| + | 0 1 1 0 0 | ||
| + | 1 0 1 0 0 | ||
| + | 1 1 0 1 1 | ||
| + | 0 0 1 0 1 | ||
| + | 0 0 1 1 0 | ||
| + | 2 | ||
| + | 1 3 | ||
| + | 0 4 | ||
| + | </pre> | ||
| + | | | ||
| + | <pre style="font-size:12px"> | ||
| + | 1 | ||
| + | </pre> | ||
| + | | | ||
| + | The data center has 5 nodes. There are 2 failed nodes: nodes 1 and 3. The critical servers are 0 and 4 and since there is now a route between them, the result is 1. | ||
|} | |} | ||
Versiunea curentă din 26 aprilie 2014 09:13
Data Centers
Little John is all grown up now and working in a high tech data center. One day, as he got to work, he finds out that hackers attacked his network and managed to disable some of the servers. A disabled server can't route data in or out, so it behaves as all links to and from it are disabled. Some of the remaining servers are critical to data access within his company and he wants to know if there is still a route for the data between them.
Help Little John write a program to find out if those servers are still linked.
Requirement
Given a number of servers N and an adjacency matrix NxN specifying the links between those servers, a number K of failed servers, and pair of servers (i, j), specify if there is still a route between server i and server j.
Input Data
A file called data_center.in, containing the number of servers N on the first line and N x N subsequent values, defining the adjacency matrix, arranged in a square, on N lines, followed by the number K of failed servers, K values specifying the servers on the following line, and the pair (i, j) on the last line.
Output Data
A file called data_center.out, containing the value 0 if there is no route between the two specified servers and 1 if there is.
Restrictions
1 ≤ K ≤ N ≤ 1000
Examples
| Input | Output | Comments |
5 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 2 0 4 |
0 |
The data center has 5 nodes. There is only 1 failed node: node 2. The critical servers are 0 and 4 and since there is no route between them, the result is 0. |
5 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 2 1 3 0 4 |
1 |
The data center has 5 nodes. There are 2 failed nodes: nodes 1 and 3. The critical servers are 0 and 4 and since there is now a route between them, the result is 1. |
