青蛙的约会
Description
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
Output
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4
package p1061;
import java.util.Scanner;
/**
* 青蛙问题,递归的妙用阿。
*/
public class Main {
static int length;
static int x;
static int y;
static int m;
static int n;
static void printImpossible() {
System.out.println("Impossible");
}
static void readInput() {
Scanner in = new Scanner(System.in);
x = in.nextInt();
y = in.nextInt();
m = in.nextInt();
n = in.nextInt();
length = in.nextInt();
}
/**
* here, We get 0<=speed<length. 0<=target<length. return -1 if there is
* no answer.
*/
static long compute(int speed, int target, int length) {
int target_r = target % speed;
int length_r = length % speed;
if (target_r == 0)
return target / speed;
if (length_r == 0)
return -1;
int newLength = speed;
int newSpeed = length_r;
int newTarget = speed - target_r;
long newResult = compute(newSpeed, newTarget, newLength);
if (newResult == -1)
return -1;
else {
return (target + newResult * length) / speed;
}
}
public static void main(String[] args) {
readInput();
x = x % length;
y = y % length;
m = m % length;
n = n % length;
if (m == n) {
printImpossible();
return;
}
if (x == y) {
System.out.println(0);
return;
}
int speed;
int target;
if (m > n) {
speed = m - n;
if (y > x) {
target = y - x;
} else {
target = y + length - x;
}
} else {
speed = n - m;
if (x > y) {
target = x - y;
} else {
target = x + length - y;
}
}
long result = compute(speed, target, length);
if (result == -1) {
printImpossible();
} else {
System.out.println(result);
}
}
}
分享到:
- 2009-09-30 15:35
- 浏览 1139
- 评论(0)
- 论坛回复 / 浏览 (0 / 2500)
- 查看更多
相关推荐
关于acm青蛙过河的一道题代码acm,请大家参考之,希望有用处
EFM32系列微控制器是Silicon Labs推出的一款针对能效敏感型应用的32位MCU,其内部包含了一个模拟比较器模块ACMP,该模块是片上集成的模拟电压比较器。ACMP模块在低功耗模式下能够保持运行,因此对于需要电池供电的...
"ACM problem set題目(譯)"是一个专门为初学者准备的资源,它包含了ACM竞赛中的一些题目中文翻译,目的是帮助那些中文为母语的学习者更好地理解和解决这些问题。 ACM竞赛的题目通常涵盖了各种算法和数据结构,包括...
标题中的"acm.rar_Fan Problem ACM"表明这是一个与ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)相关的压缩文件,其中包含了名为"Fan Problem"的题目。ACM竞赛是全球范围内极具影响...
"ACM_ACM Hwang .p" 暗示了这个压缩包可能包含由 ACM 专家 Hwang 教授的一些教程或讲义,这些材料通常对参赛者或对算法竞赛感兴趣的学习者非常有价值。"ACM java_pku 1689 rubbery_ppt" 提到的可能是关于 Java 语言...
“青蛙过河”问题属于典型的ACM/ICPC竞赛中的算法题目。这类题目通常涉及一系列复杂的逻辑推理和算法设计,旨在考验参赛者的逻辑思维能力和编程技巧。本题设定了一群不同大小的青蛙需要从河的一侧(记为A)过河到另...
总之,"ACM题--Problem A: Welcome to JL2009"作为ACM竞赛中的一道经典题目,不仅具有较高的趣味性和挑战性,也是锻炼和提升编程能力的好题目。通过此类题目的训练,选手们可以在算法设计、逻辑分析和问题解决能力...
【深信服企业级云 aCMP 用户手册】是深信服科技股份有限公司针对其aCMP 6.0.15版本的云管理平台所编写的一份详细指南,旨在帮助用户理解和操作这一云管平台。手册涵盖了从基础概念到高级功能的全方位介绍,适合网络...
标题中的"acmp.rar_ ACMP_anolog"表明这是一个与ACMP(Analog Comparator,模拟比较器)相关的压缩文件,而“anolog compare”进一步强调了这是关于模拟比较器的工作原理或应用。ACMP通常用于比较两个模拟信号的电压...
纳瓦特的一个好经 典的一个例程、纳瓦特单片机是 一个便宜的单片机
"p_acm"、"pku_acm"以及"pu_acm.pku_pku"等标签可能是用于分类或标识这些代码属于北京大学(Peking University, PKU)的ACM训练题目。"acm"一词重复出现,进一步强调了这是关于ACM编程竞赛的内容。 描述中提到"acmer...
Mini51 ACMP(模拟比较器模块)是其中的重要组成部分,用于比较两个模拟信号的大小,并可以配置相关的中断服务程序来响应比较结果的变化。 ### 知识点一:ACMP的基本功能和特性 - 输入电压范围:ACMP模块能够处理的...
【标题】"Problem D.rar" 是一个压缩文件,其中包含了对 ACM(国际大学生程序设计竞赛,简称ACM/ICPC)某道试题的解答。这个压缩包特别关注的是"ACM_ACM试题",暗示了内容可能涉及过去比赛中的一个问题及其解决方案...
ACM面试题解析 从给定的文件中,我们可以总结出四个不同的问题,每个问题都有其独特的解决方案和要点。 试题一:青蛙相遇问题 该问题的核心是判断两只青蛙是否能够相遇,并计算出它们相遇所需要的跳跃次数。为了...
#include #include using namespace std; int main() { int a[10][4]={{0},{1},{6,2,4,8},{1,3,9,7},{6,4},{5},{6},{1,7,9,3},{6,8,4,2},{1,9}},m,n,j; while(cin>>j) { while(cin>>n) ...}
【标题】"北大acm_p1001试题c++版"所指的是一道源自北京大学ACM(国际大学生程序设计竞赛)的编程题目,它使用C++语言编写。ACM竞赛是全球知名的大学生编程比赛,旨在提升参赛者的算法设计、问题解决以及编程能力。...
近期,我有幸接触到了一个名为“Problem J.rar”的压缩文件,它包含了2004年ACM竞赛的试题题解,这无疑为有志于提升算法能力的学习者提供了一笔宝贵的财富。 “Problem J.rar”中的“Problem J.doc”文件是关键的...
### 杭电ACM-HDUOJ 1001 SUM problem #### 题目背景与概述 杭电ACM-HDUOJ 1001 SUM problem 是一道非常基础且适合编程初学者练习的题目。根据描述,这道题目是“A+B PROBLEM”的一种变形,主要考察的是循环结构和...
产品知识点、产品型号参数、许可详情、角色、防火墙策略