Time Limit: 2 sec / Memory Limit: 256 MB
問題文
今日の日付は 2015/10/25 です。
この日付を文字列としてみたとき、文字列に含まれる全ての文字（2,0,1,5,/）がちょうど 2 回ずつ現れています。
このように文字列に含まれる全ての文字がちょうど 2 回ずつ現れる文字列を「ダブル文字列」と呼ぶことにします。
あなたは小文字アルファベットのみからなる文字列 S を与えられるので、S に含まれる文字を全て含むようなダブル文字列を 1 つ出力してください。
出力する文字列には S に含まれない文字が含まれていても良いですが、小文字アルファベット以外の文字が含まれてはいけません。
入力
入力は以下の形式で標準入力から与えられる。
S
- 1 行目には、文字列 S (1 ≦ |S| ≦ 10) が与えられる。ただし、|S| は文字列 S の長さを表す。
- S は小文字アルファベットのみからなる。
- 文字列 S に 2 回以上現れるような文字がないことが保証される。
出力
S に含まれる文字を全て含むような小文字アルファベットのみからなるダブル文字列を 1 行に出力せよ。ダブル文字列は複数存在することもあるが、そのうちの 1 つを出力すれば良い。出力の末尾に改行を入れること。
入力例1
on
出力例1
noon
onno、onon、oonn、lemonmelon などの文字列も正解となります。
入力例2
meat
出力例2
teammate
Problem Statement
It is 10/25/2015 today.
This date has an interesting property as a string: all letters contained in this string (1, 0, 2, 5, /) appear exactly twice in this string.
We will call such a string double: a string T is double if and only if any letter that appears at least once in T appears exactly twice in T.
You are given a string S consisting of lowercase alphabets. Construct and print a double string that contains all letters in S.
Your output may contain letters that are not in S, but may not contain letters other than lowercase alphabets.
Input
Input is given from Standard Input in the following format:
S
- The first line contains a string S (1 ≦ |S| ≦ 10).
- S consists of lowercase alphabets.
- No letter appears more than once in S.
Output
Print a double string consisting of lowercase alphabets that contains all letters in S. When there are multiple solutions, any of them will be accepted. Print a newline at the end of output.
Sample Input 1
on
Sample Output 1
noon
These solutions will also be accepted: onno, onon, oonn and lemonmelon.
Sample Input 2
meat
Sample Output 2
teammate
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はテストの結果を採点しています。ところが、高橋君はある問題の正解を忘れてしまいました。この問題は、N 人が解答していて、それぞれの人の答えは 0 以上 M 以下の整数でした。高橋君は、半分を超える人が同じ答えだった場合、それを正解とすることにしました。
N 人のこの問題に対する解答が与えられるので、高橋君は何を正解とするか出力してください。ただし、高橋君が正解を決められない場合、? を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), M (1 ≦ M ≦ 10^5) が空白区切りで与えられる。
- 2 行目には、N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には、i 番目の人の解答を表す整数 A_i (0 ≦ A_i ≦ M) が与えられる。
出力
高橋君が正解とする整数を 1 行に出力せよ。ただし、高橋君が正解を決められない場合、1 行に ? を出力せよ。出力の末尾に改行を入れること。
部分点
この問題には部分点が設定されている。
- N ≦ 100, M ≦ 100 を満たすデータセットに正解した場合は、40 点が与えられる。
- 追加の制約のないデータセットに正解した場合は、上記とは別に 60 点が与えられる。
入力例1
3 2 2 1 2
出力例1
2
入力例2
4 2 2 1 2 1
出力例2
?
入力例3
10 1 0 0 0 0 0 0 1 1 1 1
出力例3
0
入力例4
10 5 0 1 2 3 4 5 5 5 5 5
出力例4
?
Problem Statement
Mr. Takahashi is marking examination papers of his students. Unfortunately, he has forgotten the correct answer to a certain question.
N students answered this question by an integer between 0 and M, inclusive. He has decided to assume the correct answer to be the integer X if more than half of the students answered X.
You are given the answers of the N students to this question. If he is going to assume the correct answer to be some integer X, print the value of X. If he is unable to assume the correct answer to be any integer, print ?.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N
- The first line contains two space-separated integers N (1 ≦ N ≦ 10^5) and M (1 ≦ M ≦ 10^5).
- The second line contains N space-separated integers A_1, A_2, ..., A_N. For each i (1 ≦ i ≦ N), A_i (0 ≦ A_i ≦ M) represents the answer of the i^{th} student.
Output
If Mr. Takahashi is going to assume the correct answer to be some integer X, print the value of X in a single line. Otherwise, print ?. Be sure to print a newline at the end of output.
Partial Points
Partial points may be awarded in this problem:
- 40 points will be awarded for passing the test set satisfying N ≦ 100, M ≦ 100.
- Another 60 points will be awarded for passing the test set without additional constraints.
入力例1
3 2 2 1 2
出力例1
2
入力例2
4 2 2 1 2 1
出力例2
?
入力例3
10 1 0 0 0 0 0 0 1 1 1 1
出力例3
0
入力例4
10 5 0 1 2 3 4 5 5 5 5 5
出力例4
?
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は部屋が N 室ある旅館を経営しています。今日は M 組の予約が入っていますが、全ての予約を適切に部屋に割り振ることができるかを確認していませんでした。各予約について、その組の人数以上の定員の部屋を割り振る必要があります。各予約について必ず 1 つの部屋が割り当てられる必要があり、1 つの予約について複数の部屋を割り当てたり、複数の予約を 1 つの部屋に割り当てたりすることはできません。全ての予約に部屋を割り振ることができるならば YES を、割り振ることができないならば NO を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N B_1 B_2 ... B_M
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), M (1 ≦ M ≦ 10^5) が空白区切りで与えられる。
- 2 行目には、N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には、i 番目の部屋の定員を表す整数 A_i (1 ≦ A_i ≦ 10^5) が与えられる。
- 3 行目には、M 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ M) 番目には、i 番目の予約の人数を表す整数 B_i (1 ≦ B_i ≦ 10^5) が与えられる。
出力
全ての予約に部屋を割り振ることができるならば YES を、割り振ることができないならば NO を 1 行に出力せよ。出力の末尾に改行を入れること。
部分点
この問題には部分点が設定されている。
- N ≦ 100, M ≦ 100 を満たすデータセットに正解した場合は、60 点が与えられる。
- 追加の制約のないデータセットに正解した場合は、上記とは別に 40 点が与えられる。
入力例1
3 2 2 2 3 3 1
出力例1
YES
入力例2
3 2 2 2 3 3 3
出力例2
NO
入力例3
3 4 10 10 10 1 1 1 1
出力例3
NO
入力例4
10 10 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1
出力例4
YES
Problem Statement
Mr. Takahashi runs a N-room hotel. M parties have reservations today, but unfortunately he forgot to make sure that it is possible to assign rooms to all the reservations.
Each reservation needs to be assigned a room with the capacity of at least the size of the party. Exactly one room should be assigned to each reservation: it is not allowed to assign more than one room to one reservation, or assign one room to more than one reservation.
Determine whether it is possible to assign rooms to all reservations following the restrictions.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N B_1 B_2 ... B_M
- The first line contains two integer N (1 ≦ N ≦ 10^5) and M (1 ≦ M ≦ 10^5).
- The second line contains N space-separated integers A_1, A_2, ..., A_N. For each i (1 ≦ i ≦ N), A_i (1 ≦ A_i ≦ 10^5) represents the capacity of the i^{th} room.
- The third line contains M space-separated integers B_1, B_2, ..., B_M. For each i (1 ≦ i ≦ M), B_i (1 ≦ B_i ≦ 10^5) represents the size of the party making the i^{th} reservation.
Output
Print YES in a single line if it is possible to assign rooms to all reservations following the restrictions. Print NO otherwise. Be sure to print a newline at the end of output.
Partial Points
Partial points may be awarded in this problem:
- 60 points will be awarded for passing the test set satisfying N ≦ 100, M ≦ 100.
- Another 40 points will be awarded for passing the test set without additional constraints.
入力例1
3 2 2 2 3 3 1
出力例1
YES
入力例2
3 2 2 2 3 3 3
出力例2
NO
入力例3
3 4 10 10 10 1 1 1 1
出力例3
NO
入力例4
10 10 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1
出力例4
YES
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
10^{100} 個の白いマスが横 1 列に並んでいます。左から i (1≦i≦10^{100}) 番目のマスをマス i と呼びます。
また、駒が N 個あり、i (1≦i≦N) 番目の駒を駒 i と呼びます。
さらに、0 から 10^{100} までの数を数えることのできるカウンタが 1 つあります。
これらのマスと駒に対し N 回の操作を行います。i (1≦i≦N) 回目の操作は以下のように行います。
- まず、マス S_i に駒 i を置き、カウンタを 0 に初期化する。
- 駒のあるマスの色が白ならそのマスを黒に塗ってカウンタを 1 増加させ、駒のあるマスの色が黒なら 1 つ右のマスに駒を移動させる。
- 2. を繰り返していき、カウンタの値が C_i になったらその時点で操作を終了する。
これらの操作が終わった時点で N 個の駒がそれぞれどのマスにあるかを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 C_1 S_2 C_2 : S_N C_N
- 1 行目には、整数 N (1 ≦ N ≦ 10^5) が与えられる。
- 2 行目からの N 行には、各操作の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、整数 S_i (1 ≦ S_i ≦ 10^9), C_i (1≦C_i≦10^9) が与えられる。これは i 回目の操作のはじめに駒 i を置くマスがマス S_i であり、カウンタが C_i になった時点で操作 i が終了となることを表す。
部分点
この問題には部分点が設定されている。
- 全ての操作が終わった時点での駒のあるマスの番号が全て 10^5 以下であるデータセットに正解した場合は、35 点が与えられる。
- N ≦ 1000 を満たすデータセットに正解した場合は、上記とは別に 40 点が与えられる。
- 追加の制約のないデータセットに正解した場合は、上記とは別に 25 点が与えられる。
出力
出力は N 行からなる。このうち i (1≦i≦N) 行目には、全ての操作が終わった時点で駒 i があるマスの番号を表す 1 つの整数を出力せよ。出力の末尾にも改行を入れること。
入力例1
4 3 3 10 1 4 2 2 4
出力例1
5 10 7 11
下図は各操作後のマスと駒の状態を表しています。
入力例2
8 2 1 3 1 1 1 5 1 1 1 9 1 8 2 7 9
出力例2
2 3 1 5 4 9 10 18
入力例3
5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例3
1999999999 2999999999 3999999999 4999999999 5999999999
出力が 32 bit整数型に収まらない場合もあることに注意してください。
Problem Statement
10^{100} squares are arranged in a row. The squares are numbered 1 through 10^{100} from left to right.
We have N pieces numbered 1 through N, and a counter that can store an integer between 0 and 10^{100}, inclusive.
We will perform N processes using these tools. Initially, the squares are painted white. The i^{th} (1≦i≦N) process is as follows:
- Place piece i on square S_i, and set the counter to 0.
- Look at the color of the square where piece i is placed. If the square is white, paint it black and increment the counter by 1. Otherwise (if the square is black), move piece i one square right. As a result, a square may contain multiple pieces.
- Terminate the process if the value of the counter is C_i. Otherwise, go back to step 2.
Find the final position of each of the N pieces after all the N processes.
Input
Input is given from Standard Input in the following format:
N S_1 C_1 S_2 C_2 : S_N C_N
- The first line contains an integer N (1 ≦ N ≦ 10^5).
- The following N lines describe the processes. The i^{th} (1 ≦ i ≦ N) of them contains two space-separated integers S_i (1 ≦ S_i ≦ 10^9) and C_i (1≦C_i≦10^9), denoting the initial position of piece i in the i^{th} process and the termination condition of the i^{th} process, respectively.
Partial Points
Partial points may be awarded in this problem:
- 35 points will be awarded for passing the test set satisfying the following: The number of the square where each piece is located after all the processes does not exceed 10^5.
- Another 40 points will be awarded for passing the test set satisfying N ≦ 1000.
- Another 25 points will be awarded for passing the test set without additional constraints.
Output
Print N lines, the i^{th} (1≦i≦N) of which should contain the number of the square where the piece i is located after all the N processes. Be sure to print a newline at the end of output.
Sample Input 1
4 3 3 10 1 4 2 2 4
Sample Output 1
5 10 7 11
Illustrated below is the state of the squares and the pieces after each process:
Sample Input 2
8 2 1 3 1 1 1 5 1 1 1 9 1 8 2 7 9
Sample Output 2
2 3 1 5 4 9 10 18
Sample Input 3
5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
1999999999 2999999999 3999999999 4999999999 5999999999
Beware that the correct output may not fit into a 32-bit integer.