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
で分ければ終了する．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. public class ToastXToast {  
7.  int INF=1<<28;  
8.  double EPS=1e-9;  
9.   
10.  public int bake(int[] a, int[] b) {  
11.   Arrays.sort(a); // o  
12.   Arrays.sort(b); // x  
13.   boolean f=true;  
14.   for(int j=0;j<b.length;j++){  
15.    for(int i=0;i<a.length;i++){  
16.     f&=a[i]<b[j];  
17.    }  
18.   }  
19.   if(f){  
20.    return 1;  
21.   }  
22.   else if(a[0]>b[0]||a[a.length-1]>b[b.length-1]){  
23.    return -1;  
24.   }  
25.   else if(a.length>=2&&b.length>=2){  
26.    return 2;  
27.   }  
28.   else{  
29.    return -1;  
30.   }  
31.  }  
32.   
33.  void debug(Object...os){  
34.   System.err.println(Arrays.deepToString(os));  
35.  }  
36.   
37.  void print(String s){  
38.   System.out.print(s);  
39.  }  
40.   
41.  void println(String s){  
42.   System.out.println(s);  
43.  }  
44.   
45.  public static void main(String[] args) {  
46.   ToastXToast temp = new ToastXToast();  
47.  }  
48. }  

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を上げていきたいものです…．