Educational Codeforces Round 16 （A-E）

Educational Codeforces Round 16 （A-E）

A. King Moves

time limit per test

memory limit per test

input

output

The only king stands on the standard chess board. You are given his position in format "cd", where c is the column from 'a' to 'h' and dis the row from '1' to '8'. Find the number of moves permitted for the king.

Check the king's moves here moves from the position e4

Input

The only line contains the king's position in the format "cd", where 'c' is the column from 'a' to 'h' and 'd' is the row from '1' to '8'.

Output

Print the only integer x

Example

input

e4

output

8

题解：额。。。水题

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

B. Optimal Point on a Line

time limit per test

memory limit per test

input

output

n points on a line with their coordinates xi. Find the point x

Input

n (1 ≤ n ≤ 3·105) — the number of points on the line.

n integers xi (9 ≤ xi ≤ 109) — the coordinates of the given n

Output

x

Example

input

4 1 2 3 4

output

2

题解：额。。。水题

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

C. Magic Odd Square

time limit per test

memory limit per test

input

output

n × n matrix with different numbers from 1 to n2, so the sum in each row, column and both main diagonals are odd.

Input

n (1 ≤ n ≤ 49).

Output

n lines with n integers. All the integers should be different and from 1 to n2. The sum in each row, column and both main diagonals should be odd.

Examples

input

1

output

1

input

3

output

2 1 4 3 5 7 6 9 8

题解：让你分别使矩阵的行，列，斜的数加起来都是奇数。输入是odd。基础构造。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

D. Two Arithmetic Progressions

time limit per test

memory limit per test

input

output

a1k + b1 and a2l + b2. Find the number of integers x such that L ≤ x ≤ R andx = a1k' + b1 = a2l' + b2, for some integers k', l' ≥ 0.

Input

a1, b1, a2, b2, L, R (0 < a1, a2 ≤ 2·109,  - 2·109 ≤ b1, b2, L, R ≤ 2·109, L ≤ R).

Output

x.

Examples

input

2 0 3 3 5 21

output

3

input

2 4 3 0 6 17

output

2

题解：让你找出符合x = a1k' + b1 = a2l' + b2，且 L ≤ x ≤ R的x的个数。

这题被人hack了。（待补。。。数学题）。。。

E. Generate a String

time limit per test

memory limit per test

input

output

zscoder

n

x seconds to insert or delete a letter 'a' from the text file and y

zscoder wants to find the minimum amount of time needed for him to create the input file of exactly n

Input

n, x and y (1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109) — the number of letters 'a' in the input file and the parameters from the problem statement.

Output

t

Examples

input

8 1 1

output

4

input

8 1 10

output

8

题解：初始化有一个空的文本，要求生成得到n 个‘a’字母，  插入或删除一个‘a’需要x秒，复制目前的字符串需要y秒，问你达到n个‘a’字母最少要几秒。

设dp[i]表示第 i 个‘a’字符最少要多少秒。

那么初始化dp[1]=x。

如果 i 等于奇数。则dp[i]=min(dp[i-1]+x,dp[(i+1)/2]+x+y)；只可能是插入或删除，或插入或删除和复制都有。

如果 i 等于偶数。则dp[i]=min(dp[i/2]+y,dp[i-1]+x)。只可能是复制以及插入或删除。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

F. String Set Queries

time limit per test

memory limit per test

input

output

m queries over a set D

sto the setD. It is guaranteed that the stringssfrom the setD. It is guaranteed that the stringsis in the setD.sfind the number of occurrences of the strings from the setD. If some stringpfromDhas several occurrences ins

online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query of the third type. Use functions fflush in C++ and BufferedWriter.flush inJava

Input

m (1 ≤ m ≤ 3·105) — the number of queries.

m lines contains integer t (1 ≤ t ≤ 3) and nonempty string s

3·105.

Output

c — the desired number of occurrences in the string s.

Examples

input

5 1 abc 3 abcabc 2 abc 1 aba 3 abababc

output

2 2

input

10 1 abc 1 bcd 1 abcd 3 abcd 2 abcd 3 abcd 2 bcd 3 abcd 2 abc 3 abcd

output

3 2 1 0

(待补。。。AC自动机)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。