CEOI1994-2003资源-CSDN文库

共73个文件

htm：50个

gif：19个

png：1个

需积分: 10 131 浏览量 2009-02-08 01:46:14 上传评论 3 收藏 208KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

CEOI19942003.rar （73个子文件）

ceoi94_03

ceoi005.htm 1KB

ceoi019.htm 4KB

ceoi019.gif 2KB

ceoi035.htm 2KB

ceoi020.htm 1KB

ceoi045.htm 6KB

ceoi047b.gif 3KB

ceoi046.htm 3KB

ceoi043.gif 2KB

ceoi029.htm 2KB

ceoi016.htm 2KB

ceoi027.htm 3KB

ceoi008.htm 2KB

ceoi030a.gif 6KB

ceoi037.jpg 13KB

ceoi040b.gif 4KB

ceoi007.htm 2KB

ceoi011.htm 2KB

ceoi025.htm 1KB

ceoi033.png 1KB

ceoi015.htm 2KB

ceoi038.gif 2KB

ceoi043.htm 3KB

ceoi032.htm 2KB

ceoi012.htm 2KB

ceoi023.htm 3KB

ceoi044.gif 2KB

ceoi024.htm 3KB

ceoi004.htm 809B

ceoi033.htm 2KB

ceoi047.htm 5KB

ceoi040.htm 2KB

ceoi002.htm 2KB

ceoi009.htm 957B

ceoi018b.gif 3KB

ceoi001.gif 1KB

ceoi036.htm 2KB

ceoi024.gif 1KB

ceoi030.htm 3KB

ceoi037.htm 3KB

ceoi031.htm 2KB

ceoi042.htm 3KB

ceoi021.htm 1KB

ceoi028.htm 2KB

ceoi049.htm 6KB

ceoi040a.gif 4KB

ceoi047a.gif 1KB

ceoi017.htm 975B

ceoi048.htm 4KB

ceoi022.htm 2KB

ceoi026.htm 3KB

index.htm 2KB

ceoi003.htm 2KB

ceoi045a.gif 2KB

ceoi039.htm 2KB

ceoi018.htm 2KB

ceoi041.gif 1KB

ceoi006.htm 2KB

ceoi045b.gif 2KB

ceoi012.gif 4KB

ceoi034.htm 3KB

ceoi041.htm 3KB

ceoi013.htm 3KB

ceoi014.htm 2KB

ceoi030b.gif 6KB

ceoi038.htm 3KB

ceoi03.rar 50KB

ceoi010.htm 1KB

ceoi018a.gif 3KB

ceoi001.htm 1KB

ceoi022.gif 1KB

ceoi02.zip 66KB

ceoi044.htm 5KB

<html> <head> <title>Printed Circuit</title> </head> <body> <center> <h1>CEOI 2001 Day 1 Problem 2</h1> <h1>Printed Circuit</h1> </center> A printed circuit is a board that consists of nodes and wire segments connecting pairs of nodes. We consider a special kind of printed circuits where the nodes are arranged in a rectangular grid, and the wire segments connect (vertically or horizontally) adjacent nodes only. A printed circuit is called connected if any two distinct nodes are connected with a series of wire segments. Given is a printed circuit where wire segments already connect several adjacent nodes. We have to add new wire segments in order to make the printed circuit connected. The cost of a new wire segment is 1 if it is vertical and 2 if it is horizontal in the grid. <img SRC="ceoi045a.gif" WIDTH="171" HEIGHT="132"> <img SRC="ceoi045b.gif" WIDTH="173" HEIGHT="133"> <blockquote> <blockquote> Figure 1      Figure 2   </blockquote> </blockquote> You are to write a program that computes a least cost completion of a given circuit. Your program should solve the following three subtasks: <ol TYPE="A"> <li>Determine the number of new wire segments of a least cost completion.</li> <li>Compute the value of the least cost.</li> <li>Produce a list of wire segments of a least cost completion.</li> </ol> <h2>Input</h2> The first line of the file circuit.in contains two integers, N and M. N (1<=N<= 100) is the number of rows and M (1<= M<= 100) is the number of columns in the grid. The nodes of the circuit are identified by their coordinates; the node in the upper left corner is at (1,1), and the node in the lower right corner is at (N, M). Each of the next N lines contains M integers. The number in row i and column j of these lines describes the wire segments between the pair of nodes (i, j) and (i+1, j), and also between the pair of nodes (i, j) and (i, j+1) in the following way. <ul> <li>0 means that neither the pair of nodes (i, j) and (i+1, j) nor the pair of nodes (i, j) and (i, j+1) are connected by wire segments.</li> </ul> <ul> <li>1 means that only the pair of nodes (i, j) and (i+1, j) is connected by a wire segment.</li> </ul> <ul> <li>2 means that only the pair of nodes (i, j) and (i, j+1) is connected by a wire segment.</li> </ul> <ul> <li>3 means that both the pair of nodes (i, j) and (i+1, j), and the pair of nodes (i, j) and (i, j+1) are connected by wire segments.</li> </ul> Note that not all 4 values are valid at certain positions (e.g. at position (N, M) only value 0 is valid). <h2>Output</h2> The first line of the file circuit.out should contain two integers, K and V. The integer K is the number of new wire segments of a least cost completion; and the integer V is the value of the least cost. The rest of the file must contain K lines; the list of wire segments of a least cost completion (in arbitrary order). Each line must contain three numbers describing exactly one new wire segment: i, j and d, where (i, j) are the coordinates of a node, and d is either 1 or 2. 1 means that the new wire segment connects the nodes (i, j) and (i+1, j), and 2 means that the new wire segment connects the nodes (i, j) and (i, j+1) <h2>Example</h2> The example input file corresponds to the circuit in Figure 1. The example output file is a possible least cost completion, and is depicted in Figure 2. <table BORDER="1" CELLSPACING="1" CELLPADDING="1" WIDTH="378"> <tr> <td WIDTH="50%" VALIGN="TOP">circuit.in</td> <td WIDTH="50%" VALIGN="TOP">circuit.out</td> </tr> <tr> <td WIDTH="50%" VALIGN="TOP"> 4 5 2 1 1 2 1 0 3 0 1 0 3 0 0 3 1 0 2 0 2 0 </td> <td WIDTH="50%" VALIGN="TOP"> 5 6 1 1 1 3 2 1 3 3 1 3 3 2 2 5 1 </td> </tr> </table> <h2>Grading</h2> If your answer is correct for subtask A then you obtain 1 point. You obtain 2 additional points if the answer is correct also for subtask B. If your answer is correct for all the three subtasks then you obtain 5 points. Note that it is not necessary in order to score points for subtask A (B) that the output file contains any output for subtask C. </td> </tr> </table> </div> </body> </html>

评论收藏

内容反馈