F - Micromasters Certificates


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

The Department of Computer Engineering has provided several micromasters, each containing a curriculum. If a student successfully completes all the courses of a micromaster, he will receive the certificate of that micromaster. A course may be included in the curriculum of several micromasters.

Soroush, who only thinks about getting a certificate and doesn’t care about the type of certificate, wants to get 33 micromasters certificates by taking the minimum possible number of courses. The micromasters curriculums are posted on the bulletin board. Help Soroush reach his goal according to the micromasters curriculums.

ورودی🔗

The input represents a bulletin board. The board consists of at most 400400 rows and 400400 columns. Each micromasters curriculum is encapsulated in a rectangular box. The boundaries of the bulletin board and the curriculum boxes are represented by characters “+”, “-”, and “|” for corners, horizontal sides, and vertical sides, respectively. The curriculum boxes are disjoint (with no characters in common) and each has its own boundary. Each line inside a curriculum box contains at most one course name. Course names consist of alphanumeric and space characters. Course names are not case-sensitive, and spaces do not matter in them. For example, “General math1” and “generalMath 1” are the same. There are at most 5050 curriculum boxes and each box contains at most 3030 courses. It is guaranteed that there are at least 33 boxes on the board and there is at least 11 course in each box.

خروجی🔗

Print a single line containing the minimum number of courses that should be taken by Soroush to get at least 3 certificates.

مثال🔗

ورودی نمونه ۱🔗

+-------------------------------------------------+
|  +-------------------+                          |
|  |Algorithm Design   |   +-------------------+  |
|  |  Programming      |   |PROGRAMMING        |  |
|  |Discrete Structures|   |   Web Prgramming  |  |
|  |   Data Structures |   |                   |  |
|  +-------------------+   | DatabaseDesign    |  |
|                          |Software Test      |  |
|     +--------------+     |     Patterns      |  |
|     |    Python    |     +-------------------+  |
|     +--------------+                            |
|          +------------------------+             |
|          |Programming             |             |
|          |          AI            |             |
|          |    Algorithm     design|             |
|          |Database Design         |             |
|          +------------------------+             |
+-------------------------------------------------+
Plain text

خروجی نمونه ۱🔗

8
Plain text