Problem:


Score : 700 points

Problem Statement

You are given an integer N.
Build an undirected graph with N vertices with indices 1 to N that satisfies the following two conditions:

The graph is simple and connected.

There exists an integer S such that, for every vertex, the sum of the indices of the vertices adjacent to that vertex is S.

It can be proved that at least one such graph exists under the constraints of this problem.

Constraints

All values in input are integers.

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

In the first line, print the number of edges, M, in the graph you made. In the i-th of the following M lines, print two integers a_i and b_i, representing the endpoints of the i-th edge.

The output will be judged correct if the graph satisfies the conditions.

Sample Input 1

3

Sample Output 1

2
1 3
2 3

For every vertex, the sum of the indices of the vertices adjacent to that vertex is 3.



Sample input:
3


Sample output:
2
1 3
2 3

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int):
    ans = []
    if N%2==0:
        for i in range(1, N+1):
            for j in range(i+1, N+1):
                if i+j==N+1:
                    continue
                ans.append([i, j])
    else:
        for i in range(1, N):
            for j in range(i+1, N):
                if i+j==N:
                    continue
                ans.append([i, j])
        for i in range(1, N):
            ans.append([N, i])

    print(len(ans))
    for elem in ans:
        print(elem[1], elem[0])

    #check(ans, N)

    return

def check(ans, N):
    import numpy as np
    print(np.sum(np.array(ans))//N)


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
E = []

if N%2==0:
  for i in range(1, N+1):
    for j in range(i+1, N+1):
      if i+j!=N+1:
        E += [(i, j)]
else:
  for i in range(1, N):
    for j in range(i+1, N):
      if i+j!=N:
        E += [(i, j)]
    E += [(i, N)]

print len(E)
for e in E:
  print e[0], e[1]

Submission status: Accepted

Solution code:
def main():
    n = int(raw_input())
    a = n * (n + 1) / 2
    for i in xrange(2, a):
        if a % i:
            continue
        t = a / i
        g = [[] for j in xrange(i)]
        y = range(1, n + 1)[::-1]
        for j in xrange(i - 1):
            s = 0
            ny = []
            for x in y:
                if s + x <= t:
                    s += x
                    g[j].append(x)
                else:
                    ny.append(x)
            y = ny
        g[-1] = y
        ans = []
        for j in xrange(i):
            for x in g[j]:
                for y in g[j-1]:
                    ans.append((x, y))
            if i == 2:
                break
        print len(ans)
        for x, y in ans:
            print x, y
        return
main()

Submission status: Accepted

Solution code:
n = int(input())

if n % 2 == 0:
    print(n * n // 2 - n)
    for a in range(1, n + 1):
        for b in range(a + 1, n + 1):
            if a + b != n + 1:
                print('{0} {1}'.format(a, b))
else:
    print((n - 1) ** 2 // 2)
    for a in range(1, n + 1):
        for b in range(a + 1, n + 1):
            if a + b != n:
                print('{0} {1}'.format(a, b))

Submission status: Accepted

Solution code:
N = int(input())
if N % 2 == 0:
    ans = []
    for i in range(1, N+1):
        for j in range(1, i):
            if i + j != N + 1:
                ans.append((i, j))
else:
    ans = []
    for i in range(1, N+1):
        for j in range(1, i):
            if i + j != N:
                ans.append((i, j))
print(len(ans))
for s in ans:
    print(*s)

Submission status: Accepted

Solution code:

# reason about even and odd case separately (kind of)
"""
 12345
1.xx.x
2x..xx
3x..xx
4.xx.x
5xxxx.

 123456
1.xxxx.
2x.xx.x
3xx..xx
4xx..xx
5x.xx.x
6.xxxx.
"""

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())

g=[[1]*n for _ in range(n)]

# do the X thing
n2=n-n%2
for i in range(n2):
    g[i][n2-1-i]=0
    g[n2-1-i][i]=0
g[n-1][n-1]=0

out=[]
for i in range(n):
    for j in range(i+1,n):
        if g[i][j]:
            out.append([i+1,j+1])
print(len(out))
for i,j in out:
    print("%d %d"%(i,j))

Submission status: Accepted

Solution code:
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())

n = ii()
ed = {(i, j) for i in range(1, n) for j in range(i + 1, n + 1)}
i, j = 1, n - n % 2
while i < j:
    ed.remove((i, j))
    i += 1
    j -= 1
print(len(ed))
print(*('%d %d' % e for e in ed), sep='\n')

Submission status: Accepted

Solution code:
import sys
N = int(input())

ans = []
if N % 2:
    print(N*(N-1)//2 - N//2)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if i + j != N:
                ans.append("%d %d\n" % (i, j))
else:
    print(N*(N-1)//2 - N//2)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if i + j != N+1:
                ans.append("%d %d\n" % (i, j))
sys.stdout.writelines(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = []
if n % 2 == 0:
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            if j != n-i+1:
                ans.append([i,j])
else:
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            if j != n-i:
                ans.append([i,j])
print(len(ans))
for i, j in ans:
    print(i,j)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    n = I()
    b = LI()
    d = defaultdict(int)
    for i in b:
        d[i] += 1
    a = []
    ans = []
    return
#B
def B():
    n = I()
    if n%2:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
    else:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n+1-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
n = int(input())
ans = []
if n % 2 == 0:
    m = n + 1
else:
    m = n
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if i + j == m:
            continue
        ans.append('{} {}'.format(i, j))
print(len(ans))
print('\n'.join(ans))

Submission status: Runtime Error

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
node=[]
if n%2==0:
    for i in range(n):
        for j in range(i,n):
            if j==i or j==n-1-i:
                continue
            node.append((i+1,j+1))
else:
    for i in range(n):
        for j in range(i,n):
            if j==i or j==n-2-i:
                continue
            node.append((ix+1,j+1))
    
print(len(node))
for i in node:
    print(*i)

Submission status: Runtime Error

Solution code:
n=int(input())
ans=[]
if n%2==0:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n+1:
                ans.appned([i,j])
else:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n:
                ans.appned([i,j])
print(len(ans))
for i,j in ans:
    print(i,j)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
print(m*(m-1)//2-m//2)

for i in range(n):
    a = n-1-i if n%2 == 0 else n-2-i
    for j in range(i,n):
        if j != a:
            print(i+1,j+1)

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N = ri()
answer_set = {}
for i in range(1, N):
    for j in range(i+1, N+1):
        if i+j == N:
            continue
        else:
            answer_set.add((i, j))

print(len(answer_set))
for x in answer_set:
    print(*x)

Submission status: Runtime Error

Solution code:
n=int(input())
m=n//2*2
ans=[]
for i in range(1,m//2):
  for j in range(1+i,m-i+1):
  ans.append((i,j))
  ans.append((n-j,n-i))
if n%2:
  for i in range(1,n):
    ans.append((i,n))
print(len(ans),*ans,sep="\n")

Submission status: Runtime Error

Solution code:
n = input()
a = []
b = []
for i in range(n):
  for j in range(i, n):
    a.append([i+1, j+1])
for i in range(len(a)):
  if a[i][0] + a[i][1] != n:
    b.append(a[i])
m = len(b)
print(m)
for i in range(m):
  print(b[i][0], b[i][1])

Submission status: Runtime Error

Solution code:
N = int(input())

Ls = set()
for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        Ls.add((i, j))

K = N - (N % 2)
for i in range(1, K):
    Ls.remove((i, K - i + 1))

print(len(Ls))
for l in Ls:
    print("%d %d" % l)

Submission status: Runtime Error

Solution code:
N = int(input())
ans = []
for i in range(1,N+1):
  for j in range(i+1,N+1):
    ans.append(sorted([i,j]))

if N%2==1:
  for i in range(1, N//2+1):
    del ans[ans.index(sorted([i, N-i]))]
else:
  for i in range(1, N//2+1):
    del ans[ans.index(sorted([i, N-i]))]

print(len(ans))
[print(*a) for a in ans]

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n=int(input())
tmp=(n+1)//2*(n-2)
# print(tmp)
if n%2==0:
    print(N*(N-2)//2)
else:
    print(((N-1)*(N-3))//2+N-1)
for i in range(n):
    for j in range(i+1,n):
        if (i+1)+(j+1)!=n+(n+1)%2:
            print(i+1,j+1)

Submission status: Runtime Error

Solution code:
n=int(input())
ans=[]
if n%2==0:
  for i in range((n-1)//2):
    for j in range(i+1,n-i):
      if i==0:
        ans.aopend(((n-i),j))
      else:
        ans.append((i,j))
        ans.append(((n-i),j))
if n2%==1:
  for i in range(1,n//2):
    for j in range(i+1,n-i):
      ans.append((i,j))
      ans.append(((n-i),j))
print(len(ans))
for u,v in ans:
  print(u,v)

Submission status: Runtime Error

Solution code:
def find(n):
    """
    tn = int(n/2)
    s = 2 * tn + 1
    :param n:
    :return:
    """
    tn = int(n/2)
    s = 2 * tn + 1
    count = 0
    line_list = []
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            if i + j != s:
                line_list.append(f"{i} {j}")
                count +=1

    return count, line_list


if __name__ == '__main__':
    n = input()

    count, line_list = find(int(n))
    print(count)
    print("\n".join(line_list))

Submission status: Runtime Error

Solution code:
N = int(input())
ans = []
for i in range(1,N):   
    for j in range(i+1,N+1):
        if i+j != (N//2)*2 + 1
            ans.append([i,j])
            
print(len(ans))
for a,b in ans:
    print(a,b)

Submission status: Runtime Error

Solution code:
n,a,b=int(input()),[],[]
for i in range(1,n+1):
  for j in range(i,n+1):
    if i!=j and i+j!=n:
      a.append(i)
      b.append(j)
print(len(a))
for i,j in a,b:print(i,j)

Submission status: Runtime Error

Solution code:
N = int(input())
ans = []
M = n + 1 * (N % 2 == 0)
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if i + j == M:
            continue
        ans.append('{} {}'.format(i, j))
print(len(ans))
print('\n'.join(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
ans = []
lis = []
for i in range(N):
    lis.append(i + 1)
if N % 2 == 0:
    M = (N - 2) * N // 2
    for i in range(1, N):
        for j in range(1, N):
            if j != i and i != lis[-j]:
              	tmp = sorted([i, lis[-j]]) 
                if tmp not in ans:
                    ans.append(tmp)
    print(M)
    for i in range(M):
        print(' '.join(map(str, ans[i])))
else:
    M = (N - 1) ** 2 // 2
    for i in range(1, N):
        for j in range(2, N):
            if j != i + 1 and i != lis[-j]:
              	tmp = sorted([i, lis[-j]])
                if tmp not in ans:
                    ans.append(tmp)
    for i in range(1, N):
        ans.append([N, i])
    print(M)
    for i in range(M):
        print(' '.join(map(str, ans[i])))

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(range(1,N+1))
Nsum = sum(X)

n = 2 
while Nsum % n != 0:
    n += 1

group = [[] for i in range(n)]
value = int(Nsum/n)

for i in range(n-1):
    for j in range(N):
        if sum(X[-j-1:]) > value:
            break
    group[i] = X[-j:]
    X = X[:-j]
    ex = value - sum(group[i])
    if ex != 0:
        group[i].append(X.pop(ex))

group[-1] = X

LEN = []
LENpr = 0
for i in range(n):
    LEN.append(len(group[i]))
for i in range(n-1):
    LENpr += LEN[i] * sum(LEN[i+1:])

print(LENpr)

for i in range(n-1):
    for j in range(i+1,n):
        for k in range(LEN[i]):
            for l in range(LEN[j]):
                print(group[i][k],group[j][l])

Submission status: Runtime Error

Solution code:
N = int(input())
ans = []
lis = []
for i in range(N):
    lis.append(i + 1)
if N % 2 == 0:
    M = (N - 2) * N // 2
    for i in range(1, N // 2 + 1):
        for j in range(1, N):
            if j != i and i != lis[-j]:
                ans.append([i, lis[-j]])
    print(M)
    for i in range(M):
        print(' '.join(map(str, ans[i])))
else:
    M = (N - 1) ** 2 // 2
    for i in range(1, (N - 1) // 2 + 1):
        for j in range(2, N):
            if j != i + 1 and i != lis[-j]:
                ans.append([i, lis[-j]])
    for i in range(1, N):
        ans.append([N, i])
    print(M)
    for i in range(M):
        print(' '.join(map(str, ans[i])))

Submission status: Runtime Error

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

int main(){
  int n;
  cin >> n;
  cout << (n*(n-1)/2) - (n/2)<< endl;
  for(int x = 1; x <= n; x++){
    for(int y = x+1; y<= n; y++){
      if(x != n - y + ((n+1)%2)){
        cout << x << " " << y << endl;
      }
    }
  }
}

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

n,m = map(int,input().split())
cnt = [0] * n
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    cnt[a] += 1
    cnt[b] += 1
cnt = sorted(cnt, reverse = True)

odd = 0
even = 0
two = 0

g = gb(cnt)
for k,v in g:
    vv = len(list(v))
    if k == 2:
        two += 1
        continue
    if vv % 2 == 0:
        even += 1
    else:
        odd += 1
        
if two > even + odd:
    print('No')
elif odd == 1:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

n,m = map(int,input().split())
cnt = [0] * n
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    cnt[a] += 1
    cnt[b] += 1
cnt = sorted(cnt, reverse = True)

odd = 0
even = 0
two = 0
g = gb(cnt)
for k,v in g:
    vv =len(list(v))
    if k == 2:
        two += 1
        continue
    if vv % 2 == 0:
        even += 1
    else:
        odd += 1
if odd == 1:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys

N = int(input())

if N % 2 == 0:
    print((N-2)*(N-1)//2)
    for i in range(N):
        for j in range(i,N):
            if (i+1+j+1) != (N+1):
            print((i+1)+' '(j+1))
else:
    print((N-2)*(N-1)//2)
    for i in range(N):
        for j in range(i,N):
            if (i+1+j+1) != (N):
            print((i+1)+' '(j+1))

Submission status: Runtime Error

Solution code:
N=input()
import requests
requests.get('https://vote-slide.herokuapp.com/client?'+N)
#ほんの些細な出来心です。
#アカウント凍結とかしないで・・・

Submission status: Runtime Error

Solution code:
n = int(input())
list = []
a = []
for i in range(n):
  list.append(int(input))

for i in range(1, n):
  for j in range(1, i):
    if list[i] == j:
      a.insert(j, j)

if a == list:
  for i in range(n):
    print(list[i])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import itertools
N=int(input())

def returnSplit(N):
    if N%2==0:
        return [[i+1,N-i] for i in range(N//2)]
    else:
        return [[N],*returnSplit(N-1)]


blocks=returnSplit(N)
retval=[]

for i in range(len(blocks)):
    for j in range(i+1,len(blocks)):
        for k in itertools.product(blocks[i],blocks[j]):
            retval.append(k)


print(len(retval))
for i in retval:
    print("{0} {1}".format(*i))

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from functools import reduce


class Divisor:
    def __init__(self, n):
        """ make divisors list and prime factorization list of n
            complexity: O(n^(1/2))
            used in ProjectEuler No.12, yukicoder No.36
        """
        assert(n >= 1)
        number = n
        if number == 1:
            self.primeFactorization = {1: 1}
        else:
            self.primeFactorization = {}
            for i in range(2, int(n**0.5)+1):
                cnt = 0
                while number % i == 0:
                    cnt += 1
                    number //= i
                if cnt > 0:
                    self.primeFactorization[i] = cnt
            if number > 1:
                self.primeFactorization[number] = 1

    def primeFactors(self):
        return deepcopy(self.primeFactorization)

    def numDivisors(self):
        """ the number of divisors """
        if self.primeFactorization.get(1, 0) == 1:
            return 1
        numDiv = 1
        for _, cnt in self.primeFactorization.items():
            numDiv *= cnt+1
        return numDiv

    def sumDivisors(self):
        return reduce(lambda x, y: x * y, [sum(p**i for i in range(n+1)) for p, n in self.primeFactorization.items()])


def divisorsList(n):
    assert(n >= 1)
    divsList = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divsList.append(i)
            if n // i != i:
                divsList.append(n//i)
    return sorted(divsList)


def subsum(arr, M):
    dp = [0] * (M + 1)
    prev = [-1] * (M + 1)
    dp[0] = 1
    for x in arr:
        for i in reversed(range(M + 1)):
            if dp[i] and i + x <= M and not dp[i + x]:
                dp[i + x] = 1
                prev[i + x] = i
    assert dp[-1]
    ans = []
    now = M
    while prev[now] != -1:
        ans.append(now - prev[now])
        now = prev[now]
    return ans


def dfs(groups, i, now):
    if i == len(groups):
        print(*now)
        return
    for x in groups[i]:
        now.append(x)
        dfs(groups, i + 1, now)
        now.pop()


def main(N):
    sumall = N * (N + 1) // 2
    group_num = divisorsList(sumall)[1]
    groups = []
    selected = set()
    rest = list(range(1, N + 1))
    for i in range(group_num):
        g = subsum(rest, sumall // group_num)
        groups.append(g)
        selected |= set(g)
        rest = [x for x in rest if x not in selected]
    edges = []
    for i in range(len(groups)):
        for j in range(len(groups)):
            if i >= j:
                continue
            for x1 in groups[i]:
                for x2 in groups[j]:
                    edges.append((x1, x2))
    print(len(edges))
    for e in edges:
        print(*e)


if __name__ == '__main__':
    N = int(input())
    main(N)

Submission status: Runtime Error

Solution code:
import itertools
n = int(input())
ns = list(range(1,n+1))
cs = list(itertools.combinations(ns, 2))
top = n if n % 2 == 0 else n-1

for nn in range(n):
  tpl = (nn+1, top-nn)
  if tpl[0] >= tpl[1]:
    break
  #print(f'removing {tpl}')
  cs.remove(tpl)

print(len(cs))
for a, b in cs:
  print(f'{a} {b}')

Submission status: Runtime Error

Solution code:
def solve():
  N = int(input())
  M = (N - 2) * 2
  for i in range(3, N + 1):
    print(f'1 {i}\n{i - 1} {i}')

solve()