結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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
0