TopCoder 練習 NewAlbum(SRM 296 Div1 Easy)

NewAlbum(SRM 296 Div1 Easy)

■問題
length分/曲である音楽をnSongs曲CDに入れたい．但し，1枚辺りcdCapacity分しかCDに入れることは出来ない．また，CDに詰める曲数が13で割りきれてはいけない．最小何枚のCDで足りるか．

■解法
下のコードはかなり適当ですが，方針は以下の通り．
1. 1枚のCDに最大で何曲詰められるかを計算．
2. 13で割り切れるかどうかを考慮しない状態で，必要なCDの最小枚数を求める．
3. どう分配しても13で割りきれてしまう場合は，CDの枚数を+1する．

view plainprint?

1. public class NewAlbum{  
2.  public int leastAmountOfCDs(int nSongs, int length, int cdCapacity){  
3.   long oneCd=1;  
4.   for(;(oneCd+1)*length+(oneCd)<=cdCapacity;oneCd++)  
5.    ;  
6.   if(oneCd%13==0) oneCd--;  
7.   long left=0, right=1000000;  
8.   for(int i=0;i<100;i++){  
9.    long mid=(left+right)/2;  
10.    if(nSongs<=oneCd*mid)  
11.     right=mid;  
12.    else  
13.     left=mid;  
14.   }  
15.   int ret=(int)right;  
16.   if(nSongs%ret==0&(nSongs/ret)%13==0)  
17.    ret++;  
18.   if((nSongs%oneCd)%13==0&&oneCd*ret==nSongs+1)  
19.    ret++;  
20.   return ret;  
21.  }  
22. }  

public class NewAlbum{
 public int leastAmountOfCDs(int nSongs, int length, int cdCapacity){
  long oneCd=1;
  for(;(oneCd+1)*length+(oneCd)<=cdCapacity;oneCd++)
   ;
  if(oneCd%13==0) oneCd--;
  long left=0, right=1000000;
  for(int i=0;i<100;i++){
   long mid=(left+right)/2;
   if(nSongs<=oneCd*mid)
    right=mid;
   else
    left=mid;
  }
  int ret=(int)right;
  if(nSongs%ret==0&(nSongs/ret)%13==0)
   ret++;
  if((nSongs%oneCd)%13==0&&oneCd*ret==nSongs+1)
   ret++;
  return ret;
 }
}