A - Task Failed Successfully

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は N 日間のタスク目標を設定しました。

高橋君は i (1 \leq i \leq N) 日目に A_i 個のタスクを完了することを目標としており、実際には B_i 個のタスクを完了しました。

高橋君が目標より多くのタスクを完了した日数を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq A_i, B_i \leq 100
  • 入力される値はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ。

入力例 1

4
2 8
5 5
5 4
6 7

出力例 1

2

高橋君は 1 日目と 4 日目に目標より多くのタスクを完了しました。

入力例 2

5
1 1
1 1
1 1
1 1
1 1

出力例 2

0

入力例 3

6
1 6
2 5
3 4
4 3
5 2
6 1

出力例 3

3

Score : 100 points

Problem Statement

Takahashi set task goals for N days.

He aimed to complete A_i tasks on day i (1 \leq i \leq N), and actually completed B_i tasks.

Find the number of days when he completed more tasks than his goal.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i, B_i \leq 100
  • All input values are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer.

Sample Input 1

4
2 8
5 5
5 4
6 7

Sample Output 1

2

Takahashi completed more tasks than his goal on the 1st and 4th days.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

0

Sample Input 3

6
1 6
2 5
3 4
4 3
5 2
6 1

Sample Output 3

3
B - Handmaid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある人物の名前 S が与えられます。S の先頭の文字は英大文字であり、先頭以外の文字は英小文字です。

この人物の侍女の名前は、S の頭文字を英小文字に直し、先頭に Of をつけて得られる文字列です。この侍女の名前を答えてください。

制約

  • S は長さ 1 以上 10 以下の文字列
  • S の先頭の文字は英大文字
  • S の先頭以外の文字は英小文字

入力

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

S

出力

答えを 1 行に出力せよ。

入力例 1

Glen

出力例 1

Ofglen

Glen の頭文字を英小文字に直すと glen となり、さらに先頭に Of をつけると Ofglen となります。

入力例 2

I

出力例 2

Ofi

入力例 3

Fred

出力例 3

Offred

Score : 100 points

Problem Statement

You are given the name S of a certain person. The first character of S is an uppercase English letter, and the other characters are lowercase English letters.

The name of this person's handmaid is the string obtained by converting the first letter of S to lowercase and adding Of to the beginning. Find the name of this handmaid.

Constraints

  • S is a string of length between 1 and 10, inclusive.
  • The first character of S is an uppercase English letter.
  • The characters of S other than the first are lowercase English letters.

Input

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

S

Output

Output the answer on one line.

Sample Input 1

Glen

Sample Output 1

Ofglen

Converting the first letter of Glen to lowercase gives glen, and adding Of to the beginning gives Ofglen.

Sample Input 2

I

Sample Output 2

Ofi

Sample Input 3

Fred

Sample Output 3

Offred
C - Substring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

  • S は英小文字からなる長さ 1 以上 100 以下の文字列

入力

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

S

出力

答えを出力せよ。

入力例 1

yay

出力例 1

5

S の空でない部分文字列は以下の 5 種類です。

  • a
  • y
  • ay
  • ya
  • yay

入力例 2

aababc

出力例 2

17

入力例 3

abracadabra

出力例 3

54

Score: 200 points

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

  • S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

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

S

Output

Print the answer.

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

  • a
  • y
  • ay
  • ya
  • yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54
D - Which is ahead?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人が 1 列に並んでおり、前から i 番目に並んでいる人は人 P_i です。

Q 個のクエリを処理して下さい。i 番目のクエリは以下のものです。

  • 整数 A_i,B_i が与えられる。人 A_i と人 B_i のうち、より前に並んでいる人の番号を出力せよ。

制約

  • 入力は全て整数
  • 1\leq N\leq 100
  • 1\leq P_i\leq N
  • P_i \neq P_j\ (i\neq j)
  • 1\leq Q \leq 100
  • 1\leq A_i<B_i\leq N

入力

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

N
P_1 \ldots P_N
Q
A_1 B_1
\vdots
A_Q B_Q

出力

Q 行出力せよ。i 行目には、i 番目のクエリの答えを出力せよ。

入力例 1

3
2 1 3
3
2 3
1 2
1 3

出力例 1

2
2
1

1 番目のクエリでは、人 2 は前から 1 番目、人 3 は前から 3 番目なので、人 2 がより前にいます。

2 番目のクエリでは、人 1 は前から 2 番目、人 2 は前から 1 番目なので、人 2 がより前にいます。

3 番目のクエリでは、人 1 は前から 2 番目、人 3 は前から 3 番目なので、人 1 がより前にいます。

入力例 2

7
3 7 2 1 6 5 4
13
2 3
1 2
1 3
3 6
3 7
2 4
3 7
1 3
4 7
1 6
2 4
1 3
1 3

出力例 2

3
2
3
3
3
2
3
3
7
1
2
3
3

Score: 200 points

Problem Statement

There are N people standing in a line. The person standing at the i-th position from the front is person P_i.

Process Q queries. The i-th query is as follows:

  • You are given integers A_i and B_i. Between person A_i and person B_i, print the person number of the person standing further to the front.

Constraints

  • All inputs are integers.
  • 1 \leq N \leq 100
  • 1 \leq P_i \leq N
  • P_i \neq P_j\ (i \neq j)
  • 1 \leq Q \leq 100
  • 1 \leq A_i < B_i \leq N

Input

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

N
P_1 \ldots P_N
Q
A_1 B_1
\vdots
A_Q B_Q

Output

Print Q lines. The i-th line should contain the response for the i-th query.

Sample Input 1

3
2 1 3
3
2 3
1 2
1 3

Sample Output 1

2
2
1

In the first query, person 2 is at the first position from the front, and person 3 is at the third position, so person 2 is further to the front.

In the second query, person 1 is at the second position from the front, and person 2 is at the first position, so person 2 is further to the front.

In the third query, person 1 is at the second position from the front, and person 3 is at the third position, so person 1 is further to the front.

Sample Input 2

7
3 7 2 1 6 5 4
13
2 3
1 2
1 3
3 6
3 7
2 4
3 7
1 3
4 7
1 6
2 4
1 3
1 3

Sample Output 2

3
2
3
3
3
2
3
3
7
1
2
3
3
E - Max Ai+Bj

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

長さ N の整数列 A,B が与えられます。1 以上 N 以下の整数 i,j を選んで、 A_i + B_j の値を最大化してください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9\,(i=1,2,\dots,N)
  • |B_j| \leq 10^9\,(j=1,2,\dots,N)
  • 入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

A_i + B_j の最大値を出力せよ。

入力例 1

2
-1 5
3 -7

出力例 1

8

(i,j)=(1,1),(1,2),(2,1),(2,2) に対する A_i+B_j の値はそれぞれ 2,-8,8,-2 であり、(i,j)=(2,1) が最大値 8 を達成します。

入力例 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

出力例 2

33

Score : 250 points

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9 (i=1,2,\dots,N)
  • |B_j| \leq 10^9 (j=1,2,\dots,N)
  • All input values are integers.

Input

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the maximum possible value of A_i + B_j.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33