Tenka1 Programmer Beginner Contest

A - Accepted...?

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

すぬけ君はあるプログラミングコンテストのために、6 問の問題を用意しました。りんごさんはすぬけ君の用意した各問題についてそれぞれ、プログラミングコンテストに採用するかどうかを決めました。

長さ 6 の文字列 S の i 文字目が 1 ならすぬけ君の用意した i 問目の問題が採用されたことを、0 なら採用されなかったことを表します。

すぬけ君が用意した問題の中で、プログラミングコンテストに採用された問題は何問あるでしょうか。

制約

S の長さは 6 である
S は 0 と 1 のみからなる

入力

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

出力

すぬけ君が用意した問題のうち、プログラミングコンテストに採用された問題の数を出力せよ。

入力例 1

出力例 1

1,2,3,4 問目の合計 4 問が採用されました。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 100 points

Problem Statement

Snuke prepared 6 problems for a upcoming programming contest. For each of those problems, Rng judged whether it can be used in the contest or not.

You are given a string S of length 6. If the i-th character of s is 1, it means that the i-th problem prepared by Snuke is accepted to be used; 0 means that the problem is not accepted.

How many problems prepared by Snuke are accepted to be used in the contest?

Constraints

The length of S is 6.
S consists of 0 and 1.

Inputs

Input is given from Standard Input in the following format:

Outputs

Print the number of problems prepared by Snuke that are accepted to be used in the contest.

Sample Input 1

Sample Output 1

The first, second, third and fourth problems are accepted, for a total of four.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

B - Different Distribution

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 200 点

問題文

何人かの人がゲームをしました。全ての人の点数は異なる非負整数でした。

高橋君は、N 個の情報を持っています。i 個目の情報は、得点の大きいほうから A_i 番目の人の得点が B_i 点であったことを表します。

ゲームの参加人数としてありうる最大値を求めてください。

制約

1 \leq N \leq 10^5
1 \leq A_i \leq 10^9(1\leq i\leq N)
0 \leq B_i \leq 10^9(1\leq i\leq N)
i ≠ j ならば A_i ≠ A_j
与えられる条件すべてを満たす得点の組が存在することが保障される
入力は全て整数である

入力

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

N
A_1 B_1
:
A_N B_N

出力

ゲームの参加人数としてありうる最大値を出力せよ。

入力例 1

出力例 1

点数が大きいほうから順に 12,9,8,7,5,2,1,0 点である状況が、参加人数の最大値を達成する一例です。

入力例 2

出力例 2

入力例 3

2
1 1000000000
1000000000 1

出力例 3

1000000001

Score : 200 points

Problem Statement

A group of people played a game. All players had distinct scores, which are positive integers.

Takahashi knows N facts on the players' scores. The i-th fact is as follows: the A_i-th highest score among the players is B_i.

Find the maximum possible number of players in the game.

Constraints

1 \leq N \leq 10^5
1 \leq A_i \leq 10^9(1\leq i\leq N)
0 \leq B_i \leq 10^9(1\leq i\leq N)
If i ≠ j, A_i ≠ A_j.
There exists a possible outcome of the game that are consistent with the facts.
All input values are integers.

Inputs

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_N B_N

Outputs

Print the maximum possible number of players in the game.

Sample Input 1

Sample Output 1

The maximum possible number of players is achieved when, for example, the players have the following scores: 12,9,8,7,5,2,1,0.

Sample Input 2

Sample Output 2

Sample Input 3

2
1 1000000000
1000000000 1

Sample Output 3

1000000001

C - 4/N

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

整数 N が与えられる。

4/N = 1/h + 1/n + 1/w を満たす正整数 h, n, w を求めよ。

条件を満たす解が複数ある場合、どれを出力しても良い。

制約

N に対して h, n, w \leq 3500 となる解が存在することが保証される。

入力

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

出力

条件を満たす正整数 h, n, w の組を空白区切りで１つ出力せよ。

h n w

入力例 1

出力例 1

1 2 2

4/2 = 1/1 + 1/2 + 1/2である。

入力例 2

出力例 2

872 1012974 1539173474040

解として3500を超える整数を使っても良い。

入力例 3

出力例 3

3498 3498 3498

Score : 300 points

Problem Statement

You are given an integer N.

Find a triple of positive integers h, n and w such that 4/N = 1/h + 1/n + 1/w.

If there are multiple solutions, any of them will be accepted.

Constraints

It is guaranteed that, for the given integer N, there exists a solution such that h,n,w \leq 3500.

Inputs

Input is given from Standard Input in the following format:

Outputs

Print a triple of positive integers h, n and w that satisfies the condition, in the following format:

h n w

Sample Input 1

Sample Output 1

1 2 2

4/2 = 1/1 + 1/2 + 1/2.

Sample Input 2

Sample Output 2

872 1012974 1539173474040

It is allowed to use an integer exceeding 3500 in a solution.

Sample Input 3

Sample Output 3

3498 3498 3498

D - IntegerotS

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 500 点

問題文

非負整数専門店「せいすうや」には、N 個の非負整数が売られています。i 個目の非負整数は A_i で、その価値は B_i です。価値の異なる同じ非負整数が複数売られていることもあります。

高橋君は、「せいすうや」でいくつかの整数を買うことにしました。高橋君は、買う整数たちの bitwise or が K 以下になるような任意の組み合わせで、整数を買うことができます。高橋君は、買った整数たちの価値の総和をできるだけ大きくしたいです。

高橋君が達成できる、価値の総和の最大値を求めてください。ただし、bitwise or とは、ビットごとの論理和を表します。

制約

1 \leq N \leq 10^5
0 \leq K < 2^{30}
0 \leq A_i < 2^{30}(1\leq i\leq N)
1 \leq B_i \leq 10^9(1\leq i\leq N)
入力は全て整数である

入力

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

N K
A_1 B_1
:
A_N B_N

出力

高橋君が達成できる価値の総和の最大値を出力せよ。

入力例 1

出力例 1

2 と 3 を購入することで、最大値 8 を達成できます。

入力例 2

出力例 2

2 と 4 を購入することで、最大値 9 を達成できます。

入力例 3

出力例 3

Score : 500 points

Problem Statement

Seisu-ya, a store specializing in non-negative integers, sells N non-negative integers. The i-th integer is A_i and has a utility of B_i. There may be multiple equal integers with different utilities.

Takahashi will buy some integers in this store. He can buy a combination of integers whose bitwise OR is less than or equal to K. He wants the sum of utilities of purchased integers to be as large as possible.

Find the maximum possible sum of utilities of purchased integers.

Constraints

1 \leq N \leq 10^5
0 \leq K < 2^{30}
0 \leq A_i < 2^{30}(1\leq i\leq N)
1 \leq B_i \leq 10^9(1\leq i\leq N)
All input values are integers.

Inputs

Input is given from Standard Input in the following format:

N K
A_1 B_1
:
A_N B_N

Outputs

Print the maximum possible sum of utilities of purchased integers.

Sample Input 1

Sample Output 1

Buy 2 and 3 to achieve the maximum possible total utility, 8.

Sample Input 2

Sample Output 2

Buy 2 and 4 to achieve the maximum possible total utility, 9.

Sample Input 3