Description

HT Chen is an aspiring (also a little bit naughty) professor in NTHU. One day he felt extremely bored in his laboratory, so he decided to write down some strings on a paper. After writing down some strings, HT discovered that for some special string s, he could find two distinct indices l and r such that if he reverses the substring s[l, r], the whole string would still remain unchanged. HT found this property very exquisite, so he decided to name this kind of substring after "exquisite substring".

HT is wondering how many "exquisite substrings" are there in each string he wrote on the paper. Counting them by hand will be a dreadful work, so he decides to give extra homework so you guys can help him solve this problem.

If you can't solve this problem, HT maybe be disappointed and the upcoming midterm will become harder than usual.

** For someone who doesn't know the definition of substring : https://en.wikipedia.org/wiki/Substring 

Input

There are multiple lines in each testcase. Each line contains a string s_i that HT wrote on the paper.

The input file is ended by 'EOF'.

It is guaranteed that :

• At most 10 lines in each testcase.
• testcase #1 ~ #4 : 1 ≤ | s | ≤ 200
• testcase #5 Bonus: 1 ≤ | s | ≤ 2000

Output

For each string s_i, please output a line contains one integer representing the number of "exquisite substrings" in s_i.

(i.e. Please print '\n' after each answer.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

related problem: 11112-Big Number

Hey, do you want to hear something amazing? Square of a 16-digit integer can be larger that the maximum of long long int.

Given a 16-digit integer n with no trailing zeros, please output the result of n*n.

Hint and Suggested Implementation

How to represent an integer that is too long to be stored in either int or long long int?

A simple and intuitive method is to use a string ( char array ). Addition and Multiplication can be implemented using 直式 , for example :

Another method is to use an int array. An integer can be sliced up to several 4-digit numbers, with each of them stored in array. Addition and Multiplication can be implemented using 直式 as well, for example :

From another point of view, the first method (using char array) is to implement big number multiplication under base 10 system, while the second method (using int array, with each array element storing a 4-digit number) is to implement big number multiplication under base 10000 multiplication.

Below is a suggested way to implement big number multiplication using the second method. For this problem, you can either fill in the ??? in the code below, or feel free to write your own version of big number multiplication.

x
1
#include <stdio.h>
2
#define BIGINT_WIDTH 4
3
#define BIGINT_BASE 10000
4
#define DIGIT_NUM 16
5
#define NUM_SIZE (DIGIT_NUM/BIGINT_WIDTH)
6
#define ANS_SIZE (NUM_SIZE*2)
7
​
8
int main()
9
{
10
    int num[NUM_SIZE] = {0}; // store input number (under base 10000)
11
    int ans[ANS_SIZE] = {0}; // store answer (under base 10000)
12
    char input[DIGIT_NUM];   // store input nunber (under base 10)
13
    
14
    // input : input 16-digit number to a char array (under base 10)
15
    for(int i = 0; i < DIGIT_NUM; i++) scanf("%c", &input[i]);
16
​
17
    // convert from base 10 to base 10000
18
    for(int d = 0; d < DIGIT_NUM; d++)
19
    {
20
        int num_idx = (DIGIT_NUM-d-1)/BIGINT_WIDTH;
21
        num[num_idx] *= 10;
22
        num[num_idx] += input[d]-'0';
23
    }
24
​
25
    // TODO: multiplication
26
    for(int up = 0; up < NUM_SIZE; up++)
27
        for(int down = 0; down < NUM_SIZE; down++)
28
            ans[???] += num[???]*num[???];
29
​
30
    // TODO: deal with carry (處理進位)
31
    for(int d = 0; d < ANS_SIZE-1; d++)
32
    {
33
        ???
34
    }
35
​
36
    // print answer
37
    printf("%4d", ans[ANS_SIZE-1]);
38
    for(int d = ANS_SIZE-2; d >= 0; d--) printf("%04d", ans[d]);
39
    printf("\n");
40
​
41
    return 0;
42
}
43
​

Input

A 16-digit integer n with no trailing zeros. In other words, (10^15) <= n <= (10^16)-1.

Output

The result of n*n. There should be a new line character in the end, and the output format is always 32-digit wide with space prepended if needed.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One day, Little-Brick(小磚頭) found 3 functions,
GCD, LCM and POWER
GCD(a, b) is to compute the greatest common divisor of a and b,
LCM(a, b) is to compute the least common multiplier of a and b,
POWER(a, b) is to compute a^b.

Little-Brick's is not so good as math,
even that he doesn't know how to use these functions,
he doesn't care about it,
he decide to take 4 numbers and substitute them into these functions.

Now, he is asking you to tell him the answer of the result of substitute these 4 numbers into functions in all order,
that is, given you 4 integer A, B, C, D,
you should output the result of GCD(LCM(POWER(A, B), C), D), GCD(POWER(LCM(A, B), C), D), LCM(GCD(POWER(A, B), C), D), LCM(POWER(GCD(A, B), C), D), POWER(GCD(LCM(A, B), C), D), POWER(LCM(GCD(A, B), C), D), each in a single line.

Hint: LCM(a, b) = a * b / GCD(a, b)

You can follow the format of the following suggested code,
or feel free to have your own version.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>

int gcd(int a, int b) {
	// your code here
}

int lcm(int a, int b) {
	// your code here
}

int power(int a, int b) {
	// your code here
}

int main() {
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	printf("%d\n", gcd(lcm(power(a, b), c), d));
	// ... other 5 lines 
	return 0;
}

Input

Input contain 4 integer A, B, C, D, seperate by spaces.
1<= A, B, C, D <= 100

Output

Output contains 6 lines.

Output he result of GCD(LCM(POWER(A, B), C), D), GCD(POWER(LCM(A, B), C), D), LCM(GCD(POWER(A, B), C), D), LCM(POWER(GCD(A, B), C), D), POWER(GCD(LCM(A, B), C), D), POWER(LCM(GCD(A, B), C), D), each in a single line.

It is guarantee that the result of every call of function will < 2³¹

Sample Input  Download

Sample Output  Download

Tags

Discuss