Code Jam 2010 Round 1A Problem C

简介:

Problem C. Number Game

Problem

Arya and Bran are playing a game. Initially, two positive integers A and B are written on a blackboard. The players take turns, starting with Arya. On his or her turn, a player can replace A with A - kB for any positive integer k, or replace B with B - kA for any positive integer k. The first person to make one of the numbers drop to zero or below loses.

For example, if the numbers are initially (12, 51), the game might progress as follows:

Arya replaces 51 with 51 - 312 = 15, leaving (12, 15) on the blackboard. Bran replaces 15 with 15 - 112 = 3, leaving (12, 3) on the blackboard. Arya replaces 12 with 12 - 33 = 3, leaving (3, 3) on the blackboard. Bran replaces one 3 with 3 - 13 = 0, and loses. We will say (A, B) is a winning position if Arya can always win a game that starts with (A,B) on the blackboard, no matter what Bran does. Given four integers A1, A2, B1, B2, count how many winning positions (A, B) there are with A1 ≤ A ≤ A2 and B1 ≤ B ≤ B2.

Input

The first line of the input gives the number of test cases, T. T test cases follow, one per line. Each line contains the four integers A1, A2, B1, B2, separated by spaces.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of winning positions (A, B) with A1 ≤ A ≤ A2 and B1≤ B ≤ B2.

Limits

1 ≤ T ≤ 100. 1 ≤ A1 ≤ A2 ≤ 1,000,000. 1 ≤ B1 ≤ B2 ≤ 1,000,000.

Small dataset

A2 - A1 ≤ 30. B2 - B1 ≤ 30.

Large dataset

A2 - A1 ≤ 999,999. B2 - B1 ≤ 999,999.

No additional constraints.

Sample


Input  

3
5 5 8 8
11 11 2 2
1 6 1 6

Output

Case #1: 0
Case #2: 1
Case #3: 20


解题思路:终于把动态规划理解的差不多了,用动态规划写了解法,做了一些优化,可以解决小数据量。但是大数据量效率太差等不到解出来的时刻了。看了解析才知道这是又玩起组合游戏。高效解决问题基于2点: 1. If A ≥ 2B, then (A, B) is a winning position. 设k使得0<A-kB<B,那么(A-kB, B)如果必败,那么我们就减去kB。如果(A-kB, B)必胜,那么我们见减去(k-1)B,这样对方只能再减去B,我们得到(A-kB, B),必胜 2. Theorem: (A, B) is a winning position if and only if A ≥ φ B.

论证过程是:

Round 1: (A, B). If A ≥ 2B, i.e., A/B ≥ 2, then (A, B) is winning.
Round 2: (B, A-B). If B ≥ 2(A-B), i.e., A/B ≤ 3/2, then (A, B) is losing.
Round 3: (A-B, 2B-A). If A-B ≥ 2(2B-A), i.e., A/B ≥ 5/3, then (A, B) is wining.
Round 4: (2B-A, 2A-3B). If 2B-A ≥ 2(2A-3B), i.e., A/B ≤ 8/5, then (A, B) is losing.
And so on.
1,2,3,5,8是斐波那契数列,A/B是后项与前项的比值,即φ = (1 + √ 5) / 2。已知A,找出B中小于等于A/φ或者大于等于A*φ的部分。


void run() {
    int C = sc.nextInt();
    double ratio = (1 + sqrt(5)) / 2;
    for (int c = 1; c <= C; c++) {
        int a1 = sc.nextInt();
        int a2 = sc.nextInt();
        int b1 = sc.nextInt();
        int b2 = sc.nextInt();
        long count = 0;
        for (int i = a1; i <= a2; i++) {
            double up = i * ratio;
            double down = i / ratio;
            if (b1 >= up || b2 <= down)
                count += b2 - b1 + 1;
            else {
                if (b1 <= down)
                    count += max(0, (int) floor(down) - b1 + 1);
                if (b2 >= up)
                    count += max(0, b2 - (int) ceil(up) + 1);
            }
        }
        System.out.println(String.format("Case #%d: %d", c, count));
    }
}


目录
相关文章
|
3月前
|
JSON API 数据格式
实时外汇行情接口接入教程
本教程将指导您如何通过简单的几步接入实时外汇行情接口,获取您所需的外汇数据。
|
人工智能 弹性计算 边缘计算
2020年国内十大云计算商排名榜
云计算在中国经过数年发展后,技术和市场都越发成熟。随着性能和稳定的提高,成本的降低,个人和企业用户都开始逐步接受云服务,但无论在全球范围还是中国范围内,云计算市场还只是起步阶段。 中国云市场来看,表面看似巨头已经瓜分天下,但实际上,出色的新秀在不断涌现,利用自己的特色优势在细分市场中分一杯羹。笔者根据企业实力,产品性能、性价比、服务评价等方面选出了市场认可度高的中国十大公有云计算服务商云计算服务商。
|
3月前
|
机器学习/深度学习 人工智能 API
AI 发展 && MCP
AI发展——计算机视觉、ChatGPT、Sora、DeepSeek、生成式AI。什么是MCP,Prompt、LLM、Function Call、Agent、MCP是什么,各自区别;MCP如何工作,MCP架构、MCP Server工作原理,Cursor如何使用MCP,自定义MCP Server
395 46
|
3月前
|
Kubernetes API Go
利用k8s client-go库创建CRD的informer的操作流程
以上步骤将创建一个针对特定 CRD 的 informer,该 informer 会触发相应的事件处理程序以便您对事件进行响应。这是一个高级的方案,需要对 Go 编程语言和 Kubernetes 内部机制有深入的了解。在应用之前,强烈建议深入了解 Kubernetes client-go 库以及其工作原理。
132 9
|
6月前
|
人工智能 物联网 Android开发
【04】优雅草星云物联网AI智控系统从0开发鸿蒙端适配-deveco studio-自定义一个设置输入小部件组件-完成所有设置setting相关的页面-优雅草卓伊凡
【04】优雅草星云物联网AI智控系统从0开发鸿蒙端适配-deveco studio-自定义一个设置输入小部件组件-完成所有设置setting相关的页面-优雅草卓伊凡
317 92
|
12月前
|
机器学习/深度学习 人工智能 机器人
计算机视觉技术介绍
【10月更文挑战第14天】 计算机视觉技术介绍
|
8月前
|
数据采集 Web App开发 API
FastAPI与Selenium:打造高效的Web数据抓取服务 —— 采集Pixabay中的图片及相关信息
本文介绍了如何使用FastAPI和Selenium搭建RESTful接口,访问免版权图片网站Pixabay并采集图片及其描述信息。通过配置代理IP、User-Agent和Cookie,提高爬虫的稳定性和防封禁能力。环境依赖包括FastAPI、Uvicorn和Selenium等库。代码示例展示了完整的实现过程,涵盖代理设置、浏览器模拟及数据提取,并提供了详细的中文注释。适用于需要高效、稳定的Web数据抓取服务的开发者。
374 15
FastAPI与Selenium:打造高效的Web数据抓取服务 —— 采集Pixabay中的图片及相关信息
|
10月前
|
SQL DataWorks 数据可视化
阿里云DataWorks评测:大数据开发治理平台的卓越表现
阿里云DataWorks是一款集数据集成、开发、分析与管理于一体的大数据平台,支持多种数据源无缝整合,提供可视化ETL工具和灵活的任务调度机制。其内置的安全体系和丰富的插件生态,确保了数据处理的高效性和安全性。通过实际测试,DataWorks展现了强大的计算能力和稳定性,适用于中小企业快速搭建稳定高效的BI系统。未来,DataWorks将继续优化功能,降低使用门槛,并推出更多灵活的定价方案,助力企业实现数据价值最大化。
|
11月前
|
安全 物联网 网络安全
智能设备的安全隐患:物联网(IoT)安全指南
智能设备的安全隐患:物联网(IoT)安全指南
910 12
|
12月前
|
存储 运维 虚拟化
虚拟化数据恢复——Hyper-V虚拟化故障导致虚拟机文件丢失的数据恢复案例
在Windows Server上部署的Hyper-V虚拟化环境中,因存储中虚拟机数据文件丢失导致服务瘫痪。北亚企安数据恢复工程师通过物理检测、操作系统及文件系统检测,确定为人为格式化造成,并通过镜像硬盘、重组RAID、分析并恢复文件索引项等步骤,成功恢复数据,最终在新Hyper-V环境中验证并迁移所有虚拟机,确保用户业务恢复正常运行。