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 append a copy of str2 to str1 strcat(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 ap

for (i = 0; i < n-1; i++)
{
    for (j = 0; j < n-1-i; j++)
    {
        if (ap[j] > ap[j + 1])
        {
            temp = ap[j];
            ap[j] = ap[j + 1];
            ap[j + 1] = temp;
        }
    }
}

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

Description

Input

The first line contains a string s, which consists of only lowercase Latin characters. The second line contains a integer Q. The next Q lines, each contains two characters A and B.

Output

Print the resulting string in one line after applying the Q operations.

(remember to print a new line character)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Cookie Monster is back! This time, he has bought all the cookies in the entire supermarket. There are a total of N cookies, and for each cookie, there is a number d_i indicating how delicious the i-th cookie is. Generally, the larger d_i, the more delicious the i-th cookie is. However, Cookie Monster considers the number 7 to be his lucky number, so he especially loves cookies that contain the digit '7' in their d_i. Moreover, if a cookie's d_i contains a '7' at a higher-order position, the Cookie Monster would tend to choose that cookie first. Considering the example of 5 cookies with 48767, 48763, 379498, 377777, and 12345689, respectively, we have

Since both 377777 and 379498 have a '7' at the same highest-order position but 379498 has a larger d_i value than 377777, Cookie Monster will choose the cookie with 379498.

We can summarize Cookie Monster's selection strategy as follows:

• For any two cookies, always choose the one that contains the digit 7.
• If both cookies contain the digit 7, he will prioritize the one with the higher-order position of the digit 7.
• If both cookies share the same highest-order position of the digit 7 or neither contains the digit 7, he will prioritize the one with a larger d_i.

Now, given the numbers d_i for N cookies, please help Cookie Monster determine the order in which he should eat the cookies.

Input

The first line contains one integers N, representing the number of cookies.
The next N lines each contains a positive integer d_i.

Constraints

• Test Case 1: there is no '7' in every d_i.
• Test Case 2: 1 ≤ d_i ≤ 10⁸.
• Test Cases 3 ~ 8: satisfy no additional constraints.
• For all test cases: 1 ≤ N  ≤ 1000, 1 ≤ d_i ≤ 10¹⁰⁰.

Output

Output N lines, indicating the order in which Cookie Monster eats the cookies. In the order that the higher priority prints first.

Remember to print a ‘\n’ at the end of the output.

Do not include any spaces at the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Just before the deadline for Doraemon to submit his final project to the eeclass system, another power outage occurred, causing him to lose all of his homework files. It seems that fate has determined that Doraemon will have to retake the course next year...

Fortunately, the government is making efforts to assist Doraemon's university in addressing this power issue by establishing a new electrical substation! The electrical grid for the campus consists of n-1 cables connecting each of the n locations, ensuring that any two locations can be connected.

Previously, we established a substation (in problem 14080 - Power Outage), but power outages have occurred again... It appears that the strategies to balance the number of locations haven't proven effective. However, we have discovered that minimizing the distance from each location to the substation can efficiently reduce energy loss and significantly decrease the chance of encountering another power outage issue.

To determine the optimal location for its construction, they need to find the location where the greatest distance from the station to any other location is minimized.

The graph above represents the layout of the electrical grid for the campus. Each circle represents a location, and each line connecting the locations represents a power cable with a distance of 1 unit. The blue numbers beside the circles indicate the index number of location, and the value inside each circle represents the distance from the electrical substation.

If we establish the substation at location index number 10 (in green), the farthest distance from there would be 3 units.
However, if we establish the substation at location index number 6 (in red), the farthest distance from there would be 4 units.
Therefore, it seems that establishing the electrical substation at location index number 10 might be the best choice.

Template

#include <stdio.h>
#include <stdlib.h>
#define N 100001

int cable[N][2], neighborCount[N], *neighbor[N];
int n;

void readGraph() {
    scanf("%d", &n);
    for (int i=0; i<n-1; i++) {
        scanf("%d %d", &cable[i][0], &cable[i][1]);
        neighborCount[cable[i][0]]++;
        neighborCount[cable[i][1]]++;
    }
    for (int i=1; i<=n; i++) {
        neighbor[i] = (int*)malloc(neighborCount[i] * sizeof(int));
    }
    int neighborIndex[N] = {};
    for (int i=0; i<n-1; i++) {
        int u = cable[i][0], v = cable[i][1];
        neighbor[u][neighborIndex[u]++] = v;
        neighbor[v][neighborIndex[v]++] = u;
    }
}

int main() {
    readGraph();
    // Test the following code
    /*
    for (int i=1; i<=n; i++) {
        int neighborCnt = neighborCount[i];
        printf("%d connects to ", i);
        for (int j=0; j<neighborCnt; j++) {
            printf("%d ", neighbor[i][j]);
        }
        printf("\n");
    }
     */
    return 0;
}

Utilizing the provided readGraph() function can help in managing the preprocess of the given graph:

• neighborCount[i] stores the number of neighbors for the i-th location.
• neighbor[i] is a dynamic array with a size equal to neighborCount[i], and it stores the index number of neighbors for the i-th location.

Try uncommenting the code in the main() function to see how it works.

Constraints

• Testcase 1~6 - n ≤ 10³
  • 1: he provided electrical grid is arranged in a straight line. (a₁ <--> a₂ <--> a₃ <--> ... <--> a_n)
  • 2~3: For the optimal location of a substation, the sum of the number of locations for each cable direction yields the same value, and the farthest distance for each direction of cable is also the same.
  • 4~6: No additional constraints.
• Testcase 7 (Bonus) - n ≤ 10⁵
  • ​No additional constraints. (hint: consider to conduct multiple tree searches and record additional information)

Input

The first line contain one positive integer n (1 ≤ n ≤ 10⁵) - the number of locations in the electrical grid.
Each of the following n-1 lines contains two integers u and v (1 ≤ u, v ≤ n) - a power cable connecting location index numbers u and v. It is guaranteed that the provided graph is a tree.

Output

Output one line contain one integer - the number of the location that is the best choice for establishing the electrical substation.

In this problem, there may be multiple locations considered optimal;
you should output the one with the smallest index number.

Sample Input  Download

Sample Output  Download

Tags

Discuss