[J'ai essayé l'examen d'entrée de Google (non officiel)](http://yasigani-ni.com/every-day/google%E3%81%AE%E5%85%A5%E7%A4%BE% E8% A9% A6% E9% A8% 93% E9% 9D% 9E% E5% 85% AC% E5% BC% 8F% E3% 81% AB% E3% 83% 81% E3% 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 81% 97% E3% 81% A6% E3% 81% BF% E3% 81% 9F /)
Je l'ai essayé avec java.
Si vous utilisez une fonction qui compte le nombre de 1 qui apparaissent, la quantité de calcul augmente à mesure que le nombre augmente, il est donc efficace de calculer séquentiellement sans en faire une fonction.
hoge.java
class hoge{
public static void main(String[] args) {
int ret =0;
for(int j=1;j<Integer.parseInt(args[0]);j++){
ret +=((" "+j+" ").split("1").length-1);
if(j<=ret){
System.out.println(ret);
}
}
}
}
>java hoge 200000
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
199992
199993
199994
199995
199996
199997
199998
199999
200000
199981
Puisqu'il y a un calcul, j'ai l'impression qu'il peut être accéléré en échangeant des nombres, mais j'ai arrêté parce qu'il n'apparaissait pas dans la formule.
Alternativement, il peut être plus rapide de dériver une expression approximative, puis de deviner. Cela prendra du temps si vous n'utilisez pas la bibliothèque.
Recommended Posts