2016年5月13日星期五

ACM帳號終於辦好了 JAVA上傳簡直被各種80

ACM帳號終於辦好了

JAVA上傳簡直被各種80

前面一定要是public class Main才能過

public class UVA就不過了

改成 class UVA 倒是可以過

還有那超麻煩的輸出排版

上傳後各種超時

想說是不是我寫得太爛

我隨便去找一題別人寫的

還不是一樣超時

林阿罵哩

用JAVA來寫是不是太自虐@@

改一天再來把寫過的修一修

2016/5/14要去成大的桂冠杯玩一下闖關組

所以最近才跑來練練ACM 哀英文太差了

UVA 389: Basically Speaking

Q389: Basically Speaking

有一家製造計算機的公司請你幫忙設計新型的計算機。這台計算機必須可以做不同數字系統的轉換（例如：將一個2進位的數字轉換成10進位的數字）。這台計算機還必須有下列的特性：

有 7-digit 的顯示
除了有 0 ～ 9 的按鈕之外，還有 A ～ F 的按鈕
支援 2 進位到 16 進位

Input

輸入含有多組測試資料。
每組測試資料一列，含有 3 個數字。第一個數字為你所要轉換的數字。第二個數字為要轉換的數字為多少進位。第三個數字為要將這個數字轉成多少進位的數。在這3個數前後可能有一或多個空白字元存在。
以Sample Input 第一組測試資料為例：將 1111000 從 2 進位轉換成 10 進位。

Output

對每組測試資料輸出一列，輸出轉換後出現在計算機顯示器上的數字。這些數字長度為 7，靠右對齊。如果這個數字太大無法以計算機顯示器顯示，則輸出 "ERROR"。輸出格式請參考 Sample Output。

Sample Input	Sample Output
1111000 2 10 1111000 2 16 2102101 3 10 2102101 3 15 12312 4 2 1A 15 2 1234567 10 16 ABCD 16 15 0 10 2 000234 10 10 F00000 16 10	120 78 1765 7CA ERROR 11001 12D687 D071 0 234 ERROR

http://luckycat.kshs.kh.edu.tw/homework/q389.htm

import java.util.Scanner;

public class UVA_389 {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

while(true){

String sb=sc.nextLine(),s_n=sc.nextLine(),s_m=sc.nextLine();

String s="",a="",b=""; //沒是幾進位的數字也要在那邊輸入空白有夠不爽的

for(int i=0;i<sb.length();i++)

if(sb.charAt(i)!=' ')

s+=String.valueOf(sb.charAt(i));

for(int i=0;i<s_n.length();i++)

if(s_n.charAt(i)!=' ')

a+=String.valueOf(s_n.charAt(i));

for(int i=0;i<s_m.length();i++)

if(s_m.charAt(i)!=' ')

b+=String.valueOf(s_m.charAt(i));

int n=Integer.parseInt(a),m=Integer.parseInt(b);

int ans=Integer.parseInt(s,n);

char[] bef=new char[8];

int c=0;

while(ans>0 && c<7){

bef[c++]=change(ans%m);

ans/=m;

}

if(c>=7){

System.out.println(" ERROR");

}else{

for(int i=7-c;i>1;i--)

System.out.print(" ");

for(int i=c;i>=0;i--)

System.out.print(bef[i]);

System.out.println();

}

private static char change(int a){

switch(a){

case 0:

return '0';

case 1:

return '1';

case 2:

return '2';

case 3:

return '3';

case 4:

return '4';

case 5:

return '5';

case 6:

return '6';

case 7:

return '7';

case 8:

return '8';

case 9:

return '9';

case 10:

return 'A';

case 11:

return 'B';

case 12:

return 'C';

case 13:

return 'D';

case 14:

return 'E';

case 15:

return 'F';

}

return 0;

}

2016年5月12日星期四

UVA 386: Perfect Cubes

Q386: Perfect Cubes

我們可以找到所謂的"完美立方"（Perfect Cube）方程式：a³= b³+ c³+ d³
例如：12³= 6³+ 8³+ 10³
這個問題是要請你寫一個程式找到 a<= 200，所有這樣的集合{a,b,c,d}來滿足以上的方程式（a,b,c,d均大於1）

Output

輸出應該像是以下所示：每一個Perfect Cube一列，並且不同的列之間，a以非遞減的順序出現。而在同同一列中b,c,d也是以非遞減的順序出現。
若存在a可以由好幾組b,c,d的組合產生，越小的b應該要越先出現（可以參考輸出的第三、四列）。

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)
......
......
......

http://luckycat.kshs.kh.edu.tw/homework/q386.htm

public class UVA_386 {
public static void main(String[] args) {
for(int a=6;a<=200;a++){
for(int b=2;b<a;b++){
for(int c=b;c<a;c++){
for(int d=c;d<a;d++){
if(Math.pow(a,3)==Math.pow(b,3)+Math.pow(c,3)+Math.pow(d,3)){
System.out.printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);
}
}
}
}
}
}
}

UVA 374: Big Mod

Q374: Big Mod

計算 R = B^P mod M
對相當大的B、P、M請寫一個有效率的演算法來。

Input

每筆測試資料有3行，各有1個整數分別代表B、P、M。
其中 0 <= B <= 2147483647 0 <= P <= 2147483674 1 <= M <= 46340

Output

輸出計算的結果，每筆測試資料一行。

Sample input

Sample Output

13
2
13195

http://luckycat.kshs.kh.edu.tw/homework/q374.htm

import java.util.Scanner;

public class UVA_374 {

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  while(true){
   System.out.println();
   int B=sc.nextInt(),P=sc.nextInt(),M=sc.nextInt();
   long R=1;
   for(int i=1;i<=P;i++){
    R*=B;
    R%=M;
   }
   System.out.println(R);
  }

 }

}

UVA 382: Perfection

Q382: Perfection

一個整數b如果可以被另一個整數a整除（在這裡a>b），我們稱b是a的一個因數。
Perfect Number是一個正整數並且等於其所有因數的和。例如：6和28都是perfect number。因為6=1+2+3，28=1+2+4+7+14。如果一個正整數不是perfect，那他就是deficient或者是abundant，根據其所有因數的和是小於或大於這個數本身。因此，9是deficient因為1+3<9。而12是abundant因為1+2+3+4+6>12。
請寫一個程式求出某一個數是perfect, deficient 或者abundant。

Input

有一連串（不會超過100個）的正整數n（1 <= n < 60000）,n=0代表輸入結束。

Output

請參考 Sample Output。
數字部分佔5個字元長度，靠右對齊。與後方的敘述間空2個空白格。

Sample Input

15 28 6 56 60000 22 496 0

Sample Output

PERFECTION OUTPUT
   15  DEFICIENT
   28  PERFECT
    6  PERFECT
   56  ABUNDANT
60000  ABUNDANT
   22  DEFICIENT
  496  PERFECT
END OF OUTPUT

http://luckycat.kshs.kh.edu.tw/homework/q382.htm

import java.util.Scanner;

public class UVA_382 {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int n;

System.out.println("PERFECTION OUTPUT");

while((n=sc.nextInt())!=0){

long total=0;

for(int i=1;i<n;i++){

if(n%i==0)

total+=i;

}

if(total==n)

System.out.printf("%5d PERFECT\n",n);

else if(total>n)

System.out.printf("%5d ABUNDANT\n",n);

else

System.out.printf("%5d DEFICIENT\n",n);

}

if(n==0)

System.out.println("END OF OUTPUT");

}

UVA 357: Let Me Count The Ways

Q357: Let Me Count The Ways

經過在百貨公司的一場血拼之後，小梅發現她身上的零錢共有17分（cent，美金貨幣單位，其他貨幣及面值請參考下方紅字部分），分別是1個dime，1個nickel，以及2個penny。隔天，小梅去便利商店買完東西後發現她身上的零錢恰好又是17分，這次是2個nickel及7個penny。小梅就在想，有幾種硬幣的組合可能湊成17分呢？經過仔細算算之後，發現共有6種。

你的問題就是：給一個金額，請你回答共有多少種硬幣組合的方式。

p.s 美國的零錢共有以下幾種硬幣以及其面值：

penny, 1 cent
nickel, 5 cents
dime, 10 cents
quarter, 25 cents
half-dollar, 50 cents

Input

每組測試資料1列，有1個整數n（0 <= n <=30000），代表零錢的總金額。

Output

對每組測試資料請輸出共有多少種硬幣組合方式。輸出格式為以下2種其中之一。

There are m ways to produce n cents change.
There is only 1 way to produce n cents change.

Sample input

17 
11
4

Sample Output

There are 6 ways to produce 17 cents change. 
There are 4 ways to produce 11 cents change. 
There is only 1 way to produce 4 cents change.

http://luckycat.kshs.kh.edu.tw/homework/q357.htm

import java.util.Scanner;

public class UVA_357 {

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int[] coin={1,5,10,25,50};
  long[] m=new long[30001];
  for(int i=0;i<30001;i++)                          //DP演算法
   m[i]=0;
  m[0]=1;
  for(int i=0;i<5;i++){
   for(int j=coin[i];j<=30000;j++){
    m[j]+=m[j-coin[i]];
   }
  }
  while(true){
   int n=sc.nextInt();
   
   /*for(int i=0;i<=n/50;i++){
    for(int j=0;j<=(n-i*50)/25;j++){
     for(int z=0;z<=(n-i*50-j*25)/10;z++){
      for(int x=0;x<=(n-i*50-j*25-z*10)/5;x++){
        m+=(n-i*50-j*25-z*10-x*5)>=0?1:0;
      }
     }
    }
    
   }*/
   
   if(m[n]==1){
    System.out.printf("There is only 1 way to produce %d cents change.\n",n);
   }else{
    System.out.println("There are "+m[n]+" ways to produce "+n+" cents change.");
   }
   
  }

 }

}

UVA 356:Square Pegs And Round Holes

Q356:Square Pegs And Round Holes

在一個邊長為 2n 的正方形棋盤中央畫一個直徑為 2n-1 的圓，以下的圖為n=3

寫一個程式判斷有多少個格子是一部份在圓中，以及有多少個格子是完全被包含在圓當中。

Input

輸入包含好幾組測試資料，每組一列，含有一個正整數 n（n<=150）

Output

對每一組測試資料，輸出2列，第一列為部分被包含在圓中的格子數。第二列為完全被包含在圓中的格子數。

請注意：各測試資料之間要空一列。請參考Sample output

Sample Iutput

3
4

Sample Output

In the case n = 3, 20 cells contain segments of the circle.
There are 12 cells completely contained in the circle.

In the case n = 4, 28 cells contain segments of the circle.
There are 24 cells completely contained in the circle.

http://luckycat.kshs.kh.edu.tw/homework/q356.htm

import java.util.Scanner;

public class UVA_356 {

static int n;

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

while((n=sc.nextInt())<=150){

System.out.println();

int cover=0;

int cross=0;

for(int i=0;i<=n*2;i++){

for(int j=0;j<=n*2;j++){ //上下左右四個點 (0,0)(0,1)(1,0)(0.0)

if(dist(i,j)<=n-0.5 && dist(i,j+1)<=n-0.5 && dist(i+1,j)<=n-0.5

&& dist(i+1,j+1)<=n-0.5)

cover++;

else if(dist(i,j)<=n-0.5 || dist(i,j+1)<=n-0.5 || dist(i+1,j)<=n-0.5

|| dist(i+1,j+1)<=n-0.5)

cross++;

}

System.out.printf("In the case n = %d, %d cells contain segments of the circle.\n",n,cross);

System.out.printf("There are %d cells completely contained in the circle.\n",cover);

}

private static double dist(int i,int j){

return Math.sqrt((n-i)*(n-i)+(n-j)*(n-j));

}

UVA 355: The Bases Are Loaded

Q355: The Bases Are Loaded

寫一個程式做進位制之間的轉換（2進位到16進位）。其中A代表10，B代表11......，F代表15。

Input

每組測試資料一列，有3個值。第一個值為一個正整數m，代表要轉換的這個數是幾進位的數。第二個值為一個正整數n，代表要把這個數轉換成幾進位的數。第三個值就是要轉換的數（m進位），這個值最長不會超過10個字元的長度，且有可能在m進位之下是不正確的（例如Sample Input中的第二列，126不是一個正確的5進位數）。
以Sample Input的第一列為例說明：要把2進位表示法的10101轉換成10進位的表示法。

Output

每組測試資料輸出一列，把m進位的數轉換成n進位的數。格式請參考Sample Output。

Sample Input

Sample Output

10101 base 2 = 21 base 10 
126 is an illegal base 5 number 
A4C base 15 = 1821 base 11
0 base 5 = 0 base 15

http://luckycat.kshs.kh.edu.tw/homework/q355.htm

import java.util.Scanner;
public class UVA_355 {

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int m,n;
  String c;
  while(true){
   m=sc.nextInt();
   n=sc.nextInt();
   c=sc.next();
   
   
   String convert;
   try{
    convert=Long.toString(Long.valueOf(c,m),n).toUpperCase();
    System.out.println(c+" base "+m+" = "+convert+" base "+n );
   }catch(Exception e){
    System.out.println(c+" is an illegal base "+m+" number" );
   }

  }

 }

}

2016年5月11日星期三

UVA 343: What Base Is This ?

Q343: What Base Is This ?

我們知道在一個數字中不同的位置其權重（weight）是不同的。例如10進位的數字362中，2的權重是10⁰，6的權重是10¹，3的權重是10²。所以這個數10進位的值=3*10²+6*10¹+2*10⁰。同樣的機制也適用於其他的進位制。然而362這個數字在9進位制或14進位制中所代表的值是和10進位制的362不同的。
在本問題中，給你2個數字（以X、Y代表），請你寫一個程式找出X最小是多少進位制，且Y最小是多少進位制，才能使X，Y代表相同的值。例如：給你12和5。若用10進位來看的話，這2個數明顯是不同的。但是假如你用3進位來看12,用6進位來看5呢？12_(3進位)=1*3¹+2*3⁰=5_(10進位)，而5_(6進位)=5_(10進位)。所以如果你選對進位制的話，12和5是可以代表相同的值的。

Input

每組測試資料一列，包含2個數字X、Y。X、Y可以2進位制到36進位制來看待。在表達上，0～9就代表0～9，A,B,C,......,Z則分別代表10,11,12,......,35

Output

每組測試資料輸出的一列，格式請參考Sample Output。請注意X、Y有可能在2進位制到36進位制中均無法使之相等。

Sample Input

Sample Output

12 (base 3) = 5 (base 6)
10 (base 10) = A (base 11)
12 (base 17) = 34 (base 5)
123 is not equal to 456 in any base 2..36
1 is not equal to 2 in any base 2..36
10 (base 2) = 2 (base 3)
0 (base 2) = 0 (base 2)

http://luckycat.kshs.kh.edu.tw/homework/q343.htm

A,B,C,......,Z則分別代表10,11,12,......,35 這一行還是看不懂



import java.util.Scanner;
public class UVA_343 {
 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  while(true){
   String X=sc.next(),Y=sc.next();
   int[] X_base=new int[37];
   int[] Y_base=new int[37];
   boolean flag=false;
   for(int i=2;i<37;i++){
    try{
     X_base[i]=Integer.parseInt(X,i);
    }catch(Exception e){
     X_base[i]=-1;
    }
    try{
     Y_base[i]=Integer.parseInt(Y,i);
    }catch(Exception e){
     Y_base[i]=-1;
    }
   }
   System.out.println(Y_base[11]);
   
   int base_x=-1,base_y=-1;
   for(int i=2;i<37;i++){
    if(X_base[i]>=0){
     for(int j=2;j<37;j++){
      if(X_base[i]==Y_base[j]){
       
       flag=true;
       base_x=i;
       base_y=j;
       break;
      }
     }
    }
    if(flag)
     break;
   }
   if(flag)
     System.out.println(X+" (base "+base_x+")="+Y+" (base "+base_y+")");
   else{
    System.out.println(X+" is not equal to "+Y+" in any base 2..36");
   }
  }

 }

}

UVA 340: Master-Mind Hints

Q340: Master-Mind Hints

Master-Mind是一種2個人的遊戲。其實就是學生常玩的幾A幾B的遊戲（規則或許有些許不同）。其中一個人擔任出題者，他選一串1到9數字當作密碼（可以重複）。另一個人為解題者，他要去猜密碼為何。解題者每次猜測後，出題者以某種格式回答他這次猜的結果。
在遊戲開始之前，雙方先協議密碼的長度，假設是n。在出題者設定密碼（s₁,s₂,...s_n）後，由解題者來猜（g₁,g₂,...g_n）。如果同樣位置g_i=s_i，那解題者得到一個A。如果g_i=s_j，但i不等於j，那解題者得到一個B。請注意：不管是得A或得B，每個g_i最多只能對應到一個s_j，而且得A比得B優先。舉例說明：密碼為1 2 3 4，若猜題者猜1 1 5 6，那出題者應該回答1A0B，而不是0A1B。
如果某個猜測得到 nA0B，那就代表猜題者完全猜中密碼了。

Input

輸入含有多組測試資料。每組測試資料的第一列含有1個正整數 N（N <= 1000），代表密碼的長度。第二列有N個1到9的數字，代表密碼。接下來有數量不等的猜測，每個一列，亦含有N個1到9的數字。若此猜測的N個數字均為0，代表此組測試資料結束。
N=0代表整個輸入結束。請參考Sample Input。

Output

對每一組測試資料，輸出這是第幾組。然後輸出出題者回答猜題者各個猜測的結果是幾A幾B，以（A,B）的形式表示。請參考Sample Output。

Sample Input

4
1 3 5 5
1 1 2 3
4 3 3 5
6 5 5 1
6 1 3 5
1 3 5 5
0 0 0 0
10
1 2 2 2 4 5 6 6 6 9
1 2 3 4 5 6 7 8 9 1
1 1 2 2 3 3 4 4 5 5
1 2 1 3 1 5 1 6 1 9
1 2 2 5 5 5 6 6 6 7
0 0 0 0 0 0 0 0 0 0
0

Sample Output

Game 1:
    (1,1)
    (2,0)
    (1,2)
    (1,2)
    (4,0)
Game 2:
    (2,4)
    (3,2)
    (5,0)
    (7,0)

http://luckycat.kshs.kh.edu.tw/homework/q340.htm

import java.util.Scanner;
public class UVA_340 {

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n;
  int game=1;
  while((n=sc.nextInt())!=0){
   int[] pass1=new int[n];
   for(int i=0;i<n;i++)
    pass1[i]=sc.nextInt();
   
   int[] pass=new int[n];
   int[] guess=new int[n];
   
   
   System.out.println("Game "+game++ +":");
   while(true){
    for(int i=0;i<n;i++){
     guess[i]=sc.nextInt();
     pass[i]=pass1[i];
    }
     
    if(guess[0]==0) break;
    
    int A=0,B=0;
    for(int i=0;i<n;i++){
      if(pass[i]==guess[i]){
       A++;
       guess[i]=0;
       pass[i]=0;
       
       }
    }
    
    for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
      if(guess[i]==0)
       continue;
      else{
       if(guess[i]==pass[j]){
        B++;
        guess[i]=0;
        pass[j]=0;
       }
      }
     }
    }
    System.out.println("("+A+","+B+")");
   }
  }

 }

}

UVA 300 - Maya Calendar

Q300 - Maya Calendar

馬亞教授在研究馬雅文明的曆法上有了重大的發現，教授從繩結上的訊息發現馬雅文明的一年有19個月共365天，這種曆制稱作"Haab"，前18個月每月有20天，由0開始編號到19，而第19個月只有5天，分別為0, 1, 2, 3, 4，另外，每個月都有一個名字，依序為：pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu, uayet。馬雅人相信第19個月是不幸的月份，所在在該月所有經濟活動都會停止，甚至會避免從事家務，連地都不掃了。

另外，基於宗教上的理由，馬雅人還會使用另一種曆制，該曆制稱為"Tzolkin"，這種曆制的一年有260天，分為20種日子，每種日子13天，用13個整數與20個日子的名稱來區分每一天，整數為1~13，20種日子的名稱為：imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau。
注意，在Tzolkin這種曆制每一天的名稱不會衝突，例如一年前幾天的名稱如下所示：
1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, 8 imix, 9 ik, 10 akbal...

每一年以整數表示，例如：0, 1, ...，由0開始表示，所以兩種歷制的第一天分別為：

Haab: 0. pop 0
Tzolkin: 1 imix 0

請寫一個程式幫助馬亞教授做日期的轉換，由Haab曆制轉到Tzolkin曆制。

Input

Haab的日期格式為：日月年
輸入的第一列為一個整數表示共有多少日期需要轉換，接下來有n列，每一列為一個以Haab曆制表示的日期，年份最多到5000。

Output

Tzolkin的日期格式為：數字名稱年
請在輸出的第一列顯示共有幾組日期，接下來的n列顯示對應的Tzolkin日期。

Sample Input	Sample Outpu
3 10. zac 0 0. pop 0 10. zac 1995	3 3 chuen 0 1 imix 0 9 cimi 2801

中文翻譯：Ruby兔的 ACM園地, 修改by Luckycat

http://luckycat.kshs.kh.edu.tw/homework/q300.htm

import java.util.Scanner;

public class UVA_300 {

static String[] Haab={"pop", "no", "zip", "zotz", "tzec", "xul", "yoxkin", "mol", "chen", "yax", "zac", "ceh", "mac", "kankin"

, "muan", "pax", "koyab", "cumhu", "uayet"};

static String[] Tzolkin={"imix", "ik", "akbal", "kan", "chicchan", "cimi", "manik", "lamat", "muluk", "ok", "chuen", "eb"

, "ben", "ix", "mem", "cib", "caban", "eznab", "canac", "ahau"};

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

System.out.println(n);

while(n-->0){

String s_day=sc.next();

String month=sc.next();

int year=sc.nextInt();

String s=s_day.substring(0,s_day.length()-1);

int day=Integer.parseInt(s)+1;

int index=0;

for(int i=0;i<Haab.length;i++)

if(Haab[i].equals(month))

index=i;

int Allday=year*365+index*20+day;

int T_year=Allday/260;

Allday%=260;

String T_month=Tzolkin[Allday%20-1];

Allday%=13;;

int T_day=Allday;

System.out.println(T_day+" "+T_month+" "+T_year);

}

2016年5月10日星期二

UVA 294: Divisors

Q294: Divisors

給你一個範圍的數，請你寫一個程式找出在這個範圍內的數，哪一個數有最多的除數（就是小於等於這個數，且可以被這個數除盡的數。例如：6有4個除數，分別是1,2,3,6）。數的大小很大，範圍也不小，所以你的程式必須有效率，否則可能無法在幾秒內跑完。

Input

輸入的第一列有一個正整數N，代表以下有幾組測試資料。每組測試資料一列，含有2個正整數L，U，代表某一範圍的數中最小及最大的數。並且 1 <= L <= U <= 1000000000，0 <= U-L <= 10000

Output

對每一組測試資料，找出在範圍內有最多除數的數P（如果有不止一個數有最多除數，請找最小的那個），以及他有多少個除數D。然後依這樣的格式輸出：'Between L and H, P has a maximum of D divisors.。請參考Sample Output。

Sample Input

3
1 10
1000 1000
999999900 1000000000

Sample Output

Between 1 and 10, 6 has a maximum of 4 divisors.
Between 1000 and 1000, 1000 has a maximum of 16 divisors.
Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.

http://luckycat.kshs.kh.edu.tw/homework/q294.htm

http://celinechiu0809.blogspot.tw/2015/04/uva294-divisors.html

import java.util.Scanner;

public class UVA_294 {

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  
  boolean[] prime=new boolean[40000];
  prime[0]=true; prime[1]=true;
  for(int i=2;i<Math.sqrt(40000);i++){
   if(!prime[i]){
    for(int j=i*2;j<40000;j+=i){
     prime[j]=true;
    }
   }
  }
  
  while(true){
   int n=sc.nextInt();
   while(n-->0){
    int L=sc.nextInt(),U=sc.nextInt();
    int MAX=0,index=0;
    for(int i=L;i<=U;i++){
     int ans=1,sum=i;
     for(int j=2;j<=Math.sqrt(i);j++){
      int count=0;
      if(!prime[j]){
       while(sum%j==0){
         sum/=j;
         count++;
         }
         ans*=count+1;
      }
     }
     if(ans>MAX){
      MAX=ans;
      index=i;
     }
    }

    System.out.println("Between "+L+" and "+U+", "+index+" has a maximum of "+MAX+" divisors.");
   }
  }

 }

}

UVA 275 Expanding Fractions

Expanding Fractions

這個題目要求你把兩個整數的商展開來。你應該清楚，有很多整數的商展開來以後會變成循環小數。你必須找出這些循環的部份。給你整數的商，你要印出它的小數展開式，當小數部份已經沒有了或是即將開始第一次重覆之前就要停止輸出。如果有循環，你要說明循環節有幾位數。

輸入Input

會有多個輸入案例，每個案例由同一行的兩個整數所組成。第一個整數代表分數的分子，第二個則代表分母。本題目的分子永遠小於分母，分母永遠小於 1000。當分子分母同時為 0時，輸入檔結束。

輸出Output

相對於每個輸入案例，要輸出該分數的小數展開式，第一個字元是小數點。如果可以完全展開，印出完整的小數。如果是無限小數，就印到 (但不包含) 第一個重覆出現的循環節之前。

例如：4/11 = .3636363636...，應該印出 .36。(注意，要找出最小的循環節。在此案例中 3636 和 363636 都是循環節，但是最短的循節是 36。)

由於有些展開式會很長，請分行顯示，除了最後一行可以比較短外，每行必須剛好 50 個字元，包含開始的小數點。

在最後一行的小數展開式之後，緊接著要說「This expansion terminates. 」 (完全展開) 或「The last n digits repeat forever.」，其中 n 代表循環節的位數。

所有案例的輸出之後都要有一行空行 (包括最後一個案例) 。

實用小提示: 循環節的長度不會大於分母。

範例輸入Sample Input

3 7

345 800

112 990

53 122

0 0

範例輸出Sample Output

.428571

The last 6 digits repeat forever.

.43125

This expansion terminates.

.113

The last 2 digits repeat forever.

.4344262295081967213114754098360655737704918032786

885245901639

The last 60 digits repeat forever.

翻譯：郭兆平

http://luckycat.kshs.kh.edu.tw/homework/q275.htm

import java.util.Scanner;

public class UVA_275 {

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n,m;
  while((n=sc.nextInt())!=0 && (m=sc.nextInt())!=0){
   int[] math=new int[1001];
   System.out.print(".");
   math[n]=1;
   if(n==m || n==0){
    System.out.println("This expansion terminates.");
    continue;
   }
   int time=1,judge=0;
   while(true){
    if(time%50==0)
     System.out.println();
    System.out.print(n*10/m);
    n=n*10%m;
    time++;
    if(n==0){
     judge=1;
     break;
    }
    if(math[n]>0){
     break;
    }
    math[n]=time;
   }
   if(judge==1){
    System.out.println("\nThis expansion terminates.");
   }else{
    System.out.println("\nThe last 60 digits repeat forever.");
   }
   
  }

 }

}

UVA 264: Count on Cantor

Q264: Count on Cantor

現代數學中有一個有名的證明（由Georg Cantor所提出的）：有理數是可數的。他使用一個圖表（Cantor's 列舉）列舉出有理數，如下圖所示：

在此圖中，第一項是1/1,第2項是1/2,第三項是2/1,第四項是3/1,第五項是2/2,以下依此類推。

Input and Output

輸入每筆資料1行，含有1個正整數n (1<=n<=10⁷)。
對每行輸入，輸出在Cantor's 列舉圖中的第n項。

Sample Iutput

3
14
7

Sample Output

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4

http://luckycat.kshs.kh.edu.tw/homework/q264.htm

import java.util.Scanner;

public class UVA_264 {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

while(true){

int n=sc.nextInt();

int slash, term;

int part1, part2;

slash = 1;

term = 1;

while( term < n ) term += ++slash;

part1 = 1 + term - n;

part2 = slash - part1 + 1;

if(slash%2==1){

System.out.println("TERM "+n+" IS "+part1+"/"+part2);

}else{

System.out.println("TERM "+n+" IS "+part2+"/"+part1);

}

UVA 170: Clock Patience

Q170: Clock Patience

紙牌專家 Albert Smith正在寫一本關於紙牌遊戲的書。為了重複確認書中的例子，他正在寫程式來找出一副牌的最佳玩法。其中一種叫做「時鐘」紙牌的描述如下：紙牌被發出去（面朝下）成為一個時鐘的樣式，每個小時的位置有一堆紙牌，然後在中心也有額外的一堆（總共13堆，這13堆的名字分別為A, 2, 3, ..., T, J, Q,K。見下圖）。發牌的順序為先發一點鐘的牌（面朝下），然後二點鐘的牌，依此發牌到十二點鐘，最後發時鐘中心的牌。如此重複4圈，也就是說一副牌有52張，依此方法發牌，這13堆牌每堆會有4張牌。

遊戲開始的時候，K堆的最上面一張牌被翻開變成目前牌，然後看這張牌的點數，將這張牌移到相對的那堆牌最下面（面朝上），然後翻開這堆牌的最上方一張牌成為目前牌。例如：如果目前牌的點數是J，那這牌就被移到J堆牌的最下面，然後翻開J堆牌的最上方那張牌成為目前牌。遊戲如此不斷下去直到要翻牌的時候發現那堆牌已經沒有面朝下的牌了，這時候遊戲結束。如果所有的牌都被翻開，那表示你的運氣真的太好了！
你的任務是寫一個程式讀入一堆牌，然後模擬這個遊戲。

Input

輸入包含多組測試資料。每組測試資料4列，每列有13張牌的資料。每張牌以2個字元代表。第一個字元代表牌的點數（A=Ace, 2~9, T=10, J=Jack, Q=Queen, K=King），第二個字元代表牌的花色（C=Clubs, D=Diamonds, H=Hearts, S=Spades）
若遇到僅含#的一列代表輸入結束。請參考Sample Input。

Output

對每組測試資料輸出遊戲結束時總共翻開多少張牌（2位數，必要時在前面加0），以及最後被翻開的那張牌。輸出格式請參考Sample Output。

Sample Input	Sample Output
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC 9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D 6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C 6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C 9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C #	44,KD 42,KC

http://luckycat.kshs.kh.edu.tw/homework/q170.htm

import java.util.Scanner;

public class UVA_170 {

static String[][] puke=new String[5][13];

static int[] count;

static String answer;

static int run_time=0;

public static void main(String[] args) { //第一組的run_time好像有錯以後再改

Scanner sc=new Scanner(System.in);

while(true){

String[][] puke2=new String[5][13];

for(int i=0;i<4;i++){

for(int j=0;j<13;j++){

puke2[i][j]=sc.next();

}

count=new int[13];

count[12]=1; //最一開始的第一張

run_time=1; //第一張翻了

puke=puke2;

String now=puke[3][12]; //K的最上面一張

Clock(now);

System.out.println(run_time+","+answer);

}

private static void Clock(String now){

//System.out.println(now+" "+run_time);

char s_point=now.charAt(0); //ex:3C

int point=p(s_point);

if(count[point]==4){

answer=now;

return;

}

puke[4][point]=now; //放到最後一張

count[point]++;

run_time++;

now=puke[0][point]; //換這張要翻起來

reset(point);

Clock(now);

}

private static void reset(int point){

for(int i=0;i<4;i++){

puke[i][point]=puke[i+1][point];

}

private static int p(char s_point){

switch(s_point){

case 'A':

return 0;

case '2':

return 1;

case '3':

return 2;

case '4':

return 3;

case '5':

return 4;

case '6':

return 5;

case '7':

return 6;

case '8':

return 7;

case '9':

return 8;

case 'T':

return 9;

case 'J':

return 10;

case 'Q':

return 11;

case 'K':

return 12;

}

return -1;

}

UVA 160 : Factors and Factorials

Q160: Factors and Factorials

階乘的數學表示式是 N!, 代表從 1 乘到 N 的結果, 如下：

1! = 1
N! = N * (N-1)!

階乘的成長速度相當驚人, 5! = 120, 10! = 3,628,800, 而表示階乘的其中一種方法是去紀錄每一個質因數出現的頻率。例如 825 這個值, 可以用數字序列 (0 1 2 0 1), 來表示 0 個 2, 1 個 3, 2 個 5, 0 個 7, 1 個 11。
所以數字序列中的每個元素是代表連續出現的質因數, 而上面的數值, 代表該質因數出現的頻率。

寫一個程式讀入一個數字 N (2<=N<=100), 算出階乘結果，以之前的方式來表示這個階乘。

Input

輸入有許多筆測試資料, 一筆一列, 每一列包含一個數字 N, 當 N=0 代表輸入結束, 這一列不該被處理。

Output

每一筆測試資料, 需要輸出一組區塊結果, 這組區塊, 先輸出 N! = , 接下來以上述的方式, 依序輸出該質因數在這個階乘中出現的頻率次數為何（長度3，靠右對齊）, 請注意, 每一列最多只能印出 15 個質因數, 多餘的得換一列再印出。

詳細輸出格式請參考 Sample Output。

Sample Input	Sample Output
5 53 0	5! = 3 1 1 53! = 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

Translated by Tino

http://luckycat.kshs.kh.edu.tw/homework/q160.htm
http://using-c.blogspot.tw/2008/02/p160-factors-and-factorials.html

import java.util.Scanner;
public class UVA_160 {

public static void main(String[] args) {
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,
43,47,53,59,61,67,71,73,79,83,89,97};
Scanner sc=new Scanner(System.in);
int n;
int[][] primeTable=new int[101][25];
for(int i=2;i<=100;i++){
int k=i; //2!~100!
int j=0; //prime[j]開始
while(k>=2){ //小於最小質數2就結束
if(k%prime[j]==0){
primeTable[i][j]++;
k/=prime[j]; //能除的話就一直除
}else{
j++; //prime[j]質數不能除所以j+1
}
}
}

while((n=sc.nextInt())!=0){
System.out.print(n+"! = ");
int line=0;
for(int i=0;i<25;i++){
int total=0;
for(int j=0;j<=n;j++){
total+=primeTable[j][i]; //把所有的prime[j]都加起來
}
if(total!=0){
System.out.print(total+" ");
line++;
}
if(line%15==0)
System.out.println();
}
}
}
}

最後的排版不知道有沒有問題

2016年5月9日星期一

UVA113_Power_of_Cryptography

Q113: Power of Cryptography

給你兩個整數 n（n >= 1）和 p（p >=1），你必須寫一個程式來計算出 p 的正 n 次方根。在這個問題裡，p 皆可表成 kⁿ 的形式，其中 k 為整數。（k也就是你的程式所要求的）

Input

每組測試資料2列，第1列有1個整數 n（1 <= n <= 200），第2列有1個整數 p（1 <= p <= 10¹⁰¹）。並且存在一個整數 k，（1 <= k <= 10⁹），使得 kⁿ=p。

Output

每組測試資料請輸出 k。

Sample Input

2
16
3
27
7
4357186184021382204544

Sample Output

4
3
1234

http://luckycat.kshs.kh.edu.tw/homework/q113.htm

import java.util.Scanner;

public class UVA113_Power_of_Cryptography {   //我還以為要用大數

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  while(true){
   double n=sc.nextDouble(),p=sc.nextDouble();
   System.out.println((int)(Math.pow(p,1/n)+0.5));
  }
 }

}

UVA 102 Ecological Bin Packing

Q102: Ecological Bin Packing

有3個桶子用來裝回收的玻璃瓶，玻璃瓶的顏色有三種：棕色（Brown）、綠色（Green）、透明色（Clear）。在這個問題裡我們會告訴你每個桶子裏的玻璃瓶的顏色及數量，現在要搬移桶子裏的玻璃瓶使得最後每個桶子裡都只有單一顏色的玻璃瓶，以方便回收。你的任務就是要算出最小搬移的瓶子數。你可以假設每個桶子的容量無限大，並且總共搬移的瓶子數不會超過2³¹。

Input

每筆測試資料一行，每行有9個整數.前3個代表第1個桶子裡Brown, Green, Clear顏色的瓶子數。接下來的3個數代表第2個桶子裡Brown, Green, Clear顏色的瓶子數。最後的3個數代表第3個桶子裡Brown, Green, Clear顏色的瓶子數。

例如：10 15 20 30 12 8 15 8 31
表示有20個Clear色的玻璃瓶在第1個桶子裏，12個Green色的玻璃瓶在第2個桶子裏，15個Brown色的玻璃瓶在第3個桶子裏。

Output

對每一筆測試資料，輸出3個桶子內最後存放之玻璃瓶顏色，以及最小搬移的瓶子數。請以大寫的'G'、 'B'、 'C' 分別代表綠色（Green）、棕色（Brown）、透明色（Clear）。

例如：BCG 30
代表最後搬移的結果第1個桶子內的玻璃瓶顏色為Brown，第2個桶子內的玻璃瓶顏色為Clear，第3個桶子內的玻璃瓶顏色為Green.並且總共搬移了30個玻璃瓶。

如果最小搬移瓶子數有一組以上的組合，請輸出字典順序最小的那一組答案。

Sample input

1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10

Sample Output

BCG 30
CBG 50

from:http://luckycat.kshs.kh.edu.tw/homework/q102.htm

import java.util.Scanner;
public class UVa102_Ecological_Bin_Packing {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(true){
String[] Bin={"BCG","BGC","CBG","CGB","GBC","GCB"};//3!
int[] move=new int[6];
int[] B=new int[3];
int[] G=new int[3];
int[] C=new int[3];
for(int i=0;i<3;i++){
B[i]=sc.nextInt();
G[i]=sc.nextInt();
C[i]=sc.nextInt();
}
move[0]=B[1]+B[2]+C[0]+C[2]+G[0]+G[1]; //把B[1],B[2]移出 C[0],C[2]移出 G[0],G[1]移出
move[1]=B[1]+B[2]+G[0]+G[2]+C[0]+C[1];
move[2]=C[1]+C[2]+B[0]+B[2]+G[0]+G[1];
move[3]=C[1]+C[2]+G[0]+G[2]+B[0]+B[1];
move[4]=G[1]+G[2]+B[0]+B[2]+C[0]+C[1];
move[5]=G[1]+G[2]+C[0]+C[2]+B[0]+B[1];

int MIN=0;
for(int i=1;i<6;i++){
if(move[MIN]>move[i]){
MIN=i;
}
}
System.out.println(Bin[MIN]+" "+move[MIN]);
}
}
}

訂閱：文章 (Atom)

2016年5月13日 星期五

Q389: Basically Speaking

2016年5月12日 星期四

Q386: Perfect Cubes

Q374: Big Mod

Q382: Perfection

Q357: Let Me Count The Ways

Q355: The Bases Are Loaded

2016年5月11日 星期三

Q343: What Base Is This ?

Q340: Master-Mind Hints

Q300 - Maya Calendar

中文翻譯：Ruby兔的 ACM園地, 修改by Luckycat

2016年5月10日 星期二

Q294: Divisors

輸入Input

輸出Output

範例輸入Sample Input

範例輸出Sample Output

Q170: Clock Patience

Q160: Factors and Factorials

2016年5月9日 星期一

Q113: Power of Cryptography

Q102: Ecological Bin Packing

2016年5月13日星期五

2016年5月12日星期四

2016年5月11日星期三

2016年5月10日星期二

2016年5月9日星期一