C - KEYENCE building

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

1 から N の番号がついた N 人の人がいます。

人 i はキーエンス本社ビルの建築面積を S_i 平方メートルであると予想しました。

キーエンス本社ビルは下図のような形をしています。ただし、a,b はある 正の整数 です。
つまり、キーエンス本社ビルの建築面積は 4ab+3a+3b 平方メートルと表されます。

N 人のうち、この情報のみによって、予想した面積が確実に誤りであるとわかる人数を求めてください。

キーエンス本社ビル見取り図

制約

  • 1 \leq N \leq 20
  • 1 \leq S_i \leq 1000
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 \ldots S_N

出力

答えを出力せよ。

入力例 1

3
10 20 39

出力例 1

1

a=1,b=1 のとき面積は 10 平方メートル、a=2,b=3 のとき面積は 39 平方メートルとなります。

しかし a,b がどのような正の整数であったとしても面積が 20 平方メートルになることはありません。

よって、人 2 の予想だけは確実に誤りであることがわかります。

入力例 2

5
666 777 888 777 666

出力例 2

3

Score : 200 points

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Sketch of KEYENCE headquarters building

Constraints

  • 1 \leq N \leq 20
  • 1 \leq S_i \leq 1000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
S_1 \ldots S_N

Output

Print the answer.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3
D - Restaurant Queue

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君はAtCoderレストランの前の待ち行列の管理をしたいです。はじめ、待ち行列に並んでいる人はいません。 また、待ち行列に並ぶ人は必ず注文する料理のメニュー番号が書かれた食券を持って並びます。

Q 個のクエリが与えられるので順に処理してください。クエリは 2 種類あり、以下のいずれかの形式で与えられます。

  • 1 X: 待ち行列の末尾に 1 人並ぶ。このとき並ぶ人はメニュー番号が X の食券を持って並ぶ。
  • 2: 待ち行列の先頭にいる人をレストランに案内する。このとき案内される人が持っている食券のメニュー番号を出力する。

制約

  • 1 \leq Q \leq 100
  • 1 \leq X \leq 100
  • 2 つ目の形式のクエリについて、案内する前に待ち行列に並んでいる人がいる
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 X

2

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

入力例 1

6
1 3
1 1
1 15
2
1 3
2

出力例 1

3
1

はじめ、待ち行列に並んでいる人はいません。

  • 1 つ目のクエリについて、メニュー番号が 3 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3 です。
  • 2 つ目のクエリについて、メニュー番号が 1 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3,1 です。
  • 3 つ目のクエリについて、メニュー番号が 15 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3,1,15 です。
  • 4 つ目のクエリについて、待ち行列の先頭にいる人をレストランに案内します。案内する人はメニュー番号が 3 の食券を持っているので 3 を出力します。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 1,15 です。
  • 5 つ目のクエリについて、メニュー番号が 3 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 1,15,3 です。
  • 6 つ目のクエリについて、待ち行列の先頭にいる人をレストランに案内します。案内する人はメニュー番号が 1 の食券を持っているので 1 を出力します。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 15,3 です。

入力例 2

7
1 3
1 1
1 4
1 1
1 5
1 9
1 2

出力例 2



2 つ目の形式のクエリがないことがあることに注意してください。






Score : 200 points







Problem Statement
Takahashi wants to manage the waiting line in front of the AtCoder Restaurant. Initially, the waiting line is empty. Each person who joins the line holds a meal ticket with the menu number of the dish they will order.


Process Q queries in order. There are two types of queries, given in the following formats:


    

  • 1 X: One person joins the end of the waiting line holding a ticket with menu number X.
    • 

  • 2: Takahashi guides the person at the front of the waiting line into the restaurant. Print the menu number on that person’s ticket.
    • 












Constraints
    

  • 1 \leq Q \leq 100
    • 

  • 1 \leq X \leq 100
    • 

  • For each query of the second type, there is at least one person in the line before guiding.
    • 

  • All input values are integers.
    • 
















Input
The input is given from Standard Input in the following format:


Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q



Each query has one of the following two formats:


1 X



2












Output
For each query, print the answer as specified in the problem statement, each on its own line.















Sample Input 1
6
1 3
1 1
1 15
2
1 3
2












Sample Output 1
3
1



Initially, the waiting line is empty.


    

  • For the first query, a person holding a ticket with menu number 3 joins the end of the line. The sequence of menu numbers held by people in line from front to back is 3.
    • 

  • For the second query, a person holding a ticket with menu number 1 joins the end of the line. The sequence becomes 3,1.
    • 

  • For the third query, a person holding a ticket with menu number 15 joins the end of the line. The sequence becomes 3,1,15.
    • 

  • For the fourth query, guide the person at the front into the restaurant. That person holds menu number 3, so print 3. The sequence becomes 1,15.
    • 

  • For the fifth query, a person holding a ticket with menu number 3 joins the end of the line. The sequence becomes 1,15,3.
    • 

  • For the sixth query, guide the person at the front into the restaurant. That person holds menu number 1, so print 1. The sequence becomes 15,3.
    • 














Sample Input 2
7
1 3
1 1
1 4
1 1
1 5
1 9
1 2












Sample Output 2


Note that there may be no queries of the second type.






			


			
		

	
		

		

			E - Rotate and Palindrome
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 300 点







問題文
長さ N の文字列 S が与えられます。S_i\ (1\leq i \leq N) を S の左から i 番目の文字とします。


あなたは以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことができます。


    

  • 

    A 円払う。 S の左端の文字を右端に移動する。すなわち、S_1S_2\ldots S_N を S_2\ldots S_NS_1 に変える。
    

    • 

  • 

    B 円払う。 1 以上 N 以下の整数 i を選び、 S_i を好きな英小文字で置き換える。
    

    • 



S を回文にするためには最低で何円必要ですか？


回文とは
ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 T は回文です。













制約
    

  • 1\leq N \leq 5000
    • 

  • 1\leq A,B\leq 10^9
    • 

  • S は英小文字からなる長さ N の文字列
    • 

  • S 以外の入力は全て整数
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N A B
S












出力
答えを整数として出力せよ。















入力例 1
5 1 2
rrefa












出力例 1
3



最初に 2 番目の操作を 1 回行います。2 円払い、i=5 として S_5 を e で置き換えます。 S は rrefe となります。


次に 1 番目の操作を 1 回行います。1 円払い、S は refer となります。これは回文です。


よって 3 円払うことで S を回文にすることができました。 2 円以下払うことで S を回文にすることは不可能なので、これが答えです。













入力例 2
8 1000000000 1000000000
bcdfcgaa












出力例 2
4000000000



答えは 32 bit 整数に収まらない場合があることに注意してください。






Score : 300 points







Problem Statement
You are given a string S of length N.  Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.


You may perform the following two kinds of operations zero or more times in any order:


    

  • 

    Pay A yen (the currency in Japan).  Move the leftmost character of S to the right end.  In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.
    

    • 

  • 

    Pay B yen.  Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.
    

    • 



How many yen do you need to pay to make S a palindrome?


What is a palindrome?
A string T is a palindrome if and only if the i-th character from the left and the i-th character from the right are the same for all integers i (1 \le i \le |T|), where |T| is the length of T.













Constraints
    

  • 1\leq N \leq 5000
    • 

  • 1\leq A,B\leq 10^9
    • 

  • S is a string of length N consisting of lowercase English letters.
    • 

  • All values in the input except for S are integers.
    • 
















Input
The input is given from Standard Input in the following format:


N A B
S












Output
Print the answer as an integer.















Sample Input 1
5 1 2
rrefa












Sample Output 1
3



First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e.  S is now rrefe.


Then, pay 1 yen to perform the operation of the first kind once.  S is now refer, which is a palindrome.


Thus, you can make S a palindrome for 3 yen.  Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.













Sample Input 2
8 1000000000 1000000000
bcdfcgaa












Sample Output 2
4000000000



Note that the answer may not fit into a 32-bit integer type.






			


			
		

	
		

		

			F - Flavors
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 300 点







問題文
N カップのアイスクリームがあります。

i カップ目の味は F_i 、美味しさは S_i ( S_i は偶数 ) です。  


あなたは、 N 個のカップの中から 2 つを選んで食べることにしました。

このときの満足度は次のように定義されます。  


    

  • 食べたアイスクリームの美味しさを s,t ( 但し、 s \ge t ) とする。
      

    • 2 つのカップの味が異なるなら、満足度は \displaystyle s+t である。
      • 

    • そうでないなら、満足度は \displaystyle s + \frac{t}{2} である。
      • 

    

    • 



満足度として達成可能な最大値を求めてください。











制約
    

  • 入力は全て整数
    • 

  • 2 \le N \le 3 \times 10^5
    • 

  • 1 \le F_i \le N
    • 

  • 2 \le S_i \le 10^9
    • 

  • S_i は偶数
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N
F_1 S_1
F_2 S_2
\vdots
F_N S_N













出力
答えを整数として出力せよ。















入力例 1
4
1 4
2 10
2 8
3 6













出力例 1
16




2 カップ目と 4 カップ目のアイスを食べることを考えます。  


    

  • 2 カップ目の味は 2 、美味しさは 10 です。
    • 

  • 4 カップ目の味は 3 、美味しさは 6 です。
    • 

  • 両者の味は異なるので、満足度は 10+6=16 です。
    • 



以上より、満足度 16 を達成できます。

満足度を 16 より大きくすることはできません。













入力例 2
4
4 10
3 2
2 4
4 12













出力例 2
17




1 カップ目と 4 カップ目のアイスを食べることを考えます。  


    

  • 1 カップ目の味は 4 、美味しさは 10 です。
    • 

  • 4 カップ目の味は 4 、美味しさは 12 です。
    • 

  • 両者の味は同じなので、満足度は 12+\frac{10}{2}=17 です。
    • 



以上より、満足度 17 を達成できます。

満足度を 17 より大きくすることはできません。






Score : 300 points







Problem Statement
We have N cups of ice cream.

The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).  


You will choose and eat two of the N cups.

Your satisfaction here is defined as follows.


    

  • Let s and t (s \ge t) be the deliciousness of the eaten cups.
      

    • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
      • 

    • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.
      • 

    

    • 



Find the maximum achievable satisfaction.











Constraints
    

  • All input values are integers.
    • 

  • 2 \le N \le 3 \times 10^5
    • 

  • 1 \le F_i \le N
    • 

  • 2 \le S_i \le 10^9
    • 

  • S_i is even.
    • 
















Input
Input is given from Standard Input in the following format:


N
F_1 S_1
F_2 S_2
\vdots
F_N S_N













Output
Print the answer as an integer.















Sample Input 1
4
1 4
2 10
2 8
3 6













Sample Output 1
16




Consider eating the second and fourth cups.  


    

  • The second cup has a flavor of 2 and deliciousness of 10.
    • 

  • The fourth cup has a flavor of 3 and deliciousness of 6.
    • 

  • Since they have different flavors, your satisfaction is 10+6=16.
    • 



Thus, you can achieve the satisfaction of 16.

You cannot achieve a satisfaction greater than 16.













Sample Input 2
4
4 10
3 2
2 4
4 12













Sample Output 2
17




Consider eating the first and fourth cups.  


    

  • The first cup has a flavor of 4 and deliciousness of 10.
    • 

  • The fourth cup has a flavor of 4 and deliciousness of 12.
    • 

  • Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.
    • 



Thus, you can achieve the satisfaction of 17.

You cannot achieve a satisfaction greater than 17.






			


			
		

	
		

		

			G - 183183
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 400 点







