TopCoder Member SRM 503

SRM 503(12/19 1:00~3:00)

■FoxMakingDice(Div1 Easy)

Toastmanは，パンを何枚か焼きたい．パンには幾つかの種類があり，ある種類のパンは，X分未満焼くとunder toasted，X分超過焼くとover toastedとなる．
Toastmanは，パンを焼いたが，m_i分焼いてunder toastedだったもの，また，n_i分焼いてover toastedだったものが出来た．Toastmanは何種類のパンを用いたかを覚えていないが，ある種類のパンを焼いたときにunder toasted・over toastedだったものがそれぞれ少なくとも1枚以上はあったという．
パンの種類の最小数を答えよ．

under toastedだったものをU，over toastedだったものをOとし，それらを焼かれた時間の数直線にプロットする．例えば下図．
UOUOOUOUOUOUO

・パンの種類が1つで良い場合．

UUUUU | OOOOOO
上のような場合．Xは，"|"で表される．

・パンが何種類あっても不可能な場合．

O…………
または，
…………U
の場合．

・パンの種類が2つで良い場合．

上記のどれにも当てはまらない場合．
何故なら，必ずパンの順列は，
U[…………]O
となり，
U | […………]O
で分けると，
[…………]内のOは全て排除され．
[U……U]O
となる．その後，
[U……U] | O
で分ければ終了する．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class ToastXToast {
 int INF=1<<28;
 double EPS=1e-9;

 public int bake(int[] a, int[] b) {
  Arrays.sort(a); // o
  Arrays.sort(b); // x
  boolean f=true;
  for(int j=0;j<b.length;j++){
   for(int i=0;i<a.length;i++){
    f&=a[i]<b[j];
   }
  }
  if(f){
   return 1;
  }
  else if(a[0]>b[0]||a[a.length-1]>b[b.length-1]){
   return -1;
  }
  else if(a.length>=2&&b.length>=2){
   return 2;
  }
  else{
   return -1;
  }
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args) {
  ToastXToast temp = new ToastXToast();
 }
}

■Result

○×× 0 0
144.26pt.

■Rating

1243 -> 1279
若干上昇．少しずつRatingを上げていきたいものです…．