50070. Elevator

I'm a slow walker, but I never walk backwards.

Problem Description

Write a program to simulate the movements of an elevator.

A building has $F$ floors and an elevator. The floors are labeled as $1, \cdots , F$, and the elevator is initially at floor $1$.

There are only two buttons in the elevator. One is Up and the other is Down. If the button Up is pressed, the elevator will go up $u$ floors. If the button Down is pressed, the elevator will go down $d$ floors. The elevator will not move if the destination floor is invalid, i.e. smaller than $1$ or greater than $F$. It will continue follow the next instruction.

The elevator is not well designed so it will break right after the user gives four consecutive down-invalid instructions, or four consecutive up-invalid instructions. That is, if a U indicates a up-invalid instruction and D indicates a down-invalid instruction, then both UUUU and DDDD will break the elevator, but UDUD will not. However, if a V indicates a valid instruction, then neither DDVDD nor UUUVU will break because these four Ds or Us are not consecutive. When the elevator breaks, it will stop executing any further instructions.

(如果目標樓層不合法,即小於 $1$ 或大於 $F$,電梯不會移動,但可以繼續執行下一個指令;但如果同一個不合法的按鍵被連續按超過三次,電梯會壞掉,並且不會執行之後的任何指令).

Given a series of movement instructions, you need to output the position of the elevator after each instruction. You also need to keep track of which floors the elevator has been to, and output them at the end of the program.

You need to write two files, main.c and elevator.c. File main.c reads in instructions and call functions in elevator.c to move the elevator. Note that you cannot define any new structure in main.c -- you can only use the functions defined in the elevator.h. Also note that you should implement the structure in elevator.c, and you may choose any implementation you wish.

We will test main.c and elevator.c separately. You will get $40$ points if main.c is correct. You will get the other $60$ points if elevator.c is correct.

The structure and functions you need to implement in elevator.c are defined in elevator.h.

elevator.h

1
2
3
4
5
6
7
8
9
10
11
#define MAXF 1000
#define MAXL 1500
 
struct Elevator;
typedef struct Elevator Elevator;
 
Elevator* newElevator(int u, int d, int F);
int up(Elevator* elevator);
int down(Elevator* elevator);
int visited(Elevator* elevator, int floor);
int getPosition(Elevator* elevator);
  1. struct Elevator

    Implement the structure and define the variables needed in this structure.

  2. Elevator* newElevator(int u, int d, int F)

    Returns a pointer of Elevator. $u$ is the number of floors the elevator moves up when button Up is pressed. $d$ is the number of floors the elevator moves down when button Down is pressed. $F$ is the maximum floor the elevator can stop at. Hint: Use malloc to create an Elevator structure and initialize the variables in Elevator here.

  3. int up(Elevator* elevator)

    This function will be called when button Up is pressed.

    • Move the elevator up $u$ floors and return $1$ if the destination floor is valid.
    • Return $0$ if the destination floor is invalid but the elevator is still fine (not broken).
    • Return $-1$ if the elevator is broken.
  4. int down(Elevator* elevator)

    This function will be called when button Down is pressed.

    • Move the elevator down $d$ floors and return $1$ if the destination floor is valid.
    • Return $0$ if the destination floor is invalid but the elevator is still fine (not broken).
    • Return $-1$ if the elevator is broken.
  5. int visited(struct Elevator* elevator, int floor)

    Return $1$ if the elevator has visited floor $floor$. Otherwise, return $0$;

  6. int getPosition(struct Elevator* elevator)

    Return the current position of the elevator.

Compile

You can compile both your main.c and elevator.c by

gcc -std=c99 -O2 elevator.c -c
gcc -std=c99 -O2 main.c -c
gcc -std=c99 -O2 main.o elevator.o

You can compile your main.c program with TA’s p10159-ta_elevator.o (download ta_elevator-linux64.o, ta_elevator-windows32.o, ta_elevator-windows64.o) file by

gcc -std=c99 -O2 main.c -c
gcc -std=c99 -O2 main.o p10159-ta_elevator.o

You can compile your elevator.c program with TA’s p10159-ta_main.o (download ta_main-linux64.o, ta_main-windows32.o, ta_main-windows64.o) file by

gcc -std=c99 -O2 elevator.c -c
gcc -std=c99 -O2 p10159-ta_main.o elevator.o

If you don't know how to write files according to the given .h file, here is an example.
如果不知道要怎麼根據 .h 檔寫另外兩個檔案,這裡有一個範例。

Input Format

There are multiple test cases. The first line contains a number $N$, indicating the number of test case. Each test case contains two lines, the first line contains three integers, $u$, $d$ and $F$, indicating the number of floors the elevator goes up and down, and the maximum floor the elevator can stop at. The second line contains the movement instructions, which is a string consists of letter $U$ and $D$. $U$ means the button Up is pressed and $D$ means the button Down is pressed. Note that if an instruction is invalid, the elevator will not move, and it will continue follow the next instruction. However, if the elevator is broken, it will ignore all the rest of the instructions (see sample input 2).

  • $1 \leq u, d, F \leq 1000$
  • $1 \leq \text{number of instructions} \lt 1500$

Output Format

For each test case, after each instruction, output “Valid $x$”, where $x$ is the position of elevator after the the movement, if the instruction is valid; output “Invalid” and continue following the next instruction if the instruction is invalid but the elevator is not broken; output “Broken” and ignore the rest of the instructions if the elevator is broken. Finally, output the floors the elevator has been to increasingly.

Sample Input 1

1
11 8 19
UDUDUUD

Sample Output 1

Valid 12
Valid 4
Valid 15
Valid 7
Valid 18
Invalid
Valid 10
1
4
7
10
12
15
18

Sample Input 2

3
18 8 19
UDUUUDUDD
20 21 5
UDUDUUUDD
5 1 6
DDDDDUUUU

Sample Output 2

Valid 19
Valid 11
Invalid
Invalid
Invalid
Valid 3
Invalid
Invalid
Invalid
1
3
11
19
Invalid
Invalid
Invalid
Invalid
Invalid
Invalid
Invalid
Invalid
Invalid
1
Invalid
Invalid
Invalid
Broken
1

Subtasks

  • Subtasks 0 tests your main.c program with the sample intput.
  • Subtasks 1 to 11 test your main.c program (total score = 40).
  • Subtasks 12 tests your elevator.c program with the sample input.
  • Subtasks 13 to 23 test your elevator.c program (total score = 60).

Discussion