Thanks a lot for the help. It worked!
Working solution is here
I’m not able to understand why I’m getting wrong answer for my submission. I’ve tripled checked my logic and have referred to a detailed tutorial on geeksforgeeks. Here’s the link:
Following is the link to my submission:
https://www.codechef.com/viewsolution/33043153
Please help me understand where I’m going wrong.
In the given constraints, d0 and d1 are less than/equal to 9, but in some test cases, they are greater than 9. Why?
Hi, I am stuck at the multiple of 3 problem.
my thought process behind the solution is :
case 1-- if (d0 +d1)%3 ==0 then the number will be a multiple of 3.
case 2 – if (k-3)*sum%3 ==0 then also the number will be will be multiple of 3
( case 2 can happen because of any of the two a-- k is multiple of 3 b-- sum is multiple 3.)
also this code works fine on the given test cases, but is giving WA for the solution.
here’s the link for my solution : CodeChef: Practical coding for everyone
please help,
thanks
I am getting Wrong answer. I tried something different. Is my solution approach, wrong? Any suggestion or help will be appreciated. Thank you
#include<bits/stdc++.h>
using namespace std;
bool solve(){
ll k,d0,d1;
cin>>k>>d0>>d1;
int d2 = d0 + d1;
//corner case
if(k==2){
if((d0*10+d1)%3==0)
return true;
return false;
}
//corner case
if(k==3){
if((d0*100+d1*10+d2)%3==0)
return true;
return false;
}
vector<int> pattern; // pattern
/*
example : 13 8 1
the pattern we are looking to built is
pattern [ 2 2 1 2 1 1 0 1 0 0 2 0 ]
remainder of 4 5 6 7 8 9 10 11 12 13 14 15 th digit,
so, since the number ought to be 13(k) we check the 13th digits remainder.
*/
int rem = (d0*100+d1*10+d2)%3;
for (int i = 0; i < 12; i++)
{
d2 = (d2*2)%10;
rem = (rem*10 +d2)%3;
pattern.push_back(rem);
}
// debug(pattern)
/*
Since the pattern is repeating
[ 2 2 1 2 1 1 0 1 0 0 2 0 2 2 1 2 1 1 0 1 0 0 2 0 ]
it start to repeat at every 12 remainder,
so (k-3-1)%12 since we reduced the first 3 remainders which is not
repetitive. also we have checked in the corner cases.
*/
if(pattern[(k-3-1)%12]==0) return true;
return false;
}
int main() {
fastio();
ll t=1;
cin >> t;
while(t--) {
if(solve())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
I’m sorry i am new to cp but what does " the constraints imposed on K i.e. 1 <= K <= 10^{12}, means you cannot go for the O(K)O(K) approach." mean in the problem “Multiple of 3” ?