I have taken part in the team selection test of my school for Olympiad and there are some difficult problems remaining unsolved during this contest. Hope some one can help me with the outline idea, thanks so much!
Problem 1.
Let S be a string with length |S| < = 104 and S1, S2, ..., Sk are all distinct sub-strings of S (sub-string of S can be received by deleting some or all characters from S). Let fi be be number of occurrence of sub-strings Si with 1 ≤ i ≤ k. Find the total in which 2 ≤ M ≤ 109. There are T ≤ 50 tests and each test includes string S and number M. Example:
input:
2
zoo
10
@#$%
1000000
output:
2
16
Problem 2.
Let (an) be a positive integer sequence and a key X be a positive number. Count the number of ordered triples (i, j, k) such that ai + aj + ak ≥ X. There are T ≤ 50 test and each test includes number n ≤ 5000, X ≤ 1012 indicates the size of sequences, the key, respectively and n terms of sequence a1, a2, ..., an such that 1 ≤ ai ≤ 109, i = 1, 2, 3, ..., n. Example:
input:
2
5 300
100 100 100 100 100
5 301
100 100 100 100 100
output:
60
0
Problem 3.
Balanced number is a positive integer satisfied that: (1) The amount of even digit equals to the amount of odd digits. (2) The sum of even digits equals to the sum of odd digits. Ex: 1982, 11822989 are balanced numbers. Given L, R are two positive integer such that 1 ≤ L ≤ R ≤ 1012. Count the number of balanced numbers in the interval [L;R]. There are T ≤ 100 tests, each test includes 2 numbers L, R. Example:
input:
2
1 10000
45645 10987656
output:
450
29993
Problem 4.
Symmetric number is a positive integer greater than 9 and be unchanged when reading it from the left to right and from the right to left. Asymmetric number is a positive integer that not contain any symmetric number. Ex: 96276 , 1234 are asymmetric number. Given L, R such that 1 ≤ L ≤ R ≤ 1018. Count the number of asymmetric numbers in the interval [L;R]. There are T ≤ 100 tests, each test includes 2 numbers L, R. Example:
input:
2
123 321
123456789 987654321
output:
153
167386971