首页 > 试题广场 >

翻倍

[编程题]翻倍

热度指数：4491 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小易给定你数字 $\mathit A,B(A < B)$ 和系数 $\mathit p,q$ 。每次操作你可以将 $\mathit A$ 变成 $\mathit A+p$ 或者将 $\mathit p$ 变成 $\mathit p \times q$ 。问至少几次操作使得 $B \leq A$ 。

输入描述:

第一行数据组数，对于每组数据，一行四个整数。
.

输出描述:

对于每组数据，输出一个数字表示答案

示例1

输入

2
1 5 7 2
3 5 1 2

输出

1
2

示例2

输入

2
1 15 4 2
12 19 3 2

输出

3
3

算法知识视频讲解

是瑶瑶公主呀

import java.util.*;

public class Main {

    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        input.nextLine();
        for(int i=0;i<n;i++){
            String[] s = input.nextLine().split(" ");
            int A=Integer.parseInt(s[0]);
            int B=Integer.parseInt(s[1]);
            int p=Integer.parseInt(s[2]);
            int q=Integer.parseInt(s[3]);
            System.out.println(count(A,B,p,q,0));
        }
    }

    private static int count(double A,double B,double p,double q,int num){
        if(B-A<=p)
            return num+1;
        else if((B-A)/p<=q)
            return num+2;
        else {
            return count(A,B,p*q*q,q,num+2);
        }
    }

}

发表于 2020-03-04 11:53:13 回复(2)

JavaScript

牛客137496344号

var T = parseInt(readline());
while (T--) {
    var arr = readline().split(" ")
    var A = parseInt(arr[0]);
    var B = parseInt(arr[1]);
    var p = parseInt(arr[2]);
    var q = parseInt(arr[3]);
    print(test(A, B, p, q))
}
function test(A,B,p,q){
    var index = 0;
    while(A<B){
        if(q==1){
            A = A+p;
        }else{
            if(A+p<B){
                p=p*q;
            }else{
                A=A+p;
            }
        }
        index++;
    }
    return index;
}

编辑于 2020-08-07 17:21:46 回复(0)

OfferOffer快到碗里来!

function test (a, b, p, q) {
    returnMath.ceil(Math.log(((b - a) / p)) / Math.log(q)) + 1
}
let linenum = parseInt(readline())
for(let i = 0; i < linenum; i++){
    let cur = readline().split(' ').map(Number)
    print(test(cur[0], cur[1], cur[2], cur[3]))
}

编辑于 2020-08-07 22:14:31 回复(0)

熊0047

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String temp=in.nextLine();
        int num=Integer.parseInt(temp);
        int stop=1;
        while(stop<=num){
            stop++;
            temp=in.nextLine();
            String [] temps=temp.split(" ");
            long []nums=new long[temps.length];
            for(int i=0;i<temps.length;i++) {
                nums[i] = Long.parseLong(temps[i]);
            }
            long A=nums[0];
            long B=nums[1];
            long p=nums[2];
            long q=nums[3];
            int time=1;
            while (A+p<B){
                time++;
                p=p*q;
            }
            System.out.println(time);
        }
    }
}

这题由于q限定了大于等于2，所以不必考虑到底是直接加还是乘了加哪个快，直接先比较A+p是否大于等于B，若大于等于那就结束，否则就p=p*q，然后循环。

要注意的是B的范围大于了Int的范围，所以用long类型来解决。

发表于 2020-04-05 18:38:54 回复(0)

白菊花瓣

贪心算法的题目。

注意题目条件：p >= 1, q >= 2，那么 p * q > p 就是一定的。我们要求最小的操作此时，那么我们每次就希望让 A 加上个更大的值，因为 p *q > p 一定，所以我们每次就要让 p = p * q 直到 A + p >= B 退出，记录我们的操作次数。最后测试案例里面有 int 过界的情况，所以就直接全部用 long 计算了

给出 C# 代码：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

public class Program
{
    public static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());

        for(int k = 0; k < T; ++k)
        {
            string[] ipts = Console.ReadLine().Split(' ');
            long A = long.Parse(ipts[0]);
            long B = long.Parse(ipts[1]);
            long p = long.Parse(ipts[2]);
            long q = long.Parse(ipts[3]);
            Console.WriteLine(GetTime(A, B, p, q));
        }
    }

    public static long GetTime(long A, long B, long p, long q)
    {
        long time = 0;
        while(A + p < B)
        {
            p *= q;
            ++time;
        }
        return time + 1;
    }
}

发表于 2020-09-29 17:59:42 回复(0)

曦翎

#include<iostream>
using namespace std;
int main(){
long long A,B,p,q;
int n;
int T;
cin>>T;
while(T--){
  cin>>A>>B>>p>>q;
  if(A<B){
   n=1; //每次都要初始化
   while(A+p<B){
    n++;
    p=p*q;
   }
   cout<<n<<endl;
  }
    }
return 0;
}

发表于 2020-04-07 16:28:15 回复(0)

Java

胖虎喜欢静香

package test;

import java.util.Scanner;

/**
 * @author Mr.Zhao
 * @version 1.0
 * @Description:
 * @date 2020/1/5 10:48
 */
public class Test02 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        long[][] arrInt = new long[i][4];
        scanner.nextLine();
        for (int i1 = 0; i1 < i; i1++) {
            String str = scanner.nextLine();
            String[] arrString = str.split("\\s");
            for (int i11 = 0; i11 < 4; i11++) {
                arrInt[i1][i11] = Long.parseLong(arrString[i11]);
            }
        }

        for (int j = 0; j < i; j++) {
            int number = 0;
            outterLoop:for (int k = 0; k < 4; k++) {
                if (arrInt[j][0] >= arrInt[j][1]) {
                    System.out.println(number);
                    number = 0;
                } else {
                    while (arrInt[j][0] <= arrInt[j][1]) {
                        long m = arrInt[j][0] + arrInt[j][2];
                        long n = arrInt[j][2] * arrInt[j][3];
                        if (m >= arrInt[j][1]) {
                            System.out.println(++number);
                            break outterLoop;
                        }else {
                            if ((2 * arrInt[j][2]) <= n) {
                                arrInt[j][2] = n;
                                number++;
                            } else {
                                arrInt[j][0] = m;
                                number++;
                            }
                        }
                    }
                }
            }
        }
    }
}

发表于 2020-01-05 13:37:05 回复(0)

冯吃吃呀

n=int(input())
for i in range(n):
    a,b,p,q=map(int,input().split())
    k=0
    while(a<b):
        if(a+p>=b):
            a=a+p
        else:
            p=p*q
        k=k+1
    print(k)

发表于 2020-04-04 16:54:37 回复(5)

cda乔木

import sys
t = int(sys.stdin.readline())
arr = []
for i in range(t):
    arr.append(list(map(int, sys.stdin.readline().strip().split())))
for n in range(t):
    a,b,p,q = arr[n]
    res = 1
    while a + p < b:
        p = p * q
        res += 1
    print(res)

发表于 2020-02-01 13:47:00 回复(0)

pein531

T = int(input())
for _ in range(T):
    A, B, p, q = map(int, input().split())
    count = 0
    if B <= A:
        print(count)
    else:
        # 当A + p < B时，进行一次p *= q的操作，直到A + p >= B
        while A + p < B:
            p *= q
            count += 1
        # 此时还要加上一次A + p的操作
        print(count + 1)

发表于 2020-12-07 20:40:14 回复(0)

战忽先锋

import math
nums = input('请输入A,B,p,q')
list2 = nums.split(' ') #以空格切割
list1 = list(map(int,list2)) #转为int类型
A = list1[0]
B = list1[1]
p = list1[2]
q = list1[3]
a = A - B
if a<=p:
    b = 1
else:
    if q <= 1:
        b = math.ceil(a/p) #向上取整
    else:
        b = math.ceil(math.log(a/p,q))+1 #取以q为底a/p的对数
print('最少%d次操作使得B<=A'%b) #格式化输出

发表于 2020-07-19 23:40:57 回复(0)

JavaScript

今天的汤等于昨天的汤加前天的汤

let n = parseInt(readline());
for (let i = 0; i < n; i++) {
    let arr = readline().split(" ").map(Number);
    let res = f(arr);
    console.log(res);
}

function f(arr) {
    // 只有当a + p >= b时，才值得让a = a + p
    let a = arr[0];
    let b = arr[1];
    let p = arr[2];
    let q = arr[3];
    
    let count = 0;
    while (a < b) {
        if (a + p >= b) {
            a = a + p;
        } else {
            p = p * q;
        }
        count++;
    }
    
    return count;
}

发表于 2020-10-20 22:20:25 回复(0)

斐斐王P

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        long long A,B,p,q;
        cin>>A>>B>>p>>q;
        long long diff=B-A;
        int count=0;
        while (diff>p){
            p*=q;
            ++count;
        }
        cout<<count+1<<endl;
    }
}

发表于 2020-10-11 09:42:42 回复(0)

0OFFER救救我

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int group = sc.nextInt();
        for (int i = 0; i < group; i++) {
            long[] arr = new long[4];
            for (int j = 0; j < 4; j++) {
                arr[j] = sc.nextLong();
            }
            long A = arr[0];
            long B = arr[1];
            long p = arr[2];
            long q = arr[3];
            int count = 1;
            while (A + p < B) {
                count++;
                p = p * q;
            }
            System.out.println(count);
        }
    }
}

发表于 2020-08-25 10:47:23 回复(0)

Morpwin

发表于 2020-08-21 17:02:53 回复(0)

Divine0

def opCount(A, B, p, q):
    if A >= B:
        return 0
    if A + p >= B:
        return 1
    return 1 + opCount(A, B, p*q, q)


T = int(input())
alist = []
for _ in range(T):
    temp = [int(i) for i in input().split()]
    alist.append(temp)
for sub_list in alist:
    A, B, p, q = sub_list
    print(opCount(A, B, p, q))

发表于 2020-08-19 15:26:03 回复(0)

TheRealYmk

let n=readline();
let input=[];
for(let i=0;i<n;i++){
    input.push(readline().split(' ').map(item=>parseInt(item)));
}

let f=(a,b,p,q)=>{
    let i=0;
    let A=a;
    let P=p;
    while(A<b){
        i++;
        if(A+P>=b){
           return i;
        }else{
            P*=q;
        }
    }
}

for(let i=0;i<n;i++){
    console.log(f(...input[i]))
}

发表于 2020-08-15 01:03:00 回复(0)

石头剪刀布201801102003586

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int cnt;
        sc.nextLine();
        for(int i = 0; i < T; i++) {
            long A = sc.nextInt();
            long B = sc.nextInt();
            long p = sc.nextInt();
            long q = sc.nextInt();
            cnt = 0;
            while(A < B) {
                if(A + p >= B) {
                    A = A + p;
                }
                else {
                    p = p * q;
                }
                cnt++;
            }
            System.out.println(cnt);
        }
    }
}

发表于 2020-08-07 23:19:21 回复(2)

C/C++

牛客543214807号

贡献个C版本的

#include <stdio.h>
#include <stdlib.h>

int main()
{
int A,B,q;
unsigned long int p;
int i,num;

scanf("%d",&num);
int count[5]={0};

for(i=0;i<num;i++)
{
do{
scanf("%d",&A);
scanf("%d",&B);
scanf("%ld",&p);
scanf("%d",&q);
}while(getchar()!='\n');//读一整行数据

while(A<B){
if(A+p>=B){
count[i]=count[i]+1;
break;
}
else{
p=p*q;
count[i]=count[i]+1;
}
}
}
for(i=0;i<num;i++)
{
printf("%d\n",count[i]);
}
return 0;
}

发表于 2020-08-07 22:24:55 回复(0)

odd.

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

const input = []

rl.on('line', line => {
    input.push(line)
    const maxline = parseInt(input[0])
    if (input.length === maxline + 1) {
        handleInput(input)
        rl.close()
    }
})

function handleInput(input) {
    const maxline = parseInt(input.shift())
    for (let i = 0; i < maxline; i++) {
        let arr = input[i].split(' ')
        arr = arr.map(item => parseInt(item))
        doubleSize(arr)
    }
}

function doubleSize(arr) {
    let [A, B, p, q] = arr
    let count = 0
    while (B > A) {
        if (A + p >= B) {
            A = A + p
        } else {
            p = p * q
        }
        count += 1
    }
    console.log(count);
}

发表于 2020-08-07 16:49:46 回复(0)