fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. string A, B;
  9. long long max_gcd = 0;
  10.  
  11. // Funkcja obliczająca NWD
  12. long long gcd(long long a, long long b) {
  13.     while (b) {
  14.         a %= b;
  15.         swap(a, b);
  16.     }
  17.     return a;
  18. }
  19.  
  20. // Rekurencyjna funkcja przeszukująca wszystkie kombinacje znaków zapytania
  21. void solve(int index, string &a, string &b) {
  22.     if (index == 2 * n) {
  23.         long long num_a = stoll(a);
  24.         long long num_b = stoll(b);
  25.         max_gcd = max(max_gcd, gcd(num_a, num_b));
  26.         return;
  27.     }
  28.  
  29.     int i = index / n;
  30.     int pos = index % n;
  31.  
  32.     if (i == 0) {
  33.         if (A[pos] == '?') {
  34.             for (char c = '0'; c <= '9'; ++c) {
  35.                 a[pos] = c;
  36.                 solve(index + 1, a, b);
  37.             }
  38.         } else {
  39.             a[pos] = A[pos];
  40.             solve(index + 1, a, b);
  41.         }
  42.     } else {
  43.         if (B[pos] == '?') {
  44.             for (char c = '0'; c <= '9'; ++c) {
  45.                 b[pos] = c;
  46.                 solve(index + 1, a, b);
  47.             }
  48.         } else {
  49.             b[pos] = B[pos];
  50.             solve(index + 1, a, b);
  51.         }
  52.     }
  53. }
  54.  
  55. int main() {
  56.     ios_base::sync_with_stdio(false);
  57.     cin.tie(NULL);
  58.  
  59.     if (!(cin >> n)) return 0;
  60.     cin >> A >> B;
  61.  
  62.     string a = A;
  63.     string b = B;
  64.  
  65.     solve(0, a, b);
  66.  
  67.     cout << max_gcd << "\n";
  68.  
  69.     return 0;
  70. }
Success #stdin #stdout 1.45s 5316KB
comments (?)
stdin
copy 
4
??8?
????
stdout
copy 
9989
https://ideone.com/y6n055
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!