## COCI '14 Contest 1 #3 Piramida

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

Zoran and Tomislav don't really have anything important to do, so they spend their days doing various activities. Today, they built a pyramid of the height in the back garden and wrote their favorite word on it, repeating it from line to line and changing direction, as shown in the picture.

     J
N A
J E T
J A N I
A N J E T
N A J A N I

Pyramid of the height 6 marked with the word "JANJETINA"

Tomislav has now chosen lines of the pyramid, marked with , and has chosen a letter for each line. Then he asked Zoran tricky questions: "How many times does the letter appear in the row ?"

You are Zoran's counselor. Write a programme that will, for the given pyramid height and their favorite word, answer Tomislav's questions.

#### Input

The first line of input contains the integer .
The second line of input contains a word that consists of only uppercase letters of the English alphabet. The word's length will not exceed .
The third line of input contains the integer , the number of lines Tomislav has chosen.
Each of the following lines contains the pair , uppercase letter of the English alphabet which represent Tomislav's questions.

#### Output

Output lines. The line of output must contain a single integer – the number of appearances of letter in the row .

#### Scoring

In test cases worth 50% of total points, will not exceed . In test cases worth 70% of total points, length of the string will not exceed .

#### Sample Input 1

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

#### Sample Output 1

1
0
2
1
1

#### Clarification of Output for Sample Input 1

See the pyramid in the task statement.

#### Sample Input 2

5
A
5
1 A
2 A
3 A
4 A
5 B

#### Sample Output 2

1
2
3
4
0

#### Sample Input 3

3
AB
3
2 A
2 B
3 B

#### Sample Output 3

1
1
2

• haytam  commented on Nov. 14, 2017, 4:36 p.m.

why i get mle the judge is joking me he input big numbers and i get mle

• A_H_Ghaznavi  commented on June 17, 2019, 5:13 a.m. edited

The judge isn't joking you :)

Likely you used dp to solve the problem and you created a big array! But you can use another creative idea to reduce memory.

You can create 26 vector and for any letter like you save some numbers like such that in sorted form. Then create a function to find number of letter in range and use binary search.

sorry for my poor English!

• fungucide420  commented on March 28, 2017, 10:15 a.m. edited

I don't know what I did wrong. 5th batch case and onward I have WA. Can someone give me a hint on what I did wrong?

• A_H_Ghaznavi  commented on June 17, 2019, 5:15 a.m. edited

Mybe for big numbers (numbers like so that )! I got WA for that too but I fixed it!

• XIAOAGE  commented on Nov. 29, 2015, 11:57 a.m.

dont know how to solve this

• Amplify  commented on Nov. 14, 2015, 10:52 p.m.

all test cases after the 5th one fail... :(