結果
| 問題 |
No.1519 Diversity
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 17:00:23 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,592 bytes |
| コンパイル時間 | 402 ms |
| コンパイル使用メモリ | 82,408 KB |
| 実行使用メモリ | 54,552 KB |
| 最終ジャッジ日時 | 2025-06-12 17:00:28 |
| 合計ジャッジ時間 | 3,628 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 13 |
ソースコード
n = int(input())
if n == 1:
print(0)
elif n == 2:
print(1)
print(1, 2)
else:
# Calculate the maximum possible distinct degrees
k = (n + 1) // 2 + 1
# We need to construct a degree sequence that has as many distinct degrees as possible
# The approach is to create a star-like structure with some adjustments
edges = []
# Let's have one node with degree n-1
center = 1
for i in range(2, n+1):
edges.append((center, i))
# Now, reduce the degree of some nodes to create distinct degrees
# For example, the second node will have degree n-2
# We can do this by removing one edge from the second node
# But wait, in the star structure, all periphery nodes have degree 1
# So, we need to adjust some edges to create a more diverse degree sequence
# Let's connect the second node to another node to increase its degree
# For example, connect node 2 to node 3
# This will increase node 2's degree to 2, node 3's degree to 2
# But we need to ensure that the degree sequence can be arranged with as many distinct degrees as possible
# Let's try to create a degree sequence such as n-1, n-2, 2, 2, ..., 1, 0
# To achieve this, we can have node 1 connected to all others (degree n-1)
# Node 2 connected to node 1 and node 3 (degree 2)
# Node 3 connected to node 1 and node 2 (degree 2)
# Node 4 connected to node 1 (degree 1)
# If n>4, node 5 can be connected to node 1, etc.
# But wait, this may not be sufficient to maximize the distinct degree count
# Alternatively, let's try a different approach: create a chain where each node is connected to the next, except for one node which is disconnected
# For example, nodes 1-2-3-...-k, and node k+1 is disconnected
# But this approach may not maximize the distinct degree count
# Another approach: create a near-star structure with some nodes having lower degrees
# Let's try to adjust the star structure:
# Remove some edges from the periphery nodes to create a more diverse degree sequence
# For example, node 2 is connected to node 1 and node 3 (degree 2)
# Node 3 is connected to node 1 and node 2 (degree 2)
# Node 4 is connected to node 1 (degree 1)
# Node 5 is connected to node 1 (degree 1)
# This way, the degree sequence is [4, 2, 2, 1, 1] for n=5
# Which has 3 distinct degrees: 4, 2, 1
# But we can do better by making some nodes have different degrees
# Let's try to have node 2 connected to node 1 and node 3 (degree 2)
# Node 3 connected to node 1, node 2, and node 4 (degree 3)
# Node 4 connected to node 1, node 3, and node 5 (degree 3)
# Node 5 connected to node 1 and node 4 (degree 2)
# Node 1 has degree 4, node 2 has 2, node 3 has 3, node 4 has 3, node 5 has 2
# Degree sequence sorted: [4,3,3,2,2] → 3 distinct degrees
# Not better than before
# Hmm, perhaps the maximum number of distinct degrees is not easily achievable with a simple approach
# Let's try a different method: for n=5, create edges as follows
# 1-2, 1-3, 1-4, 2-3, 2-5, 3-5
# Then, degree sequence:
# 1: 3 edges (2,3,4)
# 2: 3 edges (1,3,5)
# 3: 3 edges (1,2,5)
# 4: 1 edge (1)
# 5: 2 edges (2,3)
# Sorted: [3,3,3,2,1]
# Distinct degrees: 3,2,1 → 3 distinct
# Still not better
# Let's think differently: try to have degrees 3,2,2,1,0 for n=5
# How to construct this:
# Node 1: connected to 2,3,4 → degree 3
# Node 2: connected to 1 and 5 → degree 2
# Node 3: connected to 1 → degree 1
# Node 4: connected to 1 → degree 1
# Node 5: connected to 2 → degree 1
# Wait, this gives degree sequence [3,2,1,1,1]
# Only 3 distinct
# Need to adjust
# Another approach:
# Node 1: connected to 2,3,4 → degree 3
# Node 2: connected to 1,3 → degree 2
# Node 3: connected to 1,2 → degree 2
# Node 4: connected to 1 → degree 1
# Node 5: not connected → degree 0
# Then, degree sequence is [3,2,2,1,0] → 4 distinct degrees
# This is better
# So, the edges are:
# 1-2, 1-3, 1-4, 2-3
# Let's check:
# Edges:
# 1-2 → degrees 1 and 2
# 1-3 → degrees 1 and 3
# 1-4 → degree 1 and 4
# 2-3 → degrees 2 and 3
# So, node 1 has degree 3
# Node 2 has edges with 1 and 3 → degree 2
# Node 3 has edges with 1 and 2 → degree 2
# Node 4 has edge with 1 → degree 1
# Node 5 has no edges → degree 0
# Sorted degree sequence: [3,2,2,1,0] → 4 distinct degrees
# This is correct
# So, for n=5, we can construct such a graph
# Now, generalize this approach
# The idea is:
# - Node 1 is connected to nodes 2,3,...,k → degree k-1
# - Node 2 is connected to node 1 and node 3 → degree 2
# - Node 3 is connected to node 1 and node 2 → degree 2
# - Node 4 is connected to node 1 → degree 1
# - Nodes beyond 4 are not connected → degree 0
# But this may not scale for larger n
# Alternatively, for general n, we can:
# - Connect node 1 to nodes 2,3,...,m (m is chosen such that the degree sequence can have as many distinct degrees as possible)
# - For other nodes, connect them in a way that creates as many distinct degrees as possible
# But this requires careful construction
# For the purpose of this problem, we can implement the following approach:
# - For even n, connect node 1 to all other nodes (degree n-1)
# Then, connect node 2 to node 1 and node 3 (degree 2)
# Connect node 3 to node 1 and node 2 (degree 2)
# Connect node 4 to node 1 → degree 1
# And so on, leaving some nodes with degree 0
# But this may not maximize the distinct degrees
# Another approach is to construct a star graph and then adjust some edges to create more distinct degrees
# This is what we did for n=5
# So, let's implement this for general n
# The steps are:
# 1. Connect node 1 to nodes 2,3,4
# 2. Connect node 2 to node 3
# 3. Leave node 5 disconnected
# For n=5, this gives the desired degree sequence
# For larger n, we can extend this pattern
# For example, for n=6:
# Connect node 1 to 2,3,4,5 (degree 4)
# Connect node 2 to 3 (degree 2)
# Connect node 3 to 2 (degree 2)
# Connect node 4 to 1 (degree 1)
# Connect node 5 to 1 (degree 1)
# Leave node 6 disconnected (degree 0)
# Degree sequence: [4,2,2,1,1,0] → 4 distinct degrees
# Which is correct
# So, the general approach is:
# - Node 1 is connected to nodes 2,3,4,...,m (m is chosen such that the number of distinct degrees is maximized)
# - Node 2 is connected to node 3 (to create a degree of 2)
# - Node 3 is connected to node 2 (to create a degree of 2)
# - Nodes 4,5,...,m are connected only to node 1 (degree 1)
# - Nodes beyond m are disconnected (degree 0)
# This way, the degree sequence will be [m-1, 2, 2, 1, 1, ..., 0]
# Which has 4 distinct degrees (if m >=3)
# For example, when n=5, m=4 → degree sequence [3,2,2,1,0] → 4 distinct
# When n=6, m=5 → degree sequence [4,2,2,1,1,0] → 4 distinct
# When n=7, m=5 → degree sequence [4,2,2,1,1,0,0] → 4 distinct
# So, the number of distinct degrees is 4 for n >=5
# Which aligns with the formula floor((n+1)/2) +1 when n >=5
# For n=3, the maximum distinct degrees are 3
# For n=4, the maximum distinct degrees are 3
# Let's proceed to implement this logic
m = 4 # For n>=5, m is 4
if n >= 5:
edges = []
# Connect node 1 to 2,3,4,5,...,m
for i in range(2, m+1):
edges.append((1, i))
# Connect node 2 to 3
edges.append((2, 3))
# Nodes beyond m are disconnected
# If n > m+1, we need to leave nodes m+2,...,n disconnected
else:
# Handle small cases
if n == 3:
edges = [(1,3), (2,3)]
elif n == 4:
edges = [(1,2), (1,3), (1,4), (2,3)]
# For n=4, the degree sequence is [3,2,2,1] → 3 distinct degrees
# Output the edges
print(len(edges))
for u, v in edges:
print(u, v)
# Note: The above code is a simplified version and may need adjustments for all cases
# For example, for n=6, the code would connect node 1 to 2,3,4,5, but the degree of node 1 would be 4
# Nodes 2 and 3 are connected (degrees 2 each)
# Nodes 4 and 5 are connected only to 1 (degrees 1 each)
# Node 6 is disconnected (degree 0)
# Degree sequence: [4,2,2,1,1,0] → 4 distinct degrees