Problem:


Score : 600 points

Problem Statement

We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.

After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

1 \leq N \leq 2000

1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_{3N}

Output

Print the maximum number of points you can gain.

Sample Input 1

2
1 2 1 2 2 1

Sample Output 1

2

Let us rearrange the five leftmost cards so that the integers written on the six cards will be 2\ 2\ 2\ 1\ 1\ 1 from left to right.

Then, remove the three leftmost cards, all of which have the same integer 2, gaining 1 point.

Now, the integers written on the remaining cards are 1\ 1\ 1.

Since these three cards have the same integer 1, we gain 1 more point.

In this way, we can gain 2 points - which is the maximum possible.

Sample Input 2

3
1 1 2 2 3 3 3 2 1

Sample Output 2

1

Sample Input 3

3
1 1 2 2 2 3 3 3 1

Sample Output 3

3



Sample input:
2
1 2 1 2 2 1


Sample output:
2

Submission status: Runtime Error

Solution code:
import sys
from random import randint
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
aa = a[: ]
a.reverse()
res = 0
for _ in range(N):
  a = aa[: ]
  for _ in range(N):
    rres = 0
    t = [a.pop(), a.pop()]
    for _ in range(3): t.append(a.pop())
    i = randint(0, 2)
    j = randint(i + 1, 3)
    k = randint(j + 1, 4)
    rres += t.pop(i) == t.pop(j - 1) == t.pop(k - 2)
  res = max(res, rres)
print(res)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
from collections import deque,defaultdict
dic = defaultdict(int)
cnt = 0
for a in A:
    dic[a] +=1
def helper(A,cnt):
    A.sort()
    if A[0]==A[2]:
        cnt += 1
        return A[3:],cnt
    elif A[2]==A[-1]:
        cnt += 1
        return A[:2],cnt
    tmp = []
    q = deque([])
    for a in A:
        if dic[a]%3==1:
            q.append(a)
        if dic[a]%3==2:
            q.appendleft(a)
        else:
            tmp.append(a)
    ans = tmp + q
    return ans[:2],cnt
for _ in range(n-1):
    a = A[:5]
    B = A[5:]
    ans,cnt = helper(a,cnt)
    A = ans + B
A.sort()
print(cnt+1 if A[0]==A[-1] else cnt)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50



def run():
    N, *A = map(int, read().split())
    A = A[::-1]

    dic = defaultdict(lambda:0)
    for a in A:
        dic[a] += 1

    score = 0
    while len(A) > 3:
        #print(A)
        tmp_dic = defaultdict(lambda:0)
        for i in range(5):
            tmp_a = A.pop()
            tmp_dic[tmp_a] += 1

        done = False
        for key, val in tmp_dic.items():
            if val == 3:
                score += 1
                del tmp_dic[key]
                done = True
                dic[key] -= 3
                break
            elif val > 3:
                score += 1
                tmp_dic[key] -= 3
                done = True
                dic[key] -= 3
                break

        if not done:
            lis = []
            for key in tmp_dic.keys():
                lis.append((dic[key], A[-5:].count(key), key))
            lis = sorted(lis, key = lambda x:x[0])
            cnt = 0
            #print(lis)
            for _, ,_,key in lis:
                if 3 - cnt > tmp_dic[key]:
                    cnt += tmp_dic[key]
                    dic[key] -= tmp_dic[key]
                    del tmp_dic[key]
                else:
                    dic[key] -= 3-cnt
                    tmp_dic[key] -= 3-cnt
                    cnt = 3

        for key, val in tmp_dic.items():
            for _ in range(val):
                A.append(key)
    if A[0] == A[1] and A[1] == A[2]:
        score += 1

    print(score)


if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
assert N >= 1 and N <= 2000
def pick(A, exclude=[]):
    counter = {i:0 for i in set(A)}
    for a in A:
        counter[a] += 1  
    key = None
    for k, v in counter.items():
        if v >= 3 and k not in exclude:
            return k, counter
    return None, counter
p = 0
start = 0
end = 5
# first try
while len(A[start:]) >= 5:
    key, counter = pick(A[start:start+5])
    if key:
        tmp = [a for a in A[start:start+5] if a is not key]
        while len(tmp) < 2:
            tmp.append(key)
        assert len(tmp) == 2
        A[start+3], A[start+4] = tmp[0], tmp[1]
        p += 1
    else:
        keys = []
        end += 2
        while len(keys) < 2 and end < len(A):
            key, _counter = pick(A[start:end], exclude=keys)
            if key in counter:
                if counter[key] == 2:
                    keys = [key, key]
                else:
                    keys.append(key)
            end += 2
        A[start+3], A[start+4] = keys[0], keys[1]
    start += 3
    end = start + 5
def calc(A):
    if A[0] == A[1] and A[0] == A[2]:
        return 1
    else:
        return 0
p += calc(A[start:])
print(p)

Submission status: Runtime Error

Solution code:
import numpy as np

def solve(N, A):
    # dp[n][a] := n 回操作を行って a を取って点を獲得する（or しない）ときの最大値
    #           = (2 回前の a の 1 操作前以前の値 + 区間スケジューリング) の max
    ans3 = 0
    sch = [(0, 0)] * 0
    B = [(0,0,0)] * 0
    for n in range(1, N):
        a1 = A[n*3-1]
        a2 = A[n*3]
        a3 = A[n*3+1]
        if a1 == a2 == a3:
            ans3 += 1
        elif a1 == a2 or a2 == a3 or a3 == a1:
            if a1 == a2:
                a1, a2 = a1, a3
                i1, i2 = 0, 1
            elif a2 == a3:
                a1, a2 = a2, a1
                i1, i2 = 1, 2
            elif a3 == a1:
                a1, a2 = a3, a2
                i1, i2 = 2, 0
            B.append((a2, -1, -1))
            end = len(B)
            for j in range(len(B)-1, -1, -1):
                b1, b2, b3 = B[j]
                c = [b1, b2, b3].count(a1)
                if c == 1:
                    start = j
                    sch.append((start, end))
                    break
                elif c == 2:
                    start = j - 1  # ほんまか？
                    sch.append((start, end))
                    break
            else:
                b1, b2 = A[0], A[1]
                if a1 in [b1, b2]:
                    sch.append((0, end))
        else:
            B.append((a1, a2, a3))
    N = len(B)
    dp = np.zeros((N+1, 3), dtype=np.int64)
    for n in range(1, N+1):
        b1, b2, b3 = B[n-1]
        for i, b in enumerate(B[n-1]):
            
            dp[n, i] = 
    

N = int(input())
A = list(map(int, input().split()))

Submission status: Runtime Error

Solution code:
import collections

n = int(input())
a = tuple(map(int,input().split()))

ans = 0
c = a[0:3]
for i in range(n-1):
  c += a[i*3+3:i*3+5]
  d = a[i*3+5:min(i*3+8,3*n)]
  
  cd = collections.Counter(c)
  cn = []
  for k,v in cd.items():
    if v >= 3:
      ans += 1
      for ci in c:
        if ci != k:
          cn.append(ci)
      if len(cn) < 2:
        for j in range(2-len(cn)):
          cn.append(k)
  if len(cn) == 0:
    for k,v in cd.items():
      if v == 2 and k in d:
        cn = [k,k]
  if len(cn) == 0:
    for k,v in cd.items():
      if k in d:
        cn.append(k)
  if len(cn) == 1:
    for k,v in cd.items():
      if k != cn[0]:
        cn.append(k)
        break
  elif len(cn) == 0:
    cn = c[0:2]
  c = cn
#print(cn,a[-1])
c = cn+[a[-1]]
cd = collections.Counter(c)
for k,v in cd.items():
  if v == 3:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = [0] * N
last = [0] * N
used = [0] * N

for i in range(3 * N):
  now = A[i] - 1
  count[now] += 1
  if count[now] == 3:
    last[now] = i
  #print(now)  
#print(count, last)    

score = 0
now = [A[0], A[1], A[2], A[3], A[4]]
for i in range(N - 1):
  L = [0] * 5
  for j in range(5):
    L[j] = [last[now[j] - 1], j]
  L = sorted(L)
  #print(L)
  if L[1][0] == L[2][0]:
    if L[0][0] == L[1][0]:
      score += 1
      one, two = L[3][1], L[4][1]
    elif L[2][0] == L[3][0]:
      score += 1
      one, two = L[0][1], L[4][1]
    else:
      one, two = L[0][1], L[1][1]
  elif L[2][0] == L[3][0] and L[3][0] == L[4][0]:
    score += 1
    one, two = L[0][1], L[1][1]
  else:
    one, two = L[0][1], L[1][1]
    
  if i != N - 2:
    now = [A[one], A[two], A[5 + 3 * i], A[6 + 3 * i], A[7 + 3 * i]]
  else:
    now = [A[one], A[two], A[-1]]
  
if now[0] == now[1] and now[1] == now[2]:
  score += 1
    
print(score)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = [0] * N
last = [0] * N
used = [0] * N

for i in range(3 * N):
  now = A[i] - 1
  count[now] += 1
  if count[now] == 3:
    last[now] = i
  #print(now)  
#print(count, last)    

score = 0
now = [A[0], A[1], A[2], A[3], A[4]]
for i in range(N - 1):
  L = [0] * 5
  for j in range(5):
    L[j] = [last[now[j] - 1], j]
  L = sorted(L)
  #print(L)
  if L[1][0] == L[2][0]:
    if L[0][0] == L[1][0]:
      score += 1
      one, two = L[3][1], L[4][1]
    elif L[2][0] == L[3][0]:
      score += 1
      one, two = L[0][1], L[4][1]
    else:
      one, two = L[0][1], L[1][1]
  elif L[2[0]] == L[3][0] and L[3][0] == L[4][0]:
    score += 1
    one, two = L[0][1], L[1][1]
  else:
    one, two = L[0][1], L[1][1]
    
  if i != N - 2:
    now = [A[one], A[two], A[5 + 3 * i], A[6 + 3 * i], A[7 + 3 * i]]
  else:
    now = [A[one], A[two], A[-1]]
  
if now[0] == now[1] and now[1] == now[2]:
  score += 1
    
print(score)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
As = list(map(int, input().split()))

cts = [0] * (N+1)
idxs = [[None]*3 for _ in range(N+1)]

arr = []

for i, a in enumerate(As):
    c = cts[a]
    idxs[a][c] = i
    arr.append((a, c))
    cts[a] += 1

arr.reverse()
ans = 0
for _ in range(N-1):
    cards = [arr.pop() for _ in range(5)]
    ct = Counter([c[0] for c in cards])
    mcn, mcc = ct.most_common()[0]
    if mcc == 3:
        ans += 1
        for c in cards:
            if c[0] != mcn:
                arr.append(c)
    else:
        # 1枚目がすでに捨てられていたら、捨てて良い
        firsts = []
        for c in cards:
            if c[1] == 0:
                firsts.append(c[0])
        # 3枚目が一番近いのを残す
        firsts.sort(key=lambda x: idxs[x][2])
        n = 0
        for f in firsts:
            for c in cards:
                if f == c[0]:
                    arr.append(c)
                    n += 1
                    if n >= 2: break
            if n >= 2: break
        while n < 2:
            arr.append((0, 2))
            n += 1

if arr[0][0] == arr[1][0] == arr[2][0]:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
As = list(map(int, input().split()))

cts = [0] * (N+1)
idxs = [[None]*3 for _ in range(N+1)]

arr = []

for i, a in enumerate(As):
    c = cts[a]
    idxs[a][c] = i
    arr.append((a, c))
    cts[a] += 1

arr.reverse()
ans = 0
for _ in range(N-1):
    cards = [arr.pop() for _ in range(5)]
    ct = Counter([c[0] for c in cards])
    mcn, mcc = ct.most_common()[0]
    if mcc == 3:
        ans += 1
        for c in cards:
            if c[0] != mcn:
                arr.append(c)
    else:
        # 1枚目がすでに捨てられていたら、捨てて良い
        firsts = []
        for c in cards:
            if c[1] == 0:
                firsts.append(c[0])
        # 3枚目が一番近いのを残す
        firsts.sort(key=lambda x: idxs[x][2])
        n = 0
        for f in firsts:
            for c in cards:
                if f == c[0]:
                    arr.append(c)
                    n += 1
                    if n >= 2: break
            if n >= 2: break
        while n < 2:
            arr.append((0, 2))

if arr[0][0] == arr[1][0] == arr[2][0]:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50



def run():
    N, *A = map(int, read().split())
    A = A[::-1]

    dic = defaultdict(lambda:0)
    for a in A:
        dic[a] += 1

    score = 0
    while len(A) > 3:
        #print(A)
        tmp_dic = defaultdict(lambda:0)
        for i in range(5):
            tmp_a = A.pop()
            tmp_dic[tmp_a] += 1
        done = False
        for key, val in tmp_dic.items():
            if val == 3:
                score += 1
                del tmp_dic[key]
                done = True
                dic[key] -= 3
                break
            elif val > 3:
                score += 1
                tmp_dic[key] -= val
                done = True
                dic[key] -= 3
                break

        if not done:
            lis = []
            for key in tmp_dic.keys():
                lis.append((dic[key], key))
            lis = sorted(lis, key = lambda x:x[0])
            cnt = 0
            #print(lis)
            for _, key in lis:
                if 3 - cnt > tmp_dic[key]:
                    cnt += tmp_dic[key]
                    del tmp_dic[key]
                else:
                    tmp_dic[key] -= 3-cnt
                    cnt = 3
        for key, val in tmp_dic.items():
            for _ in range(val):
                A.append(key)
    if A[0] == A[1] and A[1] == A[2]:
        score += 1

    print(score)


if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
'''
Created on 2020/08/22

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  ans=0
  N=int(pin())
  A=list(map(int,pin().split())) 
  for i in range(0,N-1,3):
    l=[A[i],A[i+1],A[i+2],A[i+3],A[i+4]]
    r=list(set(l))
    maxnum=0
    cnt=0
    for j in r:
      t=l.count(j)
      if t>maxnum:
        maxnum=j 
        cnt=t
    if cnt>=3:
      for k in range(3):
        l.remove(maxnum)
      A=l+A[i+5:]
      ans+=1
    elif cnt==2:
      A=[maxnum]*2+A[i+5:]
    else:
      A=A[i+2:]
  if A[-1]==A[-2] and A[-2]==A[-3]:
    print(ans+1)
  else:
    print(ans)
  return 
main()
#絶対に違う自信がある

Submission status: Runtime Error

Solution code:
from functools import lru_cache

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

# O(N^3), should TLE

@lru_cache(maxsize=None)
def dp(a, b, i):
    # Best you can do with [a] + [b] + A[i:]
    # Where len(A[i:]) is 3 * K - 5
    assert (3 * N - i) % 3 == 1
    assert a <= b
    if i == 3 * N - 1:
        return int(a == b == A[-1])
    best = 0
    temp = [a] + [b] + A[i : i + 3]
    assert len(temp) == 5
    for x in temp:
        if temp.count(x) >= 3:
            # If found any triple, alway take the points
            for j in range(3):
                temp.remove(x)
            assert len(temp) == 2
            if temp[0] > temp[1]:
                temp[1], temp[0] = temp[0], temp[1]
            best = 1 + dp(temp[0], temp[1], i + 3)
            break
    else:
        # keep any two
        temp.sort()
        for j in range(5):
            for k in range(j + 1, 5):
                best = max(best, dp(temp[j], temp[k], i + 3))
    return best


for i in reversed(range(2, 3 * N, 3)):
    for a in range(1, N + 1):
        for b in range(a, N + 1):
            dp(a, b, i)

print(dp(A[0], A[1], 2))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    x = a[-1]
    cnt = [0]*(n+1)
    for i in a:
        cnt[i] += 1
    lis = []
    for i in a[::-1]:
        if cnt[i] >= 3:
            lis.append(i)
            cnt[i] = 0
    ans = 0
    for i in range(0,3*n-3,3):
        cnt = [0]*(n+1)
        l = i
        r = i+5
        for x in a[l:r]:
            cnt[x] += 1
            if cnt[x] >= 3:
                keep = []
                ans += 1
                for y in a[l:r]:
                    if y != x:
                        keep.append(y)
                if len(keep) < 2:
                    keep += [x]*(2-len(keep))
                break
        else:
            keep = []
            for y in lis:
                if cnt[y]:
                    keep += [y]*cnt[y]
        a[i+3] = keep[0]
        a[i+4] = keep[1]
    if a[-3] == a[-2] == a[-1]:
        ans += 1
    print(ans)
    return

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

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    x = a[-1]
    cnt = [0]*(n+1)
    for i in a:
        cnt[i] += 1
    lis = []
    for i in a[::-1]:
        if cnt[i] >= 3:
            lis.append(i)
            cnt[i] = 0
    ans = 0
    for i in range(0,2*n-1,3):
        cnt = [0]*(n+1)
        l = i
        r = i+5
        for x in a[l:r]:
            cnt[x] += 1
            if cnt[x] >= 3:
                keep = []
                ans += 1
                for y in a[l:r]:
                    if y != x:
                        keep.append(y)
                if len(keep) < 2:
                    keep += [x]*(2-len(keep))
                break
        else:
            keep = []
            for y in lis:
                if cnt[y]:
                    keep += [y]*cnt[y]
        a[i+3] = keep[0]
        a[i+4] = keep[1]
    if a[-3] == a[-2] == a[-1]:
        ans += 1
    print(ans)
    return

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

Submission status: Runtime Error

Solution code:
N = int(input())
cards = list(map(int,input().split()))
card
points = 0
for _ in range(N-1):
        five_cards = cards[:5]
        five_cards = sorted(five_cards,key=five_cards.count,reverse=True)
        if five_cards.pop(0) == five_cards.pop(0) == five_cards.pop(0):
            points += 1
        cards = five_cards+cards[5:]
if len(set(cards))==1:
        points += 1
print(points)

Submission status: Runtime Error

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
c = 0
for i in range(n-2):
  if l[i] == i[i+1] == l[i+2]:
    c += 1
print(c)