Description

A teacher is going to deliver N gifts to N students in the class. Every student can get exactly one gift. Since the value of each gift is different, the teacher decides to deliver the gifts based on student ranks. Thus, he evaluates each gift with a value T, which means only the students who rank higher than or equal to T are allowed to receive that gift. You are asked to write a program counting how many ways there are for the teacher to deliver those gifts.

 

For example, there are 3 students in the class (N=3), and the 3 gifts are valued as 2, 3, 3. So there are 4 different ways to deliver those gifts: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, where a solution {a, b, c} means the first gift (with value 2) is delivered to the student with rank a, the second gift (with value 3) is delivered to the student with rank b, and the last gift (with value 3) is delivered to the student with rank c.

 

Input

The first line contains a positive integer N.

The second line consists of N positive integers, indicating the values Ti of the N gifts.

1 ≤ N ≤ 20

1 ≤ Ti ≤ N

T1 ≤ T2 ≤ ... ≤ TN-1 ≤ TN

(That is, the values of the gifts have been sorted for you.)

 

 

Output

Please output an integer, indicating how many ways there are to deliver those gifts.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string S, you are going to shift part of it.
Specifically, a right shift on a string is to move all the characters right but the rightmost characters would be moved to the leftmost.
For example, a shift on "abcd" would result in "dabc".

This problem ask you to implement a function shift(char *start, char *end) that shifts a substring of S starting from start and ending at end.

Reference code:
Note: It is absolutely fine if you don't follow this template.  

void shift(char *start, char *end)
{
    /* Your code */
}

int main(){
    char str[111];
    int n,l,r;
    scanf("%s",str);
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&l,&r);
        shift(&str[l-1], &str[r-1]);
        printf("%s\n", str);
    }
    printf("%s\n",str);
}

Input

The first line is a string S. (length of S<=20)
The second is a integer n. (n<=10)
The next n lines, each contains two integers l and r.(l<=r<=n)
This means that a shift on S[l-1]S[l]...S[r-1].
If the length of substring is one(l=r), then you should keep the string unchanged.
All these shifts must be done in order.

Output

The resulting string after all n shift operations. There's a newline after the string.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N licenses. Each license has a four-digit integer, each digit between 1 to 9. For example, if N=7, the input may look like

7

1324

5566

3578

4123

5656

4312

9847

We want to get the licenses that use the same digits and print the license appearing first. For example, 1324, 4123, and 4312 are the combination of the same digits (1, 2, 3, and 4), that is, of the same group. We want to get 1324. Similarly, 5566 and 5656 are the combination of the same digits (5, 5, 6, and 6). We want to get 5566. 

For output, we list the corresponding licenses in an increasing order line by line, so the output will look 

1324

5566

<Hint>

Reference algorithm:

Note: It is absolutely fine if you don't follow this template.  

0. Create a character array (char str[5];) for storing the input integers and create three arrays:

    0.1 int HIT[10000]={0}; to record the occurrences of the representative number of each group. 

    0.2 int FIRST[10000]={0}; to record the first showing number of each group. 

    0.3 int PRINT[10000]={0}; to judge which numbers to print.

1. Read the number of input integers and store it in variable N (scanf("%d", &N);).

2. For each of the next N integers, do 

    2.1 Read the four-digit integer and store it as a four-character string in str.

    2.2 Convert the read string in str to an integer p.

    2.3 Use the bubble sort algorithm to sort the four characters in str.

    2.4 Convert the sorted string to an integer m and do HIT[m]++;

    2.5 If HIT[m] is equal to 1, FIRST[m]=p.

    2.6 If HIT[m] is equal to 2, PRINT[FIRST[m]]=1.

3. Check each element of PRINT array; if the element of PRINT is equal to 1, print the corresponding integer.

 

The bubble sort algorithm:

/* Using bubble sort to rearrange an array A[n] */

for (i = n; i > 0; i--) {

   for (j = 1; j < i; j++) {

      if (A[j-1] > A[j]) {

         /* swap A[j-1] A[j] */

      }

   }

}

Input

The first line contains a number N (1<=N<=2000).

The next N lines provide the N four-digit integers.

Output

Each line shows the corresponding integer as explained in the problem description.

Remember to print a newline at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

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]

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss