神探夏洛克与野兽-问题 [英] Sherlock and The beast - issue
问题描述
问题：
夏洛克·福尔摩斯（Sherlock Holmes）对他的主要敌人Moriarty教授感到偏执。他征服莫里亚蒂的所有努力都是徒劳的。如今，Sherlock正在研究Watson博士的问题。沃森（Watson）提到，中央情报局（CIA）最近在超级计算机野兽（The Beast）方面遇到了奇怪的问题。
Question: Sherlock Holmes is getting paranoid about Professor Moriarty, his arch-enemy. All his efforts to subdue Moriarty have been in vain. These days Sherlock is working on a problem with Dr. Watson. Watson mentioned that the CIA has been facing weird problems with their supercomputer, 'The Beast', recently.
今天下午，夏洛克收到了莫里亚蒂的一封信，说他已经用病毒感染了野兽。此外，钞票上印有数字N。经过一些计算，Sherlock认为清除病毒的关键是具有N位数字的最大的体面数字。
This afternoon, Sherlock received a note from Moriarty, saying that he has infected 'The Beast' with a virus. Moreover, the note had the number N printed on it. After doing some calculations, Sherlock figured out that the key to remove the virus is the largest Decent Number having N digits.
体面数字具有以下属性：
A Decent Number has the following properties:
- 3、5或两者均为数字。不允许其他数字。
- 出现3的次数可以被5整除。
- 出现5的次数可以被3整除。
与此同时，野兽毁灭的反击速度非常快。您可以保存野兽并在Sherlock之前找到钥匙吗？
Meanwhile, the counter to the destruction of 'The Beast' is running very fast. Can you save 'The Beast', and find the key before Sherlock?
我正在尝试解决hackerrank中的 Sherlock and the beast问题（上图），这是我的结尾是什么-
I am trying to solve "Sherlock and the beast" problem (above) in hackerrank and here is what I ended with -
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
for(int i=0;i<n;i++) {
int subject = s.nextInt();
if(isPerfectlyDivisible(subject, 3)) {
System.out.println(stringBuilder("5", subject));
continue;
}
if (isPerfectlyDivisible(subject, 5)) {
System.out.println(stringBuilder("3", subject));
continue;
}
if(!isPerfectlyDivisible(subject, 5) && !(isPerfectlyDivisible(subject, 3))) {
List<Integer> multipliers = dividedMultipliers(subject);
if (multipliers.isEmpty()) {
System.out.println("-1");
} else {
System.out.println(stringBuilder("5", multipliers.get(0))+stringBuilder("3", multipliers.get(1)));
}
}
}
}
private static boolean isPerfectlyDivisible(int n, int divider) {
if (n < divider) return false;
if (n%divider == 0) return true;
return false;
}
private static List<Integer> dividedMultipliers(int n) {
List<Integer> multipliers = new ArrayList<Integer>();
for(int i=n;i>0;i--) {
if( (i%3 == 0) && ((n-i)%5 == 0)) {
multipliers.add(i);
multipliers.add(n-i);
break;
}
}
return multipliers;
}
private static String stringBuilder(String s, int times) {
StringBuffer buffer = new StringBuffer();
for(int i=0;i<times;i++) {
buffer.append(s);
}
return buffer.toString();
}
}
有测试用例对此失败。我尝试查看输入为
There were test cases failing for this. I tried looking at one of the failing test cases whose input is
5
2194
12002
21965
55140
57634
令人惊讶的是 21965 输出为全5，而我上面的代码返回全3。这似乎是预期的输出。不确定该问题出在哪里？任何见解都会有所帮助
Surprisingly for 21965 the output is all 5's whereas my code above returns all 3's..which seems to be the expected output..Not sure where the issue? Any insights would be helpful
推荐答案
您正在寻找最大的体面数，因此您应该将5s最大化。例如，21965可被5整除，但最大的21965位体面数字不是仅由3组成的数字。它是21960 5和5 3的一个。
You are looking for the largest decent number, so you should maximise the number of 5s. For example, 21965 is divisible by 5, but the largest 21965-digit decent number is not one that consists of 3s only; it is one that has 21960 5s and 5 3s.
您的 dividedMultipliers 例程已经使用了最多5s，但是将可被5整除的数字视为特殊数字会破坏该逻辑；
Your dividedMultipliers routine already goes for the most 5s, but treating a number that is divisible by 5 as special undermines that logic; it will create the least optimum decent number.
摆脱这种特殊情况。 （您也可以摆脱另一种特殊情况，即检查仅由5组成的数字，因为 dividedMultipliers 会在第一次迭代中立即处理该情况。）
Get rid of that special case. (You could also get rid of the other special case which checks against a number consisting of only 5s, because dividedMultipliers handles that case immediately in the first iteration.)
这篇关于神探夏洛克与野兽-问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
