2010年10月30日土曜日

TopCoder 練習

RabbitNumber(SRM 484 Div1 Easy)

■問題
S(x):=xの各桁の総和とする．S(x*x)=S(x)*S(x)となるxをRabbit Numberと呼ぶ．
low以上high以下の数の内，Rabbit Numberはいくつあるか．

■解法
chokudaiさんのニコ生を頼りに解く．
まず，小さい数について実験してみると，各桁は必ず3以下である事が分かる．これは，4*4=16から分かるように，4以上の数の次乗には繰り上がりが発生してしまうから．
よって，各桁が3以下である数について試せば良い．
入力の最大値は1,000,000,000であるが，上記の条件を満たすものは約260000個であり，候補が十分に絞れるので，あとは全探索すればよい．

view plainprint?
  1. public class RabbitNumber{  
  2.  public int theCount(int low, int high){  
  3.   int res=0;  
  4.   for(int i=1;;i++){  
  5.    long n=0;  
  6.    long r=1;  
  7.    for(int k=i;k!=0;k>>=2){  
  8.     n+=(k&3)*r;  
  9.     r*=10;  
  10.    }  
  11.    if(n<low)  
  12.     continue;  
  13.    if(n>high)  
  14.     break;  
  15.    if(S(n*n)==S(n)*S(n))  
  16.     res++;  
  17.   }  
  18.   return res;  
  19.  }  
  20.   
  21.  long S(long x){  
  22.   long ret=0;  
  23.   for(;x!=0;x/=10)  
  24.    ret+=(x%10);  
  25.   return ret;  
  26.  }  
  27. }  
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder 練習

AfraidOfEven(Member SRM 485 Div1 Easy)

■問題
Sashaはある等差数列{ai}を黒板に書いた．偶数が嫌いなPashaは，数列上の各数aiを偶数でなくなるまで2で割り続け，biとした．Pashaによって書き換えられた数列{bi}から元の数列{ai}を求めよ．候補が複数存在する場合は，辞書式順に最も早いものを答えとせよ．

■解法
1. a0=b02m，a1=b12nと決定する．
2. 公差d=a1-a0が求まるので，ai>=2が実現可能かを調べる．具体的には，ai=a0+di=bi2kであるので，(a0+di)/biが2のべき乗となるかどうか．
3. 全候補の内，辞書式順に最も早いものを答えとする．

計算時間は，a0，a1それぞれの決定に高々32ループ，実現可能かを調べるのに{ai}の長さループなので余裕です．

■コード
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4.   
  5. public class AfraidOfEven{  
  6.  public int[] restoreProgression(int[] seq){  
  7.   int[] ret=new int[seq.length];  
  8.   int[] arr=new int[seq.length];  
  9.   String s1=null;  
  10.   for(long a0=seq[0];a0<=Integer.MAX_VALUE;a0*=2){  
  11.    arr[0]=(int)a0;  
  12.    for(long a1=seq[1];a1<=Integer.MAX_VALUE;a1*=2){  
  13.     arr[1]=(int)a1;  
  14.     long d=a1-a0;  
  15.     long a=a1+d;  
  16.     boolean f=true;  
  17.     for(int i=2;i<seq.length;i++){  
  18.      arr[i]=(int)a;  
  19.      if(a<0) f=false;  
  20.      if(a%seq[i]!=0) f=false;  
  21.      long k=a/seq[i];  
  22.      if((k&(k-1))!=0) f=false;  
  23.      a+=d;  
  24.     }  
  25.     if(f){  
  26.      String s2=Arrays.toString(arr);  
  27.      if(s1==null||s2.length()<s1.length()||(s2.length()==s1.length()&&s2.compareTo(s1)<0)){  
  28.       System.arraycopy(arr,0,ret,0,seq.length);  
  29.       s1=s2;  
  30.      }  
  31.     }  
  32.    }  
  33.   }  
  34.   return ret;  
  35.  }  
  36. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2010年10月27日水曜日

TopCoder 練習

OneRegister(SRM 486 Div1 Easy)

wataさんのコードを参考に，というかほぼ丸写ししています．

基本的には，(s,t)と(1,t)を算出して，辞書式順に早いものを返しているようです．
rec(s,t)が非常にすっきりしていて凄い．再帰で書くとTLEするかと思いましたが，余裕だったようです．

view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4.   
  5. public class OneRegister{  
  6.  public String getProgram(int s, int t){  
  7.   String res=rec(1,t);  
  8.   if(res!=null) res="/"+res;  
  9.   res=min(res,rec(s,t));  
  10.   if(res==null) return ":-(";  
  11.   return res;  
  12.  }  
  13.  String rec(long s,long t){  
  14.   if(s==t) return "";  
  15.   if(s>t) return null;  
  16.   String a=rec(s*2,t);  
  17.   if(a!=null) a="+"+a;  
  18.   String b=s==1?null:rec(s*s,t);  
  19.   if(b!=null) b="*"+b;  
  20.   return min(a,b);  
  21.  }  
  22.  String min(String s,String t){  
  23.   if(s==null) return t;  
  24.   if(t==null) return s;  
  25.   if(s.length()<t.length()) return="" s;<br="">  if(s.length()>t.length()) return t;  
  26.   if(s.compareTo(t)<=0) return s;  
  27.   return t;  
  28.  }  
  29. }</t.length())>  
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder SRM 486

SRM 482(10/27 0:00~2:00)

久し振りの参加+悪夢再び…．

■OneRegister(DIV1 Easy)

□Problem
値を一つ格納できるレジスタがある．レジスタには，格納されている値の加減乗除を再代入できる．初めにsが格納されている時，0回以上の演算の結果，tに変更出来るか．出来る場合は，命令数が最小となるような命令列を返せ．

解法があまりにも適当だったので落ちました…．

■Result
××× 0 -0
0.0p

■Rating
1463 -> 1399
1500への道は遠い…．
投稿者 時刻: 0 件のコメント:
ラベル:

JAPLJ Contest

japljさん主催のJAPLJ Contestに参加してきました．

今回は久し振りのプログラミングコンテストでしたので散々でした．

問題はImo Judgeより閲覧できます．
解説はjapljさんの以下の記事に譲ります．
JAPLJ Contest まとめと解説

■Result
Rank34 100 0 50 - - -

A問題だけどうにかこうにか出しました．Cは嘘解法な感じだったので，半分の点数しか得られませんでした．無念．
投稿者 時刻: 0 件のコメント:

2010年10月4日月曜日

Maximum-Cup 2010

埼玉大学主催のプログラミングコンテストMaximum-Cupに参加して来ました．

Maximum-Cup 2010

問題はM-Judgeから閲覧できます．

■Problem A さいたまトラップ
幾つかのトラップがある．Sくんはトラップを除去する事にしたが，除去には決められた時間がかかる．更に，除去作業を1時間行うごとに10分間の休憩が必要である．Sくんは24時間未満に全てのトラップを除去出来るか．出来る場合は除去終了までの時間を求めよ．

サクサクッと実装したのですがWA．
ずいぶん後になって，1時間丁度で終わる場合の休憩時間の処理を間違えていたことに気付きました…．

01:39 AC

■Problem D 北海道のレストラン
幾つかのレストランに社員がいる．勤続年数100年のオーナーは接客研修会を開くため，ある1つのレストランをその会場とし，社員全員をそこに集めたい．
社員一人一人の移動コストは(勤務先のレストランと会場のレストランとの距離)x(勤続年数)で定義される．
移動コストの総和が最も小さくなるのはどのレストランか．

距離はFloyd-Warshallで求められますし，どのレストランを選ぶかも全探索で可能そうでしたのでサクサクッと組みましたがWA．
□トラップその1…オーナーも含む
オーナーは店番号1である，勤続年数100年の社員として計算の考慮に入ればければなりませんでした．
□トラップその2…レストランiとレストランjの距離は複数与えられる
これはコンテスト終了まで気付きませんでした．

■Problem G Arithmetic Geometric Sequence
http://m-judge.maximum.vc/problem.cgi?pid=10174参照．

最初は無理ゲーだと思ったのですが，数列Qにおいて，ある数k以下となる項の個数n(k)は容易に求められることが分かりました．
具体的には，
n(k)=[k/1]+[k/m]+[k/m2]+[k/m3]+[k/m4]+…
ですので，m=0,1の時だけ注意して，n(k)=xとなるkを二分探索で求めれば完了です．

03:22 AC

結局解けたのは，AとGだけという散々な結果でした．
まだまだ詰めが甘く，実装力が高いとは言えない，ということを思い知らされたコンテストでした．
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3061 Subsequence

■3061 Subsequence

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p3061;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     int INF=1<<28;  
  17.     double EPS=1e-9;  
  18.   
  19.     int n, s;  
  20.     int[] a;  
  21.   
  22.     void run(){  
  23.         for(int t=sc.nextInt(); t>0; t--){  
  24.             n=sc.nextInt();  
  25.             s=sc.nextInt();  
  26.             a=new int[n];  
  27.             for(int i=0; i<n; i++)  
  28.                 a[i]=sc.nextInt();  
  29.             println(cal()+"");  
  30.         }  
  31.     }  
  32.   
  33.     int cal(){  
  34.         int res=n+1;  
  35.         int p=0, q=0, sum=0;  
  36.   
  37.         for(;;){  
  38.             while(q<n&&sum<s)  
  39.                 sum+=a[q++];  
  40.             if(sum<s)  
  41.                 break;  
  42.             res=Math.min(res, q-p);  
  43.             sum-=a[p++];  
  44.         }  
  45.         return res%(n+1);  
  46.     }  
  47.   
  48.     void print(String s){  
  49.         System.out.print(s);  
  50.     }  
  51.   
  52.     void println(String s){  
  53.         System.out.println(s);  
  54.     }  
  55.   
  56.     public static void main(String[] args){  
  57.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  58.         new Main().run();  
  59.     }  
  60. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2456 Aggressive cows

■2456 Aggressive cows

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p2456;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     int INF=1<<28;  
  17.     double EPS=1e-9;  
  18.   
  19.     int n, c;  
  20.     int[] a;  
  21.   
  22.     void run(){  
  23.         n=sc.nextInt();  
  24.         c=sc.nextInt();  
  25.         a=new int[n];  
  26.         for(int i=0; i<n; i++)  
  27.             a[i]=sc.nextInt();  
  28.         Arrays.sort(a);  
  29.   
  30.         int low=0, up=INF;  
  31.   
  32.         for(int i=0; i<100; i++){  
  33.             int mid=(low+up)/2;  
  34.             if(C(mid))  
  35.                 low=mid;  
  36.             else  
  37.                 up=mid;  
  38.         }  
  39.         println(""+low);  
  40.     }  
  41.   
  42.     boolean C(int x){  
  43.         int last=0;  
  44.         for(int i=1; i<c; i++){  
  45.             int next=last+1;  
  46.             while(next<n&&a[next]-a[last]<x)  
  47.                 next++;  
  48.             if(next==n)  
  49.                 return false;  
  50.             last=next;  
  51.         }  
  52.         return true;  
  53.     }  
  54.   
  55.     void print(String s){  
  56.         System.out.print(s);  
  57.     }  
  58.   
  59.     void println(String s){  
  60.         System.out.println(s);  
  61.     }  
  62.   
  63.     public static void main(String[] args){  
  64.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  65.         new Main().run();  
  66.     }  
  67. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3723 Conscription

■3723 Conscription

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p3723;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     int INF=1<<28;  
  17.     double EPS=1e-9;  
  18.   
  19.     int[] p, rank;  
  20.   
  21.     void run(){  
  22.         int t=Integer.parseInt(sc.next());  
  23.         for(int k=0; k<t; k++){  
  24.             int n=Integer.parseInt(sc.next());// girl  
  25.             int m=Integer.parseInt(sc.next());// boy  
  26.             int r=Integer.parseInt(sc.next());  
  27.             E[] es=new E[r];  
  28.             for(int i=0; i<r; i++){  
  29.                 int x=Integer.parseInt(sc.next());  
  30.                 int y=Integer.parseInt(sc.next())+n;  
  31.                 int d=Integer.parseInt(sc.next());  
  32.                 es[i]=new E(x, y, d);  
  33.             }  
  34.             Arrays.sort(es, new Comparator<E>(){  
  35.                 public int compare(E e1, E e2){  
  36.                     return e2.d-e1.d;  
  37.                 }  
  38.             });  
  39.   
  40.             p=new int[n+m];  
  41.             rank=new int[n+m];  
  42.             for(int i=0; i<n+m; i++)  
  43.                 p[i]=i;  
  44.             int sumD=0;  
  45.             for(E e : es){  
  46.                 // println(e.d+"");  
  47.                 if(find(e.x)!=find(e.y)){  
  48.                     sumD+=e.d;  
  49.                     union(e.x, e.y);  
  50.                 }  
  51.             }  
  52.             int ans=10000*(n+m)-sumD;  
  53.             println(""+ans);  
  54.         }  
  55.     }  
  56.   
  57.     void union(int x, int y){  
  58.         x=find(x);  
  59.         y=find(y);  
  60.         if(rank[x]<rank[y]){  
  61.             p[x]=y;  
  62.         }else{  
  63.             p[y]=x;  
  64.             if(rank[x]==rank[y]){  
  65.                 rank[x]++;  
  66.             }  
  67.         }  
  68.     }  
  69.   
  70.     int find(int x){  
  71.         if(p[x]!=x)  
  72.             p[x]=find(p[x]);  
  73.         return p[x];  
  74.     }  
  75.   
  76.     void print(String s){  
  77.         System.out.print(s);  
  78.     }  
  79.   
  80.     void println(String s){  
  81.         System.out.println(s);  
  82.     }  
  83.   
  84.     public static void main(String[] args){  
  85.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  86.         new Main().run();  
  87.     }  
  88.   
  89.     class E{  
  90.         int x, y;  
  91.         int d;  
  92.   
  93.         E(int x, int y, int d){  
  94.             this.x=x;  
  95.             this.y=y;  
  96.             this.d=d;  
  97.         }  
  98.     }  
  99. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 1182 食物链

■1182 食物链

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p1182;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     int INF=1<<28;  
  17.     double EPS=1e-9;  
  18.   
  19.     int[] p;  
  20.     int[] rank;  
  21.   
  22.     void run(){  
  23.         int n=Integer.parseInt(sc.next());  
  24.         int k=Integer.parseInt(sc.next());  
  25.         p=new int[3*n];  
  26.         rank=new int[3*n];  
  27.         for(int i=0; i<3*n; i++)  
  28.             p[i]=i;  
  29.         int ans=0;  
  30.         for(int i=0; i<k; i++){  
  31.             int d=Integer.parseInt(sc.next());  
  32.             int x=Integer.parseInt(sc.next())-1;  
  33.             int y=Integer.parseInt(sc.next())-1;  
  34.             if(x<0||x>=n||y<0||y>=n){  
  35.                 ans++;  
  36.                 continue;  
  37.             }  
  38.             if(d==1){  
  39.                 // x=y  
  40.                 if(same(x, y+n)||same(x, y+2*n)){  
  41.                     ans++;  
  42.                 }else{  
  43.                     union(x, y);  
  44.                     union(x+n, y+n);  
  45.                     union(x+2*n, y+2*n);  
  46.                 }  
  47.             }else if(d==2){  
  48.                 // x->y  
  49.                 // x=y+n  
  50.                 if(same(x, y)||same(x, y+2*n)){  
  51.                     ans++;  
  52.                 }else{  
  53.                     union(x, y+n);  
  54.                     union(x+n, y+2*n);  
  55.                     union(x+2*n, y);  
  56.                 }  
  57.             }  
  58.         }  
  59.         println(""+ans);  
  60.   
  61.     }  
  62.   
  63.     boolean same(int x, int y){  
  64.         return findSet(x)==findSet(y);  
  65.     }  
  66.   
  67.     void union(int x, int y){  
  68.         x=findSet(x);  
  69.         y=findSet(y);  
  70.         if(rank[x]<rank[y]){  
  71.             p[x]=y;  
  72.         }else{  
  73.             p[y]=x;  
  74.             if(rank[x]==rank[y])  
  75.                 rank[x]++;  
  76.         }  
  77.     }  
  78.   
  79.     int findSet(int x){  
  80.         if(p[x]!=x)  
  81.             p[x]=findSet(p[x]);  
  82.         return p[x];  
  83.     }  
  84.   
  85.     void print(String s){  
  86.         System.out.print(s);  
  87.     }  
  88.   
  89.     void println(String s){  
  90.         System.out.println(s);  
  91.     }  
  92.   
  93.     public static void main(String[] args){  
  94.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  95.         new Main().run();  
  96.     }  
  97. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2431 Expedition

■2431 Expedition

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p2431;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     int INF=1<<28;  
  17.     double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int n=sc.nextInt();  
  21.         Stop[] stops=new Stop[n+1];  
  22.         for(int i=n-1; i>=0; i--){  
  23.             stops[i]=new Stop();  
  24.             stops[i].pos=sc.nextInt();  
  25.             stops[i].fuel=sc.nextInt();  
  26.         }  
  27.         stops[n]=new Stop();  
  28.         int l=sc.nextInt();  
  29.         int p=sc.nextInt();  
  30.         for(int i=0; i<=n; i++)  
  31.             stops[i].pos=l-stops[i].pos;  
  32.         Arrays.sort(stops, new Comparator<Stop>(){  
  33.             public int compare(Stop p1, Stop p2){  
  34.                 return p1.pos-p2.pos;  
  35.             }  
  36.         });  
  37.         int pos=0;  
  38.         int ans=0;  
  39.         PriorityQueue<Integer> q=new PriorityQueue<Integer>();  
  40.         for(int i=0; i<=n; i++){  
  41.             int d=stops[i].pos-pos;  
  42.             while(p-d<0){  
  43.                 if(q.isEmpty()){  
  44.                     println("-1");  
  45.                     return;  
  46.                 }  
  47.                 p-=q.poll();  
  48.                 ans++;  
  49.             }  
  50.             p-=d;  
  51.             pos=stops[i].pos;  
  52.             q.offer(-stops[i].fuel);  
  53.         }  
  54.         println(""+ans);  
  55.     }  
  56.   
  57.     class Stop{  
  58.         int pos;  
  59.         int fuel;  
  60.     }  
  61.   
  62.     void print(String s){  
  63.         System.out.print(s);  
  64.     }  
  65.   
  66.     void println(String s){  
  67.         System.out.println(s);  
  68.     }  
  69.   
  70.     public static void main(String[] args){  
  71.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  72.         new Main().run();  
  73.     }  
  74. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3253 Fence Repair

■3253 Fence Repair

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p3253;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=1<<28;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int n=sc.nextInt();  
  21.         PriorityQueue<Long> queue=new PriorityQueue<Long>();  
  22.         for(int i=0; i<n; i++)  
  23.             queue.offer(sc.nextLong());  
  24.         long ans=0;  
  25.         for(; queue.size()>1;){  
  26.             long k1=queue.poll();  
  27.             long k2=queue.poll();  
  28.             ans+=k1+k2;  
  29.             queue.offer(k1+k2);  
  30.         }  
  31.         println(""+ans);  
  32.     }  
  33.   
  34.     void print(String s){  
  35.         System.out.print(s);  
  36.     }  
  37.   
  38.     void println(String s){  
  39.         System.out.println(s);  
  40.     }  
  41.   
  42.     public static void main(String[] args){  
  43.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  44.         new Main().run();  
  45.     }  
  46. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3069 Saruman's Army

■3069 Saruman's Army

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p3069;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=1<<28;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         for(;;){  
  21.   
  22.             int r=sc.nextInt();  
  23.             int n=sc.nextInt();  
  24.   
  25.             if(r==-1&&n==-1)  
  26.                 break;  
  27.   
  28.             int[] a=new int[n];  
  29.             for(int i=0; i<n; i++)  
  30.                 a[i]=sc.nextInt();  
  31.             Arrays.sort(a);  
  32.   
  33.             int ans=0;  
  34.             for(int i=0; i<n;){  
  35.                 int s=a[i++];  
  36.                 while(i<n&&a[i]<=s+r)  
  37.                     i++;  
  38.                 int p=a[i-1];  
  39.                 while(i<n&&a[i]<=p+r)  
  40.                     i++;  
  41.                 ans++;  
  42.             }  
  43.             println(ans+"");  
  44.         }  
  45.     }  
  46.   
  47.     void print(String s){  
  48.         System.out.print(s);  
  49.     }  
  50.   
  51.     void println(String s){  
  52.         System.out.println(s);  
  53.     }  
  54.   
  55.     public static void main(String[] args){  
  56.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  57.         new Main().run();  
  58.     }  
  59. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3617 Best Cow Line

■3617 Best Cow Line

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p3617;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=1<<28;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int n=sc.nextInt();  
  21.         char[] cs=new char[n];  
  22.         for(int i=0; i<n; i++)  
  23.             cs[i]=sc.next().charAt(0);  
  24.         int l=0;  
  25.         int r=n-1;  
  26.         for(int k=1; k<=n; k++){  
  27.             boolean left=false;  
  28.             for(int i=0; l+i<=r-i; i++){  
  29.                 if(cs[l+i]<cs[r-i]){  
  30.                     left=true;  
  31.                     break;  
  32.                 }else if(cs[l+i]>cs[r-i]){  
  33.                     break;  
  34.                 }  
  35.             }  
  36.             if(left)  
  37.                 print(cs[l++]+"");  
  38.             else  
  39.                 print(cs[r--]+"");  
  40.             if(k%80==0)  
  41.                 println("");  
  42.         }  
  43.     }  
  44.   
  45.     void print(String s){  
  46.         System.out.print(s);  
  47.     }  
  48.   
  49.     void println(String s){  
  50.         System.out.println(s);  
  51.     }  
  52.   
  53.     public static void main(String[] args){  
  54.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  55.         new Main().run();  
  56.     }  
  57. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2386 Lake Counting

■2386 Lake Counting

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code
view plainprint?
  1. package p2386;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=1<<28;  
  17.     final double EPS=1e-9;  
  18.   
  19.     int n, m;  
  20.     int[][] a;  
  21.     boolean[][] f;  
  22.   
  23.     void run(){  
  24.         n=sc.nextInt();  
  25.         m=sc.nextInt();  
  26.         a=new int[n][m];  
  27.         f=new boolean[n][m];  
  28.         for(int j=0; j<n; j++){  
  29.             String s=sc.next();  
  30.             for(int i=0; i<m; i++){  
  31.                 a[j][i]=s.charAt(i)=='.'?0:1;  
  32.             }  
  33.         }  
  34.         int ans=0;  
  35.         for(int j=0; j<n; j++){  
  36.             for(int i=0; i<m; i++){  
  37.                 if(a[j][i]==1&&!f[j][i]){  
  38.                     ans++;  
  39.                     visit(i, j);  
  40.                 }  
  41.             }  
  42.         }  
  43.         println(ans+"");  
  44.     }  
  45.   
  46.     void visit(int x, int y){  
  47.         f[y][x]=true;  
  48.         for(int j=-1; j<=1; j++){  
  49.             int y2=y+j;  
  50.             if(y2<0||y2>=n)  
  51.                 continue;  
  52.             for(int i=-1; i<=1; i++){  
  53.                 int x2=x+i;  
  54.                 if(x2<0||x2>=m)  
  55.                     continue;  
  56.                 if(a[y2][x2]==1&&!f[y2][x2]){  
  57.                     visit(x2, y2);  
  58.                 }  
  59.             }  
  60.         }  
  61.     }  
  62.   
  63.     void print(String s){  
  64.         System.out.print(s);  
  65.     }  
  66.   
  67.     void println(String s){  
  68.         System.out.println(s);  
  69.     }  
  70.   
  71.     public static void main(String[] args){  
  72.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  73.         new Main().run();  
  74.     }  
  75. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 1852 Ants

■1852 Ants

□Problem
プログラミングコンテストチャレンジブック参照．

□Solution
プログラミングコンテストチャレンジブック参照．

□Code
view plainprint?
  1. package p1852;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final double EPS=1e-9;  
  17.   
  18.     void run(){  
  19.         for(int t=sc.nextInt(); t>0; t--){  
  20.             int length=sc.nextInt();  
  21.             int n=sc.nextInt();  
  22.             int earlist=0, latest=0;  
  23.             for(int i=0; i<n; i++){  
  24.                 int a=sc.nextInt();  
  25.                 int min=Math.min(a, length-a);  
  26.                 int max=Math.max(a, length-a);  
  27.                 earlist=max(earlist,min);  
  28.                 latest=max(latest,max);  
  29.             }  
  30.             println(earlist+" "+latest);  
  31.         }  
  32.     }  
  33.   
  34.     void print(String s){  
  35.         System.out.print(s);  
  36.     }  
  37.   
  38.     void println(String s){  
  39.         System.out.println(s);  
  40.     }  
  41.   
  42.     public static void main(String[] args){  
  43.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  44.         new Main().run();  
  45.     }  
  46. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2010年10月2日土曜日

PKU Judge Online 3085 Quick Change

■3085 Quick Change

□Problem
￠25,￠10,￠5,￠1の硬貨がある．￠nを最も硬貨が少なくなるように表せ．

□Solution
典型的な動的計画法．
dp[i][n]をi-1までの硬貨を使って，￠nを表す最小枚数とすると，
dp[i+1][n]=min{dp[i][n], dp[i][n-centi+1]+1}
ここで，centiは硬貨のiの価値．
dp[i][n]はnに初期化しておく．

□Code
view plainprint?
  1. package p3085;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int[] cents={25, 10, 5, 1};  
  21.         int n=sc.nextInt();  
  22.         for(int k=1; k<=n; k++){  
  23.             int c=sc.nextInt();  
  24.             int[] a=new int[c+1];  
  25.             for(int i=0; i<=c; i++)  
  26.                 a[i]=i;  
  27.             int[] b=new int[c+1];  
  28.             for(int j=0; j<4; j++){  
  29.                 for(int i=cents[j]; i<=c; i++){  
  30.                     int s=i-cents[j];  
  31.                     if(a[s]+1<=a[i]){  
  32.                         a[i]=a[s]+1;  
  33.                         b[i]=j;  
  34.                     }  
  35.                 }  
  36.             }  
  37.             int[] count=new int[4];  
  38.             for(;;){  
  39.                 count[b[c]]++;  
  40.                 c-=cents[b[c]];  
  41.                 if(c==0)  
  42.                     break;  
  43.             }  
  44.             println(k+" "+count[0]+" QUARTER(S), "+count[1]+" DIME(S), "  
  45.                     +count[2]+" NICKEL(S), "+count[3]+" PENNY(S)");  
  46.         }  
  47.     }  
  48.   
  49.     void print(String s){  
  50.         System.out.print(s);  
  51.     }  
  52.   
  53.     void println(String s){  
  54.         System.out.println(s);  
  55.     }  
  56.   
  57.     public static void main(String[] args){  
  58.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  59.         new Main().run();  
  60.     }  
  61. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 1028 Web Navigation

■1028 Web Navigation

□Problem
ウェブブラウザのシミュレーションを行え．命令は以下のとおりである．
BACK: 前のページに戻る．
FORWARD: 次のページに進む．
VISIT: 指定されたURLにジャンプ．
QUIT: ブラウザを終了する．

□Solution
閲覧したページをリストに格納しておけばOK．

