[C_MM275-易] 字串之編碼數值總和

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=20485

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine());
	while(n--!=0){
	char arr[]=scn.nextLine().toCharArray();
	int tot=0;
	for(int i=0;i<arr.length;i++){
	tot+=arr[i];
	}
	System.out.println(tot);
	}
	}
	/*
	題目：[C_MM275-易] 字串之編碼數值總和
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM275-易 字串之編碼數值總和.java hosted with ❤ by GitHub

這題把字串放入字元陣列中再一一的相加

[C_MM252-易] 十進位轉二進位

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15774

	import java.math.BigInteger;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	int num=scn.nextInt(),n=32-Integer.toBinaryString(num).length();
	for(int i=0;i<n;i++)
	System.out.print("0");
	System.out.println(Integer.toBinaryString(num));
	}
	}
	/*
	題目：[C_MM252-易] 十進位轉二進位
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM252-易 十進位轉二進位.java hosted with ❤ by GitHub

這題利用Integer.toBinaryString()轉換成二進位,但題目要求32位數所以前面要補齊0

Q10494 - If We Were a Child Again

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1435

	import java.math.BigInteger;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	BigInteger a,b;
	a=scn.nextBigInteger();
	String s=scn.next();
	b=scn.nextBigInteger();
	if(s.equals("%")){
	System.out.println(a.mod(b));
	}
	else{
	System.out.println(a.divide(b));
	}
	}
	}
	/*
	題目：Q10494 - If We Were a Child Again
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q10494 - If We Were a Child Again.java hosted with ❤ by GitHub

這題要一個一個去讀取如果用字串去切割空白會Runtime error
最後做大數的運算

Q1225 - Digit Counting

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3666

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	int num=scn.nextInt(),arr[]=new int [10];
	for(int i=1;i<=num;i++){
	char ary[]=Integer.toString(i).toCharArray();
	for(int j=0;j<ary.length;j++){
	arr[ary[j]-'0']++;
	}
	}
	for(int i=0;i<10;i++){
	if(i!=0)
	System.out.print(" ");
	System.out.print(arr[i]);
	}
	System.out.println();
	}
	}
	/*
	題目：Q1225 - Digit Counting
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q1225 - Digit Counting.java hosted with ❤ by GitHub

這題就把每個數字丟到陣列一個一個存入1~9 arr[ 9 ]

Q10323 - Factorial! You Must be Kidding!!!

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1264

	import java.math.BigInteger;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	BigInteger arr[]=new BigInteger[1001];
	arr[1]=new BigInteger("1");arr[0]=new BigInteger("1");
	for(int i=2;i<=1000;i++){
	arr[i]=arr[i-1].multiply(new BigInteger(Integer.toString(i)));
	}
	while(scn.hasNext()){
	int num=scn.nextInt(),sum=0;
	if(num<0){
	if(num%2==0)
	System.out.println("Underflow!");
	else
	System.out.println("Overflow!");
	}
	else if(num>1000||arr[num].compareTo(new BigInteger("6227020800"))==1)
	System.out.println("Overflow!");
	else if(arr[num].compareTo(new BigInteger("10000"))==-1)
	System.out.println("Underflow!");
	else
	System.out.println(arr[num]);
	}
	}
	/*
	題目：Q10323 - Factorial! You Must be Kidding!!!
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q10323 - Factorial! You Must be Kidding!!!.java hosted with ❤ by GitHub

這題就是判斷階層結果大於6227020800就Overflow小於1000(不包含負數)Underflow
當負數時偶數-2 -4 -6...為Underflow  奇數-1 -3 -5...為Overflow
先利用DP建立1001個階層表當輸入值大於1000直接Overflow
補充:
比較大小
int i=b1.compareTo(b2)   
i可能為-1、0、1，分别表示小於、等於、大於
i=-1   ==>  b1<b2
i=0   ==>   b1=b2 
i=1   ==>   b1>b2

Q10220 - I Love Big Numbers !

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1161

	import java.math.BigInteger;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	BigInteger arr[]=new BigInteger[1001];
	arr[1]=new BigInteger("1");arr[0]=new BigInteger("1");
	for(int i=2;i<=1000;i++){
	arr[i]=arr[i-1].multiply(new BigInteger(Integer.toString(i)));
	}
	while(scn.hasNext()){
	int num=scn.nextInt(),sum=0;
	char ary[]=arr[num].toString().toCharArray();
	for(int i=0;i<ary.length;i++)
	sum+=ary[i]-'0';
	System.out.println(sum);
	}
	}
	/*
	題目：Q10220 - I Love Big Numbers !
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q10220 - I Love Big Numbers !.java hosted with ❤ by GitHub

這題是算出階層後每一個位數的總和最大測資有1000階層會爆所以要利用大數運算動態配置儲存1000筆資料
叫出每一個位數BigInteger先變成字串toString( )再拆成字元陣列toCharArray( )
注意當0!輸出1

Q623 - 500!

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=564

	import java.math.BigInteger;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	BigInteger arr[]=new BigInteger[1001];
	arr[1]=new BigInteger("1");arr[0]=new BigInteger("1");
	for(int i=2;i<=1000;i++){
	arr[i]=arr[i-1].multiply(new BigInteger(Integer.toString(i)));
	}
	while(scn.hasNext()){
	int num=scn.nextInt();
	System.out.println(num+"!\n"+arr[num]);
	}
	}
	/*
	題目：Q623 - 500!
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q623 - 500!.java hosted with ❤ by GitHub

這題最大測資有1000階層會爆所以要利用大數運算動態配置儲存1000筆資料

ITSA 串接字串

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=29581

寫一支可以串接字串的程式。要求如下。給兩個字串s₁及s₂，將這兩個字串串接起來，得到一個新的字串s₃。s₃要滿足底下的要求：

1.          s₁字串在前面

2.          s₂字串在後面

3.          s₃是s₁及s₂所串起來的字串中，最短的字串。

關於第3點，我們用底下的例子來解說：

例1：

s₁ = “birthday”

s₂ = “daylight”

所以s₃=”birthdaylight”

例2：

s₁ = “birthdays”

s₂ = “daylight”

那 s₃ = “birthdaysdaylight”

例3：

s₁=”abc”

s₂=”bcdef”

那s₃=”abcdef”

輸入

輸入的第一行是一個整數N，其代表了共有N個字串。0 < N <= 1000 。接下來的N行包含了N個字串，每個字串為一行。每一個字串的長度介於1到100之間。

輸出

請將這N個字串串接的結果輸出。

Sample Input:	Sample Output:
3 abc bcdef g	abcdefg

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine()),j=0;
	String s[]=new String[n],str="";
	for(int i=0;i<n;i++){
	s[i]=scn.nextLine();
	}
	str+=s[0];
	for(int i=1;i<n;i++){
	j=s[i].length();
	while(true){
	if(str.contains(s[i].substring(0, j))){
	str+=s[i].substring(j, s[i].length());
	break;
	}
	j--;
	}
	}
	System.out.println(str);
	}
	}

view raw ITSA 串接字串.java hosted with ❤ by GitHub

這題做法是用要插入的字串去比對要被新增的串列中是否有重疊的字串所以從最大長度開始遞減假如跟str有重疊就插入s[i]後面的子字串

Q455 - Periodic Strings

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=396

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine()),i=0;
	for(int num=0;num<n;num++){
	String str;
	while(true){
	str=scn.nextLine();
	if(!str.equals(""))
	break;
	}
	StringBuilder sub = new StringBuilder();
	for(i=0;i<str.length();i++){
	sub.append(str.charAt(i));
	if(str.length()%sub.length()!=0)
	continue;
	boolean b=true;
	for(int j=0;j<str.length();j+=sub.length()){
	if(!str.substring(j,j+sub.length()).equals(sub.toString())){
	b=false;
	break;
	}
	}
	if(b)
	break;
	}
	if(num!=0)
	System.out.println();
	System.out.println(i+1);
	}
	}
	/*
	題目：Q455 - Periodic Strings
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q455 - Periodic Strings.java hosted with ❤ by GitHub

這題要算出最短的重複子字串的字母個數,要注意測資可能有空白行所以要重讀取,而且每個答案之間要多空一行
Periodic String=>http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubstring.html

Q10298 - Power Strings

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1239

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	String str=scn.nextLine();
	StringBuilder sub = new StringBuilder();
	if(str.equals("."))
	break;
	for(int i=0;i<str.length();i++){
	sub.append(str.charAt(i));
	if(str.length()%sub.length()!=0)
	continue;
	boolean b=true;
	for(int j=0;j<str.length();j+=sub.length()){
	if(!str.substring(j,j+sub.length()).equals(sub.toString())){
	b=false;
	break;
	}
	}
	if(b)
	break;
	}
	System.out.println(str.length()/sub.length());
	}
	}
	/*
	題目：Q10298 - Power Strings
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q10298 - Power Strings.java hosted with ❤ by GitHub

這題就是要找出最短子字串且算出有幾個重複
程式架構是子字串1~n一個一個去跟原本字串做比對
if(str.length()%sub.length()!=0)

      continue;
這個是判斷子字串是否為原本字串的倍數否就繼續執行下一個迴圈
補充若子字串用String會超時所以必須要用StringBuffer 每次append一個字母進去

Q10101 - Bangla Numbers

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1042

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int count=1;
	while(scn.hasNext()){
	long num=scn.nextLong(),arr[][]=new long [4][2];
	System.out.printf("%4d.",count++);
	call(num);
	if(num==0)
	System.out.print(" 0");
	System.out.println();
	}
	}
	public static void call(long num){
	if( num == 0 ) return;
	if(num/10000000>0){
	call(num/10000000);
	System.out.print(" kuti");
	num%=10000000;
	}
	if(num/100000>0){
	call(num/100000);
	System.out.print(" lakh");
	num%=100000;
	}
	if(num/1000>0){
	call(num/1000);
	System.out.print(" hajar");
	num%=1000;
	}
	if(num/100>0){
	call(num/100);
	System.out.print(" shata");
	num%=100;
	}
	if(num!=0)
	System.out.print(" "+num);
	}
	/*
	題目：Q10101 - Bangla Numbers
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q10101 - Bangla Numbers.java hosted with ❤ by GitHub

這題就是就是把每個除出來的數字除到剩二位為止,利用疊代直到0為止
當輸入0時直接印出0一開始空四格

[C_ST59-易] 字串旋轉運算

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=8314

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	char ary[]="abcdefghijklmnopqrstuvwxyz".toCharArray(),arr[]="abcdefghijklmnopqrstuvwxyz".toCharArray();
	for(int i=0;i<5;i++){
	int index=scn.nextInt(),num=scn.nextInt(),tot=((num+index)%26);
	if(tot<0)
	tot+=26;
	arr[index]=ary[tot];
	}
	for(char c:arr)
	System.out.print(c);
	System.out.println();
	}
	/*
	題目：[C_ST59-易] 字串旋轉運算
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_ST59-易 字串旋轉運算.java hosted with ❤ by GitHub

這題這題會給五組資訊每一組有兩個數字分別為更改位置的索引值以及左移或右移的數目
當(索引值+上位移數)%26小於0要加回26,並且位移的對象為a~z所以要建立兩個a~z陣列一個是原本乾淨沒位移過的一個是放答案的陣列

[C_ST76-易] 文字解密

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=6839

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine());
	while(n--!=0){
	String s1[]=scn.nextLine().split("[0-9-\\pP]"),s2[]=scn.nextLine().split("[0-9-\\pP]");
	ArrayList <String> list1=new ArrayList<String>(),list2=new ArrayList<String>();
	for(int i=0;i<s1.length;i++){
	if(!s1[i].equals(""))
	list1.add(s1[i]);
	}
	for(int i=0;i<s2.length;i++){
	if(!s2[i].equals(""))
	list2.add(s2[i]);
	}
	boolean b=true,p=false;
	for(int i=0;i<list1.size();i++){
	if(!list1.get(i).equals(list2.get(i))){
	if(b){
	if(p)
	System.out.print(" ");
	System.out.print(list1.get(i));
	b=false;p=true;
	}
	else{
	if(p)
	System.out.print(" ");
	System.out.print(list2.get(i));
	b=true;p=true;
	}
	}
	}
	System.out.println();
	}
	}
	/*
	題目：[C_ST76-易] 文字解密
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_ST76-易 文字解密.java hosted with ❤ by GitHub

這題處理字串切割要比較麻煩除了英文字母其他的都要捨去(包含數字標點符號空白),所以要利用政則表達是來切出字串,所以先用split( " [ 0-9-\\pP ] " ) 分別切出0~9(\d)以及標點符號 \pP是代表萬國碼字元雙引號內要跳脫字元所以兩個反斜線,最後切出來的s1以及s2長度不一因為空白也切進去了所以建立一個List儲存非""的字串
That 1000 treasure was not in City. =>That treasure was not in City
That power is not at Chiayi123.      =>That power is not at Chiayi

Q10420 - List of Conquests

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1361

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine()),count=0,i=0;
	String arr[]=new String[n];
	for(i=0;i<n;i++){
	String s[]=scn.nextLine().trim().split(" ");
	arr[i]=s[0];
	}
	Arrays.sort(arr);
	String str=arr[0];
	for(i=0;i<n;i++){
	if(str.equals(arr[i]))
	count++;
	else{
	System.out.println(arr[i-1]+" "+count);
	count=1;
	str=arr[i];
	}
	}
	System.out.println(arr[i-1]+" "+count);
	}
	/*
	題目：Q10420 - List of Conquests
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q10420 - List of Conquests.java hosted with ❤ by GitHub

這題就只是紀錄國家數目(國家要排序)注意一開始可能有空白所以要用tirm( )把前面空白省略

Q11115 - Uncle Jack

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2056

	import java.math.BigInteger;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	BigInteger D=scn.nextBigInteger();
	int N=scn.nextInt();
	if(D.equals(new BigInteger("0"))&&N==0)
	break;
	System.out.println(D.pow(N));
	}
	}
	/*
	題目：Q11115 - Uncle Jack
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q11115 - Uncle Jack.java hosted with ❤ by GitHub

這題只是D的n次方因為每個CD都不同分給大家
例如3個CD分給5個人有3*3*3*3*3種分法
由於這題測資會有10的25次方所以要用大數運算
可參考這篇:http://blog.xuite.net/wang620628/twblog/126093649-%E5%B0%876%E4%BB%B6%E7%89%A9%E5%93%81%E5%85%A8%E9%83%A8%E6%94%BE%E5%85%A54%E5%80%8B%E7%AE%B1%E5%AD%90%E5%85%A7%EF%BC%8C%E8%AB%8B%E5%95%8F%E4%B8%8B%E5%88%97%E6%9C%89%E5%B9%BE%E7%A8%AE%E6%94%BE%E6%B3%95%3F

ITSA 47 [Problem 5] Geodesic Distance

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30637

	import java.util.*;
	public class Main {
	private static double rad(double d) {
	return d * Math.PI / 180.0;
	}
	public static double GetDistance(double lat1, double lng1, double lat2, double lng2) {
	double EARTH_RADIUS = 6000;
	double radLat1 = rad(lat1);
	double radLat2 = rad(lat2);
	double a = radLat1 - radLat2;
	double b = rad(lng1) - rad(lng2);
	double s = 2 * Math.asin(Math.sqrt(
	Math.pow(Math.sin(a / 2), 2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));
	s = s * EARTH_RADIUS;
	s = Math.round(s * 10000) / 10000;
	return s;
	}
	public static void main(String[] args) {
	Scanner scn=new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	String s1=scn.next(),s2=scn.next(),s3=scn.next(),s4=scn.next();
	String c1=s1.substring(0,1),c2=s2.substring(0,1),c3=s3.substring(0,1),c4=s4.substring(0,1);
	int a=Integer.parseInt(s1.substring(1)),b=Integer.parseInt(s2.substring(1)),c=Integer.parseInt(s3.substring(1)),d=Integer.parseInt(s4.substring(1));
	if(c1.equals("W")||c1.equals("S")){
	a=0-a;
	}
	if(c2.equals("W")||c2.equals("S")){
	b=0-b;
	}
	if(c3.equals("W")||c3.equals("S")){
	c=0-c;
	}
	if(c4.equals("W")||c4.equals("S")){
	d=0-d;
	}
	System.out.println((int)GetDistance(b,a,d,c));
	}
	}
	/*
	題目：ITSA 47 [Problem 5] Geodesic Distance
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw ITSA 47 Problem 5 Geodesic Distance.java hosted with ❤ by GitHub

這題請參考這篇文章當S或W時要變成負數
http://fecbob.pixnet.net/blog/post/43546822-%5Bjava%5D-%E7%B6%93%E7%B7%AF%E5%BA%A6%E8%B7%9D%E9%9B%A2%E8%A8%88%E7%AE%97

[C_MM060-易] 疊積木

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2000

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int a=scn.nextInt(),b=scn.nextInt(),tot=0,i;
	for(i=1;tot<a;i++){
	tot+=i;
	}
	int w=i-1,h=a-(tot-w);
	System.out.printf("%.6f\n",Math.sqrt(Math.pow(w*b, 2.0)+Math.pow(h*b, 2.0)));
	}
	/*
	題目：[C_MM060-易] 疊積木
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM060-易 疊積木.java hosted with ❤ by GitHub

這題先用迴圈遞增算寬然後得出高就能利用三角形勾股定理求出對角長了

[C_MM119-中] 計算兩個整數 m 和 n 的商，精確至小數點下任意位

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=3063

	import java.math.BigDecimal;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	BigDecimal a=scn.nextBigDecimal(),b=scn.nextBigDecimal();
	int n=scn.nextInt();
	System.out.println(a.divide(b,n,BigDecimal.ROUND_HALF_EVEN).toPlainString());
	}
	}
	/*
	題目：[C_MM119-中] 計算兩個整數 m 和 n 的商，精確至小數點下任意位
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM119-中 計算兩個整數 m 和 n 的商，精確至小數點下任意位.java hosted with ❤ by GitHub

這題要使用大數BigDecimal 除法 a.divide( b,n,BigDecimal.ROUND_HALF_EVEN ).toPlainString()
要注意測資可能很大會變成科學記號所以要使用toPlainString

/*
BigDecimal.ROUND_CEILING　正數無條件進入,負數無條件捨去
BigDecimal.ROUND_DOWN 　無條件捨去到 scale 位
BigDecimal.ROUND_FLOOR　正數無條件捨去，負數無條件進入
BigDecimal.ROUND_HALF_DOWN　四捨五捨六入
BigDecimal.ROUND_HALF_EVEN　四捨六入,五入捨後該scale位數值必需為偶數
BigDecimal.ROUND_HALF_UP　四捨五入
BigDecimal.ROUND_UP　無條件進入到 scale 位
*/

[C_MM115-中] 奇妙數列

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2969

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	ArrayList <Integer>list=new ArrayList <Integer>();
	int t=0,num=scn.nextInt(),i=2,temp=1;
	list.add(1);
	while(true){
	if(!list.contains(i)){
	list.add(list.get(list.size()-1)+i);
	}
	i++;
	if(list.size()==num||num==1)
	break;
	}
	if(num==1)
	System.out.println("1");
	else
	System.out.println(list.get(list.size()-1));
	}
	}
	/*
	題目：[C_MM115-中] 奇妙數列
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM115-中 奇妙數列.java hosted with ❤ by GitHub

這題S(n)=S(n-1)+T(n-1),並且注意T(n)的值不在S(n)中

[C_MM145-易] 質因數分解

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=3631

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	long num=scn.nextLong(),n=num,i=2;
	boolean b=true;
	while(true){
	int count=0;
	while(n%i==0){
	n/=i;
	count++;
	}
	if(count>1){
	System.out.printf("%d^%d",i,count);
	b=false;
	}
	else if(count==1&&b){
	System.out.printf("%d",i);
	b=false;
	}
	else if(count==1){
	System.out.printf(" * %d",i);
	b=false;
	}
	if(n==1)
	break;
	i++;
	}
	System.out.println();
	}
	/*
	題目：[C_MM145-易] 質因數分解
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM145-易 質因數分解.java hosted with ❤ by GitHub

這題要使用long迴圈下去除

[C_MM058-中] 二項式求解

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=1903

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String s[]=scn.next().split(",");
	int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]),c=Integer.parseInt(s[2]);
	for(int i=0;i<=c/a;i++){
	if((c-a*i)%b==0)
	System.out.println(i+","+(c-a*i)/b);
	}
	}
	/*
	題目：[C_MM058-中] 二項式求解
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM058-中 二項式求解.java hosted with ❤ by GitHub

迴圈從0開始下去跑,跑到c/a為止,一一下去做判斷是否整除

Q568: Just the Facts

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=509

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	int n=scn.nextInt(),tot=1,index=0;
	for(int i=2;i<=n;i++){
	tot*=i;
	while(tot%10==0)
	tot/=10;
	tot%=100000;
	}
	System.out.printf("%5d -> %d\n",n,tot%10);
	}
	}
	/*
	題目：Q568: Just the Facts
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q568: Just the Facts.java hosted with ❤ by GitHub

這題是要找階層後尾部數過來低一個不為0的數,測資最大可能有10000階層肯定會爆
所以每乘1次要把尾數0去掉,最後再%100000

Q357: Let Me Count The Ways

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=293

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int coin[]={1,5,10,25,50};
	long dp[]=new long [30001];
	for(int i=0;i<30001;i++)
	dp[i]=1;
	for(int i=1;i<5;i++){
	for(int j=coin[i];j<30001;j++){
	dp[j]+=dp[j-coin[i]];
	}
	}
	while(scn.hasNext()){
	int num=scn.nextInt();
	if(dp[num]>1)
	System.out.printf("There are %d ways to produce %d cents change.\n",dp[num],num);
	else
	System.out.printf("There is only 1 way to produce %d cents change.\n",num);
	}
	}
	/*
	題目：Q357: Let Me Count The Ways
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q357: Let Me Count The Ways.java hosted with ❤ by GitHub

這是動態規化的問題題目限定範圍所以建立一個30001的陣列,一開始先把全部初始化1
然後再一個個幣值dp[]相加

Q530: Binomial Showdown

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=471

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	int r=scn.nextInt(),k=scn.nextInt();
	if(r==0&&k==0)
	break;
	System.out.println(combi(r,k));
	}
	}
	public static long combi(int r,int k){
	long p=1;
	if(r/2<k)
	k = r-k;
	for(int i=1;i<=k;i++){
	p=p*(r-i+1)/i;
	}
	return p;
	}
	/*
	題目：Q530: Binomial Showdown
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q530: Binomial Showdown.java hosted with ❤ by GitHub

r取k有公式=>r ! / ( r - k ) ! * k ! ,也就是斯巴卡三角形注意溢位的問題
另外要考慮到 C10取1 跟C10 取9 是一樣的,做一下轉換就能避免超時的問題

Q386: Perfect Cubes

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=322&mosmsg=Submission+received+with+ID+17836106

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	for(int i=6;i<=200;i++){
	for(int j=2;j<i;j++){
	for(int k=j+1;k<i;k++){
	for(int m=k+1;m<i;m++){
	if(i*i*i==j*j*j+k*k*k+m*m*m)
	System.out.printf("Cube = %d, Triple = (%d,%d,%d)\n",i,j,k,m);
	}
	}
	}
	}
	}
	/*
	題目：Q386: Perfect Cubes
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q386: Perfect Cubes.java hosted with ❤ by GitHub

四個迴圈結束

Q382: Perfection

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=318&mosmsg=Submission+received+with+ID+17836051

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	System.out.println("PERFECTION OUTPUT");
	while(scn.hasNext()){
	int num=scn.nextInt(),tot=0;
	if(num==0){
	System.out.println("END OF OUTPUT");
	break;
	}
	for(int i=1;i<num;i++){
	if(num%i==0)
	tot+=i;
	}
	if(tot==num)
	System.out.printf("%5d PERFECT\n",tot);
	else if(tot>num)
	System.out.printf("%5d ABUNDANT\n",num);
	else if(tot<num)
	System.out.printf("%5d DEFICIENT\n",num);
	}
	}
	/*
	題目：Q382: Perfection
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q382: Perfection.java hosted with ❤ by GitHub

完美數的求法利用圈1~n-1判斷是否整除(求公因數)若全部加總等於n就是PERFECT

[C_SO36-易] 我想要聯誼

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15532

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	int n=scn.nextInt(),count=0,j;
	String arr[]=new String [n];
	for(int i=0;i<n;i++){
	arr[i]=scn.next();
	}
	char cp[]=scn.next().toCharArray();
	for(int i=0;i<n;i++){
	for(j=0;j<cp.length;j++)
	if(arr[i].indexOf(cp[j])<0)
	break;
	if(j==cp.length)
	count++;
	}
	System.out.println(count);
	}
	}
	/*
	題目：[C_SO36-易] 我想要聯誼
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_SO36-易 我想要聯誼.java hosted with ❤ by GitHub

把每個人的分數存入字串之後再跟要求的cp去一個一個比對是否出現在字串中(indexOf)

[C_SO41-中] 撲克牌排序

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=10530

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	ArrayList <Integer> arr=new ArrayList<Integer>();
	while(scn.hasNext()){
	int num=scn.nextInt();
	if(num==0)
	break;
	arr.add(num);
	}
	Collections.sort(arr);
	Collections.reverse(arr);
	for(int i=arr.indexOf(2);i<arr.size();i++){
	System.out.println(arr.get(i));
	}
	for(int i=0;i<arr.indexOf(2);i++){
	if(arr.get(i)==11)
	System.out.printf("%c\n",'J');
	else if(arr.get(i)==12)
	System.out.printf("%c\n",'Q');
	else if(arr.get(i)==13)
	System.out.printf("%c\n",'K');
	else
	System.out.println(arr.get(i));
	}
	}
	/*
	題目：[C_SO41-中] 撲克牌排序
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_SO41-中 撲克牌排序.java hosted with ❤ by GitHub

這題利用List排序做翻轉

[C_SO09-易] 字串重排

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=1436

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	char arr[]=scn.next().toCharArray(),count=0;
	for(int i=0;i<arr.length;i++)
	if(arr[i]=='1')
	count++;
	for(int i=0;i<count;i++)
	System.out.print("1");
	for(int i=0;i<arr.length-count;i++)
	System.out.print("0");
	System.out.println();
	}
	}
	/*
	題目：[C_SO09-易] 字串重排
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_SO09-易 字串重排.java hosted with ❤ by GitHub

這題算出1有幾個就印出來就行了其餘印0

[C_SO03-中] 最遠的兩點

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=1936

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	int num=scn.nextInt(),arr[][]=new int [num][2],max=0;
	for(int i=0;i<num;i++)
	for(int j=0;j<2;j++)
	arr[i][j]=scn.nextInt();
	for(int i=0;i<num-1;i++){
	for(int j=i+1;j<num;j++){
	int tot=(arr[j][0]-arr[i][0])*(arr[j][0]-arr[i][0])+(arr[j][1]-arr[i][1])*(arr[j][1]-arr[i][1]);
	if(tot>max)
	max=tot;
	}
	}
	System.out.println(max);
	}
	}
	/*
	題目：[C_SO03-中] 最遠的兩點
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_SO03-中 最遠的兩點.java hosted with ❤ by GitHub

這題取兩點不重複所以利用雙迴圈去把可能列出來做比對

[C_MM247-易] 環狀排列

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15578

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt(),tot=1;
	for(int i=1;i<n;i++)
	tot*=i;
	if(n<0)
	tot=0;
	System.out.println(tot);
	}
	/*
	題目：[C_MM247-易] 環狀排列
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM247-易 環狀排列.java hosted with ❤ by GitHub

n個人有 n!/n個方法

[C_MM236-中] 多項式的運算

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=6460

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	String s[]=scn.nextLine().split(" ");
	int x=scn.nextInt();
	double tot=0;
	for(int i=0;i<s.length;i+=2){
	int a=Integer.parseInt(s[i]),exp=Integer.parseInt(s[i+1]);
	tot+=a*Math.pow(x, exp);
	}
	System.out.printf("%.0f\n",tot);
	}
	}
	/*
	題目：[C_MM236-中] 多項式的運算
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM236-中 多項式的運算.java hosted with ❤ by GitHub

這題利用Math.pow算出x的次方再乘上他的係數

[C_MM208-易] 求移動路徑格數

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=8304

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	int arr[][]=new int [5][2];
	for(int i=0;i<5;i++){
	arr[i][0]=scn.nextInt();
	arr[i][1]=scn.nextInt();
	}
	int tot=arr[0][0]+arr[0][1];
	for(int i=1;i<5;i++){
	tot+=Math.abs(arr[i][0]-arr[i-1][0])+Math.abs(arr[i][1]-arr[i-1][1]);
	}
	System.out.println(tot);
	}
	}
	/*
	題目：[C_MM208-易] 求移動路徑格數
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM208-易 求移動路徑格數.java hosted with ❤ by GitHub

這題把每個與前一個相減結果相加就是答案了

[C_MM204-易] 填入規律數字

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=8201

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	int arr[]=new int [4];
	for(int i=0;i<4;i++)
	arr[i]=scn.nextInt();
	if((arr[1]-arr[0])==(arr[2]-arr[1])){
	for(int i=0;i<4;i++){
	if(i!=0)
	System.out.print(" ");
	System.out.print(arr[i]);
	}
	System.out.println(" "+(arr[3]+(arr[1]-arr[0])));
	}
	else{
	for(int i=0;i<4;i++){
	if(i!=0)
	System.out.print(" ");
	System.out.print(arr[i]);
	}
	System.out.println(" "+(arr[3]*(arr[1]/arr[0])));
	}
	}
	}
	/*
	題目：[C_MM204-易] 填入規律數字
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM204-易 填入規律數字.java hosted with ❤ by GitHub

這題判斷等差等比再輸出

ITSA 47 [Problem 3] 帕斯卡三角形

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30635

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	int r=scn.nextInt(),k=scn.nextInt();
	System.out.println(combi(r,k));
	}
	}
	public static int combi(int r,int k){
	int p=1;
	for(int i=1;i<=k;i++){
	p=p*(r-i+1)/i;
	}
	return p;
	}
	/*
	題目：ITSA 47 [Problem 3] 帕斯卡三角形
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw ITSA 47 Problem 3 帕斯卡三角形.java hosted with ❤ by GitHub

[C_MM114-易] 進位轉換

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2856

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	String s=scn.next(),sub;
	if(s.contains("end"))
	break;
	else if(s.contains("0x"))
	sub=s.substring(2);
	else
	sub=s;
	System.out.println(Integer.parseInt(sub,s.contains("0x")?16:8));
	}
	}
	/*
	題目：[C_MM114-易] 進位轉換
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM114-易 進位轉換.java hosted with ❤ by GitHub

這題是字串轉任何進位所以要Integer.parseInt("字串",轉換位數成10進位)

[C_MM102-易] 小蝸牛

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2651

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String str1[]=scn.nextLine().split(" "),str2[]=scn.nextLine().split(" "),str3[]=scn.nextLine().split(" ");
	double n=0,r=0,d=0;
	int count=0;
	if(str1[1].equals("m"))
	n=Double.parseDouble(str1[0])*100;
	else
	n=Double.parseDouble(str1[0]);
	if(str2[1].equals("m"))
	r=Double.parseDouble(str2[0])*100;
	else
	r=Double.parseDouble(str2[0]);
	if(str3[1].equals("m"))
	d=Double.parseDouble(str3[0])*100;
	else
	d=Double.parseDouble(str3[0]);
	while(true){
	n-=r;
	if(n<=0)
	break;
	n+=d;
	count++;
	}
	System.out.println(count+1);
	}
	/*
	題目：[C_MM102-易] 小蝸牛
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM102-易 小蝸牛.java hosted with ❤ by GitHub

這題要注意單位換算然後迴圈進入先扣除往上爬是否小於等於0再加上往下滑,只要小於0就跳出迴圈了

[C_MM254-易] 切蛋糕問題

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15780

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int num=scn.nextInt(),tot=2;
	for(int i=1,j=2;i<num;i++,j++){
	tot+=j;
	}
	System.out.println(tot);
	}
	/*
	題目：[C_MM254-易] 切蛋糕問題
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_MM254-易 切蛋糕問題.java hosted with ❤ by GitHub

這題可依發現他是個有遞增的數列2 4 7 11 16 分別加2 3 4 5

2016 闖關組 [Problem B11] Rotate around a circle

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30527

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n = scn.nextInt();
	while (n-- != 0) {
	long D = scn.nextLong(), K = scn.nextLong(), N = scn.nextLong(), L = scn.nextLong(), a = 0, b = 0;
	if (K % 2 == 1) {//會員為奇數時
	a = ((K + 1) + (2 * L * N)) % D;
	b = ((K - 1) + (2 * L * N)) % D;
	}
	else {//會員為偶數時
	a = ((K + 1) - (2 * L * N)) % D;
	b = ((K - 1) - (2 * L * N)) % D;
	if (a < 0)
	a += D;
	if (b < 0)
	b += D;
	}
	if (a == 0)
	a = D;
	if (b == 0)
	b = D;
	System.out.println(a + " " + b);
	}
	}
	/*
	題目：[Problem B11] Rotate around a circle
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2016 闖關組 Problem B11 Rotate around a circle.java hosted with ❤ by GitHub

這題用模擬會溢位,所以要用數學方法解,環狀位置要用餘數運算
我們可以遵循它的規律
D會員人數 K會員代號 N換位次數 L每次移動距離
ex:
會員代號偶數時
8 3 2 1
原本位置 4 3 2
第一次換位結果 6 3 4
第二次換位結果 8 3 6
推導出
((k+1)-(2*N*L))%D =>8//因為偶數逆時鐘所以減若為負數加上D

會員代號奇數時
8 4 2 1
原本位置 5 4 3
第一次換位結果 3 4 1
第二次換位結果 1 4 7
((k+1)+(2*N*L))%D =>1//奇數順時鐘所以加

最後當數字為0時要變成D

[C_GD02-難] Busy day

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23932

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt(),tot=0;
	for(int i=0;i<n;i++)
	tot+=scn.nextInt();
	if(tot%2==0)
	System.out.println("YES");
	else
	System.out.println("NO");
	}
	/*
	題目：[C_GD02-難] Busy day
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_GD02-難 Busy day.java hosted with ❤ by GitHub

這題不要想太多直接全部加起來判斷是否為偶數

[C_GD03-易] 線段切割

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23935

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	int num=scn.nextInt(),tot=0,i=1;
	while(true){
	tot+=i;
	if(tot>num)
	break;
	i++;
	}
	System.out.println(i-1);
	}
	}
	/*
	題目：[C_GD03-易] 線段切割
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_GD03-易 線段切割.java hosted with ❤ by GitHub

把數字連加當大於num跳出迴圈輸出i-1

[Problem B1-易] Eigenvalues of a 2x2 Matrix

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23222

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n = scn.nextInt();
	while (n-- != 0) {
	int a = scn.nextInt(), b = scn.nextInt(), c = scn.nextInt(), d = scn.nextInt(), n1 = 0, n2 = 0;
	n1 = -(a + d);
	n2 = (a * d - c * c);
	double x = (-n1 + Math.pow(n1 * n1 - 4 * n2, 0.5)) / 2.0, y = (-n1 - Math.pow(n1 * n1 - 4 * n2, 0.5)) / 2.0;
	System.out.printf("%.2f %.2f\n", x > y ? x : y, x > y ? y : x);
	}
	}
	/*
	題目：[Problem B1-易] Eigenvalues of a 2x2 Matrix
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2014 闖關組 Problem B1-易 Eigenvalues of a 2x2 Matrix.java hosted with ❤ by GitHub

這題使用公式解 2A分之負B正負根號b平方減4AC
就能求出xy解

Q10684 : The jackpot

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1625&mosmsg=Submission+received+with+ID+17796056

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while (scn.hasNext()) {
	int n=scn.nextInt(),max=0,tot=0;
	if(n==0)
	break;
	for(int i=0;i<n;i++){
	tot+=scn.nextInt();
	if(tot<0)
	tot=0;
	if(tot>max)
	max=tot;
	}
	if(max!=0)
	System.out.printf("The maximum winning streak is %d.\n",max);
	else
	System.out.printf("Losing streak.\n");
	}
	}
	/*
	題目：Q10684 : The jackpot
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q10684 : The jackpot.java hosted with ❤ by GitHub

這題使用貪婪法,一個有序的數列中,累積總和遇到負數歸零,時間複雜度O(N)

2014 闖關組 [Problem B5-易中] Apple trees in a line

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23212

	#include<stdio.h>
	int main(){
	int n;
	while (scanf("%d",&n)!=EOF) {
	if(n==0)
	break;
	int arr[n],max=0,i,tot=0;
	for(i=0;i<n;i++)
	scanf("%d",&arr[i]);
	for(i=0;i<n;i++){
	tot+=arr[i];
	if(tot<0)
	tot=0;
	if(tot>max)
	max=tot;
	}
	printf("%d\n",max);
	}
	/*
	題目：2014 闖關組 [Problem B5-易中] Apple trees in a line
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2014 闖關組 Problem B5-易中 Apple trees in a line.java hosted with ❤ by GitHub

這題使用貪婪法,累積總和遇到負數歸零,時間複雜度O(N)

2014 闖關組 [Problem B2-易] Computing C(n,k)

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23224

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n = scn.nextInt();
	while (n-- != 0) {
	int N=scn.nextInt(),k=scn.nextInt();
	System.out.println(call(N)/(call(k)*call(N-k)));
	}
	}
	public static long call(int num){
	long tot=1;
	for(int i=1;i<=num;i++){
	tot*=i;
	}
	return tot;
	}
	/*
	題目：2014 闖關組 [Problem B2-易] Computing C(n,k)
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2014 闖關組 Problem B2-易 Computing C(n,k).java hosted with ❤ by GitHub

2014 闖關組 [Problem B3-易] Rock-paper-scissors-lizard-Spock

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23226

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n = Integer.parseInt(scn.nextLine());
	while (n-- != 0) {
	String str[]=scn.nextLine().split(" ");
	if(str[0].equals(str[1]))
	System.out.println("0");
	else if(str[0].equals("scissors")&&str[1].equals("paper"))
	System.out.println("1");
	else if(str[0].equals("paper")&&str[1].equals("rock"))
	System.out.println("1");
	else if(str[0].equals("rock")&&str[1].equals("lizard"))
	System.out.println("1");
	else if(str[0].equals("lizard")&&str[1].equals("Spock"))
	System.out.println("1");
	else if(str[0].equals("Spock")&&str[1].equals("scissors"))
	System.out.println("1");
	else if(str[0].equals("scissors")&&str[1].equals("lizard"))
	System.out.println("1");
	else if(str[0].equals("lizard")&&str[1].equals("paper"))
	System.out.println("1");
	else if(str[0].equals("paper")&&str[1].equals("Spock"))
	System.out.println("1");
	else if(str[0].equals("Spock")&&str[1].equals("rock"))
	System.out.println("1");
	else if(str[0].equals("rock")&&str[1].equals("scissors"))
	System.out.println("1");
	else
	System.out.println("2");
	}
	}
	/*
	題目：2014 闖關組 [Problem B3-易] Rock-paper-scissors-lizard-Spock
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2014 闖關組 Problem B3-易 Rock-paper-scissors-lizard-Spock.java hosted with ❤ by GitHub

2015 闖關組 [Problem B5-中易] Coin Change(換零錢方法數)

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23650

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	long dp[] = new long[15001];
	int coins[] = { 1, 5, 10, 20, 50 };
	for (int j = 0; j <= 15000; j++)
	dp[j] = 1;
	for (int i = 1; i < 5; i++) {
	for (int j = coins[i]; j <= 15000; j++) {
	dp[j] += dp[j - coins[i]];
	}
	}
	int n = scn.nextInt();
	while (n-- != 0) {
	int num = scn.nextInt();
	System.out.println(dp[num]);
	}
	}
	/*
	題目：2015 闖關組 [Problem B5-中易] Coin Change(換零錢方法數)
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2015 闖關組 Problem B5-中易 Coin Change(換零錢方法數).java hosted with ❤ by GitHub

這題利用動態規劃先把1~15000的換錢方法存入陣列(long)
coins[ ]={1,5,10,20,50}
1.首先建立dp[15001]個陣列並每個存1(一元的分法)
2.外迴圈從coin[i=1]開始~coin[4]內迴圈從j=coin[i]開始~15000,dp[ j ]+=dp[ j-coins[i] ] 
ex:10元
i=1時
dp[10]+=dp[10-5]=1+2=3
i=2時
dp[10]+=dp[10-10]=3+1=4

2016 闖關組 [Problem B10] Password Complexity

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30526

	package ITSA;
	import java.math.BigInteger;
	import java.util.*;
	public class Test {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int test=Integer.parseInt(sc.nextLine());
	for(int j=0;j<test;++j)
	{
	String in=sc.nextLine();
	String[] split=in.split(" ");
	char[] arr=split[1].toCharArray();
	int[] count=new int[52];
	BigInteger bi=new BigInteger("1");
	for(int i=1;i<=arr.length;++i)
	{
	bi=bi.multiply(new BigInteger(Integer.toString(i)));
	if(arr[i-1]>='a' && arr[i-1]<='z')
	count[arr[i-1]-'a']++;
	if(arr[i-1]>='A' && arr[i-1]<='Z')
	count[arr[i-1]-'A'+26]++;
	}
	for(int i=0;i<count.length;++i)
	{
	if(count[i]>1)
	{
	for(int k=count[i];k>0;--k)
	bi=bi.divide(new BigInteger(Integer.toString(k)));
	}
	}
	System.out.println(bi.mod(new BigInteger(split[0])));
	}
	}
	/*
	題目：2016 闖關組 [Problem B10] Password Complexity
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2016 闖關組 Problem B10 Password Complexity.java hosted with ❤ by GitHub

這題要注意可能會溢位必須要用BigInteger,有大小寫區分
ex: 排列組合abbccc =>6!/(1!*2!*3!)

2016 闖關組 [Problem B1] Product and remainder

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=15733

	import java.math.BigInteger;
	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	int num=scn.nextInt(),arr[]=new int [num],j=0;
	BigInteger tot=new BigInteger("1"),div=scn.nextBigInteger();
	for(int i=0;i<num;i++)
	arr[i]=scn.nextInt();
	for(j=0;j<num;j++){
	tot=tot.multiply(new BigInteger(Integer.toString(arr[j]%Integer.parseInt(div.toString()))));
	if(tot.mod(div).equals(new BigInteger("1"))){
	System.out.println(j+1);
	break;
	}
	}
	if(j==num)
	System.out.println(-1);
	}
	}
	/*
	題目：2016 闖關組 [Problem B1] Product and remainder
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2016 闖關組 Problem B1 Product and remainder.java hosted with ❤ by GitHub

這題要注意可能會溢位必須要用BigInteger,每個數相乘直到餘一為止

2016 闖關組 [Problem B4] Market Street

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30520

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	int num=scn.nextInt(),arr[]=new int [num],tot=0;
	for(int i=0;i<num;i++)
	arr[i]=scn.nextInt();
	for(int i=0;i<num;i++){
	tot+=arr[i]/2;
	for(int j=0;j<i;j++){
	tot+=arr[j];
	}
	}
	System.out.println(tot);
	}
	}
	/*
	題目：2016 闖關組 [Problem B4] Market Street
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2016 闖關組 Problem B4 Market Street.java hosted with ❤ by GitHub

用陣列和迴圈下去紀錄長度

2016 闖關組 [Problem B2] Simple Card Shuffling簡易洗牌法

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=15734

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	while(n--!=0){
	int arr[]=new int [52],arr2[]=new int [52],num=scn.nextInt(),rand;
	for(int i=0;i<52;i++)
	arr[i]=i+1;
	for(int i=0;i<num;i++){
	rand=scn.nextInt()-1;
	int count=0;
	while(true){
	if(rand==52)
	rand=0;
	arr2[count++]=arr[rand++];
	if(count==52)
	break;
	}
	for(int j=0;j<52;j++)
	arr[j]=arr2[j];
	}
	System.out.println(arr2[51]);
	}
	}
	/*
	題目：2016 闖關組 [Problem B2] Simple Card Shuffling簡易洗牌法
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2016 闖關組 Problem B2 Simple Card Shuffling簡易洗牌法.java hosted with ❤ by GitHub

這題建兩個二維陣列做模擬洗牌

2016 闖關組[Problem B3] The Median of a List of Numbers

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30519

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	ArrayList<Integer> list=new ArrayList<Integer>();
	while(scn.hasNext()){
	list.add(scn.nextInt());
	}
	Collections.sort(list);
	if(list.size()%2==0)
	System.out.println(list.get(list.size()/2));
	else
	System.out.println(list.get((list.size()+1)/2));
	}
	/*
	題目：2016 闖關組[Problem B3] The Median of a List of Numbers
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw 2016 闖關組 Problem B3 The Median of a List of Numbers.java hosted with ❤ by GitHub

這題由於不知有多筆測資所以放到ArrayList

[C_GD10-易] 整除的數字

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=24203

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int num = scn.nextInt(), num2 = 0, k = 0, count = 0;
	for (int i = 10000; i < 100000; i++) {
	int tot = 0;
	if (i % num == 0) {
	num2 = i / num;
	char arr1[] = String.valueOf(i).toCharArray(), arr2[] = String.valueOf(num2).toCharArray();
	int arr[] = new int[10];
	for (int j = 0; j < arr1.length; j++) {
	arr[arr1[j] - '0']++;
	}
	for (int j = 0; j < arr2.length; j++) {
	arr[arr2[j] - '0']++;
	}
	if(arr2.length==4)
	arr[0] = 1;
	for (k = 0; k < 10; k++) {
	if (arr[k] != 1)
	break;
	}
	if (k == 10) {
	System.out.printf("%05d / %05d = %d\n", i, num2, num);
	count++;
	}
	}
	}
	if (count == 0)
	System.out.printf("No solutions for %d.\n", num);
	}
	/*
	題目：[C_GD10-易] 整除的數字
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw C_GD10-易 整除的數字.java hosted with ❤ by GitHub

這題直接迴圈10000~100000中去找是否整除 再算出另一個數字,最後兩個數字去檢查是否為0~9都有

Q612 : DNA Sorting

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=553

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine());
	Boolean boo=false;
	while(n--!=0){
	if(boo)
	System.out.println();
	int a=scn.nextInt(),b=scn.nextInt(),max=0,ans[]=new int [b],count=0;
	String s[]=new String[b];
	for(int i=0;i<b;i++)
	s[i]=scn.next();
	for(int i=0;i<b;i++){
	char arr[]=s[i].toCharArray();
	for(int j=0;j<a-1;j++){
	for(int k=j+1;k<a;k++){
	if(arr[j]>arr[k])
	count++;
	}
	}
	ans[i]=count;
	if(count>max)
	max=count;
	count=0;
	}
	for(int i=0;i<=max;i++){
	for(int j=0;j<b;j++){
	if(ans[j]==i)
	System.out.println(s[j]);
	}
	}
	boo=true;
	}
	/*
	題目：Q612 : DNA Sorting
	作者：1010
	時間：西元 2016 年 8 月 */
	}
	}

view raw Q612 : DNA Sorting.java hosted with ❤ by GitHub

困難度 ★★
這題依題意算出每個字串的數字再將之排序把原來的字串從小到大印出來,最後一行不用換行

Q11577: Letter Frequency

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2624

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine());
	while(n--!=0){
	String str=scn.nextLine().toLowerCase();
	char arr[]=str.toCharArray();
	int ary[]=new int [26],max=0;
	for(int i=0;i<arr.length;i++){
	if(arr[i]>='a'&&arr[i]<='z'){
	ary[arr[i]-'a']++;
	if(max<ary[arr[i]-'a'])
	max=ary[arr[i]-'a'];
	}
	}
	for(int i=0;i<26;i++){
	if(max==ary[i])
	System.out.printf("%c",(i+'a'));
	}
	System.out.println();
	}
	}
	/*
	題目：Q11577: Letter Frequency
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q11577: Letter Frequency.java hosted with ❤ by GitHub

困難度 ★
這題就是記錄英文字母出現次數忽略大小寫相同的次數也要印出來最後要換行

Q11743 : Credit Check

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2843

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=Integer.parseInt(scn.nextLine());
	while(n--!=0){
	int tot=0;
	String str=scn.nextLine(),arr[]=str.split(" ");
	for(int i=0;i<arr.length;i++){
	char c[]=arr[i].toCharArray();
	tot+=((c[0]-'0')*2%10)+((c[0]-'0')*2/10)+((c[2]-'0')*2%10)+((c[2]-'0')*2/10)+(c[1]-'0')+(c[3]-'0');
	}
	if((tot)%10==0)
	System.out.println("Valid");
	else
	System.out.println("Invalid");
	}
	}
	/*
	題目：Q11743 : Credit Check
	作者：1010
	時間：西元 2016 年 8 月 */
	}

view raw Q11743 : Credit Check.java hosted with ❤ by GitHub

這題只是利用字元-'0'得到數字然後依題意做運算結果尾數為0季Valid