建网站 ssl solr wso2 chartjs vue绑定class vue router vue特点 安卓小程序源码 配置tomcat环境变量 小程序下拉刷新样式 mysql学习 python操作mongodb python3正则表达式 python的range python中items python正则表达式语法 python搭建网站 python学习方法 java正则表达式 java连数据库 java获取当前年月 java数组最大值 java时间转时间戳 linux教学 右键菜单背景 microkms kms神龙 winhex教程 刷声望 3d看图软件 证书小精灵 js动态添加元素 超级网游助手 文件分割 opengl版本过低 向日葵9 铁血统帅 linux解压缩命令 ps魔棒快捷键
当前位置: 首页 > 学习教程  > 编程语言

ACM题解——训练赛2_D - The Beatles

2021/2/13 20:09:09 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

ACM题解——训练赛2_D - The Beatles 题目描述 Examples Input 2 3 1 1Output 1 6Input 3 2 0 0Output 1 3Input 1 10 5 3Output 5 5题意 有n端长为k的的线段围成一个圈,每一段开头一号点为restaurant点,共n个,现在已知初始位置s距离其最近的…

ACM题解——训练赛2_D - The Beatles

题目描述

 

Examples

Input

2 3
1 1

Output

1 6

Input

3 2
0 0

Output

1 3

Input

1 10
5 3

Output

5 5

 

题意

有n端长为k的的线段围成一个圈,每一段开头一号点为restaurant点,共n个,现在已知初始位置s距离其最近的restaurant点的距离为a,它开始沿某一方向运动,每运动一次长度为l,一旦开始运动方向不能改变,(但开始之前可以选择向左或者向右运动,选定之后过程中不可改变),l未知,但是知道运动一次之后距离当前最近restaurant点距离为b;显然l的取值有多种情况;最后需要求出按照这样的 l 运动,最快几步可以回到起点s和最长几步可以回到s。

 

题解

要求步数,就是求出(l与总长度n*k的最小公倍数)再除以l,可以化简为n*k/( l与n*k的最大公约数)(e.g.l=a*b,n*k=b*c,步数=a*b*c/l=a*b*c/a*b=c=n*k/b) ,当前任务就是确定l。显然l是由a 和 b 来确定的。分析a,b与l的关系有:

因此这4种情况可以分为l=b-a,l=b-a,l=b+a,l=-b+a,l=-b-a;且可以在这四种情况的基础上一直+k,直到绕完一圈为止。然后对于每一种 l 求出回到s的步数来更新最大最小步数,最终输出即可。

代码

#include<iostream>
using namespace std;
long long int getyz(long long int x,long long int y)  //求最大公约数
{
    long long int r=0;
    if(x%y==0)
        return y;
    else
    {
        r=x%y;
        return getyz(y,r);
    }
}                            
int main()
{
    long long int n=0,k=0,a=0,b=0;
    cin>>n>>k>>a>>b;
    long long int maxx=-1;
    long long int minn=999999999999;
    long long int res[4]={0};          //四种情况
    res[0]=a+b;
    res[1]=a-b;
    res[2]=-a+b;
    res[3]=-a-b;
    for(int i=0;i<=n;i++)           
    {
        for(int j=0;j<4;j++)
        {
            long long int cor=(res[j]+k)%k;
            long long int l=i*k+cor;
            if(l!=0 && (n*k/getyz(n*k,l))<minn)
                minn=(n*k)/getyz(n*k,l);
            if(l!=0 && (n*k/getyz(n*k,l))>maxx)
                maxx=(n*k)/getyz(n*k,l);
        }
    }
    cout<<minn<<" "<<maxx<<endl;
    return 0;
}

 


本文链接: http://www.dtmao.cc/news_show_700402.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?