□Code
view plainprint?
  1. package p1028;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         LinkedList<String> backward=new LinkedList<String>();  
  21.         LinkedList<String> forward=new LinkedList<String>();  
  22.         String url="http://www.acm.org/";  
  23.         for(;;){  
  24.             String[] ss=sc.nextLine().split(" ");  
  25.             String s=ss[0];  
  26.             if(s.equals("VISIT")){  
  27.                 backward.addFirst(url);  
  28.                 forward.clear();  
  29.                 url=ss[1];  
  30.                 println(url);  
  31.             }else if(s.equals("BACK")){  
  32.                 if(backward.size()==0)  
  33.                     println("Ignored");  
  34.                 else{  
  35.                     forward.addFirst(url);  
  36.                     url=backward.removeFirst();  
  37.                     println(url);  
  38.                 }  
  39.             }else if(s.equals("FORWARD")){  
  40.                 if(forward.size()==0)  
  41.                     println("Ignored");  
  42.                 else{  
  43.                     backward.addFirst(url);  
  44.                     url=forward.removeFirst();  
  45.                     println(url);  
  46.                 }  
  47.             }else if(s.equals("QUIT")){  
  48.                 break;  
  49.             }  
  50.         }  
  51.         System.out.flush();  
  52.     }  
  53.   
  54.     void print(String s){  
  55.         System.out.print(s);  
  56.     }  
  57.   
  58.     void println(String s){  
  59.         System.out.println(s);  
  60.     }  
  61.   
  62.     public static void main(String[] args){  
  63.         System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  64.         new Main().run();  
  65.     }  
  66. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 1051 P,MTHBGWB

■1051 P,MTHBGWB

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p1051;  
  2.   
  3. import java.util.*;  
  4. import java.util.Map.Entry;  
  5. import java.lang.*;  
  6. import java.math.*;  
  7. import java.io.*;  
  8.   
  9. import static java.lang.Math.*;  
  10. import static java.util.Arrays.*;  
  11.   
  12. // AC  
  13. public class Main{  
  14.   
  15.     Scanner sc=new Scanner(System.in);  
  16.   
  17.     final int INF=Integer.MAX_VALUE;  
  18.     final double EPS=1e-9;  
  19.   
  20.     void run(){  
  21.         HashMap<Character, String> map1=new HashMap<Character, String>();  
  22.         map1.put('A', ".-");  
  23.         map1.put('B', "-...");  
  24.         map1.put('C', "-.-.");  
  25.         map1.put('D', "-..");  
  26.         map1.put('E', ".");  
  27.         map1.put('F', "..-.");  
  28.         map1.put('G', "--.");  
  29.   
  30.         map1.put('H', "....");  
  31.         map1.put('I', "..");  
  32.         map1.put('J', ".---");  
  33.         map1.put('K', "-.-");  
  34.         map1.put('L', ".-..");  
  35.         map1.put('M', "--");  
  36.         map1.put('N', "-.");  
  37.   
  38.         map1.put('O', "---");  
  39.         map1.put('P', ".--.");  
  40.         map1.put('Q', "--.-");  
  41.         map1.put('R', ".-.");  
  42.         map1.put('S', "...");  
  43.         map1.put('T', "-");  
  44.         map1.put('U', "..-");  
  45.   
  46.         map1.put('V', "...-");  
  47.         map1.put('W', ".--");  
  48.         map1.put('X', "-..-");  
  49.         map1.put('Y', "-.--");  
  50.         map1.put('Z', "--..");  
  51.   
  52.         map1.put('_', "..--");  
  53.         map1.put(',', ".-.-");  
  54.         map1.put('.', "---.");  
  55.         map1.put('?', "----");  
  56.   
  57.         HashMap<String, Character> map2=new HashMap<String, Character>();  
  58.         for(Entry<Character, String> entry : map1.entrySet())  
  59.             map2.put(entry.getValue(), entry.getKey());  
  60.   
  61.         int n=sc.nextInt();  
  62.         sc.nextLine();  
  63.         for(int t=1; t<=n; t++){  
  64.             String s=sc.nextLine();  
  65.             int len=s.length();  
  66.             String e="";  
  67.             int[] a=new int[len];  
  68.             for(int i=0; i<len; i++){  
  69.                 e+=map1.get(s.charAt(i));  
  70.                 a[i]=map1.get(s.charAt(i)).length();  
  71.             }  
  72.             String ans="";  
  73.             int k=0;  
  74.             for(int j=0; j<len; j++){  
  75.                 String key="";  
  76.                 for(int i=0; i<a[len-1-j]; i++)  
  77.                     key+=e.charAt(k++);  
  78.                 ans+=map2.get(key);  
  79.             }  
  80.             println(t+": "+ans);  
  81.         }  
  82.     }  
  83.   
  84.     void print(String s){  
  85.         System.out.print(s);  
  86.     }  
  87.   
  88.     void println(String s){  
  89.         System.out.println(s);  
  90.     }  
  91.   
  92.     public static void main(String[] args){  
  93.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  94.         new Main().run();  
  95.     }  
  96. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2010年10月1日金曜日

PKU Judge Online 3173 Parkside's Triangle

■3173 Parkside's Triangle

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p3173;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int n=sc.nextInt();  
  21.         int s=sc.nextInt();  
  22.         int[][] a=new int[n][n];  
  23.         for(int i=0; i<n; i++){  
  24.             for(int j=0; j<=i; j++){  
  25.                 a[j][i]=s++;  
  26.                 if(s==10)  
  27.                     s=1;  
  28.             }  
  29.         }  
  30.         for(int j=0; j<n; j++){  
  31.             for(int i=0; i<j; i++)  
  32.                 print("  ");  
  33.             for(int i=j; i<n; i++)  
  34.                 print(a[j][i]+(i==n-1?"":" "));  
  35.             println("");  
  36.         }  
  37.     }  
  38.   
  39.     void print(String s){  
  40.         System.out.print(s);  
  41.     }  
  42.   
  43.     void println(String s){  
  44.         System.out.println(s);  
  45.     }  
  46.   
  47.     public static void main(String[] args){  
  48.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  49.         new Main().run();  
  50.     }  
  51. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3100 Root of the Problem

■3100 Root of the Problem

□Problem
整数b，nが与えられる．anがbと最も近くなるような整数aを求めよ．

□Solution
a=elog(b)/n
なので，上式で近そうな値をとり，その周辺を探す．

□Code
view plainprint?
  1. package p3100;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         for(;;){  
  21.             int b=sc.nextInt();  
  22.             int n=sc.nextInt();  
  23.             if(b==0&&n==0)  
  24.                 break;  
  25.             int a=(int)Math.exp(Math.log(b)/n);  
  26.             a--;  
  27.             int ans=a;  
  28.             double ansPowN=Math.pow(ans, n);  
  29.             for(int i=a;; i++){  
  30.                 double iPowN=Math.pow(i, n);  
  31.                 if(Math.abs(b-iPowN)<Math.abs(b-ansPowN)){  
  32.                     ans=i;  
  33.                     ansPowN=iPowN;  
  34.                 }  
  35.                 if(iPowN>b){  
  36.                     break;  
  37.                 }  
  38.             }  
  39.             println(ans+"");  
  40.         }  
  41.     }  
  42.   
  43.     void print(String s){  
  44.         System.out.print(s);  
  45.     }  
  46.   
  47.     void println(String s){  
  48.         System.out.println(s);  
  49.     }  
  50.   
  51.     public static void main(String[] args){  
  52.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  53.         new Main().run();  
  54.     }  
  55. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3176 Cow Bowling

■3176 Cow Bowling

□Problem
          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5

このようなピラミッドを上から底辺までたどっていく．たどって来た数字を全て足し合わせたた合計の最大値を求めよ．

□Solution
下からDPしていく．

