PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
2054
PREREQUISITES:
None
PROBLEM:
Given N and K, find the sum of digits of S; where S denotes the smallest N-digit number such that it doesn’t contain a palindromic substring of length \gt K.
EXPLANATION:
Let’s try to greedily construct the smallest number we can that satisfies the palindrome property.
It’s best if the first digit is 1, since we can’t use 0.
After than, we can start using zeros - the next K digits can all be 0 without creating any palindromes of length \gt K.
However, the next character can’t be 0; and it also can’t be 1.
So, the best we can do is to place a 2.
Our number currently looks like
Now, once again we can start placing zeros.
However, this time we can only place \left \lfloor \frac{K-1}{2} \right\rfloor of them - otherwise we’d create a palindrome of the form 000\ldots 00200\ldots 000.
So, we now have the string
After this, we can’t place any more zeros; so we must place a 1.
Then, the pattern repeats — so the final string will look like
repeated upto length N.
Of course, what we’re really interested in is the sum of this string.
The zeros don’t contribute to it at all, so we just need to count the number of times 1 and 2 occur.
That’s not too hard.
The length of the pattern is L = 2 + K + \left \lfloor \frac{K-1}{2} \right\rfloor.
- The ones appear at positions 1, L+1, 2L+1, 3L+1, \ldots
So, if x ones are to appear in the string upto position N, we’d need (x-1)\cdot L + 1 \leq N.
Using this, you can find the largest valid x either with math or just binary search it. - The twos appear at positions K+2, K+2+L, K+2+2L, \ldots
Similarly, for y twos to appear in the string, we’d need K+2+L\cdot (y-1) \leq N; so the largest valid y can be found quickly.
Once x and y are known from above, the answer is just x + 2y.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
Author's code (C++)
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#define int long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void solve()
{
int n = readInt(2,1000000000,' ');
int k = readInt(1,n-1,'\n');
int q = k + 2 + (k-1)/2;
int ans = 3*(n/q);
if(n%q > k+1){
ans += 3;
} else if(n%q){
ans += 1;
}
cout << ans;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,5000,'\n');
while(T--){
solve();
cout<<'\n';
}
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's code (C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
void solve(int tc)
{
int n,k;
cin >> n >> k;
int l = (3*k+3)/2;
int ans = 3*(n/l);
n%=l;
if(n>k+1)
ans+=3;
else if(n>0)
ans++;
cout << ans << '\n';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
L = 2 + k + ((k-1)//2)
# (x-1)L + 1 <= N
# (x-1)L <= N-1
# x <= (N-1)/L + 1
x = (n-1)//L + 1
# k+2+(y-1)L <= N
# y <= (N-k-2)/L + 1
y = 0
if n >= k+2: y = (n-k-2)//L + 1
print(x + 2*y)