아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

JOI 깃발

시간 제한3초메모리 제한512 MB

요약
이미 일부 글자가 적힌 2^K × 2^K 격자를 사분면이 재귀 규칙을 따르는 JOI 깃발로 완성할 때, 고쳐야 하는 글자 수의 최솟값을 구한다.
난이도

어려움10점 중 8점

유형
분할 정복, 동적 계획법, 재귀, 구현
정답자
아직 제출이 없습니다

문제

당신은 일본정보올림피아드의 새 깃발로, 레벨 K의 JOI Flag를 만들기로 했다. 다만,

  • 레벨 0의 JOI Flag는 1 × 1 크기의 칸으로 이루어진 깃발이고, J, O, I 중 하나의 문자가 적혀 있다.
  • 정수 m > 0에 대해, 레벨 m의 JOI Flag는 2m × 2m 크기의 칸으로 이루어진 깃발이고, 각 칸에 J, O, I 중 하나의 문자가 적혀 있는 것 가운데 다음 조건을 만족하는 것이다. 칸 전체를 2m−1 × 2m−1 크기의 정사각형 4개로 나눌 때, 레벨 m − 1의 JOI Flag, J만 적힌 칸으로 이루어진 부분, O만 적힌 칸으로 이루어진 부분, I만 적힌 칸으로 이루어진 부분의 4개 부분으로 나뉜다.

예를 들어,

OIJJ
JJJJ
OOII
OOII

는 레벨 2의 JOI Flag이다. 또,

IIIIIIOO
IIIIIIOO
IIIIJOJJ
IIIIOIJJ
JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO

는 레벨 3의 JOI Flag이다.

당신의 손에는 몇 개의 칸에 J, O, I 중 하나의 문자가 적혀 있는 2K × 2K 크기의 깃발이 있다.

당신은 이 깃발에 몇 개의 문자를 더 적거나, 이미 깃발에 적혀 있는 몇 개의 문자를 고쳐서 레벨 K의 JOI Flag를 완성하기로 했다. 문자가 적혀 있지 않은 칸에는 비용 0으로 문자를 적을 수 있지만, 문자가 적힌 칸의 문자를 바꾸려면 비용 1이 든다.

레벨 K의 JOI Flag를 완성하는 데 필요한 비용의 최솟값을 구하고 싶다.

당신의 손에 있는 깃발의 정보가 주어졌을 때, 레벨 K의 JOI Flag를 완성하는 데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

표준 입력에서 다음 입력을 읽는다.

  • 1번째 줄에는 정수 K, N이 공백을 구분으로 적혀 있다. K는 JOI Flag의 레벨을, N은 문자가 적힌 칸의 개수를 각각 나타낸다. 문자에는 1, 2, ···, N의 번호가 붙어 있다.
  • 이어지는 N개 줄에는 문자의 정보가 적혀 있다. i + 1번째 줄에는 Xi, Yi, Ci가 공백을 구분으로 적혀 있다. 이것은 문자 Ci가 왼쪽에서 Xi번째 열, 위에서 Yi번째 행에 적혀 있음을 나타낸다.

출력

표준 출력에, 레벨 K의 JOI Flag를 만드는 데 필요한 비용의 최솟값을 나타내는 정수를 1줄로 출력하라.

제한

  • 1 ≤ K ≤ 30 JOI Flag의 레벨
  • 1 ≤ N ≤ 1 000 JOI Flag에 적혀 있는 문자의 개수
  • 1 ≤ Xi ≤ 2K i번째 문자가 적혀 있는 열 번호
  • 1 ≤ Yi ≤ 2K i번째 문자가 적혀 있는 행 번호
  • Ci는 J, O, I 중 하나이다.
  • 순서쌍 (Xi, Yi)는 모두 다르다.

예제2

  1. 예제 1

    입력
    2 10
2 2 J
3 3 I
1 3 I
1 1 O
3 2 J
2 1 I
4 1 O
3 4 I
4 4 O
2 3 O
    예상 출력
    3

  2. 예제 2

    입력
    4 30
16 14 J
2 8 O
10 9 J
10 13 I
6 6 O
11 14 I
1 2 I
3 2 O
3 10 O
1 12 I
4 11 I
9 5 J
15 1 O
12 4 I
16 5 J
10 7 J
3 8 J
4 10 I
4 7 I
2 11 I
2 12 O
15 5 J
15 7 J
6 9 J
5 7 O
14 5 J
12 11 J
15 10 O
13 16 I
13 11 I
    예상 출력
    9