顯示具有 [程式解題]初心者級 標籤的文章。 顯示所有文章
顯示具有 [程式解題]初心者級 標籤的文章。 顯示所有文章

2024年6月16日 星期日

o077. 2. 電子畫布

題目描述:

有一個 H ╳ W 的電子畫布,一開始數值都是 0 代表未填色,接下來請模擬 N 次畫筆操作。

每次畫筆操作為選一個座標 (r,c) 停留 t 秒,他會將曼哈頓距離 <= t 的區塊染上顏色 x。若有多個顏色重複填到相同區塊,顏色的數值會累加起來。

請輸出 N 次操作後的畫布狀態。


這題簡單來說就是要想個找出距中心點等距的菱形座標。

我思考的方式很簡單,首先找到中心點,並根據該點的資料找出他離他最遠單的Y座標端點。
得到,以下這個迴圈。

for y in range(r-t,r+t+1):

注意一下,菱形的關鍵就是從中心點到任一端點都是等距,所以我們先把中心點座標取這次拿到的Y座標算出差距得到:

ydif = abs(r-y)#ydif就是中心點與這次y座標的差距

已知ydif+xdif=t,現在t跟ydif都是已知,所以xdif = t-abs(ydif),所以就可以得出下面這個迴圈:

for x in range(c-(t-ydif) , c+(t-ydif)+1):

菱形矩陣搞定後,這題就沒有其他問題囉,以下是完整程式。


def t():
    h,w,n = [int(i) for i in input().split()]
    tt = [[0 for i in range(w)] for j in range(h)]
    
    
    for j in range(n):
        r,c,t,q = [int(i) for i in input().split()]
        for y in range(r-t,r+t+1):
            if y < 0 or y > h-1: 
                continue
            ydif = abs(r-y)
            for x in range(c-(t-ydif) , c+(t-ydif)+1):
                if x < 0 or x > w-1:
                    continue
                tt[y][x] += q
    for i in tt:
        for j in i:
           print(j , end = ' ')
        print()
t()

o076. 1. 特技表演

有一個城鎮有 n 棟高樓,樓高分別為 h1,h2,.....hn,市長想要在城鎮中心舉辦高空特技表演,該特技表演會從某棟大樓上朝右側滑翔至地面。

為了表演人員的安全,滑翔的路徑樓高必須越來越低,請你找出一個最長的滑翔路徑。

簡單來說就是要從資料中找出最長的降冪集合,這題沒什麼時間問題,直接透過迴圈查找

def t():

    n = int(input())

    d = [int(i) for i in input().split()]

    c = 0

    k = 9999999999

    ans = 0

    for i in d:

        if i < k:

            c += 1

        else:

            if ans < c:

                ans = c

            c = 1

        k = i

    if ans < c:

        ans = c

    print(ans)


t()

2024年1月15日 星期一

h206. 強者就是要戰,但......什麼才是強者呢?

         這題是很好的遞迴問題,每次遞迴的時候都要帶入此次遞迴的左右邊界、及這次是要取區間最大還是取區間最小的flag。

        完整程式如下:

def t(l , r , isBig):
    if l == r-1:
        return d[l]
    m = (l+r)//2
    if isBig: 
        g = max(t(l,m,0) , t(m,r,0))
    else:
        g = min(t(l,m,1) , t(m,r,1))
    return g
        
n = int(input())
d = [int(i) for i in input().split()]

print(t(0,n,1))

h631. 美麗人生

         白話來說,就是把測資去掉所有2、3、5的因數後,如果只剩下1,就顯示ugly,反之顯示beautiful,這邊就運用while來重複檢測輸入是否尚能被2、3、5整除,如果可以就將其整除後再檢查一次,直到不能在除2、3、5為止。

        程式碼如下:

def t():
    n = int(input())
    while n % 2 == 0:
        n //= 2
    while n % 3 == 0:
        n //= 3
    while n % 5 == 0:
        n //= 5
    if n == 1:
        print('ugly')
    else:
        print('beautiful')
        
t()

2024年1月12日 星期五

e315. NOIP2017 1.成绩

         三個輸入乘以固定的比率,算出最終答案,如果是使用python要小心浮點數運算預設是帶小數的資料,記得要取整數。

        以下附上完整程式:

try:
    while True:
        p,n,m = [int(i) for i in input().split()]
        print(int(p*0.2+n*0.3+m*0.5))
except:
    pass

APCS 2024.01 m931. 1. 遊戲選角

         考試中常常用到排序,只是往往不會只是單純排序,有些時候,會需要在排序的資料裡面,添加一些不必要排序的資料,就像這題,表面是針對戰鬥力排名,但輸出的時候是要輸出攻擊力與防禦力,所以基本上的做法就是依序將[戰鬥力、攻擊力、防禦力]當成一筆資料塞入陣列之中,透過sort指令,因為系統預設的sort指令會先依第一個欄位排序,如果第一個欄位相同就繼續比第二個,以此類推。

        完整程式如下:

n = int(input())
p = []
for i in range(n):
    q,m = [int(i) for i in input().split()]
    p.append([q**2 + m**2 , q , m])
p.sort()

print(p[-2][1] , p[-2][2])

2024年1月11日 星期四

f327. 刪除欄位

         這題就是單純的16進制轉換題,如果同樣的題目,是十進制出題,那是絕對的送分題,以十進制來看,假設收到三個char(a,b,c)需要我們將它組成一個百位數數字,那麼程式作法拆解下來就是total = a - char(0) ,再來是total = total * 10 + b - char(0) ,最後是total = total * 10 + c - char(0) ,數學式子去理解就是total = a * 100 + b * 10 + c,那麼將同樣概念運用在這題就沒問題了。

        以下附上完整程式:

d = input().split()

ft,st = 0,0
f,s = d
for i in range(len(f)):
    ft = ft * 26 +  (ord(f[i]) - ord('A')+1) 
for i in range(len(s)):
    st = st * 26 +  (ord(s[i]) - ord('A')+1) 
print(st - ft + 1)

2024年1月9日 星期二

k740. 楊輝三角形

        這題是標準的DP問題,扣除每一行的頭跟尾(都是1),每一行的資料都是由上一行的正上方與左上方提供。

        以下附上完整程式碼:

n = int(input())
d = [[1 for i in range(21)] for j in range(21)]

for i in range(1,n+1):
    for j in range(i):
        if j != 0 and j != i-1:
            d[i][j] = d[i-1][j] + d[i-1][j-1]
        print(d[i][j] , end = ' ')
    print()

k862. 輩份比較

        假設B,C是A的祖先,D,E是A的子孫,F是E的子孫,如果我們先忽略輩分這件事情,單純從A點走到F,那就是一個單純的BFS就可以解決的事情,只要在BFS的基礎上,讓每個節點記錄自己的父輩與子孫輩的成員即可。





下列附上程式碼:


class Node:
    def __init__(self):
        self.father = []
        self.child = []
        self.dis = -99999999


s = set()
n = int(input())
d = {}
for i in range(n):
    c,f = input().split()
    if c not in d:
        d[c] = Node()
    if f not in d:
        d[f] = Node()
    d[c].father.append(f)
    d[f].child.append(c)
    
start,target = input().split()

d[start].dis = 0
p = [start]
keep = True
while keep:
    for i in p:
        for j in d[i].father:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis-1
                p.append(j)
                if j == target:
                    keep = False
                    break
        for j in d[i].child:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis+1
                p.append(j)
                if j == target:
                    keep = False
                    break
        if keep == False: break
print(d[target].dis)

2024年1月8日 星期一

m685. 三角形計數器

         辨別三角形相同的方式有很多,我們選其中一個方式來解題,假設兩個三角形,各三個邊由小到大分別是a,b,c  及  a1,b1,c1,如果a/b==a1/b1 and b/c == b1/c1 and c/a == c1/a1,那麼這兩個三角形及為相似三角形,最後用上set來濾掉重複的三角形即可。

n = int(input())
s = set()
for i in range(n):
    d = [int(i) for i in input().split()]
    d.sort()
    s.add(str(d[0]/d[1]) + str(d[1]/d[2]) + str(d[2]/d[0]))
print(len(s))

m702. 傑出校友票選活動

         題目要比對各個人名出現的次數,因為人名是字串,不方便直接用陣列做排序與索引,所以可以先放到map裡面去計次,記完之後再放回vector裡做排序即可。

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    map<string , int> t;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        t[s] += 1;
    }
    vector<pair<int , string>> v;
    for(auto it=t.begin(); it != t.end(); it++) {
        pair<int,string> p;
        p.first = it->second;
        p.second = it->first;
        v.push_back(p);
    }
    sort(v.begin() , v.end());
    for(int i = 0; i < m; i++) {
        cout << v[v.size()-1-i].second << " ";
    }
    cout << endl;

    return 0;
}

l960. 星期幾?

         題目明確給定正確的資料,將其放入清單中,再收取測資作比對即可。

h = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']
s = input()
if s not in h:
    print('error')
else:
    print(h.index(s))

APCS 2024.01 m932. 2. 蜜蜂觀察

         按照慣例,APCS的第二題就是考二維陣列的運用,特別是邊界的判別。解這題的時候如果你可以畫個圖,或是心中畫個圖的畫就會簡單許多。

        現實的資料


        但我們收到清單後,資料長成這樣s = ['TyuI','ABaB']。舉個例子,起點從A開始,假設先往右上走,從上圖來說會走到T,但從清單中的結構來說,位置只是往上跑而已,依照這樣的邏輯,依序將,六個方向對應到清單的變化整理出來,這題就沒有問題了。以下附上完整程式:

m,n,k = [int(i) for i in input().split()]
s = []
for i in range(m):
    s.append(input())
step = [int(i) for i in input().split()]

table = [[-1,0],[0,1],[1,1],[1,0],[0,-1],[-1,-1]]
x,y = 0,m-1

sets = set()
ans = ''
for i in step:
    yy,xx = table[i]
    if xx+x < 0 or xx+x >= n or yy+y < 0 or yy+y >= m: 
        ans += s[y][x]
        sets.add(s[y][x])
        continue
    y,x = yy+y,xx+x
    ans += s[y][x]
    sets.add(s[y][x])
print(ans)
print(len(sets))

        有問題歡迎留言,或email與我討論。





2020年12月28日 星期一

e531: 10415 - Eb Alto Saxophone Player

UVA 10415

CPE 2020/12/22考題

解題心得:

每個音階都有對應的指法,如果欲彈奏下一個音階須按下的手指與上一個重複,則不用額外計算。

1.建立MAP來儲存每個音階要按的手指

2.建立一個狀態表(陣列)來儲存每個手指當前狀態(0沒按1按),在建立一個記數表來記錄每個手指按下幾次。

3.每次讀到下一個音階時先去狀態表查閱當前手指狀態,如果該按而還沒按則按下(記數+1)。

4.依據MAP的資料把該放開的手指放開(狀態表)。


程式碼如下:

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    map<char , vector<int>> mc;
    mc['c'] = {0,0,1,1,1,0,0,1,1,1,1};
    mc['d'] = {0,0,1,1,1,0,0,1,1,1,0};
    mc['e'] = {0,0,1,1,1,0,0,1,1,0,0};
    mc['f'] = {0,0,1,1,1,0,0,1,0,0,0};
    mc['g'] = {0,0,1,1,1,0,0,0,0,0,0};
    mc['a'] = {0,0,1,1,0,0,0,0,0,0,0};
    mc['b'] = {0,0,1,0,0,0,0,0,0,0,0};
    mc['C'] = {0,0,0,1,0,0,0,0,0,0,0};
    mc['D'] = {0,1,1,1,1,0,0,1,1,1,0};
    mc['E'] = {0,1,1,1,1,0,0,1,1,0,0};
    mc['F'] = {0,1,1,1,1,0,0,1,0,0,0};
    mc['G'] = {0,1,1,1,1,0,0,0,0,0,0};
    mc['A'] = {0,1,1,1,0,0,0,0,0,0,0};
    mc['B'] = {0,1,1,0,0,0,0,0,0,0,0};
    int t;
    cin >> t;
    string s;
    getline(cin , s);
    while(t--){
        int finger[11] = {0};
        int fingerCount[11] = {0};
        getline(cin , s);
        for(int i = 0; i < s.length(); i++){
            if(mc.count(s[i]) == 0) continue;
            for(int j = 1; j < 11; j++) {
                if(mc[s[i]][j] == 1) {
                    if(finger[j] == 0) {
                        fingerCount[j]++;
                        finger[j] = 1;
                    }
                }
            }
            for(int k = 0; k <11; k++){
                finger[k] = mc[s[i]][k];
            }
        }
        
        for(int i = 1; i < 11 ;i++){
            cout << fingerCount[i] <<" ";
        }
        cout << "\n";
    }
    
    return 0;
}

2020年10月30日 星期五

b127: 會議中心(Room)

 題目來源:https://zerojudge.tw/ShowProblem?problemid=b127

技巧:費式數列

題目老實說,看文字有點複雜😂😂😂😂😂😂😂,但仔細觀察圖面,不難發現其實是費式數列,這也是解題的一些心得,每當拿到一個新的題目,最快讓你了解題意的通常不會是題目敘述,多觀察輸出輸入,或是圖形化示例。


以下附上程式碼:

#include <iostream>
using namespace std;


int main() {
  cin.tie(0),cin.sync_with_stdio(0);
  int n = 0;
  int arr[46];
  arr[0] = 0;
  arr[1] = 1;
  arr[2] = 2;
  for(int i = 3; i < 46; i++) {
    arr[i] = arr[i-1] + arr[i-2];
  }
  int i;
  while(cin >> i) {
    cout << arr[i] << "\n";
  }
}

2020年10月29日 星期四

d411: 算了好久......

 題目來源:https://zerojudge.tw/ShowProblem?problemid=d411

技巧:大數運算


這題要注意的是,M值高達10^9999,這必然沒辦法用基本的數字運算來處理。



以下附上程式碼:

#include <iostream>
#include<string>
#include <math.h>
using namespace std;

int n;
void mod(string num , int m) {
  int check = 0;
  for(int i = 0; i < num.length(); i++) {
    check *= 10;
    check += num[i] - '0';
    check = check % m;
  }
  if(check == 0) {
    cout <<"YA!!終於算出"+num+"可被2的" + to_string(n)+"次整除了!!\n";
  }  else {
    cout << "可惡!!算了這麼久"+num+"竟然無法被2的"+to_string(n) + "次整除\n";
  }
  
}

int main() {
  cin.tie(0),cin.sync_with_stdio(0);
  int m;
  string num;
  while(cin >> num >> n) {
    m = pow(2 , n);
    mod(num , m);
  }
}


d356: NOIP2002 1.級數求和

 題目來源:https://zerojudge.tw/ShowProblem?problemid=d356


已知:Sn= 1+1/2+1/3+…+1/n,求給定任意K直,找出SN>K時,N為何


範例輸入       

1     

範例輸出

2


簡易程式碼如下:

#include <iostream>
using namespace std;
int main() {
  cin.tie(0),cin.sync_with_stdio(0);
  double b = 1,c = 1,a = 1;
  cin >> a;
  while(b <= a) {
    c+=1;
    b += 1/c;
  }
  cout << c << "\n";
}

2020年10月20日 星期二

f313: 2. 人口遷移 APCS 2020.10.17

https://zerojudge.tw/ShowProblem?problemid=f313

APCS 2020.10.17

這題比較要注意的是,先遷徙,再加總,如果邊遷徙邊作加總會算錯的唷,這題測資很善良的讓你知道邊遷邊加是錯的,如果是我就不會這麼善良了^.^。




 





解題程式碼如下:

如果有任何問題歡迎留言或來信討論。

import sys
a = []
r,c,k,m = tuple([int(i) for i in input().split()])

for i in range(r):
  a.append([int(j) for j in input().split()])
for i in range(m):
  b = [[0 for _ in range(c)] for _ in range(r)]
  for j in range(r):
    for l in range(c):
      if a[j][l] != -1:
        temp = int(a[j][l] / k)
        if j-1 >= 0 and a[j-1][l] != -1:
          b[j][l] -= temp
          b[j-1][l] += temp
        if j+1 < r and a[j+1][l] != -1:
          b[j][l] -= temp
          b[j+1][l] += temp
        if l-1 >= 0 and a[j][l-1] != -1:
          b[j][l] -= temp
          b[j][l-1] += temp
        if l+1 < c and a[j][l+1] != -1:
          b[j][l] -= temp
          b[j][l+1] += temp
  for j in range(r):
    for l in range(c):
      if a[j][l] == -1: continue
      a[j][l] += b[j][l]


maxI = -1
minI = sys.maxsize
for i in range(r):
  for j in range(c):
    if a[i][j] == -1: continue
    if a[i][j] > maxI:
      maxI = a[i][j]
    if a[i][j] < minI:
      minI = a[i][j]

print(minI)
print(maxI)

f312. 1.人力分配 APCS 2020.10.17

APCS 2020.10.17第一題的題目:
其實近幾年題目的第一題考驗的都不是程式能力,而是閱讀能力,基本上第一題所需要用到的就是基本條件式與迴圈的結合,只要讀懂題意,相信都是可以做出來的。
題目就如上面所說,A1 A2 B1 B2 C1 C2由測資提供,X2跟X1則依據題目所提供的總人數有所變化,以總人數2人為例,則兩間工廠的人數有[0,2] , [1,1] , [2,0]這三種組合。


解題程式如下:

如果有不清楚的歡迎留言或直接寄信給我討論囉。

import sys
a,b,c = tuple([int(i) for i in input().split()])
a1,b1,c1 = tuple([int(i) for i in input().split()])
n = int(input())
maxValue = -1 * sys.maxsize
for i in range(n+1):
  y = a * i*i + b * i + c + a1*(n-i)*(n-i) + b1 * (n-i) + c1
  if y > maxValue:
    maxValue = y

print(maxValue)


2020年9月19日 星期六

e621: 1. 免費停車 (Free Parking)

題目來源:https://toi-reg.csie.ntnu.edu.tw/question/201910/B1-FreeParking.pdf

線上檢驗:https://zerojudge.tw/ShowProblem?problemid=e621


求範圍區間內,不能被指定數字整除的數字,

要注意的是開頭跟結尾兩個數字都不能算進來。


程式碼如下:

有問題歡迎留言或傳訊討論。

n = int(input())
while n > 0:
  n -= 1
  ans = ""
  s,e,d = tuple([int(i) for i in input().split()])
  for i in range(s+1 , e):
    if i % d != 0:
      ans += str(i) + " "
  if ans != "":
    print(ans)
  else: 

print("No free parking spaces.") 

o079. 4. 最佳選擇

 題目描述: 給一個長度為 n 的正整數序列 a1,a2...an ,你可以執行多次操作 (包含 0 次),每次操作只能選擇這個序列的第一個或最後一個數字,再將這個數字從序列中刪除並自己搜集起來。 求滿足總和不超過 k 且搜集的數字奇數和偶數個數相同的條件下,所能搜集的數字總和最...