Description

There are N integer pointers, indexed from 0 to N-1 (N<100). Each pointer initially points to an integer of value 0.

There are two kinds of instructions. The instruction “S n k” is used to set the integer, which pointer n points to, to be k. For example, S 1 10 means that the integer that pointer 1 points to is set to 10. And the instruction “P n m” means that pointer n points to the integer that pointer m points. For example, P 2 1 means that pointer 2 points to the integer that pointer 1 points to. After P 2 1, pointer 2 and pointer 1 point to the same integer, which is pointed by pointer 1. 

Note that you don't have to change all the pointers if one pointer changes its target. The following table is an example. The instructions are P 1 2 and then P 2 3.  You do not have to change the target of pointer 1.

Finally, output all the values that pointers 0 to N-1 point to in order.

Note that

1.      This problem involves three files.

• function.h: Function definition of execInstruct.
• function.c: Function describe of execInstruct.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

Hints:

main.c

function.h

Input

The first line contains two positive X and Y. X indicates the size of data. Y indicates that there are Y instructions needed to be done.

The next Y lines contain the instructions.

Output

All the values that pointers 0 to pointer N-1 point to in order. Each value is seperated by a blank ' '.

# Note that there is no '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.

The maze type is shown in following figure:

S$###
$$#$$
$$$##
##$$F

it consists of S (starting point), #(walls), $(road) and F (final point).

In above case, it needs 7 steps from S to F as following figure,

S$###
$$#$$
$$$##
##$$F

and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.

If there is no way from S to F, then print -1.

Hint: You can use the following code to read the input.

#include<stdio.h>

int main(){
    
    ...

    while(--N>=0) {

        scanf("%d %d", &R, &C);

        for(i=0; i<R; i++)
            for(j=0; j<C; j++) {
                scanf(" %c", &maze[i][j]);
                ...
            }
    }
    
    ...

    return 0;
}

Input

The first line has an integer N(1<=N<=10^6), which means the number of test cases.

For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.

The following R lines, each containing C characters, specify the elements of the maze.

Output

Print out the least steps for each case, and there is a new line character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given the positions of N cars on a straight line, we have to list the valid moves of each car along 2 directions (i.e. right and left).

For example, a line with 3 cars is shown below:

0 1

3 4

5 6

Given the coordinate of car 1 is 3 4, it means car 1 occupies the position of 3 to 4 on the line.

The valid moves of car 1 is 1 0, which means it can move left 1 position but can’t move right

HINTS:

function.h

#define FUNCTION_H

#define LINE_SIZE 100

#define MAX_CARS 100

#define SPACE '.'


char line[LINE_SIZE];

int cars[MAX_CARS][2];

void list_moves(int);


#endif

main.c

#include <stdio.h>

#include "function.h"

int main(void)

{

    int i,j,k;

    int num_cars;


    scanf("%d",&num_cars);

    //reset line

    for (i=0; i<LINE_SIZE; i++) {

        line[i] = SPACE;

    }

    //read positions of cars and put them on the line

    for (i=0; i<num_cars; i++) {

        scanf("%d%d", &cars[i][0], &cars[i][1]);

        for (j=cars[i][0]; j<=cars[i][1]; j++) {

            line[j] = i+'0';

        }

    }

    list_moves(num_cars);

    return 0;

}

Input

The first line contains a number N (1<=N<=100), which means the total number of cars.

The following N lines contain the positions of all the N cars, where each line consists of 2 numbers: the first number is the position of the car’s head, and the second number is the position of the car’s tail.

Output

Print out the valid moves of the cars in each line.

Each line consists of 2 numbers, the valid moves toward left and right.

All of the numbers in the same line are separated by a space, and there is a '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a link list structure named Node.

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Use this structure to implement a reversing linked list.

You will be provided with main.c and function.h, and asked to implement function.c.

For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

Input

The input contains a sequence of positive integers as the linklist and the order, except the last one, which is -1, indicating the end of the sequence. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

In this problem we simulate a text editor. Given a series of keyboard input, output the final text content.

The text editing rules are defined as follows:

1. Normal alphabetical input and whitespace input (abcdefg…. and ‘ ‘): directly write after the cursor of the text content.
2. Eight special commands started with a backslash(/) character

1. The backspace command, /b: deletes a letter before the cursor.
2. The newline command, /n: creates a new line after the cursor.
3. The three navigating commands, /u, /l, and /r: move the cursor in the corresponding direction up, left, and right.

• Note that /u moves the cursor to the same position at the previous line. If the new position exceeds the end of the line, the cursor should be moved to the end of the line.

4. The sort command, /s: sorts a portion of the string in lexicographical order. The range starts from the cursor and ends at the next newline character. (Exclude the newline character.) Note that when doing sorting, the cursor should not move.
5. The copy command, /c: copies a portion of the string. The range starts from the cursor and ends at the next newline character. (Exclude the newline character.)
6. The paste command, /p: pastes the string that had been copied at the cursor.

The size of the text content is fixed to 500 characters, and the text content of test cases will not exceed 500 characters when simulating.

Example 1:

Input:

aaaaa/naaaaa/naaa/l/ubbbccccc/u/u/uddd

Output:

aaaaaddd
aabbbcccccaaa
aaa

Example 2:

Input:

edcba/c/l/l/l/p/s/c/p/pzzz

Output:

edabcabczzzabc

Hint:

The 1^st test case includes “/l”, “/s”.

The 2^nd test case includes “/r”, “/l”, “/n”, “/b”.

