読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Switching Railroad Cars(AOJ No.0013), Integral(AOJ No.0014), National Budget(AOJ No.0015)

Switching Railroad Cars(AOJ No.0013)

1,2,...,10の番号が振られた電車があり、0以上10以下の整数列が与えられる。
1以上10以下の数字は電車の
LIFOの構造への挿入を表し、
0は電車の取り出しを意味する。
取り出された順に電車の番号列を出力する

スタックに入れたり出したりするだけ

import java.util.*;
public class aoj0013 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		Stack<Integer> st = new Stack<Integer>();
		while(stdin.hasNext()){
			int i = stdin.nextInt();
			if( i == 0 ) System.out.println( st.pop() );
			else st.push(i);
		}
	}
}

Integral(AOJ No.0014)

 y=x^2
 y=0
 x=600
で囲まれる部分の面積を数値積分で求める。
ただし、
 f(x)=x^2としたとき、
面積を台形公式ではなく、長方形で
 S = \sum_{i=1}^{600/d-1} f(id)dで求める。
dは600の約数で面積は整数で答える。

import java.util.*;
public class aoj0014 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()) System.out.println( solve(stdin.nextInt()) );
	}
	static int solve(int d){
		int ans = 0;
		for( int i=d; i<600; i+=d ) ans += d*i*i;
		return ans;
	}
}

National Budget(AOJ No.0015)

0以上80桁以下の2数a,bが与えられてその和を返す。
ただし、和が80桁を超える場合は、overflowと出力する。

アルゴリズム

BigIntegerを使えば単に足すだけ。
それだと簡単すぎるので、各位ごとに足していく方法を試した。
まず、m = max(a.length, b.length)として、a,bがm桁になるまで'0'でパディングする。
各位ごとに和を計算する(桁上がりも忘れずに)。

コード

import java.util.*;
import java.math.*;
public class aoj0015 {
	static final Scanner stdin = new Scanner(System.in);
	static final Solver solver = Solver.BigInteger;
	public static void main(String[] args) {
		int n = stdin.nextInt();
		while( n-- > 0 ) System.out.println( solver.solve(stdin.next(), stdin.next() ) );
	}
	enum Solver {
		BigInteger { @Override String solve(String a, String b){
			String ans = new BigInteger(a).add( new BigInteger(b) ).toString();
			return ans.length() > 80 ? "overflow" : ans;
		}}, Naive { @Override String solve(String a, String b){
			StringBuilder A = new StringBuilder(a);
			StringBuilder B = new StringBuilder(b);
			int m = Math.max(A.length(), B.length());
			A.reverse(); B.reverse();
			while( A.length() < m ) A.append('0');
			while( B.length() < m ) B.append('0');
			int carry = 0;
			StringBuilder ans = new StringBuilder();
			for(int i=0; i<m; ++i){
				int s = (A.charAt(i) - '0') + (B.charAt(i) - '0') + carry;
	                        //int s = Character.digit( A.charAt(i), 10 ) + Character.digit( B.charAt(i), 10 ) + carry;
				carry = s/10;
				s%=10;
				ans.append(s);
			}
			if( carry > 0 ) ans.append(carry);
			return ans.length() > 80 ? "overflow" : ans.reverse().toString();
		}};
		String solve(String a, String b){ return null; }
	}
}