PracticeA - Welcome to AtCoder

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はデータの加工が行いたいです。

整数 a, b, cと、文字列 s が与えられます。 a + b + c の計算結果と、文字列 s を並べて表示しなさい。

制約

  • 1\leq a, b, c \leq 1,000
  • 1\leq|s|\leq 100

入力

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

a
b c
s

出力

a+b+c と s を空白区切りで 1 行に出力せよ。

入力例 1

1
2 3
test

出力例 1

6 test
  • 1+2+3 は 6 なので、上記のように出力します。

入力例 2

72
128 256
myonmyon

出力例 2

456 myonmyon
  • 72+128+256 は 456 なので、上記のように出力します。

注意！

CやC++を使うときは、main 関数の型を int で指定し、ちゃんとreturn 0;してください。

Javaを使うときは、クラス名をMainにしてください。mainではコンパイルエラーになります。

補足

以下に各言語ごとの解答例を記載しています。

C での解答例

#include<stdio.h>
int main()
{
    int a,b,c;
    char s[101];
    // 整数の入力
    scanf("%d", &a);
    // スペース区切りの整数の入力
    scanf("%d %d",&b,&c);
    // 文字列の入力
    scanf("%s",s);
    // 出力
    printf("%d %s\n",a+b+c,s);
    return 0;
}

C++ での解答例

#include<iostream>
using namespace std;
int main()
{
    // 整数の入力
    int a;
    cin >> a;
    // スペース区切りの整数の入力
    int b,c;
    cin >> b >> c;
    // 文字列の入力
    string s;
    cin >> s;
    // 出力
    cout << (a+b+c) << " " << s << endl;
    return 0;
}

Java での解答例

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		// スペース区切りの整数の入力
		int b = sc.nextInt();
		int c = sc.nextInt();
		// 文字列の入力
		String s = sc.next();
		// 出力
		System.out.println((a+b+c) + " " + s);
	}
}

C# での解答例

using System;
class Program
{
	static void Main(string[] args)
	{
		// 整数の入力
		int a = int.Parse(Console.ReadLine());
		// スペース区切りの整数の入力
		string[] input = Console.ReadLine().Split(' ');
		int b = int.Parse(input[0]);
		int c = int.Parse(input[1]);
		// 文字列の入力
		string s = Console.ReadLine();
		//出力
		Console.WriteLine((a+b+c) + " " + s);
	}
}

PHP での解答例

<?php
# 整数の入力
fscanf(STDIN, "%d", $a);
# スペース区切りの整数の入力
fscanf(STDIN, "%d %d", $b, $c);
# 文字列の入力
fscanf(STDIN, "%s", $s);
# 出力
echo ($a+$b+$c)." ".$s."\n";
?>

D での解答例

import std.stdio;
import std.string;
import std.conv;
void main()
{
	// 整数の入力
	int a = to!int(chomp(readln()));
	// スペース区切りの整数の入力
	string[] input = split(readln());
	int b = to!int(input[0]);
	int c = to!int(input[1]);
	// 文字列の入力
	string s = chomp(readln());
	// 出力
	writefln("%d %s", a+b+c, s);
}

Go での解答例

package main

import (
	"fmt"
)

func main() {
	var a, b, c int
	var s string
	fmt.Scanf("%d", &a)
	fmt.Scanf("%d %d", &b, &c)
	fmt.Scanf("%s", &s)
	fmt.Printf("%d %s\n", a+b+c, s)
}

Python2 での解答例

# -*- coding: utf-8 -*-
# 整数の入力
a = int(raw_input())
# スペース区切りの整数の入力
b, c = map(int, raw_input().split())
# 文字列の入力
s = raw_input()
# 出力
print str(a+b+c) + " " + s

Python3 での解答例

# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
b, c = map(int, input().split())
# 文字列の入力
s = input()
# 出力
print("{} {}".format(a+b+c, s))

Perl での解答例

# 整数の入力
my $a = <STDIN>;
# スペース区切りの整数の入力
my $input = <STDIN>;
chomp $input;
my ($b, $c) = split / /, $input;
$ret = $a + $b + $c;
# 文字列の入力
my $s = <STDIN>;
chomp $s;
# 出力
print "$ret $s\n";

