2016年5月10日星期二

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);

}

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)

JAVA UVA練習

2016年5月10日星期二

UVA 294: Divisors

Q294: Divisors

UVA 275 Expanding Fractions

輸入Input

輸出Output

範例輸入Sample Input

範例輸出Sample Output

UVA 264: Count on Cantor

UVA 170: Clock Patience

Q170: Clock Patience

UVA 160 : Factors and Factorials

Q160: Factors and Factorials

2016年5月9日星期一

UVA113_Power_of_Cryptography

Q113: Power of Cryptography

UVA 102 Ecological Bin Packing

Q102: Ecological Bin Packing

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月10日星期二

2016年5月9日星期一