PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: flamestorm153
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
Observation
PROBLEM:
Given a digital panel and the cost of turning on each of its seven types of segments, find the minimum cost of writing a factor of N on the panel.
EXPLANATION:
N is extremely large, so there is no hope of directly factorizing it and trying to write each factor. We need to be a bit more clever.
First, note that 1 is a factor of any integer. Further, 1 is contained in all of \{0, 3, 4, 7, 8, 9\} (in terms of segments that need to be drawn).
So, instead of writing any of these on the panel, we could just write 1 instead for strictly lower cost. They can thus be discarded entirely.
That leaves us with 1, 2, 5, 6.
A bit more analysis tells us:
- Using 1 in any number with length \gt 1 is pointless, we could just write the single digit 1 instead.
- If the number we write ends with 2 or 5, then we could just write the single digit 2 or 5 respectively for lower cost while still maintaining divisibility.
- So, if we are to write a number with length \gt 1, it must end with 6 and won’t contain 1.
- A number ending with 6 is even, so if such a number contains a 2 somewhere, it’s better to just write the single digit 2.
So, for numbers with length \gt 1, we only need to care about those that end with 6 and use the digits 5 and 6. How many of these do we need to check?
As it turns out, not too many!
Note that the costs are rather small, so it quickly becomes optimal to just write 1 instead of some long number consisting of 5's and 6's.
In particular, if we set B = 50 and all the other costs to 1, then writing 1 costs 51, writing 5 costs 5, and writing 6 costs 6. This is essentially the worst case, since increasing the cost of 1 would increase the cost of 5 and 6 by the same amount (all three share the C segment).
So, writing any length 10 or longer number is not optimal: it is better to just write 1.
There are \leq 2^{10} numbers of length \lt 10 whose digits consist of 5 and 6, so test them all. Checking whether a small number x divides N can be done in \mathcal{O}(|N|) by iterating across the digits of N and maintaining the remainder modulo x, and doesn’t need a BigInteger class. You can also just use Python.
Don’t forget to also check with 1 and 2. Finally, print the minimum across all factors.
TIME COMPLEXITY
\mathcal{O}(2^{10} \cdot |N|) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
vector<long long> v;
bool div(string s, long long x) {
long long curr = 0;
for (char c : s) {
curr *= 10; curr %= x;
curr += (c - '0'); curr %= x;
}
return (curr == 0);
}
void solve() {
string n;
cin >> n;
int a, b, c, d, e, f, g;
cin >> a >> b >> c >> d >> e >> f >> g;
int dc[9];
dc[1] = b + c, dc[2] = a + b + d + e + g, dc[5] = a + c + d + f + g, dc[6] = a + c + d + e + f + g;
int res = dc[1];
for (long long x : v) {
if (div(n, x)) {
int cost = 0;
while (x) {
cost += dc[x % 10];
x /= 10;
}
res = min(res, cost);
}
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
v.push_back(2);
v.push_back(5);
v.push_back(6);
for (int i = 1; i <= 8; i++) {
for (int x = 0; x < (1 << i); x++) {
int k = x, cnt = 0;
long long num = 0;
for (int j = 0; j < i; j++) {
if (k & 1) {num += 5; cnt++;}
else {num += 6;}
k >>= 1;
num *= 10;
}
num += 6;
if (cnt % 3 != 0) {v.push_back(num);}
}
}
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
return res;
}
string readString(int minl, int maxl, const string& pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1000);
in.readEoln();
while (tt--) {
string s = in.readString(1, 100, in.number);
in.readSpace();
vector<int> a(7);
for (int i = 0; i < 7; i++) {
a[i] = in.readInt(1, 50);
if (i == 6) {
in.readEoln();
} else {
in.readSpace();
}
}
vector<int> c(10);
c[1] = a[1] + a[2];
c[2] = a[0] + a[1] + a[3] + a[4] + a[6];
c[5] = a[0] + a[2] + a[3] + a[5] + a[6];
c[6] = a[0] + a[2] + a[3] + a[4] + a[5] + a[6];
reverse(s.begin(), s.end());
int ans = 1000;
auto Check = [&](long long x) {
long long t = 0;
long long p10 = 1;
for (char d : s) {
t = (t + (d - '0') * p10) % x;
p10 = p10 * 10 % x;
}
if (t == 0) {
int y = 0;
while (x > 0) {
y += c[x % 10];
x /= 10;
}
ans = min(ans, y);
}
};
Check(1);
Check(2);
Check(5);
for (int i = 0; i < 10; i++) {
for (int j = 1; j < (1 << i); j += 2) {
long long t = 0;
for (int k = i - 1; k >= 0; k--) {
t *= 10;
if (j & (1 << k)) {
t += 6;
} else {
t += 5;
}
}
Check(t);
}
}
cout << ans << '\n';
}
in.readEof();
return 0;
}
Editorialist's code (Python)
to_check = [1, 2, 5, 6]
for len in range(2, 10):
for mask in range(2 ** len):
num = 0
for i in range(len):
num *= 10
if mask & (1 << i):
num += 5
else:
num += 6
if num%5 == 0:
continue
to_check.append(num)
for _ in range(int(input())):
N, a, b, c, d, e, f, g = map(int, input().split())
cost = [0] * 10
cost[1] = b + c
cost[2] = a + b + g + e + d
cost[5] = a + f + g + c + d
cost[6] = cost[5] + e
def f(x):
ret = 0
while x > 0:
ret += cost[x%10]
x //= 10
return ret
ans = int(10 ** 9)
for x in to_check:
if N%x == 0:
ans = min(ans, f(x))
print(ans)