# SEVSEGFACT - Editorial

Author: flamestorm153
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh

TBD

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;
}

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);
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);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
while (tt--) {
string s = in.readString(1, 100, in.number);
vector<int> a(7);
for (int i = 0; i < 7; i++) {
if (i == 6) {
} else {
}
}
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';
}
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)


Very beautiful problem, though I wasn’t able to solve this in contest, but upsolving this is a real fun!

1 Like

Nice problem! I made all the observations except the last one, since I forgot to see the small costs (<50)!

It’s always a pleasure to read iceknight’s editorials, really. Hope to see more from you in the future!

1 Like

can you please help me with the last observation (i.e. the no. must end with 6 )
i am not getting that as there are no examples

I keep telling myself the low constraint is important. I’m impressed

It’s simple. Ending with 5 means that N is divisible by 5. Additionally, since the cost of 5 < cost of 6 because of the E segment being turned off, it is unnecessary to check as it’s enough to pick single 5. So last digit must be 6 for future computation.