| Show all threads Hide all threads Show all messages Hide all messages |
| [updated task] WA#2 sample tests or hints appreciated | alex_online | 1013. K-based Numbers. Version 3 | 3 Jul 2024 18:35 | 6 |
Hello, could you check if my test is correct?
4
10
1234
Answer: 222 (??)
~Thanks Why the answer is 191? As far as I understand, we need to count numbers from 1000 to 1234 without 00. There are only 12 of them:
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1100
1200
So 1234 - 1000 - 12 = 222. Where am I wrong? Thanks. > As far as I understand, we need to count numbers from 1000 to 1234 without 00
No. We need to count numbers from 1000 to 9999 without 00.
Result - 8829 - we should divide by 1234 - 7, remainder 191.
Remainder is the answer.
So answer is 191.
Edited by author 26.12.2016 15:11 My answer is also 191, but i got WA#3 |
| Help please!!!! WA 3 | Emris | 1013. K-based Numbers. Version 3 | 12 May 2024 17:09 | 2 |
I solved 1009 and 1012. Now im using new algorithm (log(n)) and program works fast and correct with my tests.
Can you give more tests? I solved 1013, my mistake was multiplication of large numbers, i use long arithmetic for multiplication and uint64 for variables and get Accept |
| Hint | Liol | 1013. K-based Numbers. Version 3 | 3 Mar 2022 10:48 | 1 |
Hint Liol 3 Mar 2022 10:48 if you WA on #3 ,please use unsigned __int64 and high-accuracy
if you WA on #9 ,try this
2
10
3
The answer is 0
Edited by author 03.03.2022 10:56 |
| Problem 1013. K-based Numbers, Version 3 was changed | Vladimir Yakovlev (USU) | 1013. K-based Numbers. Version 3 | 6 Dec 2021 02:06 | 2 |
The limitations and input/output format were changed. Old submission were moved to the problem 1012. Shouldn't the complexity of the problem be changed as well? Not sure that the complexity 189 corresponds to the intended solution for the new limitation. |
| C++ - how to value (a*b)%c, when a,b,c are long long? | ToadMonster | 1013. K-based Numbers. Version 3 | 14 May 2021 21:33 | 4 |
long long mul(long long a,long long n)
{
long long ret;
if(n==0)
return 0;
ret=mul(a,n/2);
ret=(ret+ret)%mod;
if(n%2)
ret=(ret+a)%mod;
return ret;
}
Edited by author 24.11.2016 05:02 LL product_mod(LL a, LL b, LL mod)
{
a %= mod;
b %= mod;
LL result = 0, y = a;
while(b)
{
if(b&1)
result = ((result%mod) + y) %mod;
y = (y + y)%mod;
b = b >> 1;
}
return result%mod;
}
This is also known as the Russian peasant method for multiplication.
For example, 7x13
13 = (8 + 4 + 1)
The product is re-written as 8.7 + 4.7. 1.7
In my code, y keeps track of 7, 2.7. 4.7, 8.7, etc.
It gets added to result whenever a bit is set in b. long long c = (__int128_t)a*b%md;
he he)
Edited by author 14.05.2021 21:34
Edited by author 14.05.2021 21:34 |
| Solution with using matrix | __fractal | 1013. K-based Numbers. Version 3 | 3 Dec 2019 10:17 | 1 |
Answer is number in the (1, 1) of this matrix
|k - 1 k - 1| ^ N
| 1 0 |
Example:
If n is 2 and k is 10 then
|9 9| ^ 2 = |90 81|
|1 0| |9 9|
And answer is 90.
Use fast power algorithm to count it in O(logn). |
| fast O(ln n) solution | Gleb Dubosarskii | 1013. K-based Numbers. Version 3 | 21 Nov 2018 23:37 | 2 |
This problem can be solved in logarithmic time by using of such formula |F_{n+1} F_n| |k-1 1|^n |k-1 1| | | =| | x | | |F_n F_{n-1}| |k-1 0| |1 0| and applying fast multiplication. The answer is F_n. This formula generalize corresponding formula for Fibonacci sequence https://www.nayuki.io/page/fast-fibonacci-algorithms. It can be easily proven by induction. but the formula is wrong when n=2
Edited by author 21.11.2018 23:38
Edited by author 21.11.2018 23:38 |
| Can anybody tell me the algorithm to solve this question? | Myrcella | 1013. K-based Numbers. Version 3 | 18 Aug 2018 13:05 | 4 |
I have solved 1009&1012 using dp. My algorithm is O(n). Obviously it can't pass this problem's test. I think maybe there are some ways to make it quicker but I can't figure out. When I was searching in internet for solutions, I found that they are all for 1012. I'm a Junior high school students and my math is poor (for this question) TAT. Can anybody help me?? THx in advance. You should try to look up on the Internet how to find Fibonacci number with matrix exponentiation. The level of material should be accessible to a high school student if you are willing to spend couple of hours getting comfortable with new notations/definitions. There's not much theory behind this. You also need to know how to do fast exponentiation (i.e. in O(lon n) instead of O(n)) and use Long arithmetics (like BigInteger in Java). Thanks! Luckily I have known about knoledge about quickpow. Very helpful segguestion!XD Thank you again. I think I gain a lot after solving this question! I nearly knew nothing about matrix in the past. |
| AC test cases | lakerka | 1013. K-based Numbers. Version 3 | 27 Jan 2018 12:15 | 4 |
2
1000000000000000000
4561565
Answer: 3736220
1000000000000000000
1000000000000000000
1000000000000000000
Answer: 999999999999999999
1000000000000000000
2
1000000000000000000
Answer: 207504272460937501
101654687486400
2
10054654646101
Answer: 6318728278733
5000
4000
3000
Answer: 0 |
| Need Help RUNTIME ERROR in TEST #3 | Khanhhuy_19 | 1013. K-based Numbers. Version 3 | 27 Jan 2018 12:02 | 1 |
Some one give me some kind of this test pls thanks. |
| Accepted here WA on SPO | Mahilewets Nikita [BSUIR] | 1013. K-based Numbers. Version 3 | 18 Dec 2017 21:31 | 2 |
I wrapped my solution in function and added several test cases handling and submitted it to http://www.spoj.com/problems/KBASEEN/ Got WA Maybe you try to do so I am interested whether you will be AC Did you realise that n=1 is allowed on SPOJ while not on Timus? |
| To admins | Dmitri Belous | 1013. K-based Numbers. Version 3 | 10 Mar 2017 21:14 | 1 |
Please, add a comma after "digits" in the phrase "an amount of valid K based numbers, containing N digits, modulo M".
I decided "modulo M" is related to "K based numbers", but it's related to "an amount". |
| K based numbers, containing N digits modulo M | sleepwalker | 1013. K-based Numbers. Version 3 | 17 Nov 2016 18:22 | 1 |
What does it mean? For example if K = 10, N = 3, M = 112 correct numbers are
101
102
103
104
105
106
107
108
109
110
111
Is it right?
Thanks.
Edited by author 17.11.2016 18:22 |
| интересное усложнение | Dubsage | 1013. K-based Numbers. Version 3 | 26 Feb 2016 20:05 | 3 |
|
| is N<=18? | begi | 1013. K-based Numbers. Version 3 | 16 Feb 2016 18:14 | 3 |
If N=10^18 "digits" then complexity can be too big.
Also I didn't quite understand the logic of mod M, if the test is 2 10 5: then correct answer is 0, if the test is 2 10 13, then correct answer is 3 {10, 11, 12}? Thank you!
Your test case helped me getting an AC. No. N=10^18 is correct
If use recurrence to calculating n = 1 then n = 2 then n = 3 etc then complexity too big
But there is shortcut to make exponential jumps in calculating (hint: matrix) |
| What's the difference btween -1 and m-1? | LNCP | 1013. K-based Numbers. Version 3 | 10 Feb 2016 17:26 | 2 |
It's obvious we calculate recurrence with Matrix.But in the base Matrix,I first used -1,then I got WA#3,while I replaced it with m-1,I got AC.Who can explain it to me?
Edited by author 07.02.2015 18:44 I think you mean first used +1, not -1? -1 makes strange recurrence
If you mean +1, then makes Fibonacci sequence. But problem not Fibonacci, although similar idea.
When use m - 1 to replace +1, makes problem's recurrence |
| some hint | wangbicheng1 | 1013. K-based Numbers. Version 3 | 7 Nov 2015 11:08 | 1 |
Use matrix multiplication
(an+1,an)T=M(an,an-1)T |
| Loop in python | crc | 1013. K-based Numbers. Version 3 | 7 Feb 2015 18:55 | 2 |
a "for"-loop in python for integers 1 <= i <= 10^18 needs a lot of time. Is there a way to avoid to do such a huge for-loop?
Edited by author 21.01.2015 20:28 You should calculate recurrence with Matrix and use quick-power to calculate the power of Matrix．Do you need details about the algo? |
| use python ;) | 5Ki3s0x1C9 | 1013. K-based Numbers. Version 3 | 10 Jul 2014 13:15 | 1 |
|
| Hint | Marius Žilėnas | 1013. K-based Numbers. Version 3 | 24 Oct 2013 17:11 | 1 |
Hint Marius Žilėnas 24 Oct 2013 17:11 Use the same logic as in Unit1012 (do not make recursive calls, instead use a register of 3 values, f(N-1), f(N-2) and the one you are calculating: f(N). Then calculate all values from i=2 to N and use register. This reduces memory requirements :), makes the code for this problem faster.) |