Ruby での解答例

# 整数の入力
a = gets.to_i
# スペース区切りの整数の入力
b,c=gets.chomp.split(" ").map(&:to_i);
# 文字列の入力
s = gets.chomp
# 出力
print("#{a+b+c} #{s}\n")

Haskell での解答例

{- お客様の中でHaskellを書ける方はいらっしゃいますか？
    と、Haskellの例がなくて困っていたところを @tanakh さんに助けて頂きました。本当にありがとうございました。-}
import Control.Applicative

main :: IO ()
main = do
    -- 整数の入力
    a <- readLn
    -- スペース区切り整数の入力
    [b, c] <- map read . words <$> getLine
    -- 文字列の入力
    s <- getLine
    -- 出力
    putStrLn $ show (a + b + c) ++ " " ++ s

Pascal での解答例

var
    a, b, c : integer;
    s : ShortString;
begin
    { 整数の入力 }
    readln(a);
    { スペース区切りの整数の入力 }
    read(b);
    readln(c);
    { 文字列の入力 }
    readln(s);
    { 出力 }
    writeln(a+b+c, ' ', s);
end.

JavaScript(Node.js) での解答例

// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	tmp = input[1].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(input[0], 10);
	var b = parseInt(tmp[0], 10);
	var c = parseInt(tmp[1], 10);
	var s = input[2];
	//出力
	console.log('%d %s',a+b+c,s);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Scala での解答例

// defplus @defplus さん提供
import scala.io.StdIn.*
object Main extends App {
    var a = readInt
    var num = readLine
    var s = readLine
    var sum = a + num.split(" ")(0).toInt + num.split(" ")(1).toInt
    println(sum + " " + s);
}

Problem

Your task is to process some data.
You are given 3 integers a , b , c and a string s. Output result of a + b + c and string s with a half-width break.

Constrains

  • 1\leq a, b, c \leq 1,000
  • 1\leq|s|\leq 100

Input

Input will be given in the following format from Standard Input: 

a
b c
s

Output

Output the result of a+b+c and string s with a half-width break in one line.

Input Example #1

1
2 3
test

Output Example #1

6 test
  • 1+2+3 equals to 6.

Input Example #2

72
128 256
myonmyon

Output Example #2

456 myonmyon
  • 72+128+256 equals to 456.

Notice

If you are C or C++ programmer, please designate the types of main function as int and not to forget return 0; .

If you are Java programmer, please designate your class name as Main, not main.

References

We prepared some sample answers bellow (Not all programming languages).
Please use these examples as reference.

Example of C

#include<stdio.h>

int main()
{
    int a,b,c;
    char s[101];
    // get a integer
    scanf("%d", &a);
    // get two integers separated half-width break
    scanf("%d %d",&b,&c);
    // get a string
    scanf("%s",s);
    // output
    printf("%d %s\n",a+b+c,s);
    return 0;
}

Example of C++

#include<iostream>
using namespace std;

int main()
{
    // get a integer
    int a;
    cin >> a;
    // get two integers separated with half-width break
    int b,c;
    cin >> b >> c;
    // get a string
    string s;
    cin >> s;
    // output
    cout << (a+b+c) << " " << s << endl;
    return 0;
}

Example of Java

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// get a integer
		int a = sc.nextInt();
		// get two integers separated with half-width break
		int b = sc.nextInt();
		int c = sc.nextInt();
		// get a string
		String s = sc.next();
		// output
		System.out.println((a+b+c) + " " + s);
	}
}

Example of C#

using System;
class Program
{
	static void Main(string[] args)
	{
		// get a integer
		int a = int.Parse(Console.ReadLine());
		// get two integers separated with half-width break
		string[] input = Console.ReadLine().Split(' ');
		int b = int.Parse(input[0]);
		int c = int.Parse(input[1]);
		// get a string
		string s = Console.ReadLine();
		//output
		Console.WriteLine((a+b+c) + " " + s);
	}
}

Example of PHP

