300738: CF140B. New Year Cards

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

New Year Cards

题意翻译

亚历山大开始回复朋友们写的新年问候。亚历山大有 $n$ 个朋友,每个朋友都给亚历山大写了一张新年贺卡。我们按朋友给亚历山大发信的先后顺序来将朋友从 $1$ 到 $n$ 编号。我们以同样的方式来对这些卡片进行编号,例如第 $2$ 个朋友的卡片的编号为 $2$ 。 亚历山大也寄贺卡,但他喜欢使用以前朋友发给他的卡片(一开始,亚历山大没有贺卡)。他寄贺卡遵守两条原则: $1.$ 他不会把该朋友邮寄给他的贺卡再寄回去。 $2.$对于当前他所拥有的贺卡,他只会选择他最喜欢的卡给朋友。 亚历山大计划给每一个朋友发送一张卡片(同一张牌可以多次利用)。 亚历山大以及他的朋友都有偏好列表(即喜欢的卡牌列表),表格从 $1$ 到 $n$ 。数字越小,这张卡越受喜欢。 你的任务是找到寄卡片的时间表,以确定亚历山大寄贺卡的时间,以取悦他的朋友(则他的朋友尽可能多的收到自己喜欢的贺卡)。 需要注意的是,亚历山大不会自由选择发送哪张卡,但他始终严格遵守这两条规则。 #### 输入格式 先输入一个数 $n$( $2 \le n \le 300$ ),即亚历山大的朋友数量(卡片数量), 下一行包括他的朋友的偏好列表。每行(每个列表)由从 $1$ 到 $n$ 的不同整数组成。最后一行是相同格式的亚历山大的偏好列表。 #### 输出格式 输出 $n$ 个由空格分割的数字。第 $i$ 个数字是朋友的编号,亚历山大在给第 $i$ 位朋友寄卡片之前收到了他的卡片。如果有几种解决方案,请输出其中任何一种。

题目描述

As meticulous Gerald sets the table, Alexander finished another post on Codeforces and begins to respond to New Year greetings from friends. Alexander has $ n $ friends, and each of them sends to Alexander exactly one e-card. Let us number his friends by numbers from $ 1 $ to $ n $ in the order in which they send the cards. Let's introduce the same numbering for the cards, that is, according to the numbering the $ i $ -th friend sent to Alexander a card number $ i $ . Alexander also sends cards to friends, but he doesn't look for the new cards on the Net. He simply uses the cards previously sent to him (sometimes, however, he does need to add some crucial details). Initially Alexander doesn't have any cards. Alexander always follows the two rules: 1. He will never send to a firend a card that this friend has sent to him. 2. Among the other cards available to him at the moment, Alexander always chooses one that Alexander himself likes most. Alexander plans to send to each friend exactly one card. Of course, Alexander can send the same card multiple times. Alexander and each his friend has the list of preferences, which is a permutation of integers from $ 1 $ to $ n $ . The first number in the list is the number of the favorite card, the second number shows the second favorite, and so on, the last number shows the least favorite card. Your task is to find a schedule of sending cards for Alexander. Determine at which moments of time Alexander must send cards to his friends, to please each of them as much as possible. In other words, so that as a result of applying two Alexander's rules, each friend receives the card that is preferred for him as much as possible. Note that Alexander doesn't choose freely what card to send, but he always strictly follows the two rules.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 2<=n<=300 $ ) — the number of Alexander's friends, equal to the number of cards. Next $ n $ lines contain his friends' preference lists. Each list consists of $ n $ different integers from $ 1 $ to $ n $ . The last line contains Alexander's preference list in the same format.

输出格式


Print $ n $ space-separated numbers: the $ i $ -th number should be the number of the friend, whose card Alexander receives right before he should send a card to the $ i $ -th friend. If there are several solutions, print any of them.

输入输出样例

输入样例 #1

4
1 2 3 4
4 1 3 2
4 3 1 2
3 4 2 1
3 1 2 4

输出样例 #1

2 1 1 4

说明

In the sample, the algorithm of actions Alexander and his friends perform is as follows: 1. Alexander receives card $ 1 $ from the first friend. 2. Alexander sends the card he has received (at the moment he only has one card, and therefore it is the most preferable for him) to friends with the numbers $ 2 $ and $ 3 $ . 3. Alexander receives card $ 2 $ from the second friend, now he has two cards — $ 1 $ and $ 2 $ . 4. Alexander sends a card to the first friend. Despite the fact that Alexander likes card $ 1 $ more, he sends card $ 2 $ as he cannot send a friend the card sent by that very friend. 5. Alexander receives card $ 3 $ from the third friend. 6. Alexander receives card $ 4 $ from the fourth friend. 7. Among the cards Alexander has number $ 3 $ is his favorite and he sends it to the fourth friend. Note that Alexander can send cards to multiple friends at a time (in this case the second and the third one). Alexander can send card $ 3 $ to the fourth friend after he receives the third card or after he receives the fourth card (both variants are correct).

Input

题意翻译

亚历山大开始回复朋友们写的新年问候。亚历山大有 $n$ 个朋友,每个朋友都给亚历山大写了一张新年贺卡。我们按朋友给亚历山大发信的先后顺序来将朋友从 $1$ 到 $n$ 编号。我们以同样的方式来对这些卡片进行编号,例如第 $2$ 个朋友的卡片的编号为 $2$ 。 亚历山大也寄贺卡,但他喜欢使用以前朋友发给他的卡片(一开始,亚历山大没有贺卡)。他寄贺卡遵守两条原则: $1.$ 他不会把该朋友邮寄给他的贺卡再寄回去。 $2.$对于当前他所拥有的贺卡,他只会选择他最喜欢的卡给朋友。 亚历山大计划给每一个朋友发送一张卡片(同一张牌可以多次利用)。 亚历山大以及他的朋友都有偏好列表(即喜欢的卡牌列表),表格从 $1$ 到 $n$ 。数字越小,这张卡越受喜欢。 你的任务是找到寄卡片的时间表,以确定亚历山大寄贺卡的时间,以取悦他的朋友(则他的朋友尽可能多的收到自己喜欢的贺卡)。 需要注意的是,亚历山大不会自由选择发送哪张卡,但他始终严格遵守这两条规则。 #### 输入格式 先输入一个数 $n$( $2 \le n \le 300$ ),即亚历山大的朋友数量(卡片数量), 下一行包括他的朋友的偏好列表。每行(每个列表)由从 $1$ 到 $n$ 的不同整数组成。最后一行是相同格式的亚历山大的偏好列表。 #### 输出格式 输出 $n$ 个由空格分割的数字。第 $i$ 个数字是朋友的编号,亚历山大在给第 $i$ 位朋友寄卡片之前收到了他的卡片。如果有几种解决方案,请输出其中任何一种。

加入题单

上一题 下一题 算法标签: