# 2024/4/27 APCS 第四場模擬賽 題解
## 辯論賽 (Debate)
> 出題者：JC0713
> 難度：p1
> 考點：基本 I/O、迴圈
### Statement
最近全台灣最大的辯論盃賽 APCS 盃開打了!
文彣雖然沒有參加比賽，但是要擔任冠軍賽的主計，主計有一個很重要的工作是整理裁單上的分數，並且公布比賽的結果。由於是冠軍賽，所以裁判的數量可能會非常多，而文彣希望你能幫他寫一個程式來幫他計算比賽的結果。

該場冠軍賽有 $t$ 個裁判，每個裁判給正方和反方的分數分別為 $P_i, N_i$，若$P_i \gt N_i$ 則正方得到該張裁單，否則反方得到該張裁單。若雙方得到的裁單數量不同，則獲得較多裁單的持方獲勝，否則的話由所有裁單上得到總分較多的持方獲勝，若是雙方得到裁單數及總分皆相同，則正方獲勝。

文彣希望你能寫一個程式輸出該場比賽哪方獲勝，以及雙方各自得到的裁單數以及總分。
### Input
輸入第一行有一個正整數 $t\ (t\leq100)$
接下來有$t$行輸入，每行有兩個正整數 $P_i, N_i\ (P_i, N_i \leq 100, \space P_i\ 不等於\ N_i)$，分別代表第 $i$ 位裁判給正方及反方的分數。
### Output
第一行請輸出獲勝的持方，若正方獲勝請輸出 "Positive side"，若反方獲勝請輸出 "Negative side" (皆不含雙引號)。
第二行請輸出正方裁單數 $C_p$ 及反方裁單數 $C_n$
第三行請輸出正方總分 $S_p$ 及反方總分 $S_n$
### Input Format
$t$
$P_1, N_1$
$P_2, N_2$
...
$P_t, N_t$
### Output Format
Positive side/Negative side
$C_p \space \space \space C_n$
$S_p \space \space \space S_n$
### Testcase
- Input 1

1
80 73

- Output 1

Positive side
1 0
80 73

- Input 2

3
94 103
62 71
110 98

- Output 2

Negative side
1 2
266 272

### Subtask
- Subtask 1 (50%) - $t = 1$
- Subtask 2 (50%) - 無特別限制
### Solution
使用變數維護雙方勝場數、裁單數與總分即可。
### Code
- Subtask 2

#include <bits/stdc++.h>
using namespace std;

int cnt_p, cnt_n;
int main(){
    int t; cin >> t;
    while (t--){
        int x, y; cin >> x >> y;
        if (x > y) cnt_p++;
        else cnt_n++;
        P += x; N += y;
    }
    if (cnt_p != cnt_n){
        if (cnt_p > cnt_n) cout << "Positive side\n";
        else cout << "Negative side\n";
    }else{
        if (P > N) cout << "Positive side\n";
        else cout << "Negative side\n";
    }
    cout << cnt_p << " " << cnt_n << endl;
    cout << P << " " << N << endl;
}

- Python by. 橘子

s1 = s2 = c1 = c2 = 0
for _ in range(int(input())):
    p,n = map(int,input().split())
    s1 += p
    s2 += n
    if p>n:
        c1 += 1
    else:
        c2 += 1
print("Positive side" if c1>c2 or c1==c2 and s1>=s2 else "Negative side")
print(c1,c2)
print(s1,s2)

print((lambda o,l:(lambda a,b,c,d:("Positive"if(a,c)>=(b,d)else"Negative")+f" side\n{a} {b}\n{c} {d}\n")(*(sum(map(f,o)) for f in l)))([[int(s) for s in input().split()] for _ in range(int(input()))],(lambda a:a[0]>a[1],lambda a:a[0]<=a[1],lambda a:a[0],lambda a:a[1])))

## 黑洞旅行 (Blackhole)
> 出題者：Guonuo
> 難度：p2
> 考點：模擬（迴圈、二維陣列）
### Statement
*題外話：不，你不能通過黑洞旅行，至少現在不行*

Chung的錢包掉進了時空裂縫了！因此，他派出了拉麵號在一個特殊空間中搜索。為了方便搜查，將座標以字元表示，並繪製出了以下地圖（$8\times8$ 正方形方格）

A B C D E F G H

I J K L M N O P

Q R S T U V W X

Y Z a b c d e f

g h i j k l m n

o p q r s t u v

w x y z 0 1 2 3

4 5 6 7 8 9 + /

此空間是自身環繞的：

右方出去會從左方同一橫列中回來（如：紅色箭頭）。
下方出去會從上方同一直行中回來（如：橘色箭頭）。
左上方出去則可分為從左方出去又從上方出去，即從右方、下方回來（如：紫色箭頭）。


拉麵號為防止迷路，依照特定的路徑搜查（符號表示法在 Input 中詳述），並以以下行徑方式前進：

1. $D = 1$
2. 從初始座標 $S$ 開始面相一特定方向 $t$。
3. 向該方向前進步數 $D$，完成後 $t$ 往順時鐘方向轉 $45^\circ$。
4. $D+1$，回到步驟 2.。重複步驟 2. 到 4. 共 $N$ 次。

而 Chung 忙著和提米博士約會忘記了拉麵號最後的位置 $E$，需要你幫忙找出它在哪裡！
### Input
第一行 $Q$ 表示測資數量 ( $1\le Q \le 100$ )
接下來每一行有三個數字 $S,t,N$
$S$ : 為一字元，表示在地圖上的座標。
$t$ : 為一數字，表示八方位中一方向，分別為北(0)、東北(1)、東(2)、東南(3)、南(4)、西南(5)、西(6)、西北(7)。
$N$ : 為一數字。 ( $1\le N \le 100$ )
### Output
共 $Q$ 行，輸出每次模擬後的位置 $E$ (字元)
### Input Format
$Q$
$S_1 \space t_1 \space N_1$
$S_2 \space t_2 \space N_2$
...
$S_n \space t_n \space N_n$
### Output Format
$E_1$
$E_2$
...
$E_n$
### Testcase
- Input 1

1
b 1 4

- Output 1

J

- Input 2

1
G 3 2

- Output 2

f

### Subtask
- Subtask 1 (50%) - $Q=1$
- Subtask 2 (50%) - 沒有特殊限制
### Note
範例測資 1 的路線圖（紅、橘、黃、綠）:


### Solution
- 做 `dx,dy` 陣列表示移動方向的位移，乘上前進步數即為該次的實際位移


- 將 X (橫向/左右)、Y (直向/上下) 分開處理，加上位移後 % 8 (記得處理負數!) 即為該軸結束位置

### Code by Chung

#include<bits/stdc++.h>
using namespace std;
//declare
int q,t,n;
char s;
string ss = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
char maze[9][9];
int dir[8][2] = {{-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}};
//
pair<int,int> nxt(int x,int y,int i){
    int nx = x+dir[i][0], ny = y+dir[i][1];
    if(nx == 8) nx = 0;
    if(ny == 8) ny = 0;
    if(nx == -1) nx = 7;
    if(ny == -1) ny = 7;
    return {nx, ny};
}
int main(){
    int ptr = 0;
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            maze[i][j] = ss[ptr++];
        }
    }
    cin>>q;
    while(q--){
        cin>>s>>t>>n;
        char start;
        int x,y;
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                if(maze[i][j] == s){
                    x = i;
                    y = j;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                auto [nx,ny] = nxt(x,y,t);
                x = nx, y = ny;
            }
            t++;
            if(t == 8) t = 0;
        }
        cout<<maze[x][y]<<"\n";
    }
    return 0;
}

- Python by. 橘子

s = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
f = ((-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1))
for _ in range(int(input())):
    a,b,c = input().split()
    p = s.find(a)
    x,y = divmod(p,8)
    i = int(b)
    n = int(c)
    for j in range(n):
        dx,dy = f[i%8]
        x = (x+dx*(j+1))%8
        y = (y+dy*(j+1))%8
        i+=1
    print(s[x*8+y])

- 奇妙優化

s = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
f = ((-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1))
for _ in range(int(input())):
    a,b,c = input().split()
    p = s.find(a)
    x,y = divmod(p,8)
    i = int(b)
    n = int(c)
    for j in range(8):
        cnt = (n-j-1)//8+1
        mul = ((j+cnt*4-3)*cnt)
        dx,dy = f[i%8]
        x = (x+dx*mul)%8
        y = (y+dy*mul)%8
        i+=1
    print(s[x*8+y])

print(*(lambda s,xs,ys,qs:(s[(s.find(a)//8+sum(xs[(int(b)+j)%8]*((j+((int(c)-j-1)//8+1)*4-3)*((int(c)-j-1)//8+1)) for j in range(8)))%8*8+(s.find(a)%8+sum(ys[(int(b)+j)%8]*((j+((int(c)-j-1)//8+1)*4-3)*((int(c)-j-1)//8+1)) for j in range(8)))%8] for a,b,c in qs))("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/",(-1,-1,0,1,1,1,0,-1),(0,1,1,1,0,-1,-1,-1),(input().split() for _ in range(int(input())))),sep="\n")

## 愛吃字母的怪獸 (Alphabet Monster)
> 出題者：小麥
> 難度：p3
> 考點：差分
### Statement
在 T 小鎮的某一天，一隻奇特的字母怪獸現身，它的特殊之處在於喜好三種字母：W、M、L。每當怪獸花一個小時吃到其中一個字母，它都會感到極度的開心，然而，這份快樂必須謹慎維持，因為怪獸若是被這些字母搞得太過快樂，就有可能面臨生命的終結。

每一個字母都擁有特定的開心持續時間和開心度，而這些時間可以進行疊加。舉例而言，如果 W 的開心時間為 $2$ 小時，開心度為 $4$，那麼他在 $2$ 個小時內吃下兩顆 W 其開心度為 $8$。因此，為了滿足這隻怪獸的需求，小鎮居民小麥為牠精心準備了一餐，而每一個字母怪獸一定都會吃下去。

現在，我們需要檢查這一餐中，在每一個時間點有幾個點會超越極限開心值。即便是喜歡的字母，也需要小心呵護，以免導致怪獸不幸結束它在 T 小鎮的奇妙探險。

給定一餐中所有的英文字母和怪獸的開心度極限，以及喜好的三種字母的開心度和開心時間，請你找出有幾個時間點會超過極限開心值。
### Input
第一行包含兩個正整數 $n, m$
- $n$ 代表小麥準備了幾份餐點。
- $m$ 代表怪獸的極限開心度。

第二行包含一個字串 $s$，字串中的每個字元代表小麥幫怪獸準備的餐點，由左到右代表從第一個小時到第 $n$ 個小時的餐點。

第三行包含三個正整數 $a_i$，由左由右代表 W、M、L 的開心度。

第四行包含三個正整數 $b_i$，由左由右代表 W、M、L 的開心持續時間。

**測資範圍**
- $1 \leq n \leq 2 \times 10^5$
- $1 \leq m \leq 2 \times 10^{14}$
- $1 \leq a_i,b_i \leq 10^9$

### Output
輸出有幾個時間點的怪獸快樂度會超過極限。
### Input Format

n m
s
a1 a2 a3
b1 b2 b3

### Output Format

ans

### Testcase
- Input 1

10 57
LWWLLWLLWM
6 3 15
14 6 8

- Output 1

5

### Subtask
- Subtask 1 (40%)：$1 \leq m,b_i \leq 10^4$
- Subtask 2 (60%)：題目範圍限制

### Solution
- Subtask 1
- 應該非常直覺的可以發現只要用一個陣列來維護每個時間的點開心度就行了。
- 例如在時間點 $2$ 吃，開心時間為 $5$ 開心度為 $6$，則在 $2 \sim 5$ 都加上 6 即可。
- 最後再全部掃一輪找出超過極限開心值的點加起來即可。
- Subtask 2
- 考慮使用差分
- 一樣又是使用一個陣列來維護，並且在吃的當下加上開心度，等到開心時間過後再減掉開心度，最後計算的時候做一次前綴和即可。
- 例如在時間點 $2$ 吃，開心時間為 $5$ 開心度為 $6$，則在 $2$ 加上 $6$，並且在 $2+5+1$ 減掉 $6$ 即可。
- 需要注意開心時間可能會超過 $n$，此外實作差分的時候小心少算一個。

### Code
- Subtask 1

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0);
#define int long long

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<vvp> v3p;

int n, m;
string s;
vp table(3);
vi sum;

void solve()
{
    cin >> n >> m >> s;

    for (int i = 0; i < 3; i++) cin >> table[i].first;
    for (int i = 0; i < 3; i++) cin >> table[i].second;
    
    sum.resize(n + 1); 
    for (int i = 1; i <= n; i++)
    {
        switch (s[i-1]) 
        {
            case 'W':
                for (int j = i; j <= min(n, i + table[0].second); j++)
                    sum[j] += table[0].first;
                break;
            case 'M':
                for (int j = i; j <= min(n, i + table[1].second); j++)
                    sum[j] += table[1].first;
                break;
            case 'L':
                for (int j = i; j <= min(n, i + table[2].second); j++)
                    sum[j] += table[2].first;
                break;
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i++) 
    {
        if (sum[i] > m) ans++;
    }
    
    cout << ans << '\n';
}

signed main() 
{
    fastio;
    solve();
    return 0;
}

- Subtask 2 by Chung

#include<bits/stdc++.h>
using namespace std;
//declare
const int maxn = 2e5+5;
int n,m,a['Z'+1],b['Z'+1];
int diff[maxn];
string s;
//
int main(){
    fastio;
    cin>>n>>m>>s; s = '#'+s;
    cin>>a['W']>>a['M']>>a['L']>>b['W']>>b['M']>>b['L'];
    for(int i=1;i<=n;i++){
        diff[i] += a[s[i]];
        diff[min(n + 1, i + b[s[i]])] -= a[s[i]];
    }
    int now = 0, cnt = 0;
    for(int i=1;i<=n;i++){
        now += diff[i];
        if(now > m) cnt++;
    }
    cout<<cnt<<"\n";
    return 0;
}

- Python by. 橘子

n,m = map(int,input().split())
s = input()
a = [int(s) for s in input().split()]
b = [int(s) for s in input().split()]
o = {"W":0,"M":1,"L":2}
c = [0]*n
for i,ch in enumerate(s):
    j = o[ch]
    c[i] += a[j]
    p = i+b[j]
    if p<n:
        c[p] -= a[j]
ans = 0
cur = 0
for i in c:
    cur += i
    ans += cur>m
print(ans)

print((lambda n,m,s,a,b,o:(lambda c:sum(c.__setitem__(i,c[i]+a[o[ch]]+(i and c[i-1])) or i+b[o[ch]]<n and c.__setitem__(i+b[o[ch]],c[i+b[o[ch]]]-a[o[ch]]) or 0 for i,ch in enumerate(s)) or sum(i>m for i in c))([0]*n))(*map(int,input().split()),input(),[int(s) for s in input().split()],[int(s) for s in input().split()],{"W":0,"M":1,"L":2}))

## 顯卡爭霸戰 (Graphics Card Battle)
> 出題者：Mingyee
> 難度：P4
> 考點：二分搜、圖、dsu
### Statement
經過統計，世界上共有$n$個顯卡販賣/製造商

而這些廠商十分無良，兩個廠商間的交易必然經過抽成

而有些廠商間具有競爭關係，當一群廠商與外界不交易時，我們稱這群廠商為一個**競爭集群**

但近期各大廠商開始合作，使得**競爭集群**減少，使消費者收到顯卡時，會經過極高額的抽成

於是看不下去的電神共和國政府決定出面制裁，訂出法規使所有 $\ge q$ 的抽成遭到禁止

可若將 $q$ 訂定得太低又會引起廠商的反彈，經過評估後，政府希望這個 $q$ 能**越大越好**

同時這個 $q$ 需使市場上的**競爭集群** $\ge k$ 個以維持市場價格

現在請你幫幫電神共和國政府找出最大的 $q$。

### Input Format
第一行輸入兩個正整數 $n$、$m$ 表示有 $n$ 個廠商，以及 $m$ 個交易關係 $(1 \le n, m \le 10^5)$

接下來有 $m$ 行，每行輸入三個正整數 $a$、$b$、$c$，表示 $a$ 與 $b$ 間具有需抽成 $c$ 元的交易關係

其中 $1 \le a, b \le n$ 且 $0 \le c \le 10^{9}$

第 $m+2$ 行輸入一個正整數 $k (1 \le k \le n)$，表示所需的最小**競爭集群**數

### Output Format
輸出一個正整數 $q$

### Input Example
- Input 1

4 3
4 3 6
1 3 7
1 2 5
2

- Output 1

7

- Input 2

4 4
4 3 6
1 3 7
1 2 5
2 3 4
3

- Output 2

5

### Subtask
- Subtask 1 (40%) - $n,m \le 100$ 且 $c \le 10^5$
- Subtask 2 (60%) - 無其他限制

### Solution
- Subtask 1
- 首先用 dfs 去獲得連通塊的數量，接著就可以枚舉 $q$ 解決
- 時間複雜度：$O(nq)$
- Subtask 2
- 接著觀察連通塊與 $q$ 的關係
- 可以很直覺的發現當 $q$ 越大，移除的邊越少，連通塊數量就會**遞減**
- 於是如果我們將 $q$ 由 $1$ 列到 $10^9$，並算出對應的連通塊數量，那麼會形成一個**遞減數列**
- 想到甚麼了嗎?
- 沒錯! 二分搜! 找出最右邊 $\ge k$ 的 index($q$)
- 因此就可以二分搜 + dfs 解決這題
- 時間複雜度：$O(nlogq)$
- 記得二分搜左閉右開的話要在右界 $+\ 1$，不然會拿到 95%
- Subtask 2 另解
- 題目意思：打斷所有權重 $\ge p$ 的邊使其連通塊數量 $\ge k$，找最大可能 $p$
- 權重由小到大連接邊直到連通塊數量 $\lt k$
- 任何邊 $\ge$ 此刻連接的權重都該被打斷 $\to$ 此刻連接的邊權重即是所求
- 是不是很像MST?
- ~~沒錯還真的是~~
- 開個 dsu 將邊以權重由小到大排序，不斷連接節點
- 複雜度:$O(n\alpha(n))$

### Code
- Subtask 1 (枚舉+dfs)

#include <bits/stdc++.h>
#define int int64_t
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define X first 
#define Y second
#define pb push_back

using namespace std;
constexpr int MAX_N = 1e5+5;
vector<pair<int, int> > G[MAX_N];
bool vis[MAX_N];
 
void dfs(int v, int p){
    vis[v] = 1;
    for(auto a : G[v]){
        if(p<=a.Y) continue;
        if(!vis[a.X]) dfs(a.X, p);
    }
}
 
int cal(int n,int p){
    int res=0;
    for(int x=0; x<=n+1; x++ ) vis[x] = 0;
    for(int x=1; x<=n; x++){
        if(vis[x]) continue;
        dfs(x, p);
        res++;
    }
    return res;
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k, a, b, w;
    cin >> n >> m;
    for(int x=0; x<m; x++){
        cin >> a >> b >> w;
        G[a].pb({b, w});
        G[b].pb({a, w});
    }
    cin >> k;
    int res = 0;
    while(cal(n, res) >= k){
        res++;
    }
    cout << res-1;
    
}

- Subtask 2 (DFS + 二分搜)

#include <bits/stdc++.h>
#define int int64_t
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define X first 
#define Y second
#define pb push_back
 
using namespace std;
constexpr int MAX_N = 1e5+5;
vector<pii > G[MAX_N];
bool vis[MAX_N];
 
void dfs(int v, int p){
    vis[v] = 1;   
    for(auto a : G[v]){
        if(p<=a.Y) continue;
        if(!vis[a.X]) dfs(a.X, p);
    }
}
 
int cal(int n,int p){
    int res=0;
    for(int x=0; x<=n+1; x++ ) vis[x] = 0;
    for(int x=1; x<=n; x++){
        if(vis[x]) continue;
        dfs(x, p);
        res++;
    }
    return res;
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k, a, b, w;
    cin >> n >> m;
    for(int x=0; x<m; x++){
        cin >> a >> b >> w;
        G[a].push_back({b, w});
        G[b].pb({a, w});
    }
    cin >> k;
    int l=0, r= (int)1e9+1;
    while(l+1 < r){
        int mid = (l+r)/2;
       // cout << mid << ' ';
        if(cal(n, mid) >= k) l = mid;
        else r = mid;
    }
    cout << l;
    
}

- Subtask 2 (DSU)

#include<bits/stdc++.h>
#define endl "\n"
#define int int64_t
using namespace std;
constexpr int MAX_N = 1e5+5;
int p[MAX_N];
int f(int x){ return (p[x]==x ? x : p[x]=f(p[x]));}
struct Edge{
    int a, b, w;
    Edge(int aa, int bb, int cc){
        a = aa; b = bb; w = cc;
    }
    bool operator<(Edge b){
        return w < b.w;
    }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k, a, b, c;
    cin >> n >> m;
    vector<Edge> edge;

    for(int x=0; x<=n; x++){
        p[x] = x;
    }
    for(int x=0; x<m; x++){
        cin >> a >> b >> c;
        edge.push_back(Edge(a, b, c));
    }
    cin >> k;
    sort(edge.begin(), edge.end());
    int ss=0;
    for(int x=0; x<m; x++){
        if(f(edge[x].a)!=f(edge[x].b)){
            p[f(edge[x].b)]=f(edge[x].a);
            n--;
            if(n<k){
                return cout << edge[x].w, 0;
            }
        }
    }
    cout << edge[m-1].w;
}

- Python by. 橘子

import sys
sys.setrecursionlimit(100000)
n,m = map(int,input().split())
con = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    con[a-1].append((b-1,c))
    con[b-1].append((a-1,c))
k = int(input())
l = 0
r = 10**9
while l<r:
    x = l+r+1>>1
    vis = [0 for _ in range(n)]
    cur = 0
    def dfs(i):
        vis[i] = 1
        for j,v in con[i]:
            if v<x and not vis[j]:
                dfs(j)
    for i in range(n):
        if not vis[i]:
            cur+=1
            dfs(i)
    if cur>=k:
        l = x
    else:
        r = x-1
print(l)

- BFS

n,m = map(int,input().split())
con = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    con[a-1].append((b-1,c))
    con[b-1].append((a-1,c))
k = int(input())
l = 0
r = 10**9
while l<r:
    x = l+r+1>>1
    vis = [0 for _ in range(n)]
    cur = 0
    for i in range(n):
        if not vis[i]:
            q = [i]
            vis[i] = 1
            cur+=1
            for j in q:
                for o,v in con[j]:
                    if v<x and not vis[o]:
                        vis[o] = 1
                        q.append(o)
    if cur>=k:
        l = x
    else:
        r = x-1
print(l)

- DSU

class dsu:
    __slots__ = ("p",)
    def __init__(self,n):
        self.p = [-1 for _ in range(n)]
    def g(self,i):
        if self.p[i]==-1:
            return i
        else:
            self.p[i] = self.g(self.p[i])
            return self.p[i]
    def m(self, a, b):
        a = self.g(a)
        b = self.g(b)
        if a!=b:
            self.p[a] = b
        return a!=b
n,m = map(int,input().split())
lines = [list(map(int,input().split())) for _ in range(m)]
k = int(input())
lines.sort(key=lambda o:o[2])
d = dsu(n+1)
cur = n
for a,b,c in lines:
    cur -= d.m(a,b)
    if cur<k:
        print(c)
        break