Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
正整数 N が与えられます。
1 以上 N 以下の整数をすべて足し合わせた値 1+2+\cdots+N を出力してください。
制約
- 1 \leq N \leq 100
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
1 以上 N 以下の整数をすべて足し合わせた値を出力せよ。
入力例 1
5
出力例 1
15
1+2+3+4+5=15 のため、15 を出力します。
入力例 2
1
出力例 2
1
入力例 3
29
出力例 3
435
Score : 100 points
Problem Statement
You are given a positive integer N.
Output the sum of all integers from 1 to N, that is, 1+2+\cdots+N.
Constraints
- 1 \leq N \leq 100
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Output the sum of all integers from 1 to N.
Sample Input 1
5
Sample Output 1
15
Since 1+2+3+4+5=15, output 15.
Sample Input 2
1
Sample Output 2
1
Sample Input 3
29
Sample Output 3
435
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 個の箱が横一列に並んでおり、そのうちのいくつかの箱にはクッキーが入っています。
各箱の状態は長さ N の文字列 S によって表されます。
具体的には、左から i\ (1\leq i\leq N) 番目の箱は、S の i 文字目が @ のときクッキーが 1 枚入っており、. のとき空き箱です。
高橋君は今からの D 日間、一日一回ずつ、これらの箱のいずれかに入ったクッキーを 1 枚選んで食べます。
N 個の箱のうち、D 日間が経過した後に空き箱であるものはいくつあるか求めてください。 （この値は高橋君が各日でどのクッキーを選ぶかによらないことが証明できます。）
なお、S には @ が D 個以上含まれることが保証されます。
制約
- 1\leq D \leq N \leq 100
- N,D は整数
- S は
@と.からなる長さ N の文字列 - S には
@が D 個以上含まれる
入力
入力は以下の形式で標準入力から与えられる。
N D S
出力
N 個の箱のうち、D 日間が経過した後に空き箱であるものの個数を出力せよ。
入力例 1
5 2 .@@.@
出力例 1
4
例えば、高橋君は以下のように行動する可能性があります。
- 1 日目：左から 2,3,5 番目の箱にクッキーが入っている。左から 2 番目の箱に入っているクッキーを選んで食べる。
- 2 日目：左から 3,5 番目の箱にクッキーが入っている。左から 5 番目の箱に入っているクッキーを選んで食べる。
- 2 日間が経過した後、左から 3 番目の箱にのみクッキーが入っている。よって、5 個の箱のうち 4 箱が空き箱である。
高橋君が各日で選ぶクッキーはこの例とは異なる可能性もありますが、いずれにせよ 2 日間が経過した後には 4 箱が空き箱です。 よって答えは 4 です。
入力例 2
3 3 @@@
出力例 2
3
入力例 3
10 4 @@@.@@.@@.
出力例 3
7
Score: 100 points
Problem Statement
There are N boxes arranged in a row, and some of these boxes contain cookies.
The state of these boxes is represented by a string S of length N.
Specifically, the i-th box (1\leq i \leq N) from the left contains one cookie if the i-th character of S is @, and is empty if it is ..
Over the next D days, Takahashi will choose and eat one cookie per day from among the cookies in these boxes.
Determine how many of the N boxes will be empty after D days have passed. (It can be proved that this value does not depend on which cookies Takahashi chooses each day.)
It is guaranteed that S contains at least D occurrences of @.
Constraints
- 1 \leq D \leq N \leq 100
- N and D are integers.
- S is a string of length N consisting of
@and.. - S contains at least D occurrences of
@.
Input
The input is given from Standard Input in the following format:
N D S
Output
Print the number of boxes that will be empty after D days have passed among the N boxes.
Sample Input 1
5 2 .@@.@
Sample Output 1
4
For example, Takahashi might act as follows:
- Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. He chooses the cookie in the 2nd box to eat.
- Day 2: There are cookies in the 3rd and 5th boxes. He chooses the cookie in the 5th box to eat.
- After two days have passed, only the 3rd box from the left contains a cookie. Therefore, four out of the five boxes are empty.
Even though Takahashi might choose differently on each day than in this example, there will still be four empty boxes after two days. Therefore, the answer is 4.
Sample Input 2
3 3 @@@
Sample Output 2
3
Sample Input 3
10 4 @@@.@@.@@.
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
1 から N までの番号がついた N 人の参加者が、1 から M までの番号がついた M 問からなるコンテストに参加します。
1 以上 N 以下の整数 i 、1 以上 M 以下の整数 j について、S_i の j 番目の文字が o のとき参加者 i は問題 j を解くことが可能で、S_i の j 番目の文字が x のとき参加者 i は問題 j を解くことが不可能です。
このコンテストは、二人の参加者でペアを組んで参加します。二人が協力することで M 問全てを解くことが可能であるようなペアの個数を答えてください。
より厳密には、1\leq x < y\leq N を満たす整数の組 (x,y) であって、 1 以上 M 以下の任意の整数 j について、参加者 x か参加者 y の少なくとも一方は問題 j を解くことが可能であるという条件を満たすものの個数を答えてください。
制約
- N は 2 以上 30 以下の整数
- M は 1 以上 30 以下の整数
- S_i は
o,xからなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
5 5 ooooo oooxx xxooo oxoxo xxxxx
出力例 1
5
参加者 1 と 2 のペア、参加者 1 と 3 のペア、参加者 1 と 4 のペア、参加者 1 と 5 のペア、参加者 2 と 3 のペアの 5 個のペアが条件を満たします。
例えば参加者 2 と 4 のペアは、問題 4 が解けないので条件を満たしません。
入力例 2
3 2 ox xo xx
出力例 2
1
入力例 3
2 4 xxxx oxox
出力例 3
0
Score : 200 points
Problem Statement
N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.
For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.
The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.
More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.
Constraints
- N is an integer between 2 and 30, inclusive.
- M is an integer between 1 and 30, inclusive.
- S_i is a string of length M consisting of
oandx.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
5 5 ooooo oooxx xxooo oxoxo xxxxx
Sample Output 1
5
The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.
On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.
Sample Input 2
3 2 ox xo xx
Sample Output 2
1
Sample Input 3
2 4 xxxx oxox
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
キーエンスでは良いことも悪いこともありのままに報告するという文化があります。
そこで、報告内容が元の文章のありのままであるかを確認したいです。
英小文字のみからなる文字列 S, T が与えられます。
S と T が等しいならば 0 を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力してください。
ただし、S,T の一方にのみ i 文字目が存在するときも、i 文字目は異なっているとみなすものとします。
より厳密には、S と T が等しくないならば次の条件のうちいずれかをみたす最小の整数 i を出力してください。
- 1\leq i\leq |S| かつ 1\leq i\leq |T| かつ S_i\neq T_i
- |S|< i\leq |T|
- |T|< i\leq |S|
ただし、|S|,|T| でそれぞれ S,T の長さを、S_i,T_i でそれぞれ S,T の i 文字目を表します。
制約
- S,T は英小文字のみからなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S と T が等しいならば 0 を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力せよ。
入力例 1
abcde abedc
出力例 1
3
S=abcde, T=abedc です。
S と T は 1,2 文字目は等しく、3 文字目が異なるため、 3 を出力します。
入力例 2
abcde abcdefg
出力例 2
6
S=abcde, T=abcdefg です。
S と T は 5 文字目まで等しく、T にのみ 6 文字目が存在するため、6 を出力します。
入力例 3
keyence keyence
出力例 3
0
S と T は等しいため、 0 を出力します。
Score : 200 points
Problem Statement
KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.
You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.
More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:
- 1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
- |S| < i \leq |T|.
- |T| < i \leq |S|.
Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.
Constraints
- S and T are strings 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 T
Output
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Sample Input 1
abcde abedc
Sample Output 1
3
We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.
Sample Input 2
abcde abcdefg
Sample Output 2
6
We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.
Sample Input 3
keyence keyence
Sample Output 3
0
S and T are equal, so print 0.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
414 の十進法での表記は 414 であり、これは回文です。
また、414 の八進法での表記は 636 であり、これも回文です。
これを踏まえて、以下の問題を解いてください。
正の整数 A, N が与えられます。 1 以上 N 以下の整数のうち、十進法での表記も A 進法での表記も回文であるようなものの総和を求めてください。
なお、この問題の制約下で答えは 2^{63} 未満であることが証明できます。
制約
- 2 \leq A \leq 9
- 1 \leq N \le 10^{12}
- 入力される数値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
A N
出力
答えを 1 行で出力せよ。
入力例 1
8 1000
出力例 1
2155
条件を満たす整数は 1,2,3,4,5,6,7,9,121,292,333,373,414,585 の 14 個であり、その総和は 2155 です。
入力例 2
8 999999999999
出力例 2
914703021014
入力例 3
6 999999999999
出力例 3
283958331810
Score : 350 points
Problem Statement
The decimal representation of 414 is 414, which is a palindrome.
Also, the octal representation of 414 is 636, which is also a palindrome.
Based on this, solve the following problem.
You are given positive integers A and N. Find the sum of all integers between 1 and N, inclusive, whose decimal representation and base-A representation are both palindromes.
Under the constraints of this problem, it can be proved that the answer is less than 2^{63}.
Constraints
- 2 \leq A \leq 9
- 1 \leq N \le 10^{12}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A N
Output
Output the answer in one line.
Sample Input 1
8 1000
Sample Output 1
2155
The integers satisfying the condition are 1,2,3,4,5,6,7,9,121,292,333,373,414,585 (14 integers), and their sum is 2155.
Sample Input 2
8 999999999999
Sample Output 2
914703021014
Sample Input 3
6 999999999999
Sample Output 3
283958331810