題目來源 : https://uva.onlinejudge.org/external/101/p10101.pdf
http://zerojudge.tw/ShowProblem?problemid=a741[高中生解題系統]
2015年7月29日 星期三
2015年7月28日 星期二
ITSA 桂冠賽 [Problem B4-易] Polynomials
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?a=11958
解法 : 想不到更簡單的方法~"~，因為題目表示d不超過3 ，所以我就用的暴力法....分開解
如果d==1則直接輸出，d==2則係數相乘一次，d==3則再乘一次
[Problem B4-易] Polynomials
成績: 0 / 倒扣: 0.8
Time Limit: 1 second
Problem Description
Problem Description
● EnglishTechnical Specification
Given a product (ax2 + bx + c)d, write a program to compute the coefficients of the resulting polynomial. For example, if (a, b, c, d) = (1, 2, 3, 2), we have (x2 + 2x + 3)2 = x4 + 4x3 + 10x2 + 12x + 9 and your program outputs the coefficients 1, 4, 10, 12 and 9. In this problem, a, b, c, d are all integers and d is at most three.
● Chinese
給定一個多項式乘積形式如下 : (ax2 + bx + c)d ，本題的工作是要算出多項式乘積展開後的各項係數。例如，給定 (a, b, c, d) = (1, 2, 3, 2) ，則 (x2 + 2x + 3)2 = x 4+ 4x3 + 10x2 + 12x + 9 ，你的程式需要輸出係數 1, 4, 10, 12 和 9 。 在這個問題裏 ， 每個所給的數字皆為整數 ，而且 d 不會超過 3 。
● EnglishInput Format
● Chinese
- All the given numbers are integers.
- The range of each number is as follows:
- -100 ≤ a ≤ 100 and a ≠ 0
- -100 ≤ b ≤ 100
- -100 ≤ c ≤ 100
- 1 ≤ d ≤ 3
- 每個所給的數字皆為整數
- 每個數的限制範圍如下 :
- -100 ≤ a ≤ 100 且 a ≠ 0
- -100 ≤ b ≤ 100
- -100 ≤ c ≤ 100
- 1 ≤ d ≤ 3
● EnglishOutput Format
The first line is an integer which indicates the number of test cases. Each test case consists of four integers a, b, c, d, separated by spaces, in a line.
● Chinese
第一行是一個整數代表測試資料有幾筆。每一筆測試資料都用一行四個整數 a , b, c, d 來表示，整數之間以一個以上的空格分開。
● EnglishExample
For each test case, output the coefficients of (ax2 + bx + c)d in a line by the descending power of x , separated by spaces.
● Chinese
針對每一筆測試資料，依降冪順序輸出多項式的係數。兩筆資料之間以一個斷行隔開，兩係數之間以一個空格隔開。
| Sample Input: | Sample Output: |
| 4 1 2 3 2 1 10 100 1 10 0 10 3 20 0 -1 2 | 1 4 10 12 9 1 10 100 1000 0 3000 0 3000 0 1000 400 0 -40 0 1 |
解法 : 想不到更簡單的方法~"~，因為題目表示d不超過3 ，所以我就用的暴力法....分開解
如果d==1則直接輸出，d==2則係數相乘一次，d==3則再乘一次
2015年7月27日 星期一
ITSA 桂冠賽 [Problem B7-中] The Maximum Bottleneck Spanning Tree
題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23652
這題是Maximum Spanning Tree的問題，只是他要找的是阻抗值最大的cost，可以使用Kruskal 演算法來完成，判斷cycle的方法是用Disjaint Set。
[Problem B7-中] The Maximum Bottleneck Spanning Tree
成績: 0 / 倒扣: 0.8
Time Limit: 3 second
Problem Description
Problem Description
● EnglishTechnical Specification
Let G = (V, E) be a graph to denote a communication network, in which the nodes represent sites that want to communicate. Each edge eis a communication link with a given available bandwidth b(e). For each pair of nodes u, v, we want to select a single u-v path P on which the pair will communicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains. The best achievable bottleneck rate for the pair u, v in G is simply the maximum, over all u-v paths P in G, of the values of b(P).
It is very complicated to keep track of a path for each pair of nodes. Thus, we want to find a spanning tree T of G such that for every pair of nodes u, v, the unique u-v path in the tree can attain the best achievable bottleneck rate for u, v in G. Please write a program to construct a spanning tree T in which, for each u, v in V, the bottleneck rate of the u-v path in T is as large as possible among all possible spanning trees.
● Chinese
令 G = (V, E) 為一個圖形代表通訊網路，其中點代表通訊站，而邊代表連結二站的通訊線，每一個邊 e 皆設有一個頻寬 b (e) 表示此通訊線的最高傳輸量。任二點 u , v, 我們可以選擇一條 u -v 路徑 P ，這條路徑的瓶頸 b (P) 定義為這條路徑所有邊中的最小頻寬， u 和 v 的最佳連結路徑為所有 u -v 路徑中具有最大瓶頸的路徑。
對任意二點都紀錄其最佳連結路徑是很複雜的工作，因此我們想要找出一個生成樹，使得 u 和 v 在此生成樹的唯一路徑具有最佳的瓶頸值。請撰寫一個程式找出一個生成樹 T ，使得 T 中的任意 u -v 路徑的瓶頸在所有生成樹中是最佳的 。
● EnglishInput Format
● Chinese
- All the given numbers are integers and there is no sign.
- 每個所給數字皆為整數且無正負符號
● EnglishOutput Format
The first line is an integer which indicates the number of test cases. Each test case contains m+1 lines defining an n-node graph. The first line consists of two integers. The first integer is n, 1 ≤ n ≤ 1000, which is the number of nodes in the graph. The nodes are given by their unique labels which are integers from 0 to n-1. The second integer is m, n ≤ m ≤ n(n-1)/2, which is the number of edges in the graph. For the next m lines, each line consists of three numbers x, y, and b((x,y)) separated by a space indicating the edge (x, y) and the bandwidth of (x,y).
● Chinese
第一列是 一個 整數代表測試資料有幾筆。每一筆測試資料包含 m +1 列定義一個圖形，第一列是二個數字 n 和 m ，第一個數字 n 表示此圖的節點數， 1 ≤ n ≤ 1000 ，每一個節點用一個數字唯一代表， n 個點的編號由 0 到 n -1 ，第二個數字 m 表示此圖的邊數， n ≤ m ≤ n(n-1)/2 ，剩下的 m 列標示此圖的邊，每一列都含三個數字以空白隔開，分別是 x ， y 和 b ((x,y)) 代表一個邊 (x, y) 和它的頻寬 b ((x,y)) 。
● EnglishExample
For each test case, output the sum of each b(e) for e in the spanning tree T in one line.
● Chinese
針對每一筆測試資料，輸出此生成樹所有邊的頻寬和。
Sample Input: Sample Output: 2
5 7
0 1 3
1 2 1
1 3 8
2 3 10
2 4 5
3 4 9
4 0 6
8 12
0 2 9
0 4 4
1 2 3
1 5 6
2 3 5
2 4 8
3 4 3
3 5 7
5 7 4
5 6 1
6 4 3
6 7 433
43
這題是Maximum Spanning Tree的問題，只是他要找的是阻抗值最大的cost，可以使用Kruskal 演算法來完成，判斷cycle的方法是用Disjaint Set。
ITSA 桂冠賽 [Problem B3-易] Unique elements
題目來源 ：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23648
[註]這題是找出數列中唯一出現一次的數，因此可以設一個array，計算數出現的頻率，並將頻率為1的值輸出
[Problem B3-易] Unique elements
成績: 0 / 倒扣: 0.8
Time Limit: 1 second
Problem Description
Problem Description
● EnglishTechnical Specification
Given a sequence of integers, please find the unique elements those occur only once in the sequence.
● Chinese
給定一個整數數列，請找出數列中單獨的元素，也就是只出現一次的整數。
● EnglishInput Format
● Chinese
- The number of integers in the sequence is n, where 1 ≤ n ≤ 1000.
- The integers in the sequence are 32-bit integers.
- 數列中整數的個數為 n ， 1 ≤ n ≤ 1000 。
- 數列中的整數是 32 位元整數。
● EnglishOutput Format
The input contains several test cases. Each test case contains two lines: the first line is an integer n which indicates the number of integers in the sequence; the second line contains a sequence of n integers, and consecutive integers are separated by a blank.
● Chinese
輸入包含若干測資，每筆測資包含兩行資料：第一行是一個整數 n 代表數列中有 n 個整數；第二行則是包含 n 個整數的數列，相鄰整數間以空格隔開。
● EnglishExample
For each test case, output the unique elements in increasing order in one line, and consecutive numbers are separated by a blank. If there is no unique element, output “N/A”.
● Chinese
針對每一筆測試資料，由小至大輸出單獨元素在一行中，相鄰數字間以空格隔開。如果沒有單獨元素，則輸出 “N/A” 。
| Sample Input: | Sample Output: |
| 8 1 1 1 9 9 2 2 2 5 1 2 3 4 5 10 8 7 7 1 0 0 9 2 2 6 | N/A 1 2 3 4 5 1 6 8 9 |
[註]這題是找出數列中唯一出現一次的數，因此可以設一個array，計算數出現的頻率，並將頻率為1的值輸出
ITSA 桂冠賽 [Problem B2-易] 各位數和的排序
題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23647
[Problem B2-易] 各位數和的排序
成績: 0 / 倒扣: 0.8
Time Limit: 1 second
Problem Description
Problem Description
● EnglishTechnical Specification
The digit sum of a number, say 9122, is just the sum of the digits, 9+1+2+2=14.
Given N positive integers, sort these N integers in ascending order of their digit sums. In the case that two integers have the same digit sum, the smaller integer should appear before the larger one. For example, both 3128 and 9122 have the same digit sum (i.e., 14). As 3128 < 9122, 3128 should appear before 9122.
● Chinese
對於任意一個整數 a ，令 a.digitSum 為 a 每個位數的和 (the digit sum of the number a) 。例如 a =9122 ，則 a.digitSum =9+1+2+2=14 。
給你 N 個整數，請依每個整數的 digit sum 由小到大排序這 N 個整數。若兩個整數的 digit sum 是一樣的，那便依整數的值由小到大排序。
舉例而言，令 9122 ， 3128 ，以及 5112 是給定的 3 個整數（即 N =3 ）。 9122.digitSum=14 ， 3128.digitSum=14 ，且 5112.digitSum=9 。所以你要輸出 5112 、 3128 、 9122 。在這個例子中， 3128 的 digit sum 和 9122 的 digit sum 都是 14 ，但因為 3128<9122 ，所以 3128 要排在 9122 的前面。
● EnglishInput Format
● Chinese
- 2 ≤ N ≤ 10
- All the given numbers are positive integers.
- The number of digits in a given number is from 3 to 7.
- The number of test cases is 5.
- 2 ≤ N ≤ 10
- 每個所給數字皆為整數且無正負符號
- 每個數字的位數是 3 到 7
- 共有 5 個測資
● EnglishOutput Format
The first line is an integer which indicates the number of test cases. Each test case consists of two lines.
This first line of a test case is an integer indicates N. The second line of the test case contains N integers delimited by a space.
● Chinese
第一行是一個整數代表測試資料有幾筆。每一筆測試包含了 2 行。
第一行是一個整數，其代表 N 。
第二行包含了 N 個整數，每個整數用空白隔開
● EnglishExample
For each test case, sort N integers based on the rule mentioned in the problem description section. You should separate the output integers by a space.
● Chinese
針對每一筆測試資料，依問題描述一節所說的規則來排序。在排序的串列中，每個整數請以空白隔開。
| Sample Input: | Sample Output: |
| 5 3 9122 3128 5112 4 1725 3821 2011 1428 4 1925 2011 3210 9215 4 4145 1245 1485 1478 7 5584 12635 7894 12365 98453 56487 2134567 | 5112 3128 9122 2011 3821 1428 1725 2011 3210 1925 9215 1245 4145 1485 1478 12365 12635 5584 7894 2134567 98453 56487 |
ITSA 桂冠賽 [Problem B1-易] Square and Cube
題目來源 ：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23646
[Problem B1-易] Square and Cube
成績: 0 / 倒扣: 0.8
Time Limit: 1 second
Problem Description
Problem Description
● EnglishTechnical Specification
Ali is a primary school student and is learning multiplication of integers. He has a homework assignment asking for calculate the squares and cubes of integers. You are asked to write a program to verify the answers of his math homework.
● Chinese
阿里是一位正在學習整數乘法的小學生 。他有一個算整數平方與立方的作業。本題要求你寫一程式來驗證他的答案。
● English
● Chinese
- All the given numbers are integers and there is no sign.
- The range of numbers is from 1 to 100.
- 每個所給數字皆為整數且無正負符號
- 每個數字的大小是 1 到 100
● EnglishOutput Format
The first line is an integer which indicates the number of test cases. Each test case is a number in one line. There are at most 10 cases.
● Chinese
第一行是一個整數代表測試資料有幾筆。每一筆測試資料都給定一個數值。至多有十組測資。
● English
For each test case, output the square and cube of the given number in a line.
● Chinese
針對每一筆測試資料，在一行中輸出給定數值的平方及立方值並以一個空格隔開。
| Sample Input: | Sample Output: |
| 2 4 5 | 16 64 25 125 |
ITSA 37 Problem 4 計算炸彈數
題目來源 ：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22217
[Problem 4] 計算炸彈數
成績: 0 / 倒扣: 0.8
問題描述 ：
模擬踩地雷遊戲，計算出周圍炸彈數量。
輸入一個二維陣列，每一格用 0 與 1 代表是否為炸彈， 0 代表該格不為炸彈， 1 代表該格為炸彈
例如：
上述表格代表
炸彈： (1,1), (1,3),(1,4), (2,1), (3,1), (3,2), (3,4), (4,2), (4,3)
非炸彈： (1,2), (2,2), (2,3), (2,4), (3,3), (4,1), (4,4)
請找出非炸彈的格子中周圍八格有幾顆炸彈。
上述表格 x 的值應為 5
若 x 本身就是代表一顆炸彈，則值應為 0
輸入說明 ：
5
1 0 0 1 1
0 1 0 1 0
1 0 1 0 1
0 0 0 1 0
0 1 1 1 0
5 代表陣列大小 ( 最大為 9 ，最小為 3) ，之後為每一格的值
輸出說明 ：
依序輸出，中間以空白隔開，最後 必須有換行字元 。
範例 ：
模擬踩地雷遊戲，計算出周圍炸彈數量。
輸入一個二維陣列，每一格用 0 與 1 代表是否為炸彈， 0 代表該格不為炸彈， 1 代表該格為炸彈
例如：
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 |
炸彈： (1,1), (1,3),(1,4), (2,1), (3,1), (3,2), (3,4), (4,2), (4,3)
非炸彈： (1,2), (2,2), (2,3), (2,4), (3,3), (4,1), (4,4)
請找出非炸彈的格子中周圍八格有幾顆炸彈。
| 1 | 1 | 0 |
| 0 | x | 1 |
| 1 | 1 | 0 |
若 x 本身就是代表一顆炸彈，則值應為 0
輸入說明 ：
5
1 0 0 1 1
0 1 0 1 0
1 0 1 0 1
0 0 0 1 0
0 1 1 1 0
5 代表陣列大小 ( 最大為 9 ，最小為 3) ，之後為每一格的值
輸出說明 ：
依序輸出，中間以空白隔開，最後 必須有換行字元 。
範例 ：
| 輸入範例 | 輸出範例 |
| 5 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 1 0 | 0 2 3 0 0 3 0 4 0 4 0 3 0 4 0 2 4 5 0 3 1 0 0 0 2 |
解法：
因為炸彈是1 ，因此我們可以先判斷是否為炸彈，若是炸彈則輸出0，其餘的就將它四周的值加起來(因為炸彈是1，所以全加起來就知道數目)。
但邊界問題要小心，可以將測資用1~N存 邊界都設0
這樣就不用判斷邊界了 ^&^
ITSA 37 Problem 3 最佳排程
題目來源 ：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22215
解法 ：先將整串數字存入array內,其中array[0]代表總共可表演時間
再將array[1]~array[i]的數字依小到大排序，並一一用a[0]-a[j]，
若a[0]<a[j]代表時間不夠第j個團體表演 ，則跳出迴圈並輸出答案
[Problem 3] 最佳排程
成績: 0 / 倒扣: 0.8
問題描述 ：
尾牙到了，因經濟不景氣，許多表演團體紛紛表示有意願前來表演餘興節目，員工希望在節目秀場中看到最多的表演，但受限於尾牙派對時間長度，公司必須決定邀請哪些團體來表演。請為公司寫一個程式讀入公司尾牙派對的時間和所有有意願前來表演的團體所需的表演時間，計算出公司最多可邀請多少團體來表演。例如，若公司派對長度為 200 分鐘，各表演團體所需的時間為 :
27 6 50 21 3 14 16 8 42 33 21 9
則最多可排入 11 個團體表演（ 27+6+21+3+14+16+8+42+33+21+9=200 ）。
輸入說明 ：
第一行為一個正整數 N ，代表共有幾家公司。之後接下來有 N 行，每行第一個為正整數 M （ 0 < M < 1000 ），代表該公司的派對時間限制，接下來有數個（不超過 100 個）整數，以 0 結束，代表前來申請的各個表演所需的表演時間。
輸出說明 ：
將每個公司最多可邀請的表演團體數目輸出於一行 ，最後必須有換行字元。
範例 ：
尾牙到了，因經濟不景氣，許多表演團體紛紛表示有意願前來表演餘興節目，員工希望在節目秀場中看到最多的表演，但受限於尾牙派對時間長度，公司必須決定邀請哪些團體來表演。請為公司寫一個程式讀入公司尾牙派對的時間和所有有意願前來表演的團體所需的表演時間，計算出公司最多可邀請多少團體來表演。例如，若公司派對長度為 200 分鐘，各表演團體所需的時間為 :
27 6 50 21 3 14 16 8 42 33 21 9
則最多可排入 11 個團體表演（ 27+6+21+3+14+16+8+42+33+21+9=200 ）。
輸入說明 ：
第一行為一個正整數 N ，代表共有幾家公司。之後接下來有 N 行，每行第一個為正整數 M （ 0 < M < 1000 ），代表該公司的派對時間限制，接下來有數個（不超過 100 個）整數，以 0 結束，代表前來申請的各個表演所需的表演時間。
輸出說明 ：
將每個公司最多可邀請的表演團體數目輸出於一行 ，最後必須有換行字元。
範例 ：
| 輸入範例 | 輸出範例 |
| 3 200 27 6 50 21 3 14 16 8 42 33 21 9 0 70 20 5 3 6 12 8 4 0 30 13 12 10 5 3 6 15 0 | 11 7 4 |
解法 ：先將整串數字存入array內,其中array[0]代表總共可表演時間
再將array[1]~array[i]的數字依小到大排序，並一一用a[0]-a[j]，
若a[0]<a[j]代表時間不夠第j個團體表演 ，則跳出迴圈並輸出答案
ITSA 37 Problem 2 解加密的電話號碼
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22213
[Problem 2] 解加密的電話號碼
成績: 0 / 倒扣: 0.8
問題描述 ：
給定一個 key 值及一連串已經編碼過的整數列，以空白分隔開來，請將其還原成原來的電話號碼。
電話號碼的每一個數字 n 編碼方式說明如下：
Step1. 以亂數 (1~100) 產生一個 key 值 k 。
Step2. 以 (10-n) 結果為 p , 若 p 的值 10 ，則 p = 0 。
Step3. 將 p 的值，轉成數字轉成 ASCII 碼，其值為 a 。
Step4. a + k 的值 c 即為編碼的值，並將編碼的值 c 輸出。
Step5. 重複 Step2~Step4 將電話號碼每一個數字編碼。
ASCII 碼如下所示：
例如：某一電話號碼經過編碼後的整數列為 68 74 77 76 75 7473 72 71 70 ，其 key 值 k = 20 ，則經過解碼後，還原回來的 電話號碼為 0412345678 。
輸入說明 ：
輸入一連串的整數列，以空白分隔。第一個整數代表 key 值，其後為經過編碼後的整數列。
輸出說明 ：
經過解碼後，還原回來的 電話號碼 ， 最後必須有換行字元 。
範例 ：
給定一個 key 值及一連串已經編碼過的整數列，以空白分隔開來，請將其還原成原來的電話號碼。
電話號碼的每一個數字 n 編碼方式說明如下：
Step1. 以亂數 (1~100) 產生一個 key 值 k 。
Step2. 以 (10-n) 結果為 p , 若 p 的值 10 ，則 p = 0 。
Step3. 將 p 的值，轉成數字轉成 ASCII 碼，其值為 a 。
Step4. a + k 的值 c 即為編碼的值，並將編碼的值 c 輸出。
Step5. 重複 Step2~Step4 將電話號碼每一個數字編碼。
ASCII 碼如下所示：
| ASCII 碼 十進位 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
| 數字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
輸入說明 ：
輸入一連串的整數列，以空白分隔。第一個整數代表 key 值，其後為經過編碼後的整數列。
輸出說明 ：
經過解碼後，還原回來的 電話號碼 ， 最後必須有換行字元 。
範例 ：
| 輸入範例 | 輸出範例 |
| 20 68 74 77 76 75 74 73 72 71 70 | 0412345678 |
ITSA 37 Problem 1 計算總和、乘積、差、商和餘數
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22211
[Problem 1] 計算總和、乘積、差、商和餘數
成績: 0 / 倒扣: 0.8
問題描述 ：
撰寫一個程式，要求使用者輸入兩個數字，再從使用者取得這兩個數字，然後印出這兩個數字的總和、乘積、差、商、和餘數。
輸入說明 ：
依序輸入兩個整數，整數範圍不超過 1000 。
輸出說明 ：
輸出總和、乘積、差、商、和餘數(注意格式)，最後必須有換行字元 。
範例 ：
撰寫一個程式，要求使用者輸入兩個數字，再從使用者取得這兩個數字，然後印出這兩個數字的總和、乘積、差、商、和餘數。
輸入說明 ：
依序輸入兩個整數，整數範圍不超過 1000 。
輸出說明 ：
輸出總和、乘積、差、商、和餘數(注意格式)，最後必須有換行字元 。
範例 ：
| 輸入範例 | 輸出範例 |
| 7 3 | 7+3=10 7*3=21 7-3=4 7/3=2...1 |
ITSA 38 Problem 4 迷宮路徑
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?a=11600
作法 : 用stack實作DFS
[Problem 4] 迷宮路徑
成績: 0 / 倒扣: 0.8
問題描述 ：
在一張 n×n 大小的地圖中，座標由上往下由左往右從 0 開始到 n -1 。從起點 (1,1) 到終點 (n-2, n-2) 的路徑，保證只會存在一條路徑，若遇到十字路口判斷時，判斷順序為下、上、左、右，陣列中的值 1 代表牆壁， 0 代表可以通過的點。
輸入說明 ：
第一個數字代表陣列大小 n ( n ≤ 20 ) ，後續資料為地圖配置。
輸出說明 ：
井字 (#) 代表正確路徑，星號 (*) 代表經過但不是正確的路徑，最後 必須有換行字元 。
範例 ：
在一張 n×n 大小的地圖中，座標由上往下由左往右從 0 開始到 n -1 。從起點 (1,1) 到終點 (n-2, n-2) 的路徑，保證只會存在一條路徑，若遇到十字路口判斷時，判斷順序為下、上、左、右，陣列中的值 1 代表牆壁， 0 代表可以通過的點。
輸入說明 ：
第一個數字代表陣列大小 n ( n ≤ 20 ) ，後續資料為地圖配置。
輸出說明 ：
井字 (#) 代表正確路徑，星號 (*) 代表經過但不是正確的路徑，最後 必須有換行字元 。
範例 ：
| 輸入範例 | 輸出範例 |
| 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 # 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 # 1 1 1 1 1 * * * 1 1 1 1 0 0 0 1 1 1 1 # 1 1 1 1 1 * 1 * 1 1 1 1 0 1 0 1 1 1 1 # 1 # # # 1 * 1 * 1 1 1 1 0 1 0 1 1 1 1 # 1 # 1 # 1 * 1 * 1 1 1 1 0 1 0 1 1 1 1 # 1 # 1 # 1 * 1 * 1 1 1 0 0 1 0 1 1 1 1 # 1 # 1 # * * 1 1 1 1 1 1 1 1 0 1 1 1 1 # 1 # 1 # 1 * 1 1 1 1 1 1 1 1 0 1 1 1 1 # 1 # 1 # 1 # # # # # # # # # # 1 1 1 1 # # # 1 # # # 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 # # # # # 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 * 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 # # # # # # # 1 1 1 1 1 1 1 1 1 1 1 1 1 * 1 1 1 * 1 # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
作法 : 用stack實作DFS
2015年7月26日 星期日
ITSA 38 Problem 5 Pseudo Random Generation
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22956
題意 : 給你亂數的seed 尋找第一次出現重複數字x和第一次出現x中間隔了幾個數
做法 : 我先設一個array-> test[]並預設為0 當test[x]為0代表x是第一次出現 設test[x] = sum,記錄她出現的位置 , 因此若test[x]!=0則代表找到第一個cycle(重複的數),並輸出 sum-test[x](他們之間差幾個數)
[Problem 5] Pseudo Random Generation
成績: 0 / 倒扣: 0.8
Problem Description
Random numbers are usually used in computer program. Computer can't produce pure random numbers but can produce pseudo random numbers. There are some pseudo random generators in our program language library which are usually used.
There is a method which is usually used to produce pseudo random numbers. The method is called linear congruential method. This method needs 4 parameters:
The pseudo random numbers are produced by follow program states:
Xn+1 = ( aXn + c ) mod m
For example, if a = 7, c = 5, m =12, and X0 = 4 then the program produces a series of the pseudo random numbers as follow:
In this case, the cycle length of a pseudo random numbers sequence is 6. In other words, the program produces six different pseudo random numbers and the series of the pseudo random numbers will repeat. Theoretically, the cycle length cannot exceed m hat is produced by the method (because mod m).
In this problem, you are given a, c, m, and X0 and asked to computer the cycle length. Note that, the repetition is not necessarily from the first seed. For example, if the pseudo random number sequence is {3, 7, 2, 10, 17, 8, 2, 10, 17, 8, ...} then the cycle length is 4.
Input File Format
In the first line, there is a integer n indicating how many cases. Followed the first line, there are four integers separated by a space in each line. The four integers indicate the numbers of a, c, m and X0 in this order.
Output Format
Output the cycle length of every case line by line.
Example
Random numbers are usually used in computer program. Computer can't produce pure random numbers but can produce pseudo random numbers. There are some pseudo random generators in our program language library which are usually used.
There is a method which is usually used to produce pseudo random numbers. The method is called linear congruential method. This method needs 4 parameters:
| m a c X0 | a modulus a multiplier a addend a initial number(seed number) | m > 0 0 < a < m0 ≤ c < m 0 ≤ X0 < m |
Xn+1 = ( aXn + c ) mod m
For example, if a = 7, c = 5, m =12, and X0 = 4 then the program produces a series of the pseudo random numbers as follow:
| Xn | aXn + c | Xn+ 1 = ( aXn + c ) mod m |
| 4 9 8 1 0 5 | 33 68 61 12 5 40 | 9 8 1 0 5 4 |
In this problem, you are given a, c, m, and X0 and asked to computer the cycle length. Note that, the repetition is not necessarily from the first seed. For example, if the pseudo random number sequence is {3, 7, 2, 10, 17, 8, 2, 10, 17, 8, ...} then the cycle length is 4.
Input File Format
In the first line, there is a integer n indicating how many cases. Followed the first line, there are four integers separated by a space in each line. The four integers indicate the numbers of a, c, m and X0 in this order.
Output Format
Output the cycle length of every case line by line.
Example
| Sample Input: | Sample Output: |
| 2 2179 1839 3279 1511 3561 5353 6219 1234 | 546 345 |
題意 : 給你亂數的seed 尋找第一次出現重複數字x和第一次出現x中間隔了幾個數
做法 : 我先設一個array-> test[]並預設為0 當test[x]為0代表x是第一次出現 設test[x] = sum,記錄她出現的位置 , 因此若test[x]!=0則代表找到第一個cycle(重複的數),並輸出 sum-test[x](他們之間差幾個數)
ITSA 38 Problem 3 糖果分享
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22951
[Problem 3] 糖果分享
成績: 0 / 倒扣: 0.8
問題描述 ：
兒童節前夕，老師把全班同學的座位排成格子狀，並且準備了一袋一袋的糖果要分給小朋友們。老師把一袋一袋的糖果放在某幾個同學的抽屜裡，拿到一袋糖果的同學必須而且只能把糖果分給他前後左右的同學。請寫一個程式幫老師檢查看看，是不是全班的同學都可以拿到糖果呢？
輸入說明 ：
輸入檔中第一行為一個正整數 N ，代表共有幾組測試資料。之後接下來每筆資料的第一行為三個數字 n 、 m 和 L ， 1 ≤ n ≤ 20, 1 ≤ m ≤ 20, 1 ≤ L ≤ 100 ，以空格隔開，表示座位共有 n 行、 m 列以及糖果共有 L 袋，第二行開始每行有 2 個數字 x 和 y ， 以一個空格隔開，共有 L 行，每一組 x 、 y 代表糖果放在第 x 行、第 y 列的抽屜裡。
輸出說明 ：
若全部的同學都可以拿到糖果，則輸出 Y ，否則輸出 N ；每筆測試資料輸出於一行 ，最後必須有換行字元。
範例 ：
兒童節前夕，老師把全班同學的座位排成格子狀，並且準備了一袋一袋的糖果要分給小朋友們。老師把一袋一袋的糖果放在某幾個同學的抽屜裡，拿到一袋糖果的同學必須而且只能把糖果分給他前後左右的同學。請寫一個程式幫老師檢查看看，是不是全班的同學都可以拿到糖果呢？
輸入說明 ：
輸入檔中第一行為一個正整數 N ，代表共有幾組測試資料。之後接下來每筆資料的第一行為三個數字 n 、 m 和 L ， 1 ≤ n ≤ 20, 1 ≤ m ≤ 20, 1 ≤ L ≤ 100 ，以空格隔開，表示座位共有 n 行、 m 列以及糖果共有 L 袋，第二行開始每行有 2 個數字 x 和 y ， 以一個空格隔開，共有 L 行，每一組 x 、 y 代表糖果放在第 x 行、第 y 列的抽屜裡。
輸出說明 ：
若全部的同學都可以拿到糖果，則輸出 Y ，否則輸出 N ；每筆測試資料輸出於一行 ，最後必須有換行字元。
範例 ：
| 輸入範例 | 輸出範例 |
| 3 2 3 1 1 1 4 3 4 1 2 2 2 3 2 4 2 5 4 5 1 3 2 1 3 4 4 1 5 3 | N Y N |
ITSA 38 Problem 2 井字遊戲
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22949
解法 : 先把矩陣存成一維陣列
[Problem 2] 井字遊戲
成績: 0 / 倒扣: 0.8
問題描述 ：
輸入 0 、 1 、 2 代表 * 、 Y 、 X ，直橫斜三個連成一線者為獲勝，無人獲勝則顯示 Tie 。
輸入說明 ：
輸入 0 、 1 、 2 至 3 × 3 的矩陣。
輸出說明 ：
符號轉換 0 、 1 、 2 為 * 、 Y 、 X 並輸出 ( 中間不用隔開，但要換行 ) 。
Y 符號獲勝輸出 Y bingle 、 X 符號獲勝輸出 X bingle ，其他結果輸出 Tie ， 最後必須有換行字元 。
範例 ：
輸入 0 、 1 、 2 代表 * 、 Y 、 X ，直橫斜三個連成一線者為獲勝，無人獲勝則顯示 Tie 。
輸入說明 ：
輸入 0 、 1 、 2 至 3 × 3 的矩陣。
輸出說明 ：
符號轉換 0 、 1 、 2 為 * 、 Y 、 X 並輸出 ( 中間不用隔開，但要換行 ) 。
Y 符號獲勝輸出 Y bingle 、 X 符號獲勝輸出 X bingle ，其他結果輸出 Tie ， 最後必須有換行字元 。
範例 ：
| 輸入範例 | 輸出範例 |
| 1 0 2 2 1 0 0 0 1 | Y*X XY* **Y Y bingle |
解法 : 先把矩陣存成一維陣列
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
然後仔細觀察看看，最後你會發現 ，若可連線，它們的位置後減前會相等
EX : 1-5-9 -> 9-5 = 5-1
1-4-7 -> 7-4 = 4-1
因此我將數字1的位置存入y[]，數字2的存入x[]
判斷並輸出結果
EX : 1-5-9 -> 9-5 = 5-1
1-4-7 -> 7-4 = 4-1
因此我將數字1的位置存入y[]，數字2的存入x[]
判斷並輸出結果
ITSA 38 Problem 1 英哩轉公里
[Problem 1] 英哩轉公里
成績: 0 / 倒扣: 0.8
問題描述 ：
試撰寫一程式，可由鍵盤輸入英哩，程式的輸出為公里，其轉換公式如下：
1 英哩 = 1.6 公里
輸入說明 ：
輸入欲轉換之英哩數 (int < 1000) ，不超過 50 筆。
輸出說明 ：
輸出公里 (double) ，四捨五入取到小數點以下第一位，最後必須有換行字元 。
範例 ：
試撰寫一程式，可由鍵盤輸入英哩，程式的輸出為公里，其轉換公式如下：
1 英哩 = 1.6 公里
輸入說明 ：
輸入欲轉換之英哩數 (int < 1000) ，不超過 50 筆。
輸出說明 ：
輸出公里 (double) ，四捨五入取到小數點以下第一位，最後必須有換行字元 。
範例 ：
| 輸入範例 | 輸出範例 |
| 90 95 | 144.0 152.0 |
2015年7月25日 星期六
ITSA 39 _ 解答
[Problem 1] 3x+1數列產生
[Problem 2] 矩陣分素乘積
題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23834[Problem 3] 爬樓梯
[Problem 4] 文字接龍
[Problem 5] Cable Car Assignment
[Uva 10653 Bombs! NO they are Mines!!]
題目來源 : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1594
題意: 在不採到炸彈的情況下 求最短路徑
方法 : BFS
2015年7月23日 星期四
[Uva 10112 Myacm Triangles]
題目來源 : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1053
題意 : 找出最大三角形面積 而那個三角形 裡面不能有其他點喔~
方法 : 三個點一抓 抓到後再判斷裡面是不是有其他點
[Codeforces Round #308 (Div. 2) D. Vanya and Triangles]
題目來源 : http://codeforces.com/contest/552/problem/D
題意 : 找出所有點共可以圍成多少的三角形
作法 : 用三個迴圈跑 每抓三個點 就計算他們面積是否為0
若為0則代表是 三點共線 因此不是三角形
非0則 ans++
題意 : 找出所有點共可以圍成多少的三角形
作法 : 用三個迴圈跑 每抓三個點 就計算他們面積是否為0
若為0則代表是 三點共線 因此不是三角形
非0則 ans++
2015年7月22日 星期三
[Problem - 456B - Codeforces Fedya and Maths]
题目来源 ： http://codeforces.com/problemset/problem/456/B
题意 ： 求出算式中答案
解法 ： 我一开始先将n都带入算式中看看
有看到规律吗？XD
原来只要n是四的倍数答案就是4
其余都是0
//n有点大 所以用string存比较方便 =）
题意 ： 求出算式中答案
解法 ： 我一开始先将n都带入算式中看看
原来只要n是四的倍数答案就是4
其余都是0
//n有点大 所以用string存比较方便 =）
[Uva 11000 Bee]
题目来源 ： http://7xjob4.com1.z0.glb.clouddn.com/6e44785eb5d7eb3526d096bd83ff4b8e
题意 ： 蜜蜂生产完都会死翘翘 , 但只有最开始的母蜜蜂不会死翘翘 , 母的蜜蜂生公蜜蜂 , 公的蜜蜂生一男一女,
解法 : 所以只要将目前男蜜蜂的数量加上1（不会死的母蜜蜂）就是明年的母蜜蜂数量, 将目前的公蜜蜂数量加上目前母蜜蜂的数量就是明年的公蜜蜂数量
题意 ： 蜜蜂生产完都会死翘翘 , 但只有最开始的母蜜蜂不会死翘翘 , 母的蜜蜂生公蜜蜂 , 公的蜜蜂生一男一女,
解法 : 所以只要将目前男蜜蜂的数量加上1（不会死的母蜜蜂）就是明年的母蜜蜂数量, 将目前的公蜜蜂数量加上目前母蜜蜂的数量就是明年的公蜜蜂数量
[Uva 10104 Euclid Problem]
题目来源 ： http://7xjob4.com1.z0.glb.clouddn.com/b10ac4b75a1ebfce51b98250b2cbcb4c
解法 ： 题目一看大概就知道这题要用到GCD（最大公因数）,因此一定会想到辗转相除法
但系数X Y要怎麽求得呢 ？ 我们先套到公式里面看看
套完大概就发现 可以在GCD递回中顺便求得了
下面附上程式码 ^&^
解法 ： 题目一看大概就知道这题要用到GCD（最大公因数）,因此一定会想到辗转相除法
但系数X Y要怎麽求得呢 ？ 我们先套到公式里面看看
下面附上程式码 ^&^
2015年7月21日 星期二
[Uva 12086 Potentiometers]
題意 : 先輸入一串數字 更新其值 或找出區間和
方法 : fenwick tree
今天上課筆記抄不多>"<
今天上課筆記抄不多>"<
但fenwick tree的重點蠻好懂得
簡單來說就是 先將位置換成二進位
[更新] 最後的1加1
[查詢] 最後的1減1
找最後一個1的方法就是跟其二的補數做AND --> x&(-x)
簡單來說就是 先將位置換成二進位
[更新] 最後的1加1
[查詢] 最後的1減1
找最後一個1的方法就是跟其二的補數做AND --> x&(-x)
[更新] 更a[x+x&(-x)];
[查詢] 查a[x -x&(-x)];
[查詢] 查a[x -x&(-x)];
[Uva 12532 Interval Product]
題意 : 將區段內的數字成積之正負號顯示出來
方法 :
1. Segment Tree 左右邊界真的卡很久~但最後才發現是自己想得太複雜了
2. 利用struct 可以同時將值和左右邊界存進去 蠻簡單的 =)
網上看到一篇富圖解的blog : http://pavelsimo.blogspot.tw/2012/11/uva-12532-interval-product.html
下面附上debug五小時的程式碼-..-
方法 :
1. Segment Tree 左右邊界真的卡很久~但最後才發現是自己想得太複雜了
2. 利用struct 可以同時將值和左右邊界存進去 蠻簡單的 =)
網上看到一篇富圖解的blog : http://pavelsimo.blogspot.tw/2012/11/uva-12532-interval-product.html
下面附上debug五小時的程式碼-..-
2015年7月20日 星期一
[CodeForces 550A Two Substrings]
題目網址 : http://codeforces.com/problemset/problem/550/A
題意 : 是否能在題目給你的string中找到一個AB和BA ， 順序沒差
解法 : 因為ABA或BAB可以同時為AB或BA ， 所以可以有三種case
1. ABA/BAB 配 AB
2. ABA/BAB 配 BA
3. BA 配 AB
[ACM_ICPC 7150 - Amalgamated Artichokes]
題目網址 : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5162
題意 : 給一個合成函式 ，尋找其中最大的下降高度
題意 : 給一個合成函式 ，尋找其中最大的下降高度
注意 : 若跑兩個for迴圈會TLE
最长回文
以前有曾经遇过回文问题 但是怎末写都TLE （哭哭
结果是今天看到的这一篇BLOG交会我的
http://my.oschina.net/pathenon/blog/63575
做法就是以其中一点为中心找出他最大回文的半径
所以像ASDSA
找到以D（str[3])为中心的最大半径是3 然后他后面的S(str[4])位置是4< 3+3(半径）-1 , 因此可以不用重复计算他的回文半径 因为他跟前面那个S（str[2]）是对称的 所以可以直接套用
如果有找到新的最大半径 则要记得更新哦
答案就是最大回文半径*2-1～～
附上code 但因为是看的当参考的 所以应该跟blog上的很雷同
结果是今天看到的这一篇BLOG交会我的
http://my.oschina.net/pathenon/blog/63575
做法就是以其中一点为中心找出他最大回文的半径
所以像ASDSA
找到以D（str[3])为中心的最大半径是3 然后他后面的S(str[4])位置是4< 3+3(半径）-1 , 因此可以不用重复计算他的回文半径 因为他跟前面那个S（str[2]）是对称的 所以可以直接套用
如果有找到新的最大半径 则要记得更新哦
答案就是最大回文半径*2-1～～
附上code 但因为是看的当参考的 所以应该跟blog上的很雷同
2015年7月17日 星期五
[poj 1979 Red and Black]
题目网址 ： http://poj.org/problem?id=1979
这题的题意简单来说就是“找出起点附近最大的连续黑色区块“
因此我利用BFS寻找最多可以走几步的想法来计算它
（不知道这题用DFS会不会比较快>"<
这题的题意简单来说就是“找出起点附近最大的连续黑色区块“
因此我利用BFS寻找最多可以走几步的想法来计算它
（不知道这题用DFS会不会比较快>"<
[Codeforces Round #304 (Div. 2) Soldier and Cards]
题目链接 ： http://codeforces.com/contest/546/problem/C
卡片问题
题目算蛮好懂得 看图大概就可以知道题意
将两堆卡片的最上面拿一张拿起来相比,若A堆上的那一张比B堆小,则将两张卡片由小到大放入B堆的底部 ,若A堆上的那一张比B堆大,则反之.
这题我是直接用queue实作
比较快也比较好懂（虽然还没想到第二种方法的说XD
卡片问题
题目算蛮好懂得 看图大概就可以知道题意
将两堆卡片的最上面拿一张拿起来相比,若A堆上的那一张比B堆小,则将两张卡片由小到大放入B堆的底部 ,若A堆上的那一张比B堆大,则反之.
这题我是直接用queue实作
比较快也比较好懂（虽然还没想到第二种方法的说XD
2015年7月16日 星期四
[Uva1235 - Anti Brute Force Lock]
這題有點懶寫註解XD
方法也是MST
題目問最少密碼轉動次數
可以把每一組密碼都看成一個點
點跟點之間的距離是他們需要旋轉的次數
因為是求MST所以哪一點開始並不重要
但最後要加上"0000"到其中一點的最短距離才會是答案
而點的存法用string 網路上也有人用int 因此是看個人
但array要設夠大(今天不知道為什麼一直RE
轉動次數也要算對 可以往前轉或往後 取最少值
[ex]9->1就要取2不是8
方法也是MST
題目問最少密碼轉動次數
可以把每一組密碼都看成一個點
點跟點之間的距離是他們需要旋轉的次數
因為是求MST所以哪一點開始並不重要
但最後要加上"0000"到其中一點的最短距離才會是答案
而點的存法用string 網路上也有人用int 因此是看個人
但array要設夠大(今天不知道為什麼一直RE
轉動次數也要算對 可以往前轉或往後 取最少值
[ex]9->1就要取2不是8
2015年7月14日 星期二
[Uva 10696 f91]
題目來源 : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1637
作法 : 遞迴
題意 ： 給你兩個函數 用它下去跑遞迴就好 =)
題意 ： 給你兩個函數 用它下去跑遞迴就好 =)
[Uva 11516 WiFi]
方法 : binary search
题意 ： 寻找在题目提供的ap数量下 半径最小值
做法 ： Binary Serach
因为房子一定要被包到 所以可以假设房子刚好被ap覆盖到的情况下之最少距离
因此以房子为準依直径向外扩张 最后题目所求的半径再用所得直径/2即得
题意 ： 寻找在题目提供的ap数量下 半径最小值
做法 ： Binary Serach
因为房子一定要被包到 所以可以假设房子刚好被ap覆盖到的情况下之最少距离
因此以房子为準依直径向外扩张 最后题目所求的半径再用所得直径/2即得
POJ 1989 The Cow Lineup
題意 :
農場主人請"牛"排成一row
想請問最小幾個數形成的數列 不能從牛序列取得子序列(可以不連續取得)
網路上的方法是用Greedy
做法 : Greedy
參考作法 : http://www.acmerblog.com/hdu-2712-the-cow-lineup-4312.html
訂閱：
文章 (Atom)