[109-cpi] HW4 - HackMD

--- tags: homework, 109, cpi title: '[109-cpi] HW4' --- # Homework 4 > Week 5 (10/12), Due: 10/19 09:00:00 * 範圍：Loop * NOJ --- ## Print a Repeated Pattern > [name=Judge Girl] ### Description 請寫一個程式，讀入正整數 $n$\ 接著會劃分為 $n$ phases\ 第 $i-th$ phases 由正整數序列 $1$ 至 $i$ 所構成 ### Input 一行輸入，包含一正整數 $n$ ### Output 一行輸出，將每個phases輸出並換行 ### Example Input \#1 5 ### Example Output \#1 112123123412345 ### Example Input \#2 8 ### Example Output \#2 112123123412345123456123456712345678 ### Hint * 利用迴圈即可 * 原題連結請見[Link](https://judgegirl.csie.org/problem/0/13) --- ## Three Circles > [name=Judge Girl] ### Description You are given three circles, $C_1$, $C_2$, and $C_3$. The center of $C_1$ is at $(x_1,y_1)$, and its radius is $r_1$. The centers and radius of $C_2$ and $C_3$ are defined similarly. A point $(x,y)$ is within a circle if its distance is less than or equal to the radius of the circle. For example, Both $(1,0)$ and $(0,0)$ are within the circle that centered at $(0,0)$ and has radius $1$. Now given the centers and radius of the three circles, please find the number of points $(x,y)$ where both $x$, and $y$ are integers, that are within odd number of circles. Note that the circles can overlap arbitrarily, however, the radius is no more than $10$. As a result you must be careful about how to test points, so that your program will run fast, and without doing unnecessary testing. 給定三個圓圈 $C_1$, $C_2$ 和 $C_3$。其中 $C_1$ 以 $(x_1,y_1)$ 為圓心、$r_1$ 為半徑。$C_2$ 和 $C_3$ 的圓心與半徑定義與 $C_1$ 類似。當一個點 $(x,y)$ 至圓心的距離小於或等於半徑時，我們可以說這個點位於圓內。例如，$(1,0)$ 和 $(0,0)$ 位於一個以 $(0,0)$ 為圓心、$1$ 為半徑的圓內。現在給定三個圓的圓心與半徑，請找到有多少個格子點位於奇數個圓內。圓與圓之間可以任意重疊，並且圓的半徑不會大於 $10$。注意測試格子點的方法，使得你的程式能夠跑得足夠快、避免做一些不必要的測試。 ### Input The first line of the input is the number of input cases. Each input case has three lines and each line has the $x$, $y$, coordinates of a circle, followed by the radius. The radius is no more than $10$. 第一行輸入一個整數，代表接下來將會有幾組的測試。對於每一組的測試，將會輸入三行。每一行包含三個整數 $x, y, r$，分別代表圓心 $(x, y)$ 以及半徑 $r$。 - $r \le 10$ ### Output 對於每一組測試，輸出有多少個格子點位於奇數個圓內。 ### Example Input ``` 2 0 0 1 0 0 2 2 0 1 0 0 1 1000000 0 1 0 1000000 1 ``` ### Example Output ``` 11 15 ``` ### Hint 格子點 $(x, y)$ 是當 $x$、$y$ 皆是整數的點。 ### Subtask --- ## 心跳！戀愛占卜 > [name=博傑] ### Description 奉心祭，秀知院學園在每年的寒假之前所舉辦的文化祭，是學校裡非常重要的活動之一，今年經過會長的努力爭取，變成了為期兩天的大型活動，全校上下無不熱火朝天的迎接這個年度盛事，當然，大家的亂源 --- 書記也不例外。關於奉心祭，在學校內一直流傳個一個傳說，只要在這天送出心型的禮物，就可以得到永恆的愛情，而自詡為戀愛偵探的書記，自然也要在這天參一腳，她決定要在奉心祭擺一個攤位 --- 戀愛占卜！書記她占卜的步驟如下 1. 首先，她會準備一條長 1 公尺($10^9$ 奈米)的透明膠帶，並且我們以一個整數來描述膠帶上的位置，$p$ 代表的是距離膠帶最左邊 $p$ 奈米遠的位置 1. 然後來占卜的客人會隨機挑選兩個數字 $p_1, q_1$，書記也會隨機挑選兩個數字 $p_2, q_2$ 2. 將 $[p_1, p_2], [q_1, q_2]$ 這兩個區間塗上紅色 1. 書記接下來會在心中選定一個數字 $n$，並在接下執行 $n$ 次的摺膠帶操作 1. 每次摺膠帶時，她會隨機挑選一個座標 $x$，以它為中心點，由左向右摺，並且更新膠帶上的座標，原本座標為 $p$ 的位置，在對摺過後會變成 $|p - x|$ 1. 執行完 $n$ 次操作之後，如果紅色的長度她看得順眼的話，那麼她就會為客人送上一個心型吊飾祝福他的愛情然而，要計算這麼複雜的數學對於 IQ 只有 3 的書記來說實在是太困難了，現在請你寫個程式幫幫書記，算出最後的紅色區域覆蓋長度。 ### Input 第一行為四個以空白隔開之正整數 $p_1, q_1, p_2, q_2$ 第二行為一個正整數 $n$ 接下來 $n$ 行，每行皆為一個整數 $x$ #### Limits $0 \le p_1 < p_2 < q_1 < q_2 \le 10^9$ $1 \le n \le 10^5$ $0 \le x \le 10^9$ ### Output 請輸出一個整數於一行，代表最後的紅色覆蓋長度 ### Example Input ``` 0 10 5 15 1 0 ``` ### Example Output ``` 10 ``` ### Example Input ``` 1 3 2 4 1 2 ``` ### Example Output ``` 1 ``` ### Example Input ``` 0 110 100 120 3 60 10 10 ``` ### Example Output ``` 40 ``` ### Hint 1. 改編自 TOPC 2020, pB 1. 最後書記因為沒辦法以奈米為單位來摺膠帶而沒有擺成，可喜可賀。 #### 第一組範例測資這組範測給定了兩個線段 $[0, 5]$ 和 $[10, 15]$，兩者長度皆為 $5$，並且後續摺膠帶的位置是 $0$，並沒有影響到兩個紅色線段，所以答案會是 $5 + 5 = 10$ #### 第二組範例測資這組的線段分別是 $[1, 2]$ 和 $[3, 4]$，並且摺在 $2$ 這個位置上，所以兩個線段的座標都被更新成了 $[0, 1]$，最後覆蓋長度為 $1$ ### Subtask | Case | Describe | Per. | |:--------- |:------------ | ----:| | #1 | $n=1$, $x=0$ | 10% | | #2 | 所有 $x=1$ | 50% | | #3 | 無特殊限制 | 40% | | **Total** | | 100% | --- ## HS Value > 感覺出 digit 還是比較經典\ > 資結 => matrix感覺會被罵XD > [name=育辰] ### Description 阿弘上課時，一心覺得無趣，看著窗外發呆...在腦海中他定義了 $\text{Happy value}$ & $\text{Sad value}$，合稱為 $\text{HS Value}$。 \ \ 是這樣的，今給定一組 $\text{Type}, \ \text{Integer}$, 若型態為 $1$，則為 $\text{Happy value}$, 型態為 $2$，則為 $\text{Sad value}$。 \ \ 假使 $\text{Integer}$ 給定為 $2458$, $\ \text{Happy value}$ 計算則由 $2$ 開始乘以 $1$，加上 $4$ 乘以 $2$...每加一位數，乘的基數就會增加 $1$，因此 $2458$ 的 $\text{Happy value}$ 為$$2 \times 1 + 4 \times 2 + 5 \times 3 + 8 \times 4 = 57$$ \ 而 $\text{Sad value}$ 則是從個位數開始，與以上計算相同，因此 $2458$ 的 $\text{Sad value}$ 為$$8 \times 1 + 5 \times 2 + 4 \times 3 + 2 \times 4 = 38$$ \ $\text{HS value}$ 則為 $\text{Happy value}$ 以及 $\text{Sad value}$ 的「差」，換句話說就是在一維數線上的「距離」，例如上題，則其 $\text{HS value}$ 為 $$|57-38|=19$$\ **正式定義如下：**\ 假定將第 $i$ 位數之數值，定為 $\text{digit}_i$, 則： $$\text{Happy value} = \sum_{i=1}^n{(\text{digit}_i \times (n-i+1))}$$ $$\text{Sad value}= \sum_{i=1}^n{(\text{digit}_i \times i)}$$ $$\text{HS value} = | \, \text{Happy value} - \text{Sad value} \, |$$ ### 測資說明起初給定一整數 $n$，表示接著有 $n$ 筆資料，接著每行會有一整數 $a_i$，對於每筆資料： * 在該行輸出兩個數值，以一格空格分開，注意**行末沒有空格**，先輸出 $\text{Happy value}$ 再輸出 $\text{Sad value}$ * 隔一行輸出一個整數 $\text{HS value}$，因此，輸出總共應該會有 $2n$ 行 ### Input Line $1$: 一整數 $n$，表示接著有 $n$ 筆輸入資料\ Line $2$ ~ $(n+1)$: 一整數 $a_i$ ### Limit * $1 \leq n \leq 4.5 \times 10^6, \ n \in \mathbb{N}$ * $0 \leq a_i \leq 2^{31}-1, \ a_i \in \mathbb{N}$ * Output的答案不會超出 $2^{31}-1$ ### Output * 針對輸入的每筆資料，先以一行輸出 $\text{Happy value}$ 以及 $\text{Sad value}$，請以空格隔開，行末**沒有空格** * 接著，隔行輸出 $\text{HS value}$ ### Example Input 0 1 2458 ### Example Output 0 57 38 19 ### Example Input 1 4 54321 12345 0 86355231 ### Example Output 1 35 55 20 55 35 20 0 0 0 115 182 67 ### Hint * 拿出紙筆模擬，並標明每次跑的位置，從中觀察規律去設計迴圈 * 注意 Happy value & Sad value是同行以空格隔開，VS value則在隔行輸出 * 範例測資1中 `54321`： 1. `Happy value` $$=5 \times 1 + 4 \times 2 + 3 \times 3 + 2 \times 4 + 1 \times 5$$ $$= 5 + 8 + 9 + 8 + 5$$ $$=35$$ 2. `Sad value` $$=5 \times 5 + 4 \times 4 + 3 \times 3 + 2 \times 2 + 1 \times 1$$ $$= 25 + 16 + 9 + 4 + 1$$ $$= 55$$ 3. `HS value` $$=| \ 35 - 55 \ | = 20$$ * 範例測資1中 `86355231` 1. `Happy value` $$=8 \times 1 + 6 \times 2 + 3 \times 3 + 5 \times 4 + 5 \times 5 + 2 \times 6 + 3 \times 7 + 1 \times 8$$ $$=8+12+9+20+25+12+21+8$$ $$=115$$ 2. `Sad value` $$=8 \times 8 + 6 \times 7 + 3 \times 6 + 5 \times 5 + 5 \times 4 + 2 \times 3 + 3 \times 2 + 1 \times 1$$ $$=64+42+18+25+20+6+6+1$$ $$=182$$ 3. `HS value` $$=| \ 115 - 182 \ | = 67$$ ### Subtask |Case|Describe|Per.| |:--|:--|--:| |#1|$n=1$, $a_i \neq 0$|30%| |#2|無特殊限制|70%| |**Total**||100%| > 該題切入點，百年不變的經典，給定一個數字將其digit全部相加，當然要把題目改難一點，在計算digit的同時需要做額外的處理，這題難度還是不高，但就上週情況看感覺這題AC率猜測會在33% ### [測資載點](https://drive.google.com/file/d/1YY_AfnHWx_yXVL2ALOhSpb8EICNwQtxc/view?usp=sharing) --- ## 大小姐的放學路 > [name=映達] ### Description 放學後學生們皆已離校，學生會室裡也只剩下會長和大小姐。平時的話，大小姐上下學都有專人接送；今天不湊巧，大小姐的手機因為沒電而關機，無法聯絡司機來接她。一切都看在眼裡的會長，決定護送大小姐走路回家。此時正逢小雪，銀白色中只有兩人的身影，悄然散落的雪花使得整條街格外寧靜。在這樣的時空裡，會長和大小姐必須透過聊天才能免於尷尬。聰明機靈的他們，此時卻因為害羞和緊張，需要間隔一段路程才能找到話題。更嚴重的是，因為變得反應遲緩，兩人皆成為了句點王！好不容易開啟的話題，總會神奇地在三步路以內被結束。聊天的過程中（雖然話題過於短暫）有一種情況特別讓人心跳加速。「四宮（大小姐）啊⋯⋯」「會長啊⋯⋯」。沒錯！就是當男女同時開口的時候！當兩人同時開口時，總是會頓時語塞，並產生「啊，這個人跟我好有默契啊」的想法（錯覺），不由地心頭一緊、小鹿亂撞。假設從「校門口」至「大小姐家大門」的距離為 $m$、「兩人目前的位置」至「校門口」的距離為 $x$。每當 $m$ 可以被 $x$ 整除時，會長便會想到一個新的話題，並且開口：「四宮啊⋯⋯」；每當 $x$ 為質數時，大小姐便會想到一個新的話題，並且開口：「會長啊⋯⋯」。每一個話題（因為很短暫）保證都會在其中一人想到新話題前結束、同時開口的情況只會在開啟新話題時發生。請你計算一路上總共會出現幾次，兩人因為同時開口導致的心動時刻（最後一次同時開口有可能發生在大小姐家的大門口）。 ### Input 輸入一個整數 $m$，代表從「校門口」至「大小姐家大門」的距離（先不管距離的單位是什麼，或這個距離合不合理）。對於所有輸入： - $2 \le m \le 10^8$ ### Output 輸出一個整數，代表一路上總共會出現幾次，兩人同時開口的心動時刻。 ### Example Input 0 ``` 88318230 ``` ### Example Output 0 ``` 8 ``` ### Example Input 1 ``` 99999989 ``` ### Example Output 1 ``` 1 ``` ### Hint