AOJ0233 Book Arrangement

問題リンク Book Arrangement

• 解法

マイナス10進数を下の桁から順に求める方針で解きます。
残念なことに、これを解いたのは結構前でソースが何をしてるんだかあまり思い出せません、なので記憶の片隅にあるアイデアだけ述べさせてください。
ある桁kで作ることができるのが正か負かは簡単に分かります。1の位だったら正、10の位だったら負、という感じです。
ここで、10進数において、桁kが数xだったとします。このとき、桁kで作ることができるのが正ならば、xがそのまま桁kの数字になります。負の場合、それは10-xという数になります。この場合、次の桁から値を1つ借りてくる形になるので、k+1桁目に必要な数字を1増やします。
みたいな感じで解きました。こういうアドホックな実装問題は、解いた日にすぐ記事にしないと取り返しがつきませんね・・・orz

• ソース

import java.util.Scanner;

//Book Arrangement
public class AOJ0233 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			long x = sc.nextLong();
			if(x==0)break;
			boolean sign = x>0;
			String res = "";
			x = Math.abs(x);
			boolean k = true;
			while(x>0){
				int t = (int) (x%10);
				if(sign==k)res =t + res;
				else{
					res = (10-t)%10+res;
					if(t!=0)x+=10;
				}
				k=!k;
				x/=10;
			}
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new AOJ0233().run();
	}
}