Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Statement en US

    Uploaded by

    Duc Anh Nguyen
    The document describes a rail system in Taiwan with stations located in different types of blocks along the track. It defines a task to write a function that determines the block number and type of each station given the distance between stations and one known location. It provides sample input/output and evaluation for the task.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Statement en US

    Uploaded by

    Duc Anh Nguyen
    9 views3 pages
    The document describes a rail system in Taiwan with stations located in different types of blocks along the track. It defines a task to write a function that determines the block number and type of each station given the distance between stations and one known location. It provides sample input/output and evaluation for the task.

    Original Title

    statement_en_US

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes a rail system in Taiwan with stations located in different types of blocks along the track. It defines a task to write a function that determines the block number and type of each station given the distance between stations and one known location. It provides sample input/output and evaluation for the task.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    9 views3 pages

    Statement en US

    Uploaded by

    Duc Anh Nguyen
    The document describes a rail system in Taiwan with stations located in different types of blocks along the track. It defines a task to write a function that determines the block number and type of each station given the distance between stations and one known location. It provides sample input/output and evaluation for the task.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    International Olympiad in Informatics 2014

    13-20th July 2014


    Taipei, Taiwan
    rail
    Day-1 tasks Language: en-ISC

    Rail
    Taiwan has a big railway line connecting the western and eastern shores of the island. The line
    consists of blocks. The consecutive blocks are numbered , starting from the western
    end. Each block has a one-way west-bound track on the north, a one-way east-bound track on the
    south, and optionally a train station between them.

    There are three types of blocks. A type C block has a train station that you must enter from the
    northern track and exit to the southern track, a type D block has a train station that you must enter
    from the southern track and exit to the northern track, and a type empty block has no train station. For
    example, in the following figure block 0 is type empty, block 1 is type C, and block 5 is type D. Blocks
    connect to each other horizontally. Tracks of adjacent blocks are joined by connectors, shown as
    shaded rectangles in the following figure.

    The rail system has stations numbered from 0 to . We assume that we can go from any
    station to any other station by following the track. For example we can go from station 0 to station 2
    by starting from block 2, then passing through blocks 3 and 4 by the southern track, and then passing
    through station 1, then passing through block 4 by the northern track, and finally reaching station 2 at
    block 3.

    Since there are multiple possible routes, the distance from one station to another is defined as the
    minimum number of connectors the route passes through. For example the shortest route from station
    0 to 2 is through blocks 2-3-4-5-4-3 and passes through 5 connectors, so the distance is 5.

    A computer system manages the rail system. Unfortunately after a power outage the computer no
    longer knows where the stations are and what types of blocks they are in. The only clue the computer
    has is the block number of station 0, which is always in a type C block. Fortunately the computer can
    query the distance from any station to any other station. For example, the computer can query 'what is
    the distance from station 0 to station 2?' and it will receive 5.

    Task
    You need to implement a function findLocation that determines for each station the block number
    and block type.

    1/3
    findLocation(n, first, location, stype)

    n: the number of stations.


    first: the block number of station 0.
    location: array of size ; you should place the block number of station into
    location[i].
    stype: array of size ; you should place the block type of station into stype[i]: 1 for
    type C and 2 for type D.
    You can call a function getDistance to help you find the locations and types of stations.
    getDistance(i, j) returns the distance from station i to station j. getDistance(i, i)
    will return 0. getDistance(i, j) will return -1 if i or j is outside the range
    .

    Subtasks
    In all subtasks the number of blocks is no more than 1,000,000. In some subtasks the number of
    calls to getDistance is limited. The limit varies by subtask. Your program will receive 'wrong
    answer' if it exceeds this limit.

    getDistance
    subtask points note
    calls
    1 8 unlimited All stations except 0 are in type D blocks.
    All stations to the right of station 0 are in type
    2 22 unlimited D blocks, and all stations to the left of station 0
    are in type C blocks.
    3 26 no additional limits
    4 44 no additional limits

    Implementation details
    You have to submit exactly one file, called rail.c, rail.cpp or rail.pas. This file implements
    findLocation as described above using the following signatures. You also need to include a header
    file rail.h for C/C++ implementation.
    C/C++ program

    void findLocation(int n, int first, int location[], int stype[]);

    Pascal program

    procedure findLocation(n, first : longint; var location,


    stype : array of longint);

    2/3
    The signatures of getDistance are as follows.
    C/C++ program

    int getDistance(int i, int j);

    Pascal program

    function getDistance(i, j: longint): longint;

    Sample grader
    The sample grader reads the input in the following format:
    line 1: the subtask number
    line 2: n

    line ,( ): stype[i] (1 for type C and 2 for type D), location[i].

    The sample grader will print Correct if location[0] ... location[n-1] and stype[0] ...
    stype[n-1] computed by your program match the input when findLocation returns, or
    Incorrect if they do not match.

    3/3

    You might also like