The 3^rd and 4^th test cases include “/s”, “/r”, “/l”, “/n”, “/b”.

The 5^th and 6^th test cases include “/s”, “/r”, “/l”, “/n”, “/b”, “/c”, “/p”.

The 7^th and 8^th test cases include “/s”, “/r”, “/l”, “/n”, “/b”, “/c”, “/p”, “/u”.

Hint2: You can use the following code to read the input.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX_SIZE 501

char input[MAX_SIZE] = {0};

​// It will be easier to manipulate the string in a 1D character array
char content[MAX_SIZE] = {0};

int main() {
    gets(input);

    int i;
    for (i = 0; i < MAX_SIZE; i++) {
        if (input[i] == '/') {
            if (input[i + 1] == 'b') {
                i++;
                // Your code here
            } else if (input[i + 1] == 'n') {
                i++;
                // Your code here
            } else if (input[i + 1] == 'l') {
                i++;
                // Your code here
            } else if (input[i + 1] == 'r') {
                i++;
                // Your code here
            } else if (input[i + 1] == 'u') {
                i++;
                // Your code here
            } else if (input[i + 1] == 'c') {
                i++;
                // Your code here
            } else if (input[i + 1] == 'p') {
                i++;
                // Your code here
            } else if (input[i + 1] == 's') {
                i++;
                // Your code here
            }
        } else if (isalpha(input[i]) || input[i] == ' ') {
            // Your code here
        }
    }

    printf("%s", content);

    return 0;
}

Input

The keyboard input sequence.

There is always a valid command(/b /n /l /r /u /c /p /s) right after the backslash character.

There is no newline character at the end.

Output

The final text content.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Cheat Sheet

printf() and  scanf() format

printf("%d", n);
 

FORMAT  ARGUMENT TYPE

%d, %i  int           decimal

%u      unsigned int

%x      unsigned int  hexadecimal

%#x     unsigned int  hexadecimal with prefix 0x

%f      double  

%Lf     long double

%e, %E  double      scientific notation

%c      int         to print a character

%s      char *      string (character array ended with '\0')

%p      void *      print memory address

%g, %G  double      %f or %e depending on the length

scanf("%d", &n);
 

FORMAT  ARGUMENT TYPE

%d      int *       &n, store the input integer in n

%ld     long *

%lld    long long *

%u      unsigned int *

%f      float *     read float

%lf     double *    read double

%Lf     long double *   read long double

%c      char *      read 3 characters %3c

%s      char *      read a string until whitespace

%n      int *       with %s, to get string length

                   char a[100]; int len; 
                  scanf("%s%n", a, &len);
                  len will have the string length

Frequently used functions

#include <string.h>
char str[10];
scanf("%s", str);
to get the string length using strlen(str)
to compare two strings strcmp(str1, str2) ==0 if equal
to compare the first n chars of two strings strncmp(str1, str2, n) ==0 if equal
to copy str2 to str1 strcpy(str1, str2)
to copy the first n chars of str2 to str1 strncpy(str1,str2, n) remember to add '\0' to str1
#include <ctype.h>
isspace(ch), islower(ch), isupper(ch), isdigit(ch)
isalpha(ch), toupper(ch), tolower(ch)

To create a 5-by-5 two-dimensional array, we need to write

int a[5][5];

It will be indexed as follows:

How to read the following data?
1 2 3 4 5 e
#include <stdio.h>
int main(void)
{
    int x;
    while (scanf("%d", &x) == 1) {   
     printf("x=%d\n", x);
    }
    return 0;
}

How to read the following data?

2

L 5 2
D 5 3

#include <stdio.h>

int main(void)

{

   char ch;
   int i, n, row, col;

   scanf("%d", &n);

   for (i=0; i<n; i++) {

      while(getchar()!='\n');

      scanf("%c%d%d", &ch, &row, &col);

   }

   return 0;

}

Using for loops to print a two-dimensional array

   for(i = 0; i < row; i++) {
      for (j = 0; j < col; j++) {
         printf("%5d", A[i][j]);
      }
      printf("\n");
   } 

Using bubble sort to rearrange an array A

for (i = 0; i < n; i++) {
   for (j = 1; j < n; j++) {
      if (A[j] > A[j-1]) {
         /* swap A[j] A[j-1] */
      }
   }
}

operators:
!   &&    ||    ==     !=    +    -    *    /    %
>   <     >=    <=

How to avoid common errors and how to debug for OJ

1. Put the arrays in the 'global' area. Set their size bigger than required. Avoid using variable-length arrays (e.g. int arr[n];). Keep the array size fix (e.g., int arr[1000];).

2. After writing the code for reading input data, you may print out the data to check if your code reads them correctly. Do not proceed to write subsequent code before you confirm that.

3. If your program crashes, usually it is caused by memory related errors. Check the ranges of for-loops to see if your code attempts to read or write the elements out of the arrays’ boundary.

*(a+i) is equivalent to a[i]
(a+i) is equivalent to &a[i]

qsort :

you have to include <stdlib.h>

usage :

void qsort (void *array, size_t count, size_t size, comparison_fn_t compare);

qsort an int array

int compare_int (const void *a, const void *b)

{

    const int *va = (const int *) a;

    const int *vb = (const int *) b;

    return *va-*vb;

}

qsort a double array

int compare_double (const void *a, const void *b)

{

    const double *da = (const double *) a;

    const double *db = (const double *) b;

    return (*da > *db) - (*da < *db);

}

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss