PROBLEM LINK:
Author: chirag_mathur
Testers: hellb0y_suru, valiant_vidit, abhinav42
Editorialist: chirag_mathur
DIFFICULTY:
EASY
PROBLEM:
Given a numerical system consisting of {! #,%,*,@}.
- Predict the next/upcoming magical year from the given year Y.
- Add the given age A to the magical year and print the new age X
Prerequisites:
- knowledge of sorting and recursion.
- A little amount of brain to be applied while solving or understanding the editorial
QUICK EXPLANATION:
Try storing all the magical years in a vector in a sorted manner, then find the upcoming/next magical year using lower_bound function and add it to the given age.
EXPLANATION:
According to the rules of the magical year, the magical year will be of even length and consists of only '! and ‘*’. First, we will precompute a vector with all the magical years till length 16 consisting of ‘!’ and ‘*’ using recursive function. If the length of the given year is odd then the next magical year will be the smallest possible magical year of length + 1 and if it is of even length then we can find the next magical year using lower_bound function from the precomputed vector. If the given year is a magical year then we have to take the next magical year.
Then we can define the rules of adding and carry forwarding in the given numerical system consisting of {!,#,%,*,@} for each character and then we can add the two strings which are a magical year and the given age and then print the resulting string which is the age.
The complexity of the code is O(k + T*log(n)) where k is the constant time taken to precompute the vector consisting magical year and T is the number of testcases.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<string> v;
ll n;
char addc(char a, char b)
{
if (a == '!')
{
return b;
}
else if (b == '!')
{
return a;
}
else
{
if (a == '#' && b == '#')
{
return '%';
}
else if (a == '%' && b == '%')
{
return '@';
}
else if (a == '*' && b == '*')
{
return '#';
}
else if (a == '@' && b == '@')
{
return '*';
}
else if (a == '#' && b == '%' || b == '#' && a == '%')
{
return '*';
}
else if (a == '#' && b == '*' || b == '#' && a == '*')
{
return '@';
}
else if (a == '#' && b == '@' || b == '#' && a == '@')
{
return '!';
}
else if (a == '%' && b == '@' || b == '%' && a == '@')
{
return '#';
}
else if (a == '%' && b == '*' || b == '%' && a == '*')
{
return '!';
}
else
// else if (a == '*' && b == '@' || b == '*' && a == '@')
{
return '%';
}
}
}
char carryc(char a, char b)
{
if (a == '!')
{
return '!';
}
else if (b == '!')
{
return '!';
}
else
{
if (a == '#' && b == '#')
{
return '!';
}
else if (a == '%' && b == '%')
{
return '!';
}
else if (a == '*' && b == '*')
{
return '#';
}
else if (a == '@' && b == '@')
{
return '#';
}
else if (a == '#' && b == '%' || b == '#' && a == '%')
{
return '!';
}
else if (a == '#' && b == '*' || b == '#' && a == '*')
{
return '!';
}
else if (a == '#' && b == '@' || b == '#' && a == '@')
{
return '#';
}
else if (a == '%' && b == '@' || b == '%' && a == '@')
{
return '#';
}
else if (a == '%' && b == '*' || b == '%' && a == '*')
{
return '#';
}
else
// else if (a == '*' && b == '@' || b == '*' && a == '@')
{
return '#';
}
}
}
string finalage(string yr, string age)
{
string x = yr.length() >= age.length() ? yr : age;
string y = age.length() <= yr.length() ? age : yr;
string fage = "";
int diff = x.length() - y.length();
for (int i = 1; i <= diff; i++)
{
y = '!' + y;
}
char fcarry = '!';
char c1, c2, a1, a2;
for (int i = x.length() - 1; i >= 0; i--)
{
c1 = carryc(fcarry, x[i]);
a1 = addc(fcarry, x[i]);
c2 = carryc(a1, y[i]);
a2 = addc(a1, y[i]);
fage = a2 + fage;
fcarry = addc(c1, c2);
}
if (fcarry != '!')
{
fage = fcarry + fage;
}
return fage;
}
void getpossiblevalues(string value, int numberemark, int numberstar)
{
if (value.length() > 16)
return;
if (numberemark == numberstar)
v.push_back(value);
getpossiblevalues(value + '*', numberemark, numberstar + 1);
if (value.length() != 0)
getpossiblevalues(value + '!', numberemark + 1, numberstar);
}
int main()
{
getpossiblevalues("", 0, 0);
sort(v.begin(), v.end());
//cout<<v.size()<<endl;
vector<string> v1[9];
for (int i = 0; i <= v.size(); i++)
{
v1[v[i].length() / 2].push_back(v[i]);
}
ll t;
cin >> t;
while (t--)
{
string year;
string age;
cin >> year;
cin >> age;
string magicalyr = "";
int len = year.length();
if (year.length() % 2 != 0)
{
magicalyr = v1[(year.length() + 1) / 2][0];
}
else
{
if (lower_bound(v1[year.length() / 2].begin(), v1[year.length() / 2].end(), year) == v1[year.length() / 2].end())
{
magicalyr = v1[(year.length() / 2) + 1][0];
}
else
{
int pos = lower_bound(v1[year.length() / 2].begin(), v1[year.length() / 2].end(), year) - v1[year.length() / 2].begin();
magicalyr = v1[(year.length() / 2)][pos];
if (year == magicalyr)
{
magicalyr = pos + 1 < v1[(year.length() / 2)].size() ? v1[(year.length() / 2)][pos + 1] : v1[((year.length() / 2) + 1)][0];
}
}
}
//cout<<magicalyr<<endl;
cout << finalage(magicalyr, age) << endl;
}
return 0;
}
Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;
// ! # % * @
vector<long long int> v;
long long int changeTo10(long long int n){
long long int cnt = 1,ans=0;
while(n>0){
ans+= cnt*(n%10);
n/=10;
cnt*=5;
}
return ans;
}
long long int changeTo5(long long int n){
vector<long long int> temp;
while(n>0){
temp.push_back(n%5);
n/=5;
}
reverse(temp.begin(),temp.end());
long long int ans = 0;
for(auto &i: temp) ans=ans*10 + i;
return ans;
}
long long int add(long long int &n, long long int x){
long long int a = changeTo10(n) , b = changeTo10(x);
a = a + b;
return changeTo5(a);
}
void gen(int zero, int once, long long int ans){
if(zero==0 && once==0){
v.push_back(ans);
return;
}
else{
if(once>0){
gen(zero,once-1, (ans*10) + 3 );
}
if(zero>0){
gen(zero-1,once,ans*10);
}
}
}
long long int strToNum(string &a){
long long int ans=0;
for(int i=0;i<a.size();i++){
if(a[i]=='!') ans=ans*10;
else if(a[i]=='#') ans=ans*10 + 1;
else if(a[i]=='%') ans=ans*10 + 2;
else if(a[i]=='*') ans=ans*10 + 3;
else if(a[i]=='@') ans=ans*10 + 4;
}
return ans;
}
string NumToStr(long long int n){
string res="";
if(n==0){
res = '!';
return res;
}
else{
while(n>0){
if( n%10 == 0 ) res = '!' + res;
else if( n%10 == 1 ) res = '#' + res;
else if( n%10 == 2 ) res = '%' + res;
else if( n%10 == 3 ) res = '*' + res;
else if( n%10 == 4 ) res = '@' + res;
n/=10;
}
return res;
}
}
void sol(){
string a,b; cin >> a >> b;
long long int x = strToNum(a) , y = strToNum(b);
if(x >= 33333330000000) x = 3000000003333333;
else{
auto it = upper_bound(v.begin(),v.end(),x);
x = *it;
}
x = add(x,y);
cout << NumToStr(x)<<"\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=1;i<=7;i++) gen(i,i-1,3LL);
sort(v.begin(),v.end());
long long int t; cin >> t;
while(t--) sol();
}
Tester's Solution 2
/*author : vidit shukla
(valiant_vidit)*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define bhaago ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define loop(a, b, i) for (ll i = a; i < b; i++)
#define loop1(a, b, i) for (ll i = a; i > b; i--)
#define printclock cerr << "Time : " << 1000 * (ld)clock() / (ld)CLOCKS_PER_SEC << "ms\n";
#define endl '\n'
#define yy cout << "YES" << endl
#define nn cout << "NO" << endl
#define fix(f, n) std::fixed << std::setprecision(n) << f
const double pi = std::acos(-1);
using namespace std;
const ll mod = 1000000000 + 7;
ll power(ll x, ll y, ll md)
{
ll res = 1;
x = x % md;
if (x == 0)
return 0;
while (y > 0)
{
if (y & 1)
res = (res * x) % md;
y = y >> 1;
x = (x * x) % md;
}
return res;
}
ll m_mul(ll a, ll b)
{
a = a % mod;
b = b % mod;
return (a * b + mod) % mod;
}
ll m_add(ll a, ll b)
{
a = a % mod;
b = b % mod;
return (a + b + mod) % mod;
}
ll spf[(ll)1e7 + 2] = {0};
void siv()
{
spf[1] = 1;
loop(1, 1e7 + 2, i)
spf[i] = i;
loop(2, 1e7 + 2, i)
spf[i] = 2,
i++;
for (ll i = 3; i * i < (ll)1e7 + 2; i++)
{
if (spf[i] == i)
for (ll j = i * i; j < (ll)1e7 + 2; j = j + i)
if (spf[j] == j)
spf[j] = i;
}
}
ll chk(string sm)
{
if (sm.size() % 2 != 0)
return 0;
string str = "";
loop(0, sm.size(), i)
{
if (str.size() < (sm.size()) / 2)
str = str + "3";
else
str = str + "0";
}
if (sm.compare(str) > 0)
return 1;
else
return 0;
}
string rec1(string ss, ll &zero, ll &th, ll mx)
{
if (ss.size() == 0)
return "";
string str = "";
ll cnt = 0;
loop(0, ss.size(), i)
{
if (cnt > 0 && zero != mx)
{
str = str + "0";
zero++;
}
else if (ss[i] == '0' && zero != mx)
{
ll az = zero + 1;
ll ab = th;
string sn = rec1(ss.substr(i + 1, ss.size() - i - 1), az, ab, mx);
sn = "0" + sn;
string snew = ss.substr(i, ss.size() - i);
if (sn.size() == snew.size())
{
if (sn.compare(snew) >= 0)
{
zero = az, th = ab;
return (str.substr(0, i) + sn);
}
else if (th != mx)
{
str = str + "3";
cnt = '3' - ss[i];
th++;
}
}
else if (th != mx)
{
str = str + "3";
cnt = '3' - ss[i];
th++;
}
}
else if (th != mx)
{
str = str + "3";
cnt = '3' - ss[i];
th++;
}
}
return str;
}
string cnv(string ss)
{
string str = "";
if (ss.size() % 2)
{
loop(0, ss.size() + 1, i)
{
if (i == 0)
str = str + "3";
else if (str.size() <= (ss.size() + 1) / 2)
str = str + "0";
else
str = str + "3";
}
}
else
{
ll th = 0;
ll cnt = 0;
ll ctt = 0;
loop(0, ss.size(), i)
{
if (i == 0)
{
str = str + "3";
cnt = '3' - ss[0];
th++;
continue;
}
if ((cnt > 0) && ctt != ss.size() / 2)
{
str = str + "0";
ctt++;
}
else if (ss[i] == '0' && ctt != ss.size() / 2)
{
ll az = ctt + 1;
ll bz = th;
string s11 = rec1(ss.substr(i + 1, ss.size() - i - 1), az, bz, ss.size() / 2);
string spk = ss.substr(i, ss.size() - i);
s11 = "0" + s11;
if (s11.size() == spk.size())
{
if (s11.compare(spk) >= 0)
{
ctt = az;
th = bz;
str = str + s11;
return str;
}
else if (th != ss.size() / 2)
{
str = str + "3";
cnt = 3;
th++;
}
}
else if (th != ss.size() / 2)
{
str = str + "3";
cnt = 3;
th++;
}
}
else if (th != ss.size() / 2)
{
str = str + "3";
cnt = '3' - ss[i];
th++;
}
}
}
return str;
}
void add(string &str, string ss, string sl, ll ind, ll cnt)
{
loop1(sl.size() - 1, -1, i)
{
ll diff = sl.size() - ss.size();
ll az = 0;
if (i - diff >= 0)
az = (ss[i - diff] - '0');
az = az + (sl[i] - '0') + cnt;
cnt = az / 5;
ll bk = az % 5;
str = to_string(bk) + str;
}
{
if (cnt > 0)
str = to_string(cnt) + str;
return; // str;
}
return;
}
int main()
{
bhaago;
ll tc = 1;
cin >> tc;
while (tc--)
{
ll n;
string sm, sc;
cin >> sm >> sc;
map<char, char> mp;
mp['!'] = '0';
mp['#'] = '1';
mp['%'] = '2';
mp['*'] = '3';
mp['@'] = '4';
mp['0'] = '!', mp['1'] = '#', mp['2'] = '%', mp['3'] = '*', mp['4'] = '@';
string smn = "", scn = "";
loop(0, sm.size(), i)
{
smn = smn + mp[sm[i]];
}
loop(0, sc.size(), i)
{
scn = scn + mp[sc[i]];
}
string sstr = "";
ll k1 = 0, k2 = 0;
loop(0, smn.size(), i)
{
if (smn[i] == '0')
k1++;
else if (smn[i] == '3')
k2++;
}
string sans = "";
if (k1 == k2 && k1 + k2 == smn.size())
{
add(sans, "1", smn, 0, 0);
smn = sans;
}
if (chk(smn) == 0)
sstr = cnv(smn);
else
{
smn = smn + '!';
sstr = cnv(smn);
}
smn = sstr;
string str = "";
if (smn.size() < scn.size())
add(str, smn, scn, smn.size() - 1, 0); ////to complete
else
add(str, scn, smn, scn.size() - 1, 0);
loop(0, str.size(), i)
{
cout << mp[str[i]];
}
cout << endl;
}
return 0;
}
Tester's Solution 3 (in Python)
# abhinav42
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()
import math
from collections import defaultdict
from itertools import combinations_with_replacement,permutations
import bisect
import time
arr = []
d = defaultdict(list)
mask = defaultdict(int)
mask_inv = defaultdict(str)
def solve(s,no_of_mark,no_of_star):
if(len(s)>17):
return
if(no_of_mark == no_of_star):
arr.append(s)
solve(s+"*",no_of_mark,no_of_star+1)
if(len(s)>0):
solve(s+"!",no_of_mark+1,no_of_star)
def pre_process():
mask['!'] = 0
mask['#'] = 1
mask['%'] = 2
mask['*'] = 3
mask['@'] = 4
mask_inv['0'] = '!'
mask_inv['1'] = '#'
mask_inv['2'] = '%'
mask_inv['3'] = '*'
mask_inv['4'] = '@'
solve("",0,0)
arr.sort()
for i in arr:
d[len(i)].append(i)
def add(a,b,base):
len_a = len(a)
len_b = len(b)
s = "";
sum = "";
diff = abs(len_a - len_b);
for i in range(1,diff+1):
s += "0"
if (len_a < len_b):
a = s + a
else:
b = s + b;
carry = 0;
for i in range(max(len_a, len_b) - 1,-1,-1):
curr = carry + (ord(a[i]) -ord('0')) +( ord(b[i]) - ord('0'));
carry = curr // base
curr = curr % base;
sum = chr(curr + ord('0')) + sum
if (carry > 0):
sum = chr(carry + ord('0')) + sum;
return sum
if _name_ == "_main_":
start = time.time()
pre_process()
# print("--- %s seconds ---" % (time.time() - start))
next_magical_year=""
for _ in range(int(input())):
y = input()
a = input()
if(len(y)%2==1):
next_magical_year = d[len(y)+1][0]
elif(bisect.bisect( d[len(y)] , y ) == len(d[len(y)]) ):
next_magical_year = d[len(y)+2][0]
else:
index = bisect.bisect(d[len(y)] , y)
next_magical_year = d[len(y)][index]
year = ""
age = ""
for i in next_magical_year:
year+=str(mask[i])
for i in a:
age+=str(mask[i])
ans = add(age,year,5)
final_ans = ""
for i in ans:
final_ans+=mask_inv[i]
print(final_ans)