Google Code Jam 2010 Round 1C Problem B. Load Testing

时间:2022-11-09 14:50:47

https://code.google.com/codejam/contest/619102/dashboard#s=p1&a=1

Problem

Now that you have won Code Jam and been hired by Google as a software engineer, you have been assigned to work on their wildly popular programming contest website.

Google is expecting a lot of participants (P) in Code Jam next year, and they want to make sure that the site can support that many people at the same time. During Code Jam 2010 you learned that the site could support at least L people at a time without any errors, but you also know that the site can't yet support P people.

To determine how many more machines you'll need, you want to know within a factor of Chow many people the site can support. This means that there is an integer a such that you know the site can support a people, but you know the site can't support a * C people.

You can run a series of load tests, each of which will determine whether the site can support at least X people for some integer value of X that you choose. If you pick an optimal strategy, choosing what tests to run based on the results of previous tests, how many load tests do you need in the worst case?

Input

The first line of the input gives the number of test cases, TT lines follow, each of which contains space-separated integers LP and C in that order.

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 load tests you need to run in the worst case before knowing within a factor of C how many people the site can support.

Limits

1 ≤ T ≤ 1000.
2 ≤ C ≤ 10.
LP and C are all integers.

Small dataset

1 ≤ L < P ≤ 103.

Large dataset

1 ≤ L < P ≤ 109.

Sample

Input 
 
Output 
 
4
50 700 2
19 57 3
1 1000 2
24 97 2
Case #1: 2
Case #2: 0
Case #3: 4
Case #4: 2

Explanation

In Case #2, we already know that the site can support between 19 and 57 people. Since those are a factor of 3 apart, we don't need to do any testing.

In Case #4, we can test 48; but if the site can support 48 people, we need more testing, because 48*2 < 97. We could test 49; but if the site can't support 49 people, we need more testing, because 24 * 2 < 49. So we need two tests.

Solution:

int solve(int L, int P, int C)
{
int tries = ;
for (;;) {
if (L * pow(C, pow(, tries)) >= P) {
return tries;
}
tries++;
}
} int main()
{
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout); int T;
scanf("%d\n", &T);
if (!T) {
cerr << "Check input!" << endl;
exit();
} for (int t = ; t <= T; t++) {
cerr << "solving: #" << t << " / " << T << endl; int L, P, C;
scanf("%d %d %d\n", &L, &P, &C);
auto result = solve(L, P, C);
printf("Case #%d: %d\n", t, result);
} fclose(stdin);
fclose(stdout);
return ;
}

Google Code Jam 2010 Round 1C Problem B. Load Testing的更多相关文章

  1. Google Code Jam 2010 Round 1C Problem A&period; Rope Intranet

    Google Code Jam 2010 Round 1C Problem A. Rope Intranet https://code.google.com/codejam/contest/61910 ...

  2. Google Code Jam 2010 Round 1A Problem A&period; Rotate

    https://code.google.com/codejam/contest/544101/dashboard#s=p0     Problem In the exciting game of Jo ...

  3. Google Code Jam 2010 Round 1B Problem B&period; Picking Up Chicks

    https://code.google.com/codejam/contest/635101/dashboard#s=p1   Problem A flock of chickens are runn ...

  4. Google Code Jam 2010 Round 1B Problem A&period; File Fix-it

    https://code.google.com/codejam/contest/635101/dashboard#s=p0   Problem On Unix computers, data is s ...

  5. dp - Google Code jam Qualification Round 2015 --- Problem B&period; Infinite House of Pancakes

    Problem B. Infinite House of Pancakes Problem's Link:   https://code.google.com/codejam/contest/6224 ...

  6. Google Code jam Qualification Round 2015 --- Problem A&period; Standing Ovation

    Problem A. Standing Ovation Problem's Link:   https://code.google.com/codejam/contest/6224486/dashbo ...

  7. Google Code Jam 2016 Round 1B Problem C&period; Technobabble

    题目链接:https://code.google.com/codejam/contest/11254486/dashboard#s=p2 大意是教授的学生每个人在纸条上写一个自己的topic,每个to ...

  8. Google Code Jam 2009&comma; Round 1C C&period; Bribe the *ers &lpar;记忆化dp&rpar;

    Problem In a kingdom there are * cells (numbered 1 to P) built to form a straight line segment. ...

  9. Google Code Jam 2016 Round 1C C

    题意:三种物品分别有a b c个(a<=b<=c),现在每种物品各选一个进行组合.要求每种最和最多出现一次.且要求任意两个物品的组合在所有三个物品组合中的出现总次数不能超过n. 要求给出一 ...

随机推荐

  1. MyString&lpar;重写String&rpar;

    http://wenku.baidu.com/view/d7ac113243323968011c925b.html 已知类String的原型为: class String  { public:     ...

  2. Xenia and Weights(深度优先搜索)

    Xenia and Weights time limit per test 2 seconds memory limit per test 256 megabytes input standard i ...

  3. 利用window&period;name&plus;iframe跨域获取数据详解

    详解 前文提到用jsonp的方式来跨域获取数据,本文为大家介绍下如何利用window.name+iframe跨域获取数据. 首先我们要简单了解下window.name和iframe的相关知识.ifra ...

  4. HDU 3584 三维树状数组

    三维树状数组模版.优化不动了. #include <set> #include <map> #include <stack> #include <cmath& ...

  5. Python学习(一) —— matplotlib绘制三维轨迹图

    在研究SLAM时常常需要对其输出的位姿进行复现以检测算法效果,在ubuntu系统中使用Python可以很好的完成相关的工作. 一. Ubuntu下Python的使用 在Ubuntu下使用Python有 ...

  6. 好代码是管出来的——使用Git来管理源代码

    软件开发过程中一个重要的产出就是代码,软件的编码过程一般是由一个团队共同完成,它是一个并行活动,为了保证代码在多人开发中能够顺利完成,我们需要使用代码版本控制工具来对代码进行统一存储,并追踪每一份代码 ...

  7. 解析jsonObject,赋给指定的对象

    从JSONObject中解析数据,并赋给给定的对象 public static Object parseBean(JSONObject jsonObject, Object obj) {   if ( ...

  8. 使用Python的列表推导式计算笛卡儿积

    笛卡儿积: 笛卡儿积是一个列表, 列表里的元素是由输入的可迭代类型的元素对构 成的元组,因此笛卡儿积列表的长度等于输入变量的长度的乘积, 如下图: 如果你需要一个列表,列表里是 3 种不同尺寸的 T ...

  9. 17&period;异常&lpar;三&rpar;之 e&period;printStackTrace&lpar;&rpar;介绍

    一.关于printStackTrace()方法 public void printStackTrace()方法将此throwable对象的堆栈追踪输出至标准错误输出流,作为System.err的值.输 ...

  10. 【转】Git命令大全(非常齐全)

    $ git init  // 初始化一个Git仓库$ git status   // 查看仓库的状态$ git add .   // 将所有修改添加到暂存区$ git add *  // Ant风格添 ...