問題文
正整数 x,y に対して f(x,y) を以下のように定義します。


    

  • 先頭に余分な 0 を付けない十進表記の x,y をそれぞれ文字列として解釈しこの順に連結して得られる文字列を S としたときの、 S を十進表記の整数として解釈した値。
    • 



例えば f(12,3) = 123 、f(100,40)=10040 です。


正整数 N,M と長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。


以下の条件を全て満たす整数の組 (i,j) の個数を求めてください。


    

  • 1\le i,j\le N
    • 

  • f(A_i,A_j) は M の倍数
    • 












制約
    

  • 1\le N\le 2\times 10^5
    • 

  • 1\le M\le 10^9
    • 

  • 1\le A_i\le 10^9
    • 

  • 入力される値は全て整数
    • 
















入力
入力は以下の形式で標準入力から与えられる。


N M
A_1 A_2 \ldots A_N













出力
条件を全て満たす整数の組 (i,j) の個数を出力せよ。















入力例 1
2 11
2 42













出力例 1
2




    

  • (i,j)=(1,1) のとき： f(A_1,A_1)=22 は 11 の倍数です。
    • 

  • (i,j)=(1,2) のとき： f(A_1,A_2)=242 は 11 の倍数です。
    • 

  • (i,j)=(2,1) のとき： f(A_2,A_1)=422 は 11 の倍数ではありません。
    • 

  • (i,j)=(2,2) のとき： f(A_2,A_2)=4242 は 11 の倍数ではありません。
    • 



以上より、条件を全て満たす整数の組は (i,j)=(1,1),(1,2) の 2 つです。したがって、 2 を出力してください。













入力例 2
4 7
2 8 16 183













出力例 2
4















入力例 3
5 5
1000000000 1000000000 1000000000 1000000000 1000000000













出力例 3
25















入力例 4
12 13
80 68 862370 82217 8 56 5 168 672624 6 286057 11864













出力例 4
10







Score : 400 points







Problem Statement
For positive integers x,y, define f(x,y) as follows:


    

  • The value obtained by interpreting x,y in decimal notation without leading zeros as strings, concatenating them in this order to obtain a string S, and then interpreting S as an integer in decimal notation.
    • 



For example, f(12,3) = 123 and f(100,40)=10040.


You are given positive integers N,M and a sequence of N positive integers A=(A_1,A_2,\ldots,A_N).


Find the number of pairs of integers (i,j) that satisfy all of the following conditions.


    

  • 1\le i,j\le N
    • 

  • f(A_i,A_j) is a multiple of M.
    • 












Constraints
    

  • 1\le N\le 2\times 10^5
    • 

  • 1\le M\le 10^9
    • 

  • 1\le A_i\le 10^9
    • 

  • All input values are integers.
    • 
















Input
The input is given from Standard Input in the following format:


N M
A_1 A_2 \ldots A_N













Output
Output the number of pairs of integers (i,j) that satisfy all the conditions.















Sample Input 1
2 11
2 42













Sample Output 1
2




    

  • When (i,j)=(1,1): f(A_1,A_1)=22 is a multiple of 11.
    • 

  • When (i,j)=(1,2): f(A_1,A_2)=242 is a multiple of 11.
    • 

  • When (i,j)=(2,1): f(A_2,A_1)=422 is not a multiple of 11.
    • 

  • When (i,j)=(2,2): f(A_2,A_2)=4242 is not a multiple of 11.
    • 



From the above, the pairs of integers that satisfy all the conditions are (i,j)=(1,1),(1,2), which is two pairs. Thus, output 2.













Sample Input 2
4 7
2 8 16 183













Sample Output 2
4















Sample Input 3
5 5
1000000000 1000000000 1000000000 1000000000 1000000000













Sample Output 3
25















Sample Input 4
12 13
80 68 862370 82217 8 56 5 168 672624 6 286057 11864













Sample Output 4
10