<?php
# get a integer
fscanf(STDIN, "%d", $a);
# get two integers separated with half-width break
fscanf(STDIN, "%d %d", $b, $c);
# get a string
fscanf(STDIN, "%s", $s);
# output
echo ($a+$b+$c)." ".$s."\n";
?>

Example of D

import std.stdio;
import std.string;
import std.conv;
void main()
{
	// get a integer
	int a = to!int(chomp(readln()));
	// get two integers separated with half-width break
	string[] input = split(readln());
	int b = to!int(input[0]);
	int c = to!int(input[1]);
	// get a string
	string s = chomp(readln());
	// output
	writefln("%d %s", a+b+c, s);
}

Example of Go

package main

import (
	"fmt"
)

func main() {
	var a, b, c int
	var s string
	fmt.Scanf("%d", &a)
	fmt.Scanf("%d %d", &b, &c)
	fmt.Scanf("%s", &s)
	fmt.Printf("%d %s\n", a+b+c, s)
}

Example of Python

# -*- coding: utf-8 -*-
# get a integer
a = int(raw_input())
# get two integers separated with half-width break
b, c = map(int, raw_input().split())
# get a string
s = raw_input()
# output
print str(a+b+c) + " " + s

Example of Perl

# get a integer
my $a = <STDIN>;
# get two integers separated with half-width break
my $input = <STDIN>;
chomp $input;
my ($b, $c) = split / /, $input;
$ret = $a + $b + $c;
# get a string
my $s = <STDIN>;
chomp $s;
# output
print "$ret $s\n";

Example of Ruby

# get a integer
a = gets.to_i
# get two integers separated with half-width break
b,c=gets.chomp.split(" ").map(&:to_i);
# get a string
s = gets.chomp
# output
print("#{a+b+c} #{s}\n")

Example of Haskell

{- supportedby @tanakh -}
import Control.Applicative
main :: IO ()
main = do
    -- get a integer
    a <- readLn
    -- get two integers separated with half-width break
    [b, c] <- map read . words <$> getLine
    -- get a string
    s <- getLine
    -- output
    putStrLn $ show (a + b + c) ++ " " ++ s

Example of Pascal

var
    a, b, c : integer;
    s : ShortString;
begin
    { get a integer }
    readln(a);
    { get two integers separated with half-width break }
    read(b);
    readln(c);
    { get a string }
    readln(s);
    { output }
    writeln(a+b+c, ' ', s);
end.

Example of JavaScript(Node.js)

// parameter "input" gets all data
function Main(input) {
	// the first line is assigned to input[0], the second line is assigned to input[1] similarly.
	input = input.split("\n");
	tmp = input[1].split(" ");
	// convert string from integer using "parseInt"
	var a = parseInt(input[0], 10);
	var b = parseInt(tmp[0], 10);
	var c = parseInt(tmp[1], 10);
	var s = input[2];
	//output
	console.log('%d %s',a+b+c,s);
}
// Don't edit this line!
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Example of Scala

// supported by @defplus
import scala.io.StdIn.*
object Main extends App {
    var a = readInt
    var num = readLine
    var s = readLine
    var sum = a + num.split(" ")(0).toInt + num.split(" ")(1).toInt
    println(sum + " " + s);
}
ABC086A - Product

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。

制約

  • 1 ≤ a,b ≤ 10000
  • a,b は整数

入力

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

a b

出力

積が奇数なら Odd と、 偶数なら Even と出力せよ。

入力例 1

3 4

出力例 1

Even

3 × 4 = 12 は偶数なので Even を出力してください。

入力例 2

1 21

出力例 2

Odd

1 × 21 = 21 は奇数なので Odd を出力してください。

Score : 100 points

Problem Statement

AtCoDeer the deer found two positive integers, a and b. Determine whether the product of a and b is even or odd.

Constraints

  • 1 ≤ a,b ≤ 10000
  • a and b are integers.

Input

Input is given from Standard Input in the following format:

a b

Output

If the product is odd, print Odd; if it is even, print Even.

Sample Input 1

3 4

Sample Output 1

Even

As 3 × 4 = 12 is even, print Even.

Sample Input 2

1 21

Sample Output 2

Odd

As 1 × 21 = 21 is odd, print Odd.
ABC081A - Placing Marbles

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス i には s_i が書かれています。

すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

制約

  • s_1, s_2, s_3 は 1 あるいは 0

入力

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

s_{1}s_{2}s_{3}

出力

答えを出力せよ。

入力例 1

101

出力例 1

2
  • マス 1,3 にビー玉が置かれます

入力例 2

000

出力例 2

0
  • ビー玉はどのマスにも置かれません

Score : 100 points

Problem Statement

Snuke has a grid consisting of three squares numbered 1, 2 and 3. In each square, either 0 or 1 is written. The number written in Square i is s_i.

Snuke will place a marble on each square that says 1. Find the number of squares on which Snuke will place a marble.

Constraints

  • Each of s_1, s_2 and s_3 is either 1 or 0.

Input

Input is given from Standard Input in the following format:

s_{1}s_{2}s_{3}

Output

Print the answer.

Sample Input 1

101

Sample Output 1

2
  • A marble will be placed on Square 1 and 3.

Sample Input 2

000

Sample Output 2

0
  • No marble will be placed on any square.
ABC081B - Shift only

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

黒板に N 個の正の整数 A_1, ..., A_N が書かれています．

すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

  • 黒板に書かれている整数すべてを，2 で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約

  • 1 \leq N \leq 200
  • 1 \leq A_i \leq 10^9

入力

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

N
A_1 A_2 ... A_N

出力

すぬけ君は最大で何回操作を行うことができるかを出力せよ．

入力例 1

3
8 12 40

出力例 1

2

最初，黒板には [8, 12, 40] が書かれています． このとき，書かれている整数はすべて偶数なので，操作を行うことができます．

1 回操作を行った後，黒板には [4, 6, 20] が書かれています． 再び，書かれている整数はすべて偶数なので，操作を行うことができます．

2 回操作を行った後，黒板には [2, 3, 10] が書かれています． この時，奇数 3 が書かれているため，これ以上操作を行うことはできません．

よって，すぬけ君は最大で 2 回操作を行うことができます．

入力例 2

4
5 6 8 10

出力例 2

0

最初から奇数 5 が書かれているため，すぬけ君は一回も操作を行うことができません．

入力例 3

6
382253568 723152896 37802240 379425024 404894720 471526144

出力例 3

8

Score : 200 points

Problem Statement

There are N positive integers written on a blackboard: A_1, ..., A_N.

Snuke can perform the following operation when all integers on the blackboard are even:

  • Replace each integer X on the blackboard by X divided by 2.

Find the maximum possible number of operations that Snuke can perform.

Constraints

  • 1 \leq N \leq 200
  • 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible number of operations that Snuke can perform.

Sample Input 1

3
8 12 40

Sample Output 1

2

Initially, [8, 12, 40] are written on the blackboard. Since all those integers are even, Snuke can perform the operation.

After the operation is performed once, [4, 6, 20] are written on the blackboard. Since all those integers are again even, he can perform the operation.

After the operation is performed twice, [2, 3, 10] are written on the blackboard. Now, there is an odd number 3 on the blackboard, so he cannot perform the operation any more.

Thus, Snuke can perform the operation at most twice.

Sample Input 2

4
5 6 8 10

Sample Output 2

0

Since there is an odd number 5 on the blackboard already in the beginning, Snuke cannot perform the operation at all.

Sample Input 3

6
382253568 723152896 37802240 379425024 404894720 471526144

Sample Output 3

8
ABC087B - Coins

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。

同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約

  • 0 \leq A, B, C \leq 50
  • A + B + C \geq 1
  • 50 \leq X \leq 20,000
  • A, B, C は整数である
  • X は 50 の倍数である

入力

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

A
B
C
X

出力

硬貨を選ぶ方法の個数を出力せよ。

入力例 1

2
2
2
100

出力例 1

2

条件を満たす選び方は以下の 2 通りです。

  • 500 円玉を 0 枚、100 円玉を 1 枚、50 円玉を 0 枚選ぶ。
  • 500 円玉を 0 枚、100 円玉を 0 枚、50 円玉を 2 枚選ぶ。

入力例 2

5
1
0
150

出力例 2

0

合計金額をちょうど X 円にする必要があることに注意してください。

入力例 3

30
40
50
6000

出力例 3

213

Score : 200 points

Problem Statement

You have A 500-yen coins, B 100-yen coins and C 50-yen coins (yen is the currency of Japan). In how many ways can we select some of these coins so that they are X yen in total?

Coins of the same kind cannot be distinguished. Two ways to select coins are distinguished when, for some kind of coin, the numbers of that coin are different.

Constraints

  • 0 \leq A, B, C \leq 50
  • A + B + C \geq 1
  • 50 \leq X \leq 20 000
  • A, B and C are integers.
  • X is a multiple of 50.

Input

Input is given from Standard Input in the following format:

A
B
C
X

Output

Print the number of ways to select coins.

Sample Input 1

2
2
2
100

Sample Output 1

2

There are two ways to satisfy the condition:

  • Select zero 500-yen coins, one 100-yen coin and zero 50-yen coins.
  • Select zero 500-yen coins, zero 100-yen coins and two 50-yen coins.

Sample Input 2

5
1
0
150

Sample Output 2

0

Note that the total must be exactly X yen.

Sample Input 3

30
40
50
6000

Sample Output 3

213
ABC083B - Some Sums

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

制約

  • 1 \leq N \leq 10^4
  • 1 \leq A \leq B \leq 36
  • 入力はすべて整数である

入力

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

N A B

出力

1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。

入力例 1

20 2 5

出力例 1

84

20 以下の整数のうち、各桁の和が 2 以上 5 以下なのは 2,3,4,5,11,12,13,14,20 です。これらの合計である 84 を出力します。

入力例 2

10 1 2

出力例 2

13

入力例 3

100 4 16

出力例 3

4554

Score : 200 points

Problem Statement

Find the sum of the integers between 1 and N (inclusive), whose sum of digits written in base 10 is between A and B (inclusive).

Constraints

  • 1 \leq N \leq 10^4
  • 1 \leq A \leq B \leq 36
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

Print the sum of the integers between 1 and N (inclusive), whose sum of digits written in base 10 is between A and B (inclusive).

Sample Input 1

20 2 5

Sample Output 1

84

Among the integers not greater than 20, the ones whose sums of digits are between 2 and 5, are: 2,3,4,5,11,12,13,14 and 20. We should print the sum of these, 84.

Sample Input 2

10 1 2

Sample Output 2

13

Sample Input 3

100 4 16

Sample Output 3

4554
ABC088B - Card Game for Two

Time Limit: 2 sec / Memory Limit: 256 MB

配点：200 点

問題文

N 枚のカードがあります. i 枚目のカードには, a_i という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

制約

  • N は 1 以上 100 以下の整数
  • a_i \ (1 \leq i \leq N) は 1 以上 100 以下の整数

入力

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

N
a_1 a_2 a_3 ... a_N

出力

両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

入力例 1

2
3 1

出力例 1

2

最初, Alice は 3 が書かれたカードを取ります. 次に, Bob は 1 が書かれたカードを取ります. 得点差は 3 - 1 = 2 となります.

入力例 2

3
2 7 4

出力例 2

5

最初, Alice は 7 が書かれたカードを取ります. 次に, Bob は 4 が書かれたカードを取ります. 最後に, Alice は 2 が書かれたカードを取ります. 得点差は, 7 - 4 + 2 = 5 点となります.

入力例 3

4
20 18 2 18

出力例 3

18

Score: 200 points

Problem Statement

We have N cards. A number a_i is written on the i-th card.
Alice and Bob will play a game using these cards. In this game, Alice and Bob alternately take one card. Alice goes first.
The game ends when all the cards are taken by the two players, and the score of each player is the sum of the numbers written on the cards he/she has taken. When both players take the optimal strategy to maximize their scores, find Alice's score minus Bob's score.

Constraints

  • N is an integer between 1 and 100 (inclusive).
  • a_i \ (1 \leq i \leq N) is an integer between 1 and 100 (inclusive).

Input

Input is given from Standard Input in the following format: 

N
a_1 a_2 a_3 ... a_N

Output

Print Alice's score minus Bob's score when both players take the optimal strategy to maximize their scores.

Sample Input 1

2
3 1

Sample Output 1

2

First, Alice will take the card with 3. Then, Bob will take the card with 1. The difference of their scores will be 3 - 1 = 2.

Sample Input 2

3
2 7 4

Sample Output 2

5

First, Alice will take the card with 7. Then, Bob will take the card with 4. Lastly, Alice will take the card with 2. The difference of their scores will be 7 - 4 + 2 = 5. The difference of their scores will be 3 - 1 = 2.

Sample Input 3

4
20 18 2 18

Sample Output 3

18
ABC085B - Kagami Mochi

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

X 段重ねの鏡餅 (X ≥ 1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。

ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は d_i センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

  • 1 ≤ N ≤ 100
  • 1 ≤ d_i ≤ 100
  • 入力値はすべて整数である。

入力

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

N
d_1
:
d_N

出力

作ることのできる鏡餅の最大の段数を出力せよ。

入力例 1

4
10
8
8
6

出力例 1

3

直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、これが最大です。

入力例 2

3
15
15
15

出力例 2

1

すべての餅の直径が同じときは、1 段重ねの鏡餅しか作れません。

入力例 3

7
50
30
50
100
50
80
30

出力例 3

4

Score : 200 points

Problem Statement

An X-layered kagami mochi (X ≥ 1) is a pile of X round mochi (rice cake) stacked vertically where each mochi (except the bottom one) has a smaller diameter than that of the mochi directly below it. For example, if you stack three mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, you have a 3-layered kagami mochi; if you put just one mochi, you have a 1-layered kagami mochi.

Lunlun the dachshund has N round mochi, and the diameter of the i-th mochi is d_i centimeters. When we make a kagami mochi using some or all of them, at most how many layers can our kagami mochi have?

Constraints

  • 1 ≤ N ≤ 100
  • 1 ≤ d_i ≤ 100
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N
d_1
:
d_N

Output

Print the maximum number of layers in a kagami mochi that can be made.

Sample Input 1

4
10
8
8
6

Sample Output 1

3

If we stack the mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, we have a 3-layered kagami mochi, which is the maximum number of layers.

Sample Input 2

3
15
15
15

Sample Output 2

1

When all the mochi have the same diameter, we can only have a 1-layered kagami mochi.

Sample Input 3

7
50
30
50
100
50
80
30

Sample Output 3

4
ABC085C - Otoshidama

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約

  • 1 ≤ N ≤ 2000
  • 1000 ≤ Y ≤ 2 × 10^7
  • N は整数である。
  • Y は 1000 の倍数である。

入力

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

N Y

出力

N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。

N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

入力例 1

9 45000

出力例 1

4 0 5

お年玉袋に 10000 円札 4 枚と 1000 円札 5 枚が入っていれば、合計枚数が 9 枚、合計金額が 45000 円になります。5000 円札 9 枚という可能性も考えられるため、0 9 0 も正しい出力です。

入力例 2

20 196000

出力例 2

-1 -1 -1

合計枚数が 20 枚の場合、すべてが 10000 円札であれば合計金額は 200000 円になり、そうでなければ 195000 円以下になるため、196000 円という合計金額はありえません。

入力例 3

1000 1234000

出力例 3

14 27 959

この他にも多くの候補があります。

入力例 4

2000 20000000

出力例 4

2000 0 0

Score : 300 points

Problem Statement

The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.

According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.

Constraints

  • 1 ≤ N ≤ 2000
  • 1000 ≤ Y ≤ 2 × 10^7
  • N is an integer.
  • Y is a multiple of 1000.

Input

Input is given from Standard Input in the following format:

N Y

Output

If the total value of N bills cannot be Y yen, print -1 -1 -1.

If the total value of N bills can be Y yen, let one such set of bills be "x 10000-yen bills, y 5000-yen bills and z 1000-yen bills", and print x, y, z with spaces in between. If there are multiple possibilities, any of them may be printed.

Sample Input 1

9 45000

Sample Output 1

4 0 5

If the envelope contained 4 10000-yen bills and 5 1000-yen bills, he had 9 bills and 45000 yen in total. It is also possible that the envelope contained 9 5000-yen bills, so the output 0 9 0 is also correct.

Sample Input 2

20 196000

Sample Output 2

-1 -1 -1

When the envelope contained 20 bills in total, the total value would be 200000 yen if all the bills were 10000-yen bills, and would be at most 195000 yen otherwise, so it would never be 196000 yen.

Sample Input 3

1000 1234000

Sample Output 3

14 27 959

There are also many other possibilities.

Sample Input 4

2000 20000000

Sample Output 4

2000 0 0
ABC049C - Daydream

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S = T とすることができるか判定してください。

  • T の末尾に dream dreamer erase eraser のいずれかを追加する。

制約

  • 1≦|S|≦10^5
  • S は英小文字からなる。

入力

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

S

出力

S = T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

入力例 1

erasedream

出力例 1

YES

erase dream の順で T の末尾に追加することで S = T とすることができます。

入力例 2

dreameraser

出力例 2

YES

dream eraser の順で T の末尾に追加することで S = T とすることができます。

入力例 3

dreamerer

出力例 3

NO

Score : 300 points

Problem Statement

You are given a string S consisting of lowercase English letters. Another string T is initially empty. Determine whether it is possible to obtain S = T by performing the following operation an arbitrary number of times:

  • Append one of the following at the end of T: dream, dreamer, erase and eraser.

Constraints

  • 1≦|S|≦10^5
  • S consists of lowercase English letters.

Input

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

S

Output

If it is possible to obtain S = T, print YES. Otherwise, print NO.

Sample Input 1

erasedream

Sample Output 1

YES

Append erase and dream at the end of T in this order, to obtain S = T.

Sample Input 2

dreameraser

Sample Output 2

YES

Append dream and eraser at the end of T in this order, to obtain S = T.

Sample Input 3

dreamerer

Sample Output 3

NO
ABC086C - Traveling

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 t_i に 点 (x_i,y_i) を訪れる予定です。

AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x-1,y), (x,y+1), (x,y-1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約

  • 1 ≤ N ≤ 10^5
  • 0 ≤ x_i ≤ 10^5
  • 0 ≤ y_i ≤ 10^5
  • 1 ≤ t_i ≤ 10^5
  • t_i < t_{i+1} (1 ≤ i ≤ N-1)
  • 入力は全て整数

入力

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

N
t_1 x_1 y_1
t_2 x_2 y_2
:
t_N x_N y_N

出力

旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

入力例 1

2
3 1 2
6 1 1

出力例 1

Yes

例えば、(0,0), (0,1), (1,1), (1,2), (1,1), (1,0), (1,1) と移動すればよいです。

入力例 2

1
2 100 100

出力例 2

No

(0,0) にいる状態から 2 秒後に (100,100) にいるのは不可能です。

入力例 3

2
5 1 1
100 1 1

出力例 3

No

Score : 300 points

Problem Statement

AtCoDeer the deer is going on a trip in a two-dimensional plane. In his plan, he will depart from point (0, 0) at time 0, then for each i between 1 and N (inclusive), he will visit point (x_i,y_i) at time t_i.

If AtCoDeer is at point (x, y) at time t, he can be at one of the following points at time t+1: (x+1,y), (x-1,y), (x,y+1) and (x,y-1). Note that he cannot stay at his place. Determine whether he can carry out his plan.

Constraints

  • 1 ≤ N ≤ 10^5
  • 0 ≤ x_i ≤ 10^5
  • 0 ≤ y_i ≤ 10^5
  • 1 ≤ t_i ≤ 10^5
  • t_i < t_{i+1} (1 ≤ i ≤ N-1)
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N
t_1 x_1 y_1
t_2 x_2 y_2
:
t_N x_N y_N

Output

If AtCoDeer can carry out his plan, print Yes; if he cannot, print No.

Sample Input 1

2
3 1 2
6 1 1

Sample Output 1

Yes

For example, he can travel as follows: (0,0), (0,1), (1,1), (1,2), (1,1), (1,0), then (1,1).

Sample Input 2

1
2 100 100

Sample Output 2

No

It is impossible to be at (100,100) two seconds after being at (0,0).

Sample Input 3

2
5 1 1
100 1 1

Sample Output 3

No