TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2139
  • Problem
  • P2139鸡蛋染色
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

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

    Input Format

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

    Output Format

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

    Sample Input

    样例1:
    2
    1 999
    999 1

    样例2:
    3
    400 600
    400 600
    400 600

    Sample Output

    样例1:
    AG

    样例2:
    AAG


    Source  【Codeforces Round #173 (Div. 2) 】