Code Workshop: 2月 2017

2017年2月22日星期三

[C_AR42-易] 過半元素

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

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	while(scn.hasNext()){
	String arr[]=scn.nextLine().split(" ");
	int i=0;
	for(i=0;i<arr.length;i++){
	int count=0;
	for(int j=0;j<arr.length;j++){
	if(arr[i].equals(arr[j]))
	count++;
	}
	if(arr.length/2<count){
	System.out.println(arr[i]);
	break;
	}
	}
	if(i==arr.length)
	System.out.println("NO");
	}
	}
	/*題目：[C_AR42-易] 過半元素
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_AR42-易過半元素.java hosted with ❤ by GitHub

這題由於不知有多少數列故用字串切割去比對過半數

ITSA 第50次月賽 [Problem 2] The Typhoon

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

	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(),e=scn.nextInt(),f=scn.nextInt(),g=scn.nextInt()
	,h=scn.nextInt(),i=scn.nextInt(),tot=0;
	tot=aei+dhc+gbf-ceg-bdi-afh;
	System.out.println(tot);
	}
	}
	/*題目：ITSA 第50次月賽 [Problem 2] The Typhoon
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw ITSA 第50次月賽 Problem 2 The Typhoon.java hosted with ❤ by GitHub

這題按照公式照打就行了~

ITSA 第50次月賽 [Problem 4] 偽造的金幣!!

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

	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(),count=0;
	while(num!=1){
	num=(int)Math.ceil(num/3.);
	count++;
	}
	System.out.println(count);
	}
	}
	/*題目：ITSA 第50次月賽 [Problem 4] 偽造的金幣!!
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw ITSA 第50次月賽 Problem 4 偽造的金幣!!.java hosted with ❤ by GitHub

	#include<stdio.h>
	#include<math.h>
	int main()
	{
	int N,n,i;
	scanf("%d",&N);
	for(i=0;i<N;i++)
	{
	scanf("%d",&n);
	printf("%.0lf\n",ceil(log(n)/log(3)));
	}
	return 0;
	/*題目：ITSA 第50次月賽 [Problem 4] 偽造的金幣!!
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw ITSA 第50次月賽 Problem 4 偽造的金幣.c hosted with ❤ by GitHub

這題背後原理是Divide&Conquer演算法，可以推導出只用一行程式的公式
(1)假設N = 8袋, 先分成3、3、2 三大袋(A、B、C)，先拿A、B秤，若A、B平衡，代表C有偽幣；反之A或B裡輕的那一大袋有偽幣
(2)若A是輕的有偽幣，將A袋分成1、1、1三大袋(D、E、F)，先拿D、E秤，假如天秤不穩，代表輕的那一代就是偽幣；反之，F是偽幣
從這過程中，得知不斷將問題兩半切下(Divide)去比對(Conquer)，正是這演算法的精神
至於怎變成公式，跟BigO(演算法複雜度)有關係
這種方法叫做prune & search，典型的演算法就是binary search，每比對一次，就可以去除一半不可能的，留下一半可能的繼續搜尋下去。而這一題，就是希望每秤一次，不管運氣好壞，留下來的越少越好

至於為什麼要取三堆呢?
分兩堆只能砍掉一半；分四堆以上，秤其中兩堆，運氣不好，只能砍掉這兩堆，其他留著繼續秤；分三堆，運氣不管好壞，都只會留下1/3

2017年2月21日星期二

ITSA 第53次月賽 [Problem 3] 號碼鎖最少轉動幾次

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

	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){
	char str1[]=scn.next().toCharArray(),str2[]=scn.next().toCharArray();
	int tot=0;
	for(int i=0;i<str1.length;i++){
	double a=str1[i]-'0',b=str2[i]-'0';
	if(a<b){
	double temp=b;
	b=a;
	a=temp;
	}
	tot+=Math.abs(a-b)>Math.abs(10-a)+b?(int)Math.abs(10-a)+b:(int)Math.abs(a-b);
	}
	System.out.println(tot);
	}
	}
	/*題目：ITSA 第53次月賽 [Problem 3] 號碼鎖最少轉動幾次
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw ITSA 第53次月賽 Problem 3 號碼鎖最少轉動幾次.java hosted with ❤ by GitHub

這題就使用貪婪比較從前面轉或從後面轉比較少次
大小比對這部分我是使用問號運算式當為真執行冒號前面，反之

ITSA 第53次月賽 [Problem 2] 洞穴裡的人

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

	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(),M=scn.nextInt();
	while(true){
	N=(int)(N*(1/4.));
	if(N<M)
	break;
	N+=M;
	}
	System.out.println(N);
	}
	}
	/*題目：ITSA 第53次月賽[Problem 2] 洞穴裡的人
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw ITSA 第53次月Problem 2 洞穴裡的人.java hosted with ❤ by GitHub

這題就用迴圈每次乘以1/4.若進入人數大於裡面剩餘人數就退出，並印出最後剩餘人數

Q256: Quirksome Squares

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

	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;
	int halfBound = (int)Math.pow(10, n / 2);
	for(int i=0;i<halfBound;i++){
	int num=i*i;
	if(Math.pow(num/halfBound+num%halfBound,2)==num)
	System.out.printf("%0"+n+"d\n",num);
	}
	}
	}
	/*題目：Q256: Quirksome Squares
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw Q256: Quirksome Squares.java hosted with ❤ by GitHub

這題你會發現quirksome number是一個完全平方數例如81=9*9，n=4假如有四位數0~9999依序判斷肯定會TL超時
所以我們只要判斷1、4、9、16....到(10^(n/2)-1)*(10^(n/2)-1)
簡單來說當n=4時迴圈從0開始直到100結束，求0~99的完全平方來判斷是否為quirksome number

[C_AR023-易] 字根與子字串

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

	import java.util.*;

	public class Main {

	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String s=scn.next(),t=scn.next();
	if(t.contains(s))
	System.out.println("YES");
	else
	System.out.println("NO");
	}
	/*題目：[C_AR023-易] 字根與子字串
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_AR023-易字根與子字串.java hosted with ❤ by GitHub

這題對java來說很簡單直接呼叫字串函式contains就能判別是否為子字串了

[C_AR40-易] 螺旋矩陣

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

	import java.util.*;

	public class Main {

	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String str[] = scn.nextLine().split(",");
	int n = Integer.parseInt(str[0]), index = Integer.parseInt(str[1]), count = 1, arr[][] = new int[n][n];
	if (index == 1) {//順時鐘
	for (int i = 0; i < n / 2; i++) {
	for (int j = i; j < n - i - 1; j++)
	arr[i][j] = count++;
	for (int j = i; j < n - i - 1; j++)
	arr[j][n - i - 1] = count++;
	for (int j = n - i - 1; j > i; j--)
	arr[n - i - 1][j] = count++;
	for (int j = n - i - 1; j > i; j--)
	arr[j][i] = count++;
	}
	} else {//逆時鐘
	for (int i = 0; i < n / 2; i++) {
	for (int j = i; j < n - i - 1; j++)
	arr[j][i] = count++;
	for (int j = i; j < n - i - 1; j++)
	arr[n - 1 - i][j] = count++;
	for (int j = n - i - 1; j > i; j--)
	arr[j][n - i - 1] = count++;
	for (int j = n - i - 1; j > i; j--)
	arr[i][j] = count++;
	}
	}
	if (n % 2 != 0)//遇到基數層要補上中心數
	arr[n / 2][n / 2] = count;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	System.out.printf("%03d", arr[i][j]);
	if (j != n - 1)
	System.out.print(",");
	}
	System.out.println();
	}
	}
	/*題目：[C_AR40-易] 螺旋矩陣
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_AR40-易螺旋矩陣.java hosted with ❤ by GitHub

這題螺旋矩陣最直覺方法就是模擬，那如何做呢?首先不管順(逆)時鐘都有個規律，建議各位還是在紙上寫下每個位置的索引值如下:

[0,0] [0,1] [0,2] [0,3]
[1,0] [1,1] [1,2] [1,3]
[2,0] [2,1] [2,2] [2,3]
[3,0] [3,1] [3,2] [3,3]

看到這可能還是很模糊，我們在看下面這張圖搭配索引值發現他其實是有規律的，以順時鐘來說我們依序由上排佐至右，接下來又半部由上而下，然後下半部由右至左，最後左邊由下而上內層一樣按照此規律
那在這各位可能會問我們怎知道有幾層呢?把它當作洋蔥n=4時他有4/2=2層(迴圈跑兩次的意思，觀察索引值)，那當遇到偶數時該怎麼辦呢?n=5，時就有5/2=2層，你可以發現他其實還有一層但他只有一個數字，可以把它當作成是圓的中心點個別處理arr[n / 2][n / 2] = count;

2017年2月20日星期一

[C_MM86-易] 公因數問題

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

	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(),c=scn.nextInt();
	while((a%=b)!=0&&(b%=a)!=0);
	int d=a+b;
	while((d%=c)!=0&&(c%=d)!=0);
	System.out.print("Common factor in ascending order: ");
	for(int i=2;i<=d+c;i++){
	if((d+c)%i==0){
	System.out.print(i);
	if(i!=d+c)
	System.out.print(" ");
	}
	}
	System.out.println();
	}
	/*題目：[C_MM86-易] 公因數問題
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_MM86-易公因數問題.java hosted with ❤ by GitHub

這題就是做兩次最大公因數(因為有三個數字)，最後出來的數再做質因數分解就是答案了!
這是最件簡單的最大公因數公式(輾轉相除法)
while((a%=b)!=0&&(b%=a)!=0);

[C_ST84-易] 差集

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

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String arr1[]=scn.nextLine().split(","),arr2[]=scn.nextLine().split(",");
	ArrayList<Integer> list=new ArrayList<Integer>();
	int j=0;
	for(int i=0;i<arr1.length;i++){
	for(j=0;j<arr2.length;j++){
	if(arr1[i].equals(arr2[j])){
	break;
	}
	}
	if(j==arr2.length)
	list.add(Integer.parseInt(arr1[i]));
	}
	if(list.size()>0){
	Collections.sort(list);
	for(int i=0;i<list.size();i++){
	if(i!=0)
	System.out.print(" ");
	System.out.print(list.get(i));
	}
	System.out.println();
	}else{
	System.out.println("null");
	}
	}
	/*題目：[C_ST84-易] 差集
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_ST84-易差集.java hosted with ❤ by GitHub

差集就跟交集相反，程式碼也類似

[C_ST83-易] 聯集

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

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String arr1[]=scn.nextLine().split(","),arr2[]=scn.nextLine().split(",");
	Set<Integer> set = new TreeSet<Integer>();
	for(int i=0;i<arr1.length;i++)
	set.add(Integer.parseInt(arr1[i]));
	for(int i=0;i<arr2.length;i++)
	set.add(Integer.parseInt(arr2[i]));
	int count=0;
	for(Integer s : set){
	if(count++!=0)
	System.out.print(" ");
	System.out.print(s);
	}
	System.out.println();
	}
	/*題目：[C_ST83-易] 聯集
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_ST83-易聯集.java hosted with ❤ by GitHub

這題使用Set集合來完成聯集，至於為什麼要用Set呢?原因是它是唯一實作SortedSet介面的類別，因此可針對Set中的元素進行排序

[C_ST82-易] 交集

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

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String arr1[]=scn.nextLine().split(","),arr2[]=scn.nextLine().split(",");
	ArrayList<Integer> list=new ArrayList<Integer>();
	for(int i=0;i<arr1.length;i++){
	for(int j=0;j<arr2.length;j++){
	if(arr1[i].equals(arr2[j])){
	list.add(Integer.parseInt(arr1[i]));
	break;
	}
	}
	}
	if(list.size()>0){
	Collections.sort(list);
	for(int i=0;i<list.size();i++){
	if(i!=0)
	System.out.print(" ");
	System.out.print(list.get(i));
	}
	System.out.println();
	}else{
	System.out.println("null");
	}
	}
	/*題目：[C_ST82-易] 交集
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_ST82-易交集.java hosted with ❤ by GitHub

這題使用ArrayList動態配置交集數，並且使用Collections.sort做排序

2017年2月17日星期五

[C_MM353-易] 找出一串輸入數字的中位數

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

	import java.util.*;

	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt(),arr[]=new int [n];
	for(int i=0;i<n;i++)
	arr[i]=scn.nextInt();
	Arrays.sort(arr);
	System.out.println(arr[n/2]);
	}
	/*題目：[C_MM353-易] 找出一串輸入數字的中位數
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_MM353-易找出一串輸入數字的中位數.java hosted with ❤ by GitHub

這題利用Arrays.sort()做排序很快地就能找出中位數

2017年2月16日星期四

[C_AR131-易] 判斷OX遊戲的勝負

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

	import java.util.*;

	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	String arr[][]=new String [3][3];
	for(int i=0;i<3;i++){
	String str[]=scn.nextLine().split(",");
	for(int j=0;j<3;j++)
	arr[i][j]=str[j];
	}
	if(arr[1][1].equals(arr[0][0])&&arr[2][2].equals(arr[0][0])&&!arr[0][0].equals("1")){
	System.out.println(arr[0][0]);
	}
	else if(arr[1][1].equals(arr[0][2])&&arr[2][0].equals(arr[0][2])&&!arr[0][2].equals("1")){
	System.out.println(arr[0][2]);
	}
	else{
	int i=0;
	for(i=0;i<3;i++){
	int count=1;
	String temp=arr[i][0];
	for(int j=1;j<3;j++){
	if(!arr[i][j].equals(temp)\|\|arr[i][j].equals("1"))
	break;
	else
	count++;
	}
	if(count==3){
	System.out.println(arr[i][0]);
	break;
	}
	}
	if(i==3)
	System.out.println("1");
	}
	}
	/*題目：[C_AR131-易] 判斷OX遊戲的勝負
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_AR131-易判斷OX遊戲的勝負.java hosted with ❤ by GitHub

2017年2月15日星期三

[C_MM213-易] 就決定是你了!!

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

這題就純粹依照題目的加權下去做運算

	import java.util.*;

	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt();
	for(int i=0;i<n;i++){
	int a=scn.nextInt();
	double a_tot=0;
	for(int j=0;j<a;j++){
	int level=scn.nextInt(),attr=scn.nextInt();
	if(attr==1){
	a_tot+= (level45+40)0.5+(level8+2)1.5+(level17+30)1.3+(level5+10)2;
	}else if(attr==2){
	a_tot+= (level50+45)0.5+(level5+2)1.5+(level17+30)1.3+(level7+9)2;
	}else if(attr==3){
	a_tot+= (level40+45)0.5+(level5+2)1.5+(level20+30)1.3+(level8+8)2;
	}else{
	a_tot+= (level45+45)0.5+(level6+3)1.5+(level15+30)1.3+(level10+10)2;
	}}
	int b=scn.nextInt();
	double b_tot=0;
	for(int j=0;j<b;j++){
	int level=scn.nextInt(),attr=scn.nextInt();
	if(attr==1){
	b_tot+= (level45+40)0.5+(level8+2)1.5+(level17+30)1.3+(level5+10)2;
	}else if(attr==2){
	b_tot+= (level50+45)0.5+(level5+2)1.5+(level17+30)1.3+(level7+9)2;
	}else if(attr==3){
	b_tot+= (level40+45)0.5+(level5+2)1.5+(level20+30)1.3+(level8+8)2;
	}else{
	b_tot+= (level45+45)0.5+(level6+3)1.5+(level15+30)1.3+(level10+10)2;
	}
	}
	if(b_tot<a_tot)
	System.out.println("win");
	else if(b_tot>a_tot)
	System.out.println("lose");
	else
	System.out.println("tie");
	}

	}
	/*題目：[C_MM213-易] 就決定是你了!!
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_MM213-易就決定是你了!!.java hosted with ❤ by GitHub

[C_AR117-易] 山頭林立

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

簡單來說就從第一個開始前後比對(0開始)假如大於前後者就是山頭
注意!答案輸出第一行是山頭數量

	import java.util.*;

	public class Main {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int n=scn.nextInt(),arr[]=new int[n],count=0;
	for(int i=0;i<n;i++)
	arr[i]=scn.nextInt();
	for(int i=1;i<n-1;i++){
	if(arr[i-1]<arr[i]&&arr[i+1]<arr[i])
	count++;
	}
	System.out.println(count);
	for(int i=0;i<n;i++){
	if(i==0\|\|i==n-1)
	System.out.println(arr[i]);
	else if(arr[i-1]<arr[i]&&arr[i+1]<arr[i])
	System.out.println(arr[i]+">>>>>");
	else
	System.out.println(arr[i]);
	}

	}
	/*題目：[C_AR117-易] 山頭林立
	作者：1010
	時間：西元 2017 年 2 月 */
	}

view raw C_AR117-易山頭林立.java hosted with ❤ by GitHub

訂閱：文章 (Atom)

Code Workshop

2017年2月22日星期三

[C_AR42-易] 過半元素

ITSA 第50次月賽 [Problem 2] The Typhoon

ITSA 第50次月賽 [Problem 4] 偽造的金幣!!

2017年2月21日星期二

ITSA 第53次月賽 [Problem 3] 號碼鎖最少轉動幾次

ITSA 第53次月賽 [Problem 2] 洞穴裡的人

Q256: Quirksome Squares

[C_AR023-易] 字根與子字串

[C_AR40-易] 螺旋矩陣

2017年2月20日星期一

[C_MM86-易] 公因數問題

[C_ST84-易] 差集

[C_ST83-易] 聯集

[C_ST82-易] 交集

2017年2月17日星期五

[C_MM353-易] 找出一串輸入數字的中位數

2017年2月16日星期四

[C_AR131-易] 判斷OX遊戲的勝負

2017年2月15日星期三

[C_MM213-易] 就決定是你了!!

[C_AR117-易] 山頭林立

網誌存檔

標籤

2017年2月22日 星期三

2017年2月21日 星期二

2017年2月20日 星期一

2017年2月17日 星期五

2017年2月16日 星期四

2017年2月15日 星期三

2017年2月22日星期三

2017年2月21日星期二

2017年2月20日星期一

2017年2月17日星期五

2017年2月16日星期四

2017年2月15日星期三