東京大学プログラミングコンテスト2012 練習セッション

A - Wats○n 2


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

Wats○n 2はI○Mの開発した,自然言語による問題文を読み込んで解答を出力するシステムです.天才科学者であるきたまさ君はWats○n 2に対抗するシステムを開発することにしました.彼のお手伝いをしてください.


入力

入力は複数行の英語の問題文からなります.入力の終わりはEOFによって表されます.

出力

質問に対する答えを出力してください.

制約

部分点

この問題の判定は,4つのテストケースからなり,各テストケースを正解するごとに50点の部分点を得ることが出来る.

一つ目のテストケースの一行目は以下のようである.

The next line contains four real numbers x1, y1, x2, and y2. Compute the Euclidean distance between two points (x1, y1) and (x2, y2) rounded to 5 digits after the decimal point.

訳: 次の行に4つの実数x1,y1,x2,y2が書かれています.二点(x1,y1),(x2,y2)間のユークリッド距離を小数点以下5桁で答えてください.

ヒント: 小数値を指定した桁数で出力するには,printfなどの書式付出力を用いると便利です.以下の解答例を参考にしてください.

二つ目のテストケースの一行目は以下のようである.

Compute the sum of the two positive integers written in the next line. You can assume that the sum never exceeds 10^18.

訳: 次の行に書かれた二つの正整数の和を求めてください.ただし,答えは10^18を超えないことが保証されています.

ヒント: int型整数は通常32bitの値(-2,147,483,648~2,147,483,647)しか扱うことができません.より大きな値を扱う場合には64bit整数(C++: long long, Java: long)を使いましょう.

三つ目のテストケースの一行目は以下のようである.

Each of the next 1,000,000 lines contain a positive integer of at most 10^6. Sort and output them in ascending order.

訳: 以下の1,000,000行に10^6までの正整数が書かれている.昇順にソートして出力してください.

ヒント: 巨大な入出力には時間がかかります.cinなどの遅い入出力関数を使うとそれだけでTLEとなる可能性があります.高速な入出力は以下の解答例を参考にしてください.


入力例 1

What year is it?

入力例 1 に対する出力例

2012

解答例

以下の解答例では150点分の部分点を得ることができます.

C++

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

int list[1000000];

int main() {
    char buf[2000];
    gets(buf);
    if (buf[0] == 'T') {
        double x1, y1, x2, y2;
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        printf("%.5f\n", sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
    } else if (buf[0] == 'C') {
        long long a, b;
        scanf("%lld%lld", &a, &b);
        printf("%lld\n", a + b);
    } else if (buf[0] == 'E') {
        for (int i = 0; i < 1000000; i++) {
            scanf("%d", list + i); // cinは非常に遅い
        }
        sort(list, list + 1000000);
        for (int i = 0; i < 1000000; i++) {
            printf("%d\n", list[i]); // coutは非常に遅い
        }
    } else {
        puts("I don't know.");
    }
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        if (s.charAt(0) == 'T') {
            double x1 = sc.nextDouble(), y1 = sc.nextDouble(), x2 = sc.nextDouble(), y2 = sc.nextDouble();
            System.out.printf("%.5f%n", Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
        } else if (s.charAt(0) == 'C') {
            System.out.println(sc.nextLong() + sc.nextLong());
        } else if (s.charAt(0) == 'E') {
            int[] list = new int[1000000];
            for (int i = 0; i < list.length; i++) {
                list[i] = Integer.parseInt(sc.next()); // sc.nextInt()より少し高速
            }
            Arrays.sort(list);
            PrintWriter out = new PrintWriter(System.out); // System.out.printlnは非常に遅い
            for (int i = 0; i < list.length; i++) {
                out.println(list[i]);
            }
            out.flush();
        } else {
            System.out.println("I don't know.");
        }
    }
}

Submit提出する