P3536 [POI2012]BON-Vouchers

    • 22通过
    • 77提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 数论,数学 POI 2012
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    Byteasar的糖果店有很美味的焦糖糖果卖。

    对于每一个正整数C,保证有且仅有一个包裹包含c个糖果。

    为了鼓励顾客们购买美味的糖果,Byteasar制作了m个代金券,并且保证每个包裹里都最多只有1张代金券。(一个包裹里有可能没有代金券)

    Byteasar的购物狂欢节将于下周在Byteburg举行,并且将持续n天:在狂欢节的第k天会举办一个有a[k]个客人参加的party。

    Byteasar对于第k天的早晨每个客人都会买东西这件事总是有着蜜汁自信(我也不知道为什么)。在第n天里,包含y×a[n]个糖果的包裹能够依次卖出(x为正整数)。举个栗子:如果n=2,a1=4,a2=2,那么在购物狂欢节的第一天,含有4(即a[1])×1,4×2,4×3,4×4……个糖果的包裹能够卖出去,在第二天含有2(即a[2])×1个和2×3……个糖果的包裹能够卖出去。(因为2×2的包裹第一天已经被买走了)

    现在Byteasar想要知道哪些顾客会拿到代金券。

    他想要你编写一个程序来帮他解决问题。

    输入输出格式

    输入格式:

    第一行输入一个正整数m ( 1≤m≤1 000 000),代表代金券的张数。

    接下来m行的第k行有一个正整数b[k],代表被Byteasar放入了代金券的包裹中的糖果数量。

    数据保证以单调递增的形式给出。

    接下来一行输入一个整数n,表示购物狂欢节的天数。

    接下来n行的第k行有一个正整数a[k]表示参加第k天购物狂欢节的客人数量。

    保证至少有50%以上的测试点所有的数值都不会大于5000(所以……这是暴力分?)

    输出格式:

    第一行输出一个整数z表示有z个含有代金券的包裹被售出。

    接下来z行以单调递增的形式给出拿到代金券的客人编号。

    每天的顾客都从1开始编号,一直到a[k](即不同天数的顾客之间的编号互不影响,都从1开始编号)

    由 @姜澜 提供翻译

    题目描述

    The candy shop owned by Byteasar sells delicious caramel candy.

    For every positive integer $c$ there is exactly one package that contains $c$ candies; currently no new deliveries are expected.

    To encourage customers to buy the sweets, Byteasar has planted $m$ vouchers for an annual supply of chocolate into some packages, making sure to put at most one voucher in each package.

    The carnival starts next week in Byteburg, and it will last $n$ days; on the $k$ -th day of the carnival a party with $a_k$ guests will be held.

    Byteasar is confident that on the $k$ -th day's morning each of those guests is going to buy, in his own store, the smallest package of candy available whose content can be equally distributed between the party guests. For example, if $n=2$ , $a_1=4$ , $a_2=2$ , then on the first day of the carnival he expects to sell the packages containing four, eight, twelve, and sixteen candies, selling those with two and six candies on the second day.

    Now he is wondering which customers will end up with the packages holding the vouchers.

    He has asked you to write a program that will determine this for him.

    定义n个数为幸运数字,一共有n批人,设第i批人有x个,则它们会依次取走余下的x的倍数中最小的x个,问哪些人去走了幸运数字

    输入输出格式

    输入格式:

    On the first line of the standard input there is a single integer $m$ ( $1\le m\le 1\ 000\ 000$ ) that denotes the number of vouchers.

    The $k$ -th of the $m$ lines that follow holds an integer $b_k$ ( $1\le b_k\le 1\ 000\ 000$ )denoting the size (i.e., the number of candies inside) of a package in which Byteasar has placed the $k$ -th voucher.

    These numbers are given in an increasing order.

    Then the next line contains a single integer $n$ ( $1\le n\le 1\ 000\ 000$ ) that denotes the number of carnival days.

    The $k$ -th of the $n$ lines that follow holds an integer $a_k$ ( $1\le a_k\le 1\ 000\ 000$ )denoting the number of guests attending the $k$ -th party.

    You may assume that in tests worth at least 50% of the total points none of the numbers given on the input exceeds $5\ 000$ .

    输出格式:

    In the first line of the standard output your program should print an integer $z$ - the number of packages with vouchers sold.

    The following $z$ lines should specify the numbers of those customers who bought a package with a voucher, in an increasing order.

    The customers are numbered from $1$ in the order of their purchases.

    输入输出样例

    输入样例#1: 复制
    4
    1
    6
    8
    16
    3
    4
    2
    4
    输出样例#1: 复制
    3
    2
    4
    6
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。