Code Jam 2010 Round 1B Problem A

简介:

Problem B. Picking Up Chicks

Problem

A flock of chickens are running east along a straight, narrow road. Each one is running with its own constant speed. Whenever a chick catches up to the one in front of it, it has to slow down and follow at the speed of the other chick. You are in a mobile crane behind the flock, chasing the chicks towards the barn at the end of the road. The arm of the crane allows you to pick up any chick momentarily, let the chick behind it pass underneath and place the picked up chick back down. This operation takes no time and can only be performed on a pair of chicks that are immediately next to each other, even if 3 or more chicks are in a row, one after the other.

Given the initial locations (Xi) at time 0 and natural speeds (Vi) of the chicks, as well as the location of the barn (B), what is the minimum number of swaps you need to perform with your crane in order to have at least K of the N chicks arrive at the barn no later than time T?

You may think of the chicks as points moving along a line. Even if 3 or more chicks are at the same location, next to each other, picking up one of them will only let one of the other two pass through. Any swap is instantaneous, which means that you may perform multiple swaps at the same time, but each one will count as a separate swap.

Input

The first line of the input gives the number of test cases, C. C test cases follow. Each test case starts with 4 integers on a line -- N, K, B and T. The next line contains the Ndifferent integers Xi, in increasing order. The line after that contains the N integers Vi. All distances are in meters; all speeds are in meters per second; all times are in seconds.

Output

For each test case, output one line containing "Case #x: S", where x is the case number (starting from 1) and S is the smallest number of required swaps, or the word "IMPOSSIBLE".

Limits

1 ≤ C ≤ 100; 1 ≤ B ≤ 1,000,000,000; 1 ≤ T ≤ 1,000; 0 ≤ Xi < B; 1 ≤ Vi ≤ 100; All the Xi's will be distinct and in increasing order.

Small dataset

1 ≤ N ≤ 10; 0 ≤ K ≤ min(3, N);

Large dataset

1 ≤ N ≤ 50; 0 ≤ K ≤ N;

Sample


Input 

3
5 3 10 5
0 2 5 6 7
1 1 1 1 4
5 3 10 5
0 2 3 5 7
2 1 1 1 4
5 3 10 5
0 2 3 4 7
2 1 1 1 4

Output

Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE


解题思路:一道多叉树水题。跟之前做的电话号码匹配类似,而且更简单。


class Prefix {
    Map<String, Prefix> sub = new HashMap<String, Prefix>();

    int put(String s) {
        if (s.length() == 0)
            return 0;
        int index = s.indexOf('/', 1);
        if (index < 0)
            index = s.length();
        String s1 = s.substring(0, index);
        String s2 = s.substring(index);
        int ret = 0;
        if (!sub.containsKey(s1)) {
            Prefix child = new Prefix();
            sub.put(s1, child);
            ret++;
        }
        return ret + sub.get(s1).put(s2);
    }
}

void run() {
    int C = sc.nextInt();
    for (int c = 1; c <= C; c++) {
        int N = sc.nextInt();
        int M = sc.nextInt();
        Prefix prefix = new Prefix();
        for (int i = 0; i < N; i++) {
            prefix.put(sc.next());
        }
        int count = 0;
        for (int i = 0; i < M; i++) {
            count += prefix.put(sc.next());
        }
        System.out.println(String.format("Case #%d: %d", c, count));
    }
}


目录
相关文章
|
缓存 算法
07、Netty学习笔记—(聊天业务优化:参数调优)(二)
07、Netty学习笔记—(聊天业务优化:参数调优)(二)
07、Netty学习笔记—(聊天业务优化:参数调优)(二)
|
缓存 Ubuntu Linux
LXC (Linux 虚拟环境)简单介绍
LXC是Linux containers的简称,操作系统级别的虚拟化技术。它可以在操作系统层次上为进程提供的虚拟的执行环境。一个虚拟的执行环境被称为一个容器(container)。可以为容器绑定特定的cpu和memory节点,分配特定比例的cpu时间、IO时间,限制可以使用的内存大小(包括内存和是swap空间),提供device访问控制,提供独立的namespace(网络、pid、ipc、mnt、uts)。
1339 0
LXC (Linux 虚拟环境)简单介绍
|
6月前
|
Ubuntu 安全 网络安全
在Ubuntu系统下使用vsftpd配置FTP服务器的步骤
以上就是在Ubuntu系统下使用vsftpd配置FTP服务器的步骤。这些步骤都是基础的,但足够让你建立一个简单的FTP服务器。如果你需要更高级的功能,例如SSL加密、虚拟用户等,你可能需要进一步研究vsftpd的配置选项。
346 13
|
弹性计算 安全
停止使用云服务通常需要遵循以下步骤
停止使用云服务通常需要遵循以下步骤
820 2
|
人工智能 搜索推荐 UED
还没排上SearchGPT?比Perplexity更好用的国产开源平替了解一下?
【8月更文挑战第24天】近日发布的一项研究成果提出了一种革新性的信息检索系统——MindSearch,该系统通过模仿人脑思维方式,有效解决了传统信息检索方法面对复杂查询时的不足。MindSearch利用多代理框架,将用户查询拆解成子问题逐步扩展查询图谱,实现复杂查询的精准定位;通过多层次信息检索,整合不同网页中的相关数据,提高信息提取的准确率;并且能高效处理大规模网页,3分钟内即可检索300多个网页。实验显示,MindSearch不仅提升了响应的深度与广度,还在封闭及开放式问答中表现出色,更符合用户的偏好。不过,MindSearch仍面临查询意图理解、噪音处理及可扩展性等方面的挑战。
190 4
|
机器学习/深度学习 算法
XGBoost中正则化的9个超参数
本文探讨了XGBoost中多种正则化方法及其重要性,旨在通过防止过拟合来提升模型性能。文章首先强调了XGBoost作为一种高效算法在机器学习任务中的应用价值,并指出正则化对于缓解过拟合问题的关键作用,具体包括降低模型复杂度、改善泛化能力和防止模型过度适应训练数据。随后,文章详细介绍了四种正则化方法:减少估计器数量(如使用`early_stopping_rounds`)、使用更简单的树(如调整`gamma`和`max_depth`)、采样(如设置`subsample`和`colsample`)以及收缩(如调节`learning_rate`, `lambda`和`alpha`)。
326 0
XGBoost中正则化的9个超参数
|
Java 关系型数据库 MySQL
Spring Boot事务配置管理
主要总结了 Spring Boot 中如何使用事务,只要使用 @Transactional 注解即可使用,非常简单方便。除此之外,重点总结了三个在实际项目中可能遇到的坑点,这非常有意义,因为事务这东西不出问题还好,出了问题比较难以排查,所以总结的这三点注意事项,希望能帮助到开发中的朋友。
|
分布式计算 资源调度 DataWorks
MaxCompute操作报错合集之出现“查询运行日志失败”的报错,一般是什么导致的
MaxCompute是阿里云提供的大规模离线数据处理服务,用于大数据分析、挖掘和报表生成等场景。在使用MaxCompute进行数据处理时,可能会遇到各种操作报错。以下是一些常见的MaxCompute操作报错及其可能的原因与解决措施的合集。
198 3
|
机器学习/深度学习 人工智能 自然语言处理
机器学习中的集成学习(一)
集成学习是一种将多个弱学习器组合成强学习器的方法,通过投票法、平均法或加权平均等策略减少错误率。它分为弱分类器集成、模型融合和混合专家模型三个研究领域。简单集成技术包括投票法(用于分类,少数服从多数)、平均法(回归问题,预测值取平均)和加权平均法(调整模型权重以优化结果)。在实际应用中,集成学习如Bagging和Boosting是与深度学习并驾齐驱的重要算法,常用于数据竞赛和工业标准。
|
开发框架 安全 .NET
文件上传漏洞技术总结
该文总结了文件上传技术相关的漏洞和绕过方法,包括语言可解析的后缀(如phtml、pht)、常见的MIME类型、Windows特性(如大小写、ADS流、特殊字符)、0x00截断技巧(需满足PHP版本和magic_quotes_gpc状态)、POST型0x00截断、文件头检查(通过合成图片马绕过)、二次渲染(利用未修改部分插入恶意代码)以及各种服务器的解析漏洞(Apache的.htaccess、解析漏洞,IIS的目录解析、文件解析、默认解析和IIS 7.x/Nginx的畸形解析)。此外,还提到了Java的空字节截断问题。
368 1
文件上传漏洞技术总结