Easy Assembly

题意翻译

### 题目描述 Emma 喜欢玩积木，她有若干相同大小的、标有不同数字的积木，将它们竖直堆放。 现在，她可以进行以下操作： - 分裂：从将一堆积木（数量大于 $1$）的顶端拿出若干块，按原来的顺序放在地上形成一堆新的积木。操作后积木堆数加一； - 合并：将一堆积木全部按原来的顺序全部堆到另一堆积木的顶端。操作后积木堆数减一。 她想让所有木块形成一堆且积木上的数字由顶端到底端升序排列。请求出最小操作次数。 ### 输入格式 第一行一个整数 $n$（$1\le n\le 10\,000$）表示初始积木堆数。 接下来 $n$ 行，第 $i$ 行开始一个整数 $k_i$（$k_i\ge 1$；$\sum\limits_{i=1}^n k_i\le 10\,000$）表示该堆木块数量。接下来 $k_i$ 个整数 $b_{i,j}$（$1\le b_{i,j}\le 10^9$），依次表示从顶端到底端的积木上的数字。 保证所有积木上的数字不同。 ### 输出格式 一行两个整数 $s$ 和 $c$，表示在总操作数最小的情况下分裂和合并操作的次数。 ### 样例解释 四张图依次是：初始状态、将最后一堆分裂、将第二堆合并入第一堆、将第一堆合并入第二堆。 $\qquad\qquad$$\qquad\qquad$$\qquad\qquad$

题目描述

Emma loves playing with blocks. She has several cubic blocks of the same size that are numbered with distinct integers written on them. She assembles towers from those blocks by stacking them vertically. A configuration of her game is a set of towers that she has assembled from the blocks. Emma can perform two kinds of operations on a configuration of towers: - Split any tower with more than one block in it by taking any number of blocks from the top of the tower and moving them to a new tower keeping their order, so that the top block of the old tower becomes the top block of the new tower. As a result of this operation, the number of towers increases by one. - Combine any two towers by moving blocks from one tower on top of the other tower in the same order. As a result of this operation, the number of towers decreases by one. Emma wants to stack all the blocks into a single tower so that all blocks come in order sorted by the numbers — from the block with the minimal number at the top to the block with the maximal number at the bottom. Emma wants to do as little of splitting and combining operations as possible. Your task is to find the minimal number of operations she has to make and output how many splits and combines are needed.

输入输出格式

输入格式

The first line of the input file contains an integer $ n $ ( $ 1 \le n \le 10\,000 $ ) — the number of towers in the initial configuration. Next $ n $ lines describe towers. Each tower $ i $ is described by a line that starts with the number $ k_i $ ( $ k_i \ge 1 $ ; $ \sum_1^n{k_i} \le 10\,000 $ ) — the number of blocks in the tower, followed by $ k_i $ numbers $ b_{i,j} $ ( $ 1 \le b_{i,j} \le 10^9 $ ) — numbers written on the blocks in the $ i $ -th tower, listed from top to bottom. All block numbers listed in the input are different.

输出格式

Output a line with two integers $ s $ and $ c $ — the number of split and combine operations Emma should make to get a single tower with blocks sorted by their numbers, so that the total number of operations is minimized.

输入输出样例

输入样例 #1

2
3 3 5 8
2 9 2

输出样例 #1

1 2

说明

The example needs the following operations (1 split and 2 combines). InitialSplit lastCombined 2nd onto 1stCombined 1st onto 2nd

题目大意：
Emma 喜欢玩积木，她有一些相同大小但标有不同的数字的积木，并可以将它们垂直堆叠成塔。她可以进行两种操作：分裂和合并。分裂操作是指从一堆多于一个积木的塔顶取出一部分积木，保持原有顺序放到旁边形成新的一堆；合并操作是指将一堆积木按原顺序放到另一堆的顶部。目标是使得所有积木合并成一堆，且积木上的数字从塔顶到塔底升序排列。需要求出完成目标所需的最小操作次数以及分裂和合并各需要多少次。

输入数据格式：
第一行是一个整数 \( n \)（\( 1 \le n \le 10,000 \)），表示初始积木塔的数量。
接下来 \( n \) 行，每行首先是一个整数 \( k_i \)（\( k_i \ge 1 \)），表示该塔的积木数量，然后是 \( k_i \) 个整数 \( b_{i,j} \)（\( 1 \le b_{i,j} \le 10^9 \)），表示从塔顶到底部的积木上的数字。保证所有积木上的数字不同。

输出数据格式：
输出一行两个整数 \( s \) 和 \( c \)，分别表示分裂和合并操作的最小次数。

样例解释：
四个步骤分别是：初始状态、分裂最后一堆、将第二堆合并到第一堆、将第一堆合并到第二堆。题目大意： Emma 喜欢玩积木，她有一些相同大小但标有不同的数字的积木，并可以将它们垂直堆叠成塔。她可以进行两种操作：分裂和合并。分裂操作是指从一堆多于一个积木的塔顶取出一部分积木，保持原有顺序放到旁边形成新的一堆；合并操作是指将一堆积木按原顺序放到另一堆的顶部。目标是使得所有积木合并成一堆，且积木上的数字从塔顶到塔底升序排列。需要求出完成目标所需的最小操作次数以及分裂和合并各需要多少次。 输入数据格式： 第一行是一个整数 \( n \)（\( 1 \le n \le 10,000 \)），表示初始积木塔的数量。 接下来 \( n \) 行，每行首先是一个整数 \( k_i \)（\( k_i \ge 1 \)），表示该塔的积木数量，然后是 \( k_i \) 个整数 \( b_{i,j} \)（\( 1 \le b_{i,j} \le 10^9 \)），表示从塔顶到底部的积木上的数字。保证所有积木上的数字不同。 输出数据格式： 输出一行两个整数 \( s \) 和 \( c \)，分别表示分裂和合并操作的最小次数。 样例解释： 四个步骤分别是：初始状态、分裂最后一堆、将第二堆合并到第一堆、将第一堆合并到第二堆。