|
|
Задача заставила подумать. Как уже описано на форуме, нужно научиться считать количество единиц, которые встречаются в числах от 1 до X и подбирать X бинарным поиском. И вот мне этот подсчет долго не давался. Итог такой. Считать можно рекурсивно. Для этого нужно воспользоваться тем, что для чисел вида X=999...999 искомое количество единиц равно (log10(X)+1) *10^log10(X). Этот факт я заметил эксперимнтально. То есть я имею в виду count_ones (99)=20 count_ones (999)=300 count_ones (9999)=4000 и так далее. Отсюда и вытекает способ . Вычисляем сначала для X с зануленными разрядами кроме самого главного, затем прибавляем значение функции от X с зануленным главным разрядом . Я приведу пример для небольшого числа. Пусть X=666. Тогда посчитаем отдельно для 0-99, умножим на 6, прибавим к ответу; затем отдельно для 100-200, прибавим это к ответу , затем рекурсивно для 600-666 то есть просто для 0-66. What's wrong, if the second test is 10^18? the ones of 1 to 10^18 have over the range of int64 The number of ones is less than number of floor. For me tha answer must be in Int64 The answer is within Int64. So, try to find bug in your code or algorithm... if you use line like this at TIMUS will a bug ... long long INF = 1e18; you should use long long INF = 1e9; INF *= INF; Use unsigned __int64, might help. Also, if you use binary search, make sure that left+right does not overflow prior to /2 or >>1. if you use line like this at TIMUS will a bug ... long long INF = 1e18; you should use long long INF = 1e9; INF *= INF; Thank you! Try this test 12 Answer 19 (not 20) Obvious solution looks as: 1) Suggest f(n) = amount of ones in numbers from 1 to n 2) Make binary search for f(i) It is obvious right, but constraint for input number don't allow to fast writing this solution in cpp (because we need in BigInteger). So, in my opinion, constraint are bad. If we want to make hardships with standart types in cpp and pascal, should take 1 <= n <= 10^100. In other hand, if we don't want to make it, should take 1 <= n <= 10^15. Am I wrong? Oops! I was wrong. AC without BigInteger with using c++ now :-) subj No, it is binsearch + math only math enough But it's harder to implement... Using DP and you can think and code easily. I solved this problem without papers and pens. :) What's the test? I use unsigned __int64, in debugger even the input of 10^18 is processed correctly, though... 20 -> 91 21 -> 100 31 -> 109 32 -> Petr lies 33 -> 110 35 -> Petr lies 36 -> 111 in 8200238419224828 out 4784308175746017 NEXT CODE IS NOT AC SOLUTION but it a way to test your Solution next class run with command: "java tester >test.txt" then you can run your solution and compare your answers with this tester's But you cant test some tests where n>30000, therefore try to think and about it. Good luck to TEST, I AC)) ////////////////////////tester.java/////////////////////////// import java.io.*; import java.util.*; public class tester{ public static void main(String[] args){ int s=0,ts=0; int t; int a[]=new int[30000]; for(int i=0;i<30000;i++){ a[i]=0; } for(int i=1;i<=50000;i++){ ts=s; t=i; while(t>=10){ if(t%10==1){ s++; } t/=10; } if(t==1){ s++;
} if(ts!=s) a[s-1]=i; }
for(int i=0;i<30000;i++){ if(a[i]!=0) System.out.println((i+1) + " "+ a[i]); else System.out.println((i+1)+ " " +"Petr lies"); } } } ////////////////////////end/////////////////////////// What is the first test and it's correct answer? I have TL#8, but i didn't use any special algo only calculation. can anybody say me the way and algo of this problem? my e-mail yashar25.92@mail.ru Solve the reverse problem (it's easier), and then binary-search for the answer. give me smb tests, pleaze |
|
|