This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <cfloat>
#include <random>
using namespace std;
struct birthdayNumber {
int len, three, five, eight;
const bool operator<(const birthdayNumber& rhs) const {
if(len != rhs.len) return len < rhs.len;
if(three != rhs.three) return three < rhs.three;
if(five != rhs.five) return five < rhs.five;
return eight < rhs.eight;
}
const bool operator==(const birthdayNumber& rhs) const {
return len == rhs.len && three == rhs.three && five == rhs.five && eight == rhs.eight;
}
};
vector<birthdayNumber> cache(1e6 + 5, {987654321, 987654321, 987654321, 987654321});
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// ifstream cin;
// cin.open("inputs.txt");
cache[3].len = 1;
cache[3].three = 1;
cache[5].len = 1;
cache[5].five = 1;
cache[6].len = 2;
cache[6].three = 2;
cache[8].len = 1;
cache[8].eight = 1;
for(int i = 9; i <= 1000000; ++i) {
birthdayNumber a, b, c;
a = cache[i - 3];
b = cache[i - 5];
c = cache[i - 8];
birthdayNumber d = min({a, b, c});
if(d == a) {
cache[i] = a;
cache[i].three++;
} else if(d == b) {
cache[i] = b;
cache[i].five++;
} else {
cache[i] = c;
cache[i].eight++;
}
if(cache[i].three >= 987654321) cache[i].three -= 987654321;
if(cache[i].five >= 987654321) cache[i].five -= 987654321;
if(cache[i].eight >= 987654321) cache[i].eight -= 987654321;
cache[i].len++;
}
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
if(cache[n].len == 987654321) cout << -1 << '\n';
else {
if(cache[n].three >= 987654321) cache[n].three -= 987654321;
if(cache[n].five >= 987654321) cache[n].five -= 987654321;
if(cache[n].eight >= 987654321) cache[n].eight -= 987654321;
// cout << cache[n].three << " " << cache[n].five << " " << cache[n].eight << endl;
for(int i = 0; i < cache[n].three; ++i)
cout << 3;
for(int i = 0; i < cache[n].five; ++i)
cout << 5;
for(int i = 0; i < cache[n].eight; ++i)
cout << 8;
cout << '\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |