CF914B.Conan and Agasa play a Card Game

普及-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Edogawa Conan got tired of solving cases, and invited his friend, Professor Agasa, over. They decided to play a game of cards. Conan has n cards, and the i-th card has a number a__i written on it.

They take turns playing, starting with Conan. In each turn, the player chooses a card and removes it. Also, he removes all cards having a number strictly lesser than the number on the chosen card. Formally, if the player chooses the i-th card, he removes that card and removes the j-th card for all j such that a__j < a__i.

A player loses if he cannot make a move on his turn, that is, he loses if there are no cards left. Predict the outcome of the game, assuming both players play optimally.

江户川柯南厌倦了破案,便邀请了他的朋友阿笠博士来家里做客。他们决定玩一个扑克牌游戏。柯南有 nn 张牌,其中第 ii 张牌上写有一个数字 aia_i。

两人轮流进行游戏,柯南先手。在每一轮中,当前玩家选择一张牌并将其移除;同时,他还必须移除所有数字严格小于所选牌上数字的牌。形式化地说,若玩家选择了第 ii 张牌,则他需移除该牌,并对所有满足 aj<aia_j < a_i 的 jj,也移除第 jj 张牌。

若轮到某位玩家时已无牌可选(即牌堆为空),则该玩家判负。假设双方均以最优策略进行游戏,请预测游戏的结果。

输入格式

The first line contains an integer n (1 ≤ n ≤ 105) — the number of cards Conan has.

The next line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 105), where a__i is the number on the i-th card.

第一行包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5)—— 表示康南拥有的卡片数量。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤1051 \leq a_i \leq 10^5),其中 aia_i 表示第 ii 张卡片上的数字。

输出格式

If Conan wins, print "Conan" (without quotes), otherwise print "Agasa" (without quotes).

如果柯南获胜,输出 “Conan”(不带引号),否则输出 “Agasa”(不带引号)。

输入输出样例

  • 输入#1

    3
    4 5 7

    输出#1

    Conan
  • 输入#2

    2
    1 1

    输出#2

    Agasa

说明/提示

In the first example, Conan can just choose the card having number 7 on it and hence remove all the cards. After that, there are no cards left on Agasa's turn.

In the second example, no matter which card Conan chooses, there will be one one card left, which Agasa can choose. After that, there are no cards left when it becomes Conan's turn again.

在第一个例子中,柯南只需选择数字为 7 的卡片,即可移除所有卡片。此后,轮到阿笠博士时,桌上已无剩余卡片。

在第二个例子中,无论柯南选择哪张卡片,都会剩下一张卡片,阿笠博士可以将其选走。此后,当再次轮到柯南时,桌上已无剩余卡片。

输入解题思路,AI测评打分。不知道怎么写?

首页