---
# System prepended metadata

title: ' 2023 高二第一次上機考題解'
tags: [上機考題解, C++, Python]

---

# 第一題 [物競天擇](https://zerojudge.tw/ShowProblem?problemid=f818)
python
```py=
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=[]
for i in range(n):
  c.append(a[i]*b[i])
min=100000000
z=0
for i in range(n):
  if(c[i]<min):
    min=c[i]
    z=i
print(a[z],end=' ')
print(b[z])
```
C++
```cpp=
#include <bits/stdc++.h>
#define a6isweak  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
signed main()
{
    int n;
    cin>>n;
    int a[n],b[n],c[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n;i++)
        c[i]=a[i]*b[i];
    int mins=INT_MAX,z;
    for(int i=0;i<n;i++)
     {
         if(mins>c[i])
         {
             mins=c[i];
             z=i;
         }
     }
    cout<<a[z]<<' '<<b[z]<<endl;
}
```
# 第二題 括號匹配
python
```py=
n=int(input())
z=0
for z in range(0,n):
    s=input()
    sk=[]
    bl = True
    i=0
    for i in range(0,len(s)):
        if s[i]=='[' or s[i]=='(' or s[i]=='<' or s[i]=='{':
            sk.append(s[i])
        if(s[i]==']'):
            if(len(sk)==0 or sk.pop()!="["):
                bl = False
                break
        if(s[i]==')'):
            if(len(sk)==0 or sk.pop()!="("):
                bl = False
                break
        if(s[i]=='>'):
            if(len(sk)==0 or sk.pop()!="<"):
                bl = False
                break
        if(s[i]=='}'):
            if(len(sk)==0 or sk.pop()!="{"):
                bl = False
                break
    if(len(sk)!=0):
        bl=False;
    if bl == True:
        print("Yes")
    else:
        print("No")
```
C++
```cpp=
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    cin.ignore();
    while(n--)
    {
        string s;
        getline(cin,s);
        stack <char> sk;
        bool bl = 1;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='['||s[i]=='('||s[i]=='<'||s[i]=='{')
                sk.push(s[i]);
            else if(s[i]==']')
            {
                if(sk.empty()||sk.top()!='[')
                {
                    bl = 0;
                    break;
                }
                sk.pop();
            }
            else if(s[i]==')')
            {
                if(sk.empty()||sk.top()!='(')
                {
                    bl = 0;
                    break;
                }
                sk.pop();
            }
            else if(s[i]=='>')
            {
                if(sk.empty()||sk.top()!='<')
                {
                    bl = 0;
                    break;
                }
                sk.pop();
            }
            else if(s[i]=='}')
            {
                if(sk.empty()||sk.top()!='{')
                {
                    bl = 0;
                    break;
                }
                sk.pop();
            }
        }
        if(!sk.empty())
            bl=0;
        cout<<(bl ? "Yes":"No")<<endl;
    }

    return 0;
}
```
# 第三題 [等差數列](https://zerojudge.tw/ShowProblem?problemid=b971)
## d為公差
python
```py=
n,m,d=map(int,input().split())
if(d>0):
  for i in range(n,m+1,d):
    print(i,end=' ')
if(d<0):
  for i in range(n,m-1,d):
    print(i,end=' ')
       
```
C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int n,m,d;
    cin>>n>>m>>d;
    if(d>0)
    {
        for(int i=n;i<=m;i+=d)
            cout<<i<<' ';
    }
    else
    {
        for(int i=n;i>=m;i+=d)
            cout<<i<<' ';
    }
}
```
# 第四題 奇數運算
*自出題，無原題來源*
python
```py=
n=int(input())
sum=0
a=[]
z=1
for i in range(1,n+1):
  sum+=z;
  print(z,end=' ')
  a.append(z)
  z=z+2

print()
print("sum=",end='')
print(sum)
print("average=",end='')
print(round(sum/n))
print("Median=",end='')
if n%2==0:
  print(round((a[round(n/2)]+a[round(n/2)-1])/2))
else:
  print(a[round(n/2)-1])
```
C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int n;
    cin>>n;
    vector<int> v;
    int sum=0;
    for(int i=1;i<2*n+1;i+=2)
    {
        v.push_back(i);
        cout<<i<<' ';
        sum+=i;
    }
    cout<<endl;
    cout<<"sum= "<<sum<<endl;
    cout<<"average= "<<sum/n<<endl;
    cout<<"Median= ";
    if(n%2==0)
    {
        cout<<(v[n/2]+v[n/2-1])/2;
    }
    else
        cout<<v[n/2];

}
```
# 第五題 [hello, everyone](https://zerojudge.tw/ShowProblem?problemid=b969)
python
```py=
a=list(map(str,input().split()))
s=input()
for i in range(len(a)):
  print(s,end=", ")
  print(a[i])
```
C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main()
{
    vector<string> v;
    string s;
    while(cin>>s)
    {
        v.push_back(s);
    }
    for(int i=0;i<v.size()-1;i++)
        cout<<v[v.size()-1]<<", "<<v[i]<<endl;
}
```
# 第六題 [missing number](https://cses.fi/problemset/task/1083/)
由題目限制$n<2·10^5$得
時間複雜度
$O(NlogN)$ (C++)
$O(N)$ (python)
C++很簡單，sort是$O(NlogN)$，直接排序就過了
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int n;
    cin>>n;
    int a[n-1];
    for(int i=0;i<n-1;i++)
        cin>>a[i];
    sort(a,a+n-1);
    for(int i=0;i<n-1;i++)
    {
        if(a[i]!=i+1)
        {
            cout<<i+1<<endl;
            return 0;
        }
    }
    cout<<n<<endl;
}
```
python就麻煩了，sort一樣是$O(NlogN)$，但題目只能接受到$O(N)$，所以必須建表
```py=
n=int(input())
a=[]
for i in range(n):#塞入初始
  a.append(0)
z=list(map(int,input().split()))
for i in range(n-1):
  a[z[i]-1]=1
for i in range(n):
  if a[i]==0:
    print(i+1)
    break;
```