TopCoder 練習

LockersDivOne(Member SRM 482 Div1 Easy)

愚直なシミュレーションでも動くことを確認．

view plainprint?

1. public class LockersDivOne{  
2.     public int lastOpened(int n){  
3.         int[] a=new int[n];  
4.         int[] b=new int[n];  
5.         int last=n;  
6.         for(int i=0;i<n;i++)  
7.             a[i]=i;  
8.         for(int s=2;;s++){  
9.             int k=0;  
10.             for(int i=0;i<last;i++){  
11.                 if(i%s!=0)  
12.                     b[k++]=a[i];  
13.             }  
14.             last=k;  
15.             if(last<=1)  
16.                 return b[0]+1;  
17.             for(int i=0;i<last;i++)  
18.                 a[i]=b[i];  
19.         }  
20.     }  
21. }  

public class LockersDivOne{
    public int lastOpened(int n){
        int[] a=new int[n];
        int[] b=new int[n];
        int last=n;
        for(int i=0;i<n;i++)
            a[i]=i;
        for(int s=2;;s++){
            int k=0;
            for(int i=0;i<last;i++){
                if(i%s!=0)
                    b[k++]=a[i];
            }
            last=k;
            if(last<=1)
                return b[0]+1;
            for(int i=0;i<last;i++)
                a[i]=b[i];
        }
    }
}