□Code
view plainprint?
  1. package p3176;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int n=sc.nextInt();  
  21.         int[][] a=new int[n][n];  
  22.         for(int j=0; j<n; j++)  
  23.             for(int i=0; i<=j; i++)  
  24.                 a[j][i]=sc.nextInt();  
  25.         for(int j=n-2; j>=0; j--)  
  26.             for(int i=0; i<=j; i++)  
  27.                 a[j][i]+=Math.max(a[j+1][i], a[j+1][i+1]);  
  28.         println(""+a[0][0]);  
  29.     }  
  30.   
  31.     void print(String s){  
  32.         System.out.print(s);  
  33.     }  
  34.   
  35.     void println(String s){  
  36.         System.out.println(s);  
  37.     }  
  38.   
  39.     public static void main(String[] args){  
  40.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  41.         new Main().run();  
  42.     }  
  43. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3086 Triangular Sums

■3086 Triangular Sums

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p3086;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int N=sc.nextInt();  
  21.         for(int k=1; k<=N; k++){  
  22.             int n=sc.nextInt();  
  23.             int ans=0;  
  24.             for(int i=1; i<=n; i++)  
  25.                 ans+=i*(i+1)*(i+2)/2;  
  26.             println(k+" "+n+" "+ans);  
  27.         }  
  28.     }  
  29.   
  30.     void print(String s){  
  31.         System.out.print(s);  
  32.     }  
  33.   
  34.     void println(String s){  
  35.         System.out.println(s);  
  36.     }  
  37.   
  38.     public static void main(String[] args){  
  39.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  40.         new Main().run();  
  41.     }  
  42. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3077 Rounders

■3077 Rounders

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p3077;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.  Scanner sc=new Scanner(System.in);  
  15.   
  16.  final int INF=Integer.MAX_VALUE;  
  17.  final double EPS=1e-9;  
  18.   
  19.  void run(){  
  20.   for(int n=sc.nextInt(); n>0; n--){  
  21.    int m=sc.nextInt();  
  22.    int ans=1;  
  23.    for(; m/10!=0;){  
  24.     if(m%10>=5)  
  25.      m+=10;  
  26.     m/=10;  
  27.     ans*=10;  
  28.    }  
  29.    ans*=m;  
  30.    println(ans+"");  
  31.   }  
  32.  }  
  33.   
  34.  void print(String s){  
  35.   System.out.print(s);  
  36.  }  
  37.   
  38.  void println(String s){  
  39.   System.out.println(s);  
  40.  }  
  41.   
  42.  public static void main(String[] args){  
  43.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  44.   new Main().run();  
  45.  }  
  46. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3030 Nasty Hacks

■3030 Nasty Hacks

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p3030;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.  Scanner sc=new Scanner(System.in);  
  15.   
  16.  final int INF=Integer.MAX_VALUE;  
  17.  final double EPS=1e-9;  
  18.   
  19.  void run(){  
  20.   for(int n=sc.nextInt(); n>0; n--){  
  21.    int r=sc.nextInt();  
  22.    int e=sc.nextInt();  
  23.    int c=sc.nextInt();  
  24.    e-=c;  
  25.    if(e>r)  
  26.     println("advertise");  
  27.    else if(e<r)  
  28.     println("do not advertise");  
  29.    else  
  30.     println("does not matter");  
  31.   }  
  32.  }  
  33.   
  34.  void print(String s){  
  35.   System.out.print(s);  
  36.  }  
  37.   
  38.  void println(String s){  
  39.   System.out.println(s);  
  40.  }  
  41.   
  42.  public static void main(String[] args){  
  43.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  44.   new Main().run();  
  45.  }  
  46. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 3094 Quicksum

■3094 Quicksum

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p3094;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         for(;;){  
  21.             String s=sc.nextLine();  
  22.             if(s.equals("#"))  
  23.                 break;  
  24.             int ans=0;  
  25.             for(int i=0; i<s.length(); i++)  
  26.                 if(Character.isUpperCase(s.charAt(i)))  
  27.                     ans+=(i+1)*(s.charAt(i)-'A'+1);  
  28.             println(ans+"");  
  29.         }  
  30.     }  
  31.   
  32.     void print(String s){  
  33.         System.out.print(s);  
  34.     }  
  35.   
  36.     void println(String s){  
  37.         System.out.println(s);  
  38.     }  
  39.   
  40.     public static void main(String[] args){  
  41.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  42.         new Main().run();  
  43.     }  
  44. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2136 Vertical Histogram

■2136 Vertical Histogram

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p2136;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int n='Z'-'A'+1;  
  21.         int[] a=new int[n];  
  22.   
  23.         for(int i=0; i<4; i++)  
  24.             for(char c : sc.nextLine().toCharArray())  
  25.                 if(Character.isUpperCase(c))  
  26.                     a[c-'A']++;  
  27.   
  28.         int max=0;  
  29.         for(int e : a)  
  30.             max=Math.max(max, e);  
  31.   
  32.         for(int j=max; j>0; j--){  
  33.             int last=0;  
  34.             for(int i=0; i<n; i++)  
  35.                 if(a[i]>=j)  
  36.                     last=i;  
  37.             for(int i=0; i<=last; i++){  
  38.                 print(a[i]>=j?"*":" ");  
  39.                 print(i==last?"":" ");  
  40.             }  
  41.             println("");  
  42.         }  
  43.         for(char c='A'; c<='Z'; c++)  
  44.             print(c+(c=='Z'?"":" "));  
  45.         println("");  
  46.     }  
  47.   
  48.     void print(String s){  
  49.         System.out.print(s);  
  50.     }  
  51.   
  52.     void println(String s){  
  53.         System.out.println(s);  
  54.     }  
  55.   
  56.     public static void main(String[] args){  
  57.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  58.         new Main().run();  
  59.     }  
  60. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2140 Herd Sums

■2140 Herd Sums

□Problem
自然数nを連続した自然数の和で表すには何通りのやり方があるか．
15の時は4通り．
15=1+2+3+4+5=4+5+6=7+8

□Solution
昔，考えた方法で解きました．同じようなことが書かれているページがあったので↓参照ということで．
http://www.bun-eido.co.jp/t_math/sjournal/sj28/sj282530.pdf

□Code
view plainprint?
  1. package p2140;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         int n=sc.nextInt();  
  21.         n*=2;  
  22.         int m=(int)Math.sqrt(n);  
  23.         int ans=0;  
  24.         for(int i=1; i<=m+1; i++){  
  25.             if(n%i==0){  
  26.                 int d=i;  
  27.                 int e=n/i;  
  28.                 if(d>e)  
  29.                     break;  
  30.                 if((d+e)%2==1)  
  31.                     ans++;  
  32.             }  
  33.         }  
  34.         println(ans+"");  
  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.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  47.         new Main().run();  
  48.     }  
  49. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2070 Filling Out the Team

■2070 Filling Out the Team

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p2070;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.  Scanner sc=new Scanner(System.in);  
  15.   
  16.  final int INF=Integer.MAX_VALUE;  
  17.  final double EPS=1e-9;  
  18.   
  19.  void run(){  
  20.   double[] speeds={4.5, 6.0, 5.0};  
  21.   double[] weights={150, 300, 200};  
  22.   double[] strengths={200, 500, 300};  
  23.   String[] ss={"Wide Receiver", "Lineman", "Quarterback"};  
  24.   for(;;){  
  25.    double speed=sc.nextDouble();  
  26.    double weight=sc.nextDouble();  
  27.    double strength=sc.nextDouble();  
  28.    if(speed==0&&weight==0&&strength==0)  
  29.     break;  
  30.    String ans="";  
  31.    for(int i=0; i<3; i++){  
  32.     if(speed<speeds[i]+EPS&&weight+EPS>weights[i]  
  33.       &&strength+EPS>strengths[i])  
  34.      ans+=ss[i]+" ";  
  35.    }  
  36.    if(ans.equals(""))  
  37.     println("No positions");  
  38.    else  
  39.     println(ans.substring(0, ans.length()-1));  
  40.   }  
  41.  }  
  42.   
  43.  void print(String s){  
  44.   System.out.print(s);  
  45.  }  
  46.   
  47.  void println(String s){  
  48.   System.out.println(s);  
  49.  }  
  50.   
  51.  public static void main(String[] args){  
  52.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  53.   new Main().run();  
  54.  }  
  55. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2039 To and Fro

■2039 To and Fro

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p2039;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         for(;;){  
  21.             int n=sc.nextInt();  
  22.             if(n==0)  
  23.                 break;  
  24.             String s=sc.next();  
  25.             int m=s.length()/n;  
  26.             for(int j=0; j<n; j++){  
  27.                 for(int i=0; i<m; i++){  
  28.                     int k=j+i*n;  
  29.                     if(i%2==1)  
  30.                         k+=n-1-2*j;  
  31.                     print(""+s.charAt(k));  
  32.                 }  
  33.             }  
  34.             println("");  
  35.         }  
  36.     }  
  37.   
  38.     void print(String s){  
  39.         System.out.print(s);  
  40.     }  
  41.   
  42.     void println(String s){  
  43.         System.out.println(s);  
  44.     }  
  45.   
  46.     public static void main(String[] args){  
  47.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  48.         new Main().run();  
  49.     }  
  50. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2081 Recaman's Sequence

■2081 Recaman's Sequence

□Problem
Recaman数列とは，以下で定義される．
a0=0
am=am-1-m
(am>0かつ，an=amとなるn<mが存在しない時)
am=am-1+m
(それ以外の時)

akを求めよ．

□Solution
0≦k≦500000であるため，予めakを求めておく．

□Code
view plainprint?
  1. package p2081;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.  Scanner sc=new Scanner(System.in);  
  15.   
  16.  final int INF=Integer.MAX_VALUE;  
  17.  final double EPS=1e-9;  
  18.   
  19.  void run(){  
  20.   int[] a=new int[500001];  
  21.   HashSet<Integer> set=new HashSet<Integer>();  
  22.   for(int m=1; m<500001; m++){  
  23.    int a2=a[m-1]-m;  
  24.    if(a2>0&&!set.contains(a2))  
  25.     a[m]=a2;  
  26.    else  
  27.     a[m]=a[m-1]+m;  
  28.    set.add(a[m]);  
  29.   }  
  30.   for(;;){  
  31.    int k=sc.nextInt();  
  32.    if(k==-1)  
  33.     break;  
  34.    println(a[k]+"");  
  35.   }  
  36.  }  
  37.   
  38.  void print(String s){  
  39.   System.out.print(s);  
  40.  }  
  41.   
  42.  void println(String s){  
  43.   System.out.println(s);  
  44.  }  
  45.   
  46.  public static void main(String[] args){  
  47.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  48.   new Main().run();  
  49.  }  
  50. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2013 Symmetric Order

■2013 Symmetric Order

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p2013;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.  Scanner sc=new Scanner(System.in);  
  15.   
  16.  final int INF=Integer.MAX_VALUE;  
  17.  final double EPS=1e-9;  
  18.   
  19.  void run(){  
  20.   for(int t=1;; t++){  
  21.    int n=sc.nextInt();  
  22.    if(n==0)  
  23.     break;  
  24.    String[] ss=new String[n];  
  25.    for(int i=0; i<n; i++)  
  26.     ss[i]=sc.next();  
  27.    LinkedList<String> list=new LinkedList<String>();  
  28.    for(int i=n-1; i>=0; i--)  
  29.     if(i%2==0)  
  30.      list.addFirst(ss[i]);  
  31.     else  
  32.      list.addLast(ss[i]);  
  33.    println("SET "+t);  
  34.    for(String s : list)  
  35.     println(s);  
  36.   }  
  37.  }  
  38.   
  39.  void print(String s){  
  40.   System.out.print(s);  
  41.  }  
  42.   
  43.  void println(String s){  
  44.   System.out.println(s);  
  45.  }  
  46.   
  47.  public static void main(String[] args){  
  48.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  49.   new Main().run();  
  50.  }  
  51. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2017 Speed Limit

■2017 Speed Limit

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p2017;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         for(;;){  
  21.             int n=sc.nextInt();  
  22.             if(n==-1)  
  23.                 break;  
  24.             int ph=0;  
  25.             int tot=0;  
  26.             for(int i=0; i<n; i++){  
  27.                 int v=sc.nextInt();  
  28.                 int h=sc.nextInt();  
  29.                 tot+=(h-ph)*v;  
  30.                 ph=h;  
  31.             }  
  32.             println(tot+" miles");  
  33.         }  
  34.     }  
  35.   
  36.     void print(String s){  
  37.         System.out.print(s);  
  38.     }  
  39.   
  40.     void println(String s){  
  41.         System.out.println(s);  
  42.     }  
  43.   
  44.     public static void main(String[] args){  
  45.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  46.         new Main().run();  
  47.     }  
  48. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 2027 No Brainer

■2027 No Brainer

□Problem
省略．

□Solution
省略．

□Code
view plainprint?
  1. package p2027;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         for(int n=sc.nextInt(); n>0; n--){  
  21.             int x=sc.nextInt();  
  22.             int y=sc.nextInt();  
  23.             println(x<y?"NO BRAINS":"MMM BRAINS");  
  24.         }  
  25.     }  
  26.   
  27.     void print(String s){  
  28.         System.out.print(s);  
  29.     }  
  30.   
  31.     void println(String s){  
  32.         System.out.println(s);  
  33.     }  
  34.   
  35.     public static void main(String[] args){  
  36.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  37.         new Main().run();  
  38.     }  
  39. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 1936 All in All

■1936 All in All

□Problem
文字列s，tが与えられる．sがtの部分文字列なら"Yes"，そうでなければ"No"を出力せよ．

□Solution
sとtの最長共通部分文字列がsの長さなら"Yes"．

□Code
view plainprint?
  1. package p1936;  
  2.   
  3. import java.util.*;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. // AC  
  12. public class Main{  
  13.   
  14.     Scanner sc=new Scanner(System.in);  
  15.   
  16.     final int INF=Integer.MAX_VALUE;  
  17.     final double EPS=1e-9;  
  18.   
  19.     void run(){  
  20.         for(; sc.hasNext();){  
  21.             String s=sc.next();  
  22.             String t=sc.next();  
  23.             int m=s.length();  
  24.             int n=t.length();  
  25.             int[][] dp=new int[n+1][m+1];  
  26.             for(int j=0; j<n; j++){  
  27.                 for(int i=0; i<m; i++){  
  28.                     if(s.charAt(i)==t.charAt(j))  
  29.                         dp[j+1][i+1]=dp[j][i]+1;  
  30.                     else  
  31.                         dp[j+1][i+1]=Math.max(dp[j+1][i], dp[j][i+1]);  
  32.                 }  
  33.             }  
  34.             println(dp[n][m]==m?"Yes":"No");  
  35.         }  
  36.     }  
  37.   
  38.     void print(String s){  
  39.         System.out.print(s);  
  40.     }  
  41.   
  42.     void println(String s){  
  43.         System.out.println(s);  
  44.     }  
  45.   
  46.     public static void main(String[] args){  
  47.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  48.         new Main().run();  
  49.     }  
  50. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 1256 Anagram

■1256 Anagram

□Problem
与えられた文字列を並び替えて，A<a<B<b<C<c<…という優先順位の元，辞書式順に出力せよ．但し，重複は省く．

□Solution
↑の優先順位でソートし，あとは1731と同じ．

□Code
view plainprint?
  1. package p1256;  
  2.   
  3. import java.util.*;  
  4. import java.io.BufferedOutputStream;  
  5. import java.io.PrintStream;  
  6. import java.lang.*;  
  7. import java.math.*;  
  8.   
  9. // AC  
  10. public class Main{  
  11.     Scanner sc=new Scanner(System.in);  
  12.   
  13.     char[] cs;  
  14.     int[] order;  
  15.     int n;  
  16.   
  17.     void recursive(int j){  
  18.         if(j==n){  
  19.             println(new String(cs));  
  20.             return;  
  21.         }  
  22.         for(int i=j; i<n; i++){  
  23.             // right rotate [j,i]  
  24.             char c=cs[i];  
  25.             int t=order[i];  
  26.             for(int k=i; k%gt;j; k--){  
  27.                 cs[k]=cs[k-1];  
  28.                 order[k]=order[k-1];  
  29.             }  
  30.             cs[j]=c;  
  31.             order[j]=t;  
  32.             boolean f=true;  
  33.             for(int k=j; k<=i; k++){  
  34.                 if(cs[j]==cs[k]&&order[j]%gt;order[k]){  
  35.                     f=false;  
  36.                     break;  
  37.                 }  
  38.             }  
  39.             if(f)  
  40.                 recursive(j+1);  
  41.             // left rotate [j,i]  
  42.             for(int k=j; k<i; k++){  
  43.                 cs[k]=cs[k+1];  
  44.                 order[k]=order[k+1];  
  45.             }  
  46.             cs[i]=c;  
  47.             order[i]=t;  
  48.         }  
  49.     }  
  50.   
  51.     void run(){  
  52.         for(int t=sc.nextInt(); t%gt;0; t--){  
  53.             cs=sc.next().toCharArray();  
  54.             n=cs.length;  
  55.             order=new int[n];  
  56.             for(int i=0; i<n; i++)  
  57.                 order[i]=i;  
  58.             Character[] a=new Character[n];  
  59.             for(int i=0; i<n; i++)  
  60.                 a[i]=cs[i];  
  61.             Arrays.sort(a, new Comparator<Character%gt;(){  
  62.                 @Override  
  63.                 public int compare(Character c1, Character c2){  
  64.                     char d1=Character.toLowerCase(c1);  
  65.                     char d2=Character.toLowerCase(c2);  
  66.                     if(d1!=d2)  
  67.                         return d1-d2;  
  68.                     else if(c1==c2)  
  69.                         return 0;  
  70.                     else  
  71.                         return c1-c2;  
  72.                 }  
  73.             });  
  74.             for(int i=0; i<n; i++)  
  75.                 cs[i]=a[i];  
  76.             recursive(0);  
  77.         }  
  78.         System.out.flush();  
  79.     }  
  80.   
  81.     void println(String s){  
  82.         System.out.println(s);  
  83.     }  
  84.   
  85.     void print(String s){  
  86.         System.out.print(s);  
  87.     }  
  88.   
  89.     public static void main(String[] args){  
  90.         System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  91.         new Main().run();  
  92.     }  
  93. }  
投稿者 時刻: 0 件のコメント:
ラベル:

PKU Judge Online 1731 Orders

■1731 Orders

□Problem
文字列sが与えられる．sの順列を辞書式順で生成せよ．但し，重複する文字列は省く．

□Solution
順列生成は再帰で．
重複を省くためには，以下．
まず，
s=c0c1…cn-1
に，
vk=kと数字を割り当てる．
再帰で順列を生成し，
s'=ca0ca1…can-1
となったとする．
cai=caj (i<j)
となるi,jがあった時，
vi<vj
であれば，その順列を出力し，そうでない場合は出力しない．
実際には，この判定を再帰の途中で行い，枝刈りをしている．

出力が遅かったため(TLEした)，
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
として，最後にまとめてストリームをフラッシュ．

□Code
view plainprint?
  1. package p1731;  
  2.   
  3. import java.util.*;  
  4. import java.io.BufferedOutputStream;  
  5. import java.io.PrintStream;  
  6. import java.lang.*;  
  7. import java.math.*;  
  8.   
  9. // AC  
  10. public class Main{  
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  char[] cs;  
  14.  int[] order;  
  15.  int n;  
  16.   
  17.  void recursive(int j){  
  18.   if(j==n){  
  19.    println(new String(cs));  
  20.    return;  
  21.   }  
  22.   for(int i=j; i<n; i++){  
  23.    // right rotate [j,i]  
  24.    char c=cs[i];  
  25.    int t=order[i];  
  26.    for(int k=i; k>j; k--){  
  27.     cs[k]=cs[k-1];  
  28.     order[k]=order[k-1];  
  29.    }  
  30.    cs[j]=c;  
  31.    order[j]=t;  
  32.    boolean f=true;  
  33.    for(int k=j; k<=i; k++){  
  34.     if(cs[j]==cs[k]&&order[j]>order[k]){  
  35.      f=false;  
  36.      break;  
  37.     }  
  38.    }  
  39.    if(f)  
  40.     recursive(j+1);  
  41.    // left rotate [j,i]  
  42.    for(int k=j; k<i; k++){  
  43.     cs[k]=cs[k+1];  
  44.     order[k]=order[k+1];  
  45.    }  
  46.    cs[i]=c;  
  47.    order[i]=t;  
  48.   }  
  49.  }  
  50.   
  51.  void run(){  
  52.   cs=sc.next().toCharArray();  
  53.   n=cs.length;  
  54.   order=new int[n];  
  55.   for(int i=0; i<n; i++)  
  56.    order[i]=i;  
  57.   Arrays.sort(cs);  
  58.   recursive(0);  
  59.   System.out.flush();  
  60.  }  
  61.   
  62.  void println(String s){  
  63.   System.out.println(s);  
  64.  }  
  65.   
  66.  void print(String s){  
  67.   System.out.print(s);  
  68.  }  
  69.   
  70.  public static void main(String[] args){  
  71.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  72.   new Main().run();  
  73.  }  
  74. }  
投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)