2011年4月17日日曜日

TopCoder Member SRM 503

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

■FoxMakingDice(Div1 Easy)

Toastmanは,パンを何枚か焼きたい.パンには幾つかの種類があり,ある種類のパンは,X分未満焼くとunder toasted,X分超過焼くとover toastedとなる.
Toastmanは,パンを焼いたが,mi分焼いてunder toastedだったもの,また,ni分焼いて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を上げていきたいものです….

0 件のコメント: