P3675 小清新提交答案题

    • 1通过
    • 110提交
  • 题目提供者fjzzq2002
  • 标签 模拟退火 背包 遗传 洛谷原创 Special Judge 提交答案
  • 难度 尚无评定
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    这是一道提交答案题。

    相信大家都玩过黄金矿工这款游戏吧!不过如果没有玩过建议赛后再玩。

    这道题与原游戏有一些不同,请仔细阅读规则。

    将矿区抽象为一个2s*s的矩形,以左上角作为坐标原点,向右为x轴正方向,向下为y轴正方向,建立平面直角坐标系。

    矿工开始在(s,0),矿工可以在x轴一部分:原点与(2s,0)的连线(线段)上随意移动。

    把矿区中的黄金等物品抽象为坐标系中此矩形内一个个不相交的圆,每个圆有一个价值,可正可负。

    这里我们将抓取的过程抽象为以矿工为一端射出一条射线,如果不与任何圆相交(相切不算),那么这次抓取是无效的;否则矿工将会抓取到相交的圆中最早碰到的一个(较近的交点与矿工距离最近的一个圆)。

    抱歉这幅图上的文字标错了,应为(2s,0),懒得重画了

    黄金矿工这款游戏的目的是在规定时间上抓取价值尽量高的物品。

    移动与抓取都需要时间,移动1单位距离需要花费k1的时间,将一次有效抓取的距离定义为抓取到的圆与射线较近的交点与矿工的距离,有效抓取每1单位距离需要花费k2的时间(无效抓取将会被忽略)。

    你将要操纵这位矿工,给出移动和抓取指令,使得获取的价值尽量大。如果某次操作后你所用的总时间超过了规定时限,这次及以后操作将会被忽略。详细格式可见输出描述。

    由于矿工比较懒,矿工只接受2n次操作(n为圆的个数,无论是否是无效抓取),多余操作将被忽略。

    判定时的eps为$10^{-7}$。若你射出的射线与圆两交点的距离不超过该eps,那么将不会判定为相交。若你的用时与时限的差不超过eps,那么也不会被判定为超过时限。

    由于这是提交答案题,我们会提供输入数据、评分参数和checker下载,链接在最后。

    输入输出格式

    输入格式:

    第一行五个数s、t、k1、k2、n,s、k1、k2见题面,t为规定时限,n为圆的个数。

    以下n行每行四个数$x_i,y_i,r_i,v_i$,分别表示编号为i的圆圆心x坐标、圆心y坐标、半径和价值。

    n、$v_i$一定为整数,其余量可能为实数。

    输出格式:

    若干行,表示你的操作。

    每行开头一个字符为m或g,然后一个空格。(m=move,g=grab)

    如果字符是m,接下来应该接一个实数p,$0 \leq p \leq 2s$,表示将矿工移动到(p,0)。

    如果字符是g,接下来应该接一个实数a,$0.2 \leq a \leq 179.8$,表示抓取的射线与x轴正方向夹角为a°。

    这两个实数建议保留10位小数。

    超过时限和超过2n次的操作将被忽略。如果在输出文件中包含不合法信息该点可能会直接被判为0分。

    输入输出样例

    输入样例#1: 复制
    4 233 1 1 2
    3 3 1 1
    5 2 1 -1
    输出样例#1: 复制
    m 1
    g 45
    (仅为一种可能输出)

    说明

    样例解释

    开始矿工在(4,0),移动到(1,0),花费3时间。

    如图矿工发射出一条射线,抓取到第一个圆,获取到1价值,花费$2\sqrt{2}$时间。

    当然这不是花费时间最小的解,存在其他解。

    评分标准

    对于每个点,如果你的输出不符合输出格式,得0分。

    否则,假设你获得的价值为a,每个点有三个评分参数,标准答案b、一个实数w、一个0或1的整数f。

    若$a<0$,你将获得0分。

    若$a>b$,你将获得$10+f$分(这意味着部分点你可能会获得11分)。

    否则你将获得$\lfloor 10(\frac{a}{b})^w\rfloor$分。($\lfloor x \rfloor$表示不大于x的最大整数)

    如何测试和提交

    下载下发文件(链接: http://pan.baidu.com/s/1eSh2UH0 密码: hz8d),里面有mine1.in~mine10.in、mine1.ans~mine10.ans和checker.cpp、checker_win32.exe、tester.bat、testlib.h,in、ans和checker.cpp与洛谷上实际测试使用的完全相同。windows以外的系统,可以自行编译checker.cpp。

    测试时在同一目录下放置mine1.out~mine10.out,对于windows用户,运行tester.bat,会自动调用checker_win32.exe返回每个点的结果。对于其它系统的用户,手动调用checker mine1.in mine1.out mine1.ans即可返回第一个点的评测结果,其它点同理。

    checker会返回形如points 0.9 Your ans is aaa, done bbb attempts, time used ccc, ddd remained的结果,表示这个点你可以获得9分,你得到的价值是aaa,成功进行了开始bbb个操作,用了ccc的时间,剩下ddd的时间。如果剩下的时间为负,表示最后一个(没有成功执行的)操作超时了。

    提交时可以直接将mine1.out~mine10.out打包上传,一个一个点输入提交亦可。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。