TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2139
  • 题目
  • P2139【Codeforces Round #173 (Div. 2) 】鸡蛋染色
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    比特兰人都很怪异,他们有一些奇怪的习俗。
    为准备“比特兰狂欢节”,J叔叔让G和A去把n个鸡蛋染成彩色。孩子们很高兴,因为他们可以得到一些报酬。
    J叔叔要他们给出酬劳的报价,G给出了染每只鸡蛋的价格,A也给出了他染每只鸡蛋的价格,结果G和A的n只鸡蛋报价总和恰好是1000块。
    J叔叔想把这些鸡蛋分给两个孩子染色,但他希望支付给A的酬劳总额与支付给G的总额差别不超过500块。

    请问J叔叔期望的分配方案是否可行呢?

    输入格式

    第一行,一个整数n (1 ≤ n ≤ 10^6),表示总共有n只鸡蛋
    接下来n行,每行两个整数ai 和 gi each (0 ≤ ai, gi ≤ 1000; ai + gi = 1000),ai表示A对第i只鸡蛋的报价,gi表示G对第i只鸡蛋的报价
    若有多个方案,输出字典序最小的一种

    输出格式

    如果找不到可行的方案,输出-1
    否则打印出分配的方案:一行,n个字母,依次对应n只鸡蛋的涂色者,若第i只鸡蛋是A涂的,打印"A",否则打印"G"

    样例输入

    样例1:
    2
    1 999
    999 1

    样例2:
    3
    400 600
    400 600
    400 600

    样例输出

    样例1:
    AG

    样例2:
    AAG