Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
ABC 国の消費税率は 8 パーセントです。
ABC 国にはエナジードリンク屋さんがあります。ここでは、エナジードリンク 1 本を、税抜き N 円で販売しています。
ここに消費税を加算した後の金額は \lfloor 1.08 \times N \rfloor 円となります。ただし、実数 x に対し、\lfloor x \rfloor は x 以下の最大の整数を表します。
この金額が定価の 206 円より安いなら Yay! 、定価と等しいなら so-so 、定価より高いなら :( と出力して下さい。
制約
- 1 \le N \le 300
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
180
出力例 1
Yay!
N=180 であるとき、税込価格は \lfloor 180 \times 1.08 \rfloor = 194 円ですが、この金額は定価の 206 円より安いです。
入力例 2
200
出力例 2
:(
入力例 3
191
出力例 3
so-so
この場合、税込価格がちょうど定価の 206 円と一致します。
Score : 100 points
Problem Statement
The consumption tax rate in the Republic of AtCoder is 8 percent.
An energy drink shop in this country sells one can of energy drink for N yen (Japanese currency) without tax.
Including tax, it will be \lfloor 1.08 \times N \rfloor yen, where \lfloor x \rfloor denotes the greatest integer not exceeding x for a real number x.
If this tax-included price is lower than the list price of 206 yen, print Yay!; if it is equal to the list price, print so-so; if it is higher than the list price, print :(.
Constraints
- 1 \le N \le 300
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
180
Sample Output 1
Yay!
For N=180, the tax-included price is \lfloor 180 \times 1.08 \rfloor = 194 yen, which is lower than the list price of 206 yen.
Sample Input 2
200
Sample Output 2
:(
Sample Input 3
191
Sample Output 3
so-so
In this case, the tax-included price is exactly equal to the list price of 206 yen.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
シカのAtCoDeerくんは、空の貯金箱を持っています。
AtCoDeerくんは、その貯金箱に、1 日目の朝に 1 円、2 日目の朝に 2 円 \dots というように、i 日目の朝に i 円を貯金箱に入れます。
また、AtCoDeerくんは、毎日夜に貯金箱にいくら入っているかを確認します。
AtCoDeerくんが貯金箱に N 円以上入っていることを初めて確認するのは、何日目の夜でしょうか?
制約
- 1 \le N \le 10^9
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
12
出力例 1
5
- 1 日目の朝に 1 円貯金する。 この日の夜、貯金箱の中身は 1 円である。
- 2 日目の朝に 2 円貯金する。 この日の夜、貯金箱の中身は 3 円である。
- 3 日目の朝に 3 円貯金する。 この日の夜、貯金箱の中身は 6 円である。
- 4 日目の朝に 4 円貯金する。 この日の夜、貯金箱の中身は 10 円である。
- 5 日目の朝に 5 円貯金する。 この日の夜、貯金箱の中身は 15 円である。
よって、AtCoDeerくんが貯金箱に 12 円以上入っていることを初めて確認するのは、 5 日目の夜です。
入力例 2
100128
出力例 2
447
Score : 200 points
Problem Statement
AtCoDeer has an empty piggy bank.
On the morning of the i-th day, he will put i yen (Japanese currency) in it: 1 yen on the morning of the 1-st day, 2 yen on the morning of the 2-nd day, and so on.
Each night, he will check the amount of money in it.
On which day will he find out that his piggy bank has N yen or more for the first time?
Constraints
- 1 \le N \le 10^9
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print an integer x such that AtCoDeer will find out that his piggy bank has N yen or more for the first time on the x-th day.
Sample Input 1
12
Sample Output 1
5
- On the 1-st day, the piggy bank gets 1 yen in the morning and has 1 yen at night.
- On the 2-st day, the piggy bank gets 2 yen in the morning and has 3 yen at night.
- On the 3-rd day, the piggy bank gets 3 yen in the morning and has 6 yen at night.
- On the 4-th day, the piggy bank gets 4 yen in the morning and has 10 yen at night.
- On the 5-th day, the piggy bank gets 5 yen in the morning and has 15 yen at night.
Thus, on the 5-th night, AtCoDeer will find out that his piggy bank has 12 yen or more for the first time.
Sample Input 2
100128
Sample Output 2
447
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の整数からなる配列 A=(A_1,A_2,...,A_N) が与えられるので、次の条件を全て満たす整数組 (i,j) の数を求めてください。
- 1 \le i < j \le N
- A_i \neq A_j
制約
- 入力は全て整数
- 2 \le N \le 3 \times 10^5
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
3 1 7 1
出力例 1
2
この入力では、A=(1,7,1) です。
- 整数組 (1,2) に対して、A_1 \neq A_2 です。
- 整数組 (1,3) に対して、A_1 = A_3 です。
- 整数組 (2,3) に対して、A_2 \neq A_3 です。
入力例 2
10 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
出力例 2
45
入力例 3
20 7 8 1 1 4 9 9 6 8 2 4 1 1 9 5 5 5 3 6 4
出力例 3
173
Score : 300 points
Problem Statement
Given an array of N integers A=(A_1,A_2,...,A_N), find the number of pairs (i,j) of integers satisfying all of the following conditions:
- 1 \le i < j \le N
- A_i \neq A_j
Constraints
- All values in input are integers.
- 2 \le N \le 3 \times 10^5
- 1 \le A_i \le 10^9
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
3 1 7 1
Sample Output 1
2
In this input, we have A=(1,7,1).
- For the pair (1,2), A_1 \neq A_2.
- For the pair (1,3), A_1 = A_3.
- For the pair (2,3), A_2 \neq A_3.
Sample Input 2
10 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
Sample Output 2
45
Sample Input 3
20 7 8 1 1 4 9 9 6 8 2 4 1 1 9 5 5 5 3 6 4
Sample Output 3
173
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 項からなる正整数列 A=(A_1,A_2, \dots A_N) が与えられます。
以下の操作を 0 回以上何度でも行える時、操作を最小何回行えば、A を回文にすることができますか？
- ある正整数の組 (x,y) を選ぶ。その後、現在 A に含まれる x をすべて y に置き換える。
なお、この問題では、全ての整数 i (1 \le i \le N) について、A_i=A_{N+1-i} が成り立つとき、またその時に限って、A が回文であると言います。
制約
- 入力は全て整数
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
8 1 5 3 2 5 2 3 1
出力例 1
2
- はじめ、A=(1,5,3,2,5,2,3,1) です。
- A に含まれる 3 を全て 2 に置き換えると、A=(1,5,2,2,5,2,2,1) となります。
- A に含まれる 2 を全て 5 に置き換えると、A=(1,5,5,5,5,5,5,1) となります。
以上の操作を行うと、A を 2 回の操作で回文にすることができ、これが最小です。
入力例 2
7 1 2 3 4 1 2 3
出力例 2
1
入力例 3
1 200000
出力例 3
0
A がはじめから回文である可能性もあります。
Score : 400 points
Problem Statement
You are given a sequence of N positive integers: A=(A_1,A_2, \dots A_N). You can do the operation below zero or more times. At least how many operations are needed to make A a palindrome?
- Choose a pair (x,y) of positive integers, and replace every occurrence of x in A with y.
Here, we say A is a palindrome if and only if A_i=A_{N+1-i} holds for every i (1 \le i \le N).
Constraints
- All values in input are integers.
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 2 \times 10^5
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
8 1 5 3 2 5 2 3 1
Sample Output 1
2
- Initially, we have A=(1,5,3,2,5,2,3,1).
- After replacing every occurrence of 3 in A with 2, we have A=(1,5,2,2,5,2,2,1).
- After replacing every occurrence of 2 in A with 5, we have A=(1,5,5,5,5,5,5,1).
In this way, we can make A a palindrome in two operations, which is the minimum needed.
Sample Input 2
7 1 2 3 4 1 2 3
Sample Output 2
1
Sample Input 3
1 200000
Sample Output 3
0
A may already be a palindrome in the beginning.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
整数 L,R\ (L \le R) が与えられるので、以下の条件を全て満たす整数組 (x,y) の数を求めてください。
- L \le x,y \le R
- g を x,y の最大公約数とすると、以下が成立する。
- g \neq 1 かつ \frac{x}{g} \neq 1 かつ \frac{y}{g} \neq 1
制約
- 入力は全て整数
- 1 \le L \le R \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
L R
出力
答えを整数として出力せよ。
入力例 1
3 7
出力例 1
2
いくつかの整数組を例として示します。
- (x,y)=(4,6) は条件を満たします。
- (x,y)=(7,5) は g=1 となり、条件に違反します。
- (x,y)=(6,3) は \frac{y}{g}=1 となり、条件に違反します。
条件を満たすのは (x,y)=(4,6),(6,4) の 2 組です。
入力例 2
4 10
出力例 2
12
入力例 3
1 1000000
出力例 3
392047955148
Score : 500 points
Problem Statement
Given integers L and L,R\ (L \le R), find the number of pairs (x,y) of integers satisfying all of the conditions below:
- L \le x,y \le R
- Let g be the greatest common divisor of x and y. Then, the following holds.
- g \neq 1, \frac{x}{g} \neq 1, and \frac{y}{g} \neq 1.
Constraints
- All values in input are integers.
- 1 \le L \le R \le 10^6
Input
Input is given from Standard Input in the following format:
L R
Output
Print the answer as an integer.
Sample Input 1
3 7
Sample Output 1
2
Let us take some number of pairs of integers, for example.
- (x,y)=(4,6) satisfies the conditions.
- (x,y)=(7,5) has g=1 and thus violates the condition.
- (x,y)=(6,3) has \frac{y}{g}=1 and thus violates the condition.
There are two pairs satisfying the conditions: (x,y)=(4,6),(6,4).
Sample Input 2
4 10
Sample Output 2
12
Sample Input 3
1 1000000
Sample Output 3
392047955148
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
T 個のテストケースについて、以下の問題を解いてください。
N 個の半開区間 [L_i,R_i) (1 \le i \le N) があり、 Alice と Bob がこの区間を使って次のようなゲームをします。
- Alice から始めて、以下の操作を交互に行う。
- N 個の区間の中から、既に選ばれているどの区間とも共有点をもたない区間を 1 つ選ぶ。
先に操作を行えなくなった方が負けで、もう片方のプレイヤーが勝ちます。
双方のプレイヤーが勝利に対して最善を尽くした場合、どちらが勝つことになりますか？
半開区間とは？
半開区間 [X,Y) とは、 X 以上 Y 未満のすべての実数からなる区間です。制約
- 入力は全て整数
- 1 \le T \le 20
- 1 \le N \le 100
- 1 \le L_i < R_i \le 100
入力
入力は標準入力から与えられる。入力の 1 行目は次の形式である。
T
その後、T 個のテストケースが続く。各テストケースは以下の形式で与えられる。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
計 T 行出力せよ。
そのうち i 行目には、 i 番目のテストケースについて、 Alice が勝つなら Alice 、 Bob が勝つなら Bob と出力せよ。
入力例 1
5 3 53 98 8 43 12 53 10 4 7 5 7 3 7 4 5 5 8 6 9 4 8 5 10 1 9 5 10 2 58 98 11 29 6 79 83 44 83 38 74 49 88 18 45 64 99 1 5 9
出力例 1
Bob Alice Bob Alice Alice
この入力には、 5 つのテストケースが含まれます。
1 つ目のテストケースについて、例えば以下のようにゲームが進行します。
- Alice が区間 [12,53) を選択する。
- Bob が区間 [53,98) を選択する。 ゲームに用いる区間は半開区間なので、 [12,53),[53,98) は共有点を持たない。
- Alice はこれ以上操作を行えず、負ける。 Bob はゲームに勝つ。
このテストケースについて、上記の手順が必ずしも両者にとって最善とは限りませんが、両者が最善を尽くした場合勝利するのは Bob であることが示せます。
2 つ目のテストケースのように、ひとつのテストケースに同じ区間が複数含まれる場合もあります。
Score : 600 points
Problem Statement
Solve the problem below for T test cases.
We have N half-open intervals [L_i,R_i) (1 \le i \le N). Using them, Alice and Bob will play the following game:
- Alice and Bob alternately do the following operation, Alice going first.
- From the N intervals, choose one that does not intersect with any of the intervals that are already chosen.
The player who gets unable to do the operation loses, and the other player wins.
Which player will win if both players play optimally to win?
What is a half-open interval?
A half-open interval [X,Y) is an interval consisting of all real numbers x satisfying X \leq x < Y.Constraints
- All values in input are integers.
- 1 \le T \le 20
- 1 \le N \le 100
- 1 \le L_i < R_i \le 100
Input
Input is given from Standard Input. The first line is in the following format:
T
Then, T test cases follow, each of which is in the following format:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
Print T lines.
The i-th line should contain Alice if Alice wins in the i-th test case, and Bob if Bob wins.
Sample Input 1
5 3 53 98 8 43 12 53 10 4 7 5 7 3 7 4 5 5 8 6 9 4 8 5 10 1 9 5 10 2 58 98 11 29 6 79 83 44 83 38 74 49 88 18 45 64 99 1 5 9
Sample Output 1
Bob Alice Bob Alice Alice
This input contains five test cases.
For the first test case, we will show one possible progression of the game below.
- Alice chooses the interval [12,53).
- Bob chooses the interval [53,98). Note that [12,53) and [53,98) do not intersect since they are half-open.
- Alice is unable to do an operation, and Bob wins.
These moves may not be the best choices for them, but we can show that Bob will win if both play optimally.
As seen in the second test case, there can be multiple occurrences of the same interval within a test case.