結果

問題 No.297 カードの数式
コンテスト
ユーザー uafr_cs
提出日時 2015-11-06 23:01:32
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,893 bytes
コンパイル時間 2,471 ms
コンパイル使用メモリ 87,384 KB
実行使用メモリ 63,640 KB
最終ジャッジ日時 2024-09-13 13:29:21
合計ジャッジ時間 5,774 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;

public class Main {
	
	public static long min = Long.MAX_VALUE;
	public static long max = Long.MIN_VALUE;
	
	public static long estimate_max(long total, long sign, long current, final int n_count, int[] numbers, int o_count, int[] ops){
		if(sign > 0 || ops[0] > 0){
			if(sign < 0 && ops[0] > 0){
				total += sign * current;
				sign = 1;
				current = 0;
				o_count--;
			}
			
			for(int rest = n_count - o_count, i = 9; i >= 0; i--){
				final int times = Math.min(numbers[i], rest);
			
				rest -= times;
				for(int j = 0; j < times; j++){
					current *= 10;
					current += i;
				}
			
				for(int j = 0; j < numbers[i] - times; j++){
					current += i;
				}
			}
			
			return total + sign * current;
		}else{
			for(int rest = n_count - o_count, i = 0; i < 10; i++){
				final int times = Math.min(numbers[i], rest);
			
				rest -= times;
				for(int j = 0; j < times; j++){
					current *= 10;
					current += i;
				}
			
				for(int j = 0; j < numbers[i] - times; j++){
					current += i;
				}
			}
			
			return total + sign * current;	
		}
	}
	
	public static long estimate_min(long total, long sign, long current, final int n_count, int[] numbers, int o_count, int[] ops){
		if(sign < 0 || ops[1] > 0){
			if(sign > 0 && ops[1] > 0){
				total += sign * current;
				sign = -1;
				current = 0;
				o_count--;
			}
			
			for(int rest = n_count - o_count, i = 9; i >= 0; i--){
				final int times = Math.min(numbers[i], rest);
			
				rest -= times;
				for(int j = 0; j < times; j++){
					current *= 10;
					current += i;
				}
			
				for(int j = 0; j < numbers[i] - times; j++){
					current += i;
				}
			}
			
			return total + sign * current;
		}else{
			for(int rest = n_count - o_count, i = 0; i < 10; i++){
				final int times = Math.min(numbers[i], rest);
			
				rest -= times;
				for(int j = 0; j < times; j++){
					current *= 10;
					current += i;
				}
			
				for(int j = 0; j < numbers[i] - times; j++){
					current += i;
				}
			}
			
			return total + sign * current;	
		}
	}
	
	public static void dfs(long total, long sign, long current, boolean first, final int n_count, int[] numbers, final int o_count, int[] ops){
		if(n_count == 0 && o_count == 0){
			total += current * sign;
			
			min = Math.min(min, total);
			max = Math.max(max, total);
			return;
		}
		
		final long estimate_max = estimate_max(total, sign, current, n_count, numbers, o_count, ops);
		final long estimate_min = estimate_min(total, sign, current, n_count, numbers, o_count, ops);
		if(estimate_max < max && estimate_min > min){
			return;
		}
		//System.out.println();
		
		
		if(first || n_count > o_count){
			for(int i = 0; i < 10; i++){
				if(numbers[i] > 0){
					numbers[i]--;
					dfs(total, sign, current * 10 + i, false, n_count - 1, numbers, o_count, ops);
					numbers[i]++;
				}
			}
		}
		
		if(!first){
			if(ops[0] > 0){ 
				ops[0]--;
				dfs(total + current * sign,  1, 0, true, n_count, numbers, o_count - 1, ops);
				ops[0]++;
			}
			if(ops[1] > 0){
				ops[1]--;
				dfs(total + current * sign, -1, 0, true, n_count, numbers, o_count - 1, ops);
				ops[1]++;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		char[] inputs = new char[N];
		for(int i = 0; i < N; i++){
			inputs[i] = sc.next().charAt(0);
		}
		
		int n_count = 0, o_count = 0;
		int[] ops = new int[2];
		int[] numbers = new int[10];
		for(int i = 0; i < inputs.length; i++){
			switch(inputs[i]){
			case '+': ops[0]++; o_count++; break;
			case '-': ops[1]++; o_count++; break;
			default : numbers[Character.getNumericValue(inputs[i])]++; n_count++;
			}
		}
		
		dfs(0, 1, 0, true, n_count, numbers, o_count, ops);
		
		System.out.println(max + " " + min);
	}

}
0