Skip to content

Instantly share code, notes, and snippets.

@Acarus
Created February 19, 2017 17:29
Show Gist options
  • Save Acarus/b9db9293150ddec12cde06ae62e2d5dd to your computer and use it in GitHub Desktop.
Save Acarus/b9db9293150ddec12cde06ae62e2d5dd to your computer and use it in GitHub Desktop.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
inline bool match(const string& s, string pattern) {
int i = 0;
while (i + pattern.size() - 1 < s.size()) {
if (s[i] == '0' || s.substr(i, pattern.size()) != pattern) {
return false;
}
i += pattern.size();
reverse(begin(pattern), end(pattern));
int carry = 1;
for (int j = 0; j < pattern.size(); ++j) {
if (pattern[j] + carry > '9') {
pattern[j] = '0';
} else {
pattern[j]++;
carry = 0;
break;
}
}
if (carry != 0) {
pattern += '1';
}
reverse(begin(pattern), end(pattern));
}
return i == s.size();
}
inline string solve(const string& s) {
for (int i = 1; i <= s.size()/2; ++i) {
if (match(s, s.substr(0, i))) {
return "YES " + s.substr(0, i);
}
}
return "NO";
}
int main() {
ios_base::sync_with_stdio(0);
int q;
cin >> q;
while (q --> 0) {
string s;
cin >> s;
cout << solve(s) << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment