Ideone.com

download

copy

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 105;
int n;
int a[N];
// memo array is used for memoization of function isWinning
int memo[N][N];
 
// memo1 array is used for memoization of function probWinning
double memo1[N][N];
 
// Here g denotes the current gcd in the game. taken denotes how many numbers are taken out of the game, ie how many numbers
// have been thrown out.
// This function returns whether the state denotes by (g, taken) is winning or not?
int isWinning (int g, int taken) {
      int &res = memo[g][taken];
      // memoization step.
      // if res is negative (meaning that we have not computed the answer corresponding to (g, taken) state, we need to compute that), then we will
      // do the processing of that state.
      // otherwise, we will simply return the answer.
      if (res == -1) {
            res = 0;
            // if all the numbers has been taken out, it means there is no more numbers to play with.
            // hence the person playing this turn will lose because he wont be able to make any move.
            if (taken == n) {
                  res = 0;
            } else {
                  // tot denotes number of multiples of g in the array a.
                  int tot = 0;
                  for (int i = 0; i < n; i++) if (__gcd(g, a[i]) == g) tot++;
 
                  // if not all multiples of g are thrown out, it means that there are still multiples of g currently in the array a.
                  // we can use them in the game. gcd is not going to change being the number we are going to take will be multiple of g.
                  // as gcd (g, t) = g if t = k * g (ie t is a multiple of g).
                  if (taken < tot) {
                        if (taken < tot && !isWinning(g, taken + 1)) {
                              res = 1;
                        }
                  }
 
                  // if have already won, no need to process the remaining the states. This is simply a pruning step, wont have much effect on the
                  // overall complexity. You can chose to run this step too.
                  if (res == 0) {
                        // Now we will iterate over the numbers which are having gcd with g not equal to 1 (because we will lose in that case) and
                        // not equal to g because we have already considered that case before.
                        for (int i = 0; i < n; i++) {
                              if (__gcd (g, a[i]) > 1) {
                                    if (__gcd(g, a[i]) == g) {
                                          continue;
                                          // this case has been already considered before.
                                    } else {
                                          if (!isWinning(__gcd(g, a[i]), taken + 1)) {
                                                res = 1;
                                                break;
                                          }
                                    }
                              }
                        }
                  }
            }
      }
      return res;
}
 
// Here g denotes the current gcd in the game. taken denotes how many numbers are taken out of the game, ie how many numbers
// have been thrown out.
// function returns the probability of winning if I am at state denoted by (g, taken).
double probWinning (int g, int taken) {
      double &res = memo1[g][taken];
      // memoization step.
      // if res is negative (meaning that we have not computed the answer corresponding to (g, taken) state, we need to compute that), then we will
      // do the processing of that state.
      // otherwise, we will simply return the answer.
 
      if (res <= -0.5) {
            if (g == 1) {
                  // if gcd is 1, it means that other person has made the move and has made the gcd equal to 1, Hence other person is losing.
                  // that means that player at the current step is winning. So probability of winning = 1.
                  res = 1.0;
            } else {
                  res = 0;
                  if (taken == n) {
                        res = 0;
                  } else {
                        // tot denotes number of multiples of g in the array a.
                        int tot = 0;
                        for (int i = 0; i < n; i++) if (__gcd(g, a[i]) == g) tot++;
 
                        // this is an important step to pay attention to.
                        // we have currently taken element thrown out of the game, we have tot elements which are multiples of g.
                        // hence there are still tot - taken elements which are multiples of g.
                        // we can chose any one of them with equal probability.
                        // probability of chosing one of them will be equal to (tot - taken) / (total elements that are not thrown).
                        // As total elements that are not thrown = n - taken.
                        // Hence probability of chosing one of them will be equal to (tot - taken) / (n - taken).
 
                        // Note that in this case, there wont be any change in gcd, it will remain g (because current element in consideration is multiple of g).
                        double res1 = 0;
                        if (taken < tot) {
                              res += (1 - probWinning(g, taken + 1)) * 1.0 * (tot - taken) / (n - taken);
                        }
 
                        // Now we will iterate over the numbers which are having gcd with g not equal to g because we have already considered that case before.
                        for (int i = 0; i < n; i++) {
                              if (__gcd(g, a[i]) == g) {
                                    // case already considered, nothing to do.
                                    continue;
                              } else {
                                    // You can make your current gcd to gcd(g, a[i]).
                                    // number of taken elements (or thrown elements) will increase by 1.
                                    // probability of a single case is 1 / (elements remaining) = 1 / (n - taken).
                                    res += (1 - probWinning(__gcd(g, a[i]), taken + 1)) * 1.0 / (n - taken);
                              }
                        }
 
                        // if your numbers becomes very small, it is better to make it equal to 0.
                        // sometimes it happens that your numbers keep on decreasing, then their processing of doubles in such small ranges becomes
                        // very expensive.
                        if (res < 1e-8)
                              res = 0;
                  }
            }
      }
      return res;
}
 
int main() {
      int T;
      cin >> T;
 
      while (T--) {
            cin >> n;
            int g = 0;
            for (int i = 0; i < n; i++) {
                  cin >> a[i];
                  g = __gcd(g, a[i]);
            }
 
            // if gcd g is > 1, then we can never make the game end with gcd = 1, because finally at the end gcd will be g and g > 1.
            // So in this case, both the players can keep moving until there are not any elements left.
            // So outcome of the game will be decided by parity directly.
            // if n is odd, it means that first player can pick the last number and second player will not have any option to move, Hence first player will win.
            // if n is even, then second player will win.
            // Note that in this case, even if game is played randomly, there wont be any effect on the outcome.
            if (g > 1) {
                  // dont forget to print exactly 4 digits after the decimal.
                  cout << n % 2 << " " << (n % 2) << ".0000" << endl;
                  continue;
            }
 
            // intiliaze memo array with -1, denoting state is not been processed yet.
            memset(memo, -1, sizeof(memo));
            int ok = false;
            if (isWinning(0, 0)) ok = true;
            if (ok) cout << 1 << " ";
            else cout << 0 << " ";
 
            // intiliaze memo1 array with -1, denoting state is not been processed yet.
            for (int i = 0; i < N; i++)
                  for (int j = 0; j < N; j++)
                              memo1[i][j] = -1.0;
 
            double res = probWinning(0, 0);
 
            // dont forget to print exactly 4 digits after the decimal.
            printf("%.4f\n", res);
      }
 
      return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE4gPSAxMDU7CmludCBuOwppbnQgYVtOXTsKLy8gbWVtbyBhcnJheSBpcyB1c2VkIGZvciBtZW1vaXphdGlvbiBvZiBmdW5jdGlvbiBpc1dpbm5pbmcKaW50IG1lbW9bTl1bTl07CgovLyBtZW1vMSBhcnJheSBpcyB1c2VkIGZvciBtZW1vaXphdGlvbiBvZiBmdW5jdGlvbiBwcm9iV2lubmluZwpkb3VibGUgbWVtbzFbTl1bTl07CgovLyBIZXJlIGcgZGVub3RlcyB0aGUgY3VycmVudCBnY2QgaW4gdGhlIGdhbWUuIHRha2VuIGRlbm90ZXMgaG93IG1hbnkgbnVtYmVycyBhcmUgdGFrZW4gb3V0IG9mIHRoZSBnYW1lLCBpZSBob3cgbWFueSBudW1iZXJzCi8vIGhhdmUgYmVlbiB0aHJvd24gb3V0LgovLyBUaGlzIGZ1bmN0aW9uIHJldHVybnMgd2hldGhlciB0aGUgc3RhdGUgZGVub3RlcyBieSAoZywgdGFrZW4pIGlzIHdpbm5pbmcgb3Igbm90PwppbnQgaXNXaW5uaW5nIChpbnQgZywgaW50IHRha2VuKSB7CiAgICAgIGludCAmcmVzID0gbWVtb1tnXVt0YWtlbl07CiAgICAgIC8vIG1lbW9pemF0aW9uIHN0ZXAuCiAgICAgIC8vIGlmIHJlcyBpcyBuZWdhdGl2ZSAobWVhbmluZyB0aGF0IHdlIGhhdmUgbm90IGNvbXB1dGVkIHRoZSBhbnN3ZXIgY29ycmVzcG9uZGluZyB0byAoZywgdGFrZW4pIHN0YXRlLCB3ZSBuZWVkIHRvIGNvbXB1dGUgdGhhdCksIHRoZW4gd2Ugd2lsbAogICAgICAvLyBkbyB0aGUgcHJvY2Vzc2luZyBvZiB0aGF0IHN0YXRlLgogICAgICAvLyBvdGhlcndpc2UsIHdlIHdpbGwgc2ltcGx5IHJldHVybiB0aGUgYW5zd2VyLgogICAgICBpZiAocmVzID09IC0xKSB7CiAgICAgICAgICAgIHJlcyA9IDA7CiAgICAgICAgICAgIC8vIGlmIGFsbCB0aGUgbnVtYmVycyBoYXMgYmVlbiB0YWtlbiBvdXQsIGl0IG1lYW5zIHRoZXJlIGlzIG5vIG1vcmUgbnVtYmVycyB0byBwbGF5IHdpdGguCiAgICAgICAgICAgIC8vIGhlbmNlIHRoZSBwZXJzb24gcGxheWluZyB0aGlzIHR1cm4gd2lsbCBsb3NlIGJlY2F1c2UgaGUgd29udCBiZSBhYmxlIHRvIG1ha2UgYW55IG1vdmUuCiAgICAgICAgICAgIGlmICh0YWtlbiA9PSBuKSB7CiAgICAgICAgICAgICAgICAgIHJlcyA9IDA7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgIC8vIHRvdCBkZW5vdGVzIG51bWJlciBvZiBtdWx0aXBsZXMgb2YgZyBpbiB0aGUgYXJyYXkgYS4KICAgICAgICAgICAgICAgICAgaW50IHRvdCA9IDA7CiAgICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSBpZiAoX19nY2QoZywgYVtpXSkgPT0gZykgdG90Kys7CgogICAgICAgICAgICAgICAgICAvLyBpZiBub3QgYWxsIG11bHRpcGxlcyBvZiBnIGFyZSB0aHJvd24gb3V0LCBpdCBtZWFucyB0aGF0IHRoZXJlIGFyZSBzdGlsbCBtdWx0aXBsZXMgb2YgZyBjdXJyZW50bHkgaW4gdGhlIGFycmF5IGEuCiAgICAgICAgICAgICAgICAgIC8vIHdlIGNhbiB1c2UgdGhlbSBpbiB0aGUgZ2FtZS4gZ2NkIGlzIG5vdCBnb2luZyB0byBjaGFuZ2UgYmVpbmcgdGhlIG51bWJlciB3ZSBhcmUgZ29pbmcgdG8gdGFrZSB3aWxsIGJlIG11bHRpcGxlIG9mIGcuCiAgICAgICAgICAgICAgICAgIC8vIGFzIGdjZCAoZywgdCkgPSBnIGlmIHQgPSBrICogZyAoaWUgdCBpcyBhIG11bHRpcGxlIG9mIGcpLgogICAgICAgICAgICAgICAgICBpZiAodGFrZW4gPCB0b3QpIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKHRha2VuIDwgdG90ICYmICFpc1dpbm5pbmcoZywgdGFrZW4gKyAxKSkgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXMgPSAxOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAgIC8vIGlmIGhhdmUgYWxyZWFkeSB3b24sIG5vIG5lZWQgdG8gcHJvY2VzcyB0aGUgcmVtYWluaW5nIHRoZSBzdGF0ZXMuIFRoaXMgaXMgc2ltcGx5IGEgcHJ1bmluZyBzdGVwLCB3b250IGhhdmUgbXVjaCBlZmZlY3Qgb24gdGhlCiAgICAgICAgICAgICAgICAgIC8vIG92ZXJhbGwgY29tcGxleGl0eS4gWW91IGNhbiBjaG9zZSB0byBydW4gdGhpcyBzdGVwIHRvby4KICAgICAgICAgICAgICAgICAgaWYgKHJlcyA9PSAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIE5vdyB3ZSB3aWxsIGl0ZXJhdGUgb3ZlciB0aGUgbnVtYmVycyB3aGljaCBhcmUgaGF2aW5nIGdjZCB3aXRoIGcgbm90IGVxdWFsIHRvIDEgKGJlY2F1c2Ugd2Ugd2lsbCBsb3NlIGluIHRoYXQgY2FzZSkgYW5kCiAgICAgICAgICAgICAgICAgICAgICAgIC8vIG5vdCBlcXVhbCB0byBnIGJlY2F1c2Ugd2UgaGF2ZSBhbHJlYWR5IGNvbnNpZGVyZWQgdGhhdCBjYXNlIGJlZm9yZS4KICAgICAgICAgICAgICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKF9fZ2NkIChnLCBhW2ldKSA+IDEpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKF9fZ2NkKGcsIGFbaV0pID09IGcpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIHRoaXMgY2FzZSBoYXMgYmVlbiBhbHJlYWR5IGNvbnNpZGVyZWQgYmVmb3JlLgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoIWlzV2lubmluZyhfX2djZChnLCBhW2ldKSwgdGFrZW4gKyAxKSkgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXMgPSAxOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgfQogICAgICByZXR1cm4gcmVzOwp9CgovLyBIZXJlIGcgZGVub3RlcyB0aGUgY3VycmVudCBnY2QgaW4gdGhlIGdhbWUuIHRha2VuIGRlbm90ZXMgaG93IG1hbnkgbnVtYmVycyBhcmUgdGFrZW4gb3V0IG9mIHRoZSBnYW1lLCBpZSBob3cgbWFueSBudW1iZXJzCi8vIGhhdmUgYmVlbiB0aHJvd24gb3V0LgovLyBmdW5jdGlvbiByZXR1cm5zIHRoZSBwcm9iYWJpbGl0eSBvZiB3aW5uaW5nIGlmIEkgYW0gYXQgc3RhdGUgZGVub3RlZCBieSAoZywgdGFrZW4pLgpkb3VibGUgcHJvYldpbm5pbmcgKGludCBnLCBpbnQgdGFrZW4pIHsKICAgICAgZG91YmxlICZyZXMgPSBtZW1vMVtnXVt0YWtlbl07CiAgICAgIC8vIG1lbW9pemF0aW9uIHN0ZXAuCiAgICAgIC8vIGlmIHJlcyBpcyBuZWdhdGl2ZSAobWVhbmluZyB0aGF0IHdlIGhhdmUgbm90IGNvbXB1dGVkIHRoZSBhbnN3ZXIgY29ycmVzcG9uZGluZyB0byAoZywgdGFrZW4pIHN0YXRlLCB3ZSBuZWVkIHRvIGNvbXB1dGUgdGhhdCksIHRoZW4gd2Ugd2lsbAogICAgICAvLyBkbyB0aGUgcHJvY2Vzc2luZyBvZiB0aGF0IHN0YXRlLgogICAgICAvLyBvdGhlcndpc2UsIHdlIHdpbGwgc2ltcGx5IHJldHVybiB0aGUgYW5zd2VyLgoKICAgICAgaWYgKHJlcyA8PSAtMC41KSB7CiAgICAgICAgICAgIGlmIChnID09IDEpIHsKICAgICAgICAgICAgICAgICAgLy8gaWYgZ2NkIGlzIDEsIGl0IG1lYW5zIHRoYXQgb3RoZXIgcGVyc29uIGhhcyBtYWRlIHRoZSBtb3ZlIGFuZCBoYXMgbWFkZSB0aGUgZ2NkIGVxdWFsIHRvIDEsIEhlbmNlIG90aGVyIHBlcnNvbiBpcyBsb3NpbmcuCiAgICAgICAgICAgICAgICAgIC8vIHRoYXQgbWVhbnMgdGhhdCBwbGF5ZXIgYXQgdGhlIGN1cnJlbnQgc3RlcCBpcyB3aW5uaW5nLiBTbyBwcm9iYWJpbGl0eSBvZiB3aW5uaW5nID0gMS4KICAgICAgICAgICAgICAgICAgcmVzID0gMS4wOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICByZXMgPSAwOwogICAgICAgICAgICAgICAgICBpZiAodGFrZW4gPT0gbikgewogICAgICAgICAgICAgICAgICAgICAgICByZXMgPSAwOwogICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICAvLyB0b3QgZGVub3RlcyBudW1iZXIgb2YgbXVsdGlwbGVzIG9mIGcgaW4gdGhlIGFycmF5IGEuCiAgICAgICAgICAgICAgICAgICAgICAgIGludCB0b3QgPSAwOwogICAgICAgICAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgaWYgKF9fZ2NkKGcsIGFbaV0pID09IGcpIHRvdCsrOwoKICAgICAgICAgICAgICAgICAgICAgICAgLy8gdGhpcyBpcyBhbiBpbXBvcnRhbnQgc3RlcCB0byBwYXkgYXR0ZW50aW9uIHRvLgogICAgICAgICAgICAgICAgICAgICAgICAvLyB3ZSBoYXZlIGN1cnJlbnRseSB0YWtlbiBlbGVtZW50IHRocm93biBvdXQgb2YgdGhlIGdhbWUsIHdlIGhhdmUgdG90IGVsZW1lbnRzIHdoaWNoIGFyZSBtdWx0aXBsZXMgb2YgZy4KICAgICAgICAgICAgICAgICAgICAgICAgLy8gaGVuY2UgdGhlcmUgYXJlIHN0aWxsIHRvdCAtIHRha2VuIGVsZW1lbnRzIHdoaWNoIGFyZSBtdWx0aXBsZXMgb2YgZy4KICAgICAgICAgICAgICAgICAgICAgICAgLy8gd2UgY2FuIGNob3NlIGFueSBvbmUgb2YgdGhlbSB3aXRoIGVxdWFsIHByb2JhYmlsaXR5LgogICAgICAgICAgICAgICAgICAgICAgICAvLyBwcm9iYWJpbGl0eSBvZiBjaG9zaW5nIG9uZSBvZiB0aGVtIHdpbGwgYmUgZXF1YWwgdG8gKHRvdCAtIHRha2VuKSAvICh0b3RhbCBlbGVtZW50cyB0aGF0IGFyZSBub3QgdGhyb3duKS4KICAgICAgICAgICAgICAgICAgICAgICAgLy8gQXMgdG90YWwgZWxlbWVudHMgdGhhdCBhcmUgbm90IHRocm93biA9IG4gLSB0YWtlbi4KICAgICAgICAgICAgICAgICAgICAgICAgLy8gSGVuY2UgcHJvYmFiaWxpdHkgb2YgY2hvc2luZyBvbmUgb2YgdGhlbSB3aWxsIGJlIGVxdWFsIHRvICh0b3QgLSB0YWtlbikgLyAobiAtIHRha2VuKS4KCiAgICAgICAgICAgICAgICAgICAgICAgIC8vIE5vdGUgdGhhdCBpbiB0aGlzIGNhc2UsIHRoZXJlIHdvbnQgYmUgYW55IGNoYW5nZSBpbiBnY2QsIGl0IHdpbGwgcmVtYWluIGcgKGJlY2F1c2UgY3VycmVudCBlbGVtZW50IGluIGNvbnNpZGVyYXRpb24gaXMgbXVsdGlwbGUgb2YgZykuCiAgICAgICAgICAgICAgICAgICAgICAgIGRvdWJsZSByZXMxID0gMDsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKHRha2VuIDwgdG90KSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlcyArPSAoMSAtIHByb2JXaW5uaW5nKGcsIHRha2VuICsgMSkpICogMS4wICogKHRvdCAtIHRha2VuKSAvIChuIC0gdGFrZW4pOwogICAgICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgICAgICAvLyBOb3cgd2Ugd2lsbCBpdGVyYXRlIG92ZXIgdGhlIG51bWJlcnMgd2hpY2ggYXJlIGhhdmluZyBnY2Qgd2l0aCBnIG5vdCBlcXVhbCB0byBnIGJlY2F1c2Ugd2UgaGF2ZSBhbHJlYWR5IGNvbnNpZGVyZWQgdGhhdCBjYXNlIGJlZm9yZS4KICAgICAgICAgICAgICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKF9fZ2NkKGcsIGFbaV0pID09IGcpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy8gY2FzZSBhbHJlYWR5IGNvbnNpZGVyZWQsIG5vdGhpbmcgdG8gZG8uCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBZb3UgY2FuIG1ha2UgeW91ciBjdXJyZW50IGdjZCB0byBnY2QoZywgYVtpXSkuCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIG51bWJlciBvZiB0YWtlbiBlbGVtZW50cyAob3IgdGhyb3duIGVsZW1lbnRzKSB3aWxsIGluY3JlYXNlIGJ5IDEuCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIHByb2JhYmlsaXR5IG9mIGEgc2luZ2xlIGNhc2UgaXMgMSAvIChlbGVtZW50cyByZW1haW5pbmcpID0gMSAvIChuIC0gdGFrZW4pLgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXMgKz0gKDEgLSBwcm9iV2lubmluZyhfX2djZChnLCBhW2ldKSwgdGFrZW4gKyAxKSkgKiAxLjAgLyAobiAtIHRha2VuKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgICAgICAvLyBpZiB5b3VyIG51bWJlcnMgYmVjb21lcyB2ZXJ5IHNtYWxsLCBpdCBpcyBiZXR0ZXIgdG8gbWFrZSBpdCBlcXVhbCB0byAwLgogICAgICAgICAgICAgICAgICAgICAgICAvLyBzb21ldGltZXMgaXQgaGFwcGVucyB0aGF0IHlvdXIgbnVtYmVycyBrZWVwIG9uIGRlY3JlYXNpbmcsIHRoZW4gdGhlaXIgcHJvY2Vzc2luZyBvZiBkb3VibGVzIGluIHN1Y2ggc21hbGwgcmFuZ2VzIGJlY29tZXMKICAgICAgICAgICAgICAgICAgICAgICAgLy8gdmVyeSBleHBlbnNpdmUuCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChyZXMgPCAxZS04KQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXMgPSAwOwogICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgfQogICAgICByZXR1cm4gcmVzOwp9CgppbnQgbWFpbigpIHsKICAgICAgaW50IFQ7CiAgICAgIGNpbiA+PiBUOwoKICAgICAgd2hpbGUgKFQtLSkgewogICAgICAgICAgICBjaW4gPj4gbjsKICAgICAgICAgICAgaW50IGcgPSAwOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICAgICAgICAgICBjaW4gPj4gYVtpXTsKICAgICAgICAgICAgICAgICAgZyA9IF9fZ2NkKGcsIGFbaV0pOwogICAgICAgICAgICB9CgogICAgICAgICAgICAvLyBpZiBnY2QgZyBpcyA+IDEsIHRoZW4gd2UgY2FuIG5ldmVyIG1ha2UgdGhlIGdhbWUgZW5kIHdpdGggZ2NkID0gMSwgYmVjYXVzZSBmaW5hbGx5IGF0IHRoZSBlbmQgZ2NkIHdpbGwgYmUgZyBhbmQgZyA+IDEuCiAgICAgICAgICAgIC8vIFNvIGluIHRoaXMgY2FzZSwgYm90aCB0aGUgcGxheWVycyBjYW4ga2VlcCBtb3ZpbmcgdW50aWwgdGhlcmUgYXJlIG5vdCBhbnkgZWxlbWVudHMgbGVmdC4KICAgICAgICAgICAgLy8gU28gb3V0Y29tZSBvZiB0aGUgZ2FtZSB3aWxsIGJlIGRlY2lkZWQgYnkgcGFyaXR5IGRpcmVjdGx5LgogICAgICAgICAgICAvLyBpZiBuIGlzIG9kZCwgaXQgbWVhbnMgdGhhdCBmaXJzdCBwbGF5ZXIgY2FuIHBpY2sgdGhlIGxhc3QgbnVtYmVyIGFuZCBzZWNvbmQgcGxheWVyIHdpbGwgbm90IGhhdmUgYW55IG9wdGlvbiB0byBtb3ZlLCBIZW5jZSBmaXJzdCBwbGF5ZXIgd2lsbCB3aW4uCiAgICAgICAgICAgIC8vIGlmIG4gaXMgZXZlbiwgdGhlbiBzZWNvbmQgcGxheWVyIHdpbGwgd2luLgogICAgICAgICAgICAvLyBOb3RlIHRoYXQgaW4gdGhpcyBjYXNlLCBldmVuIGlmIGdhbWUgaXMgcGxheWVkIHJhbmRvbWx5LCB0aGVyZSB3b250IGJlIGFueSBlZmZlY3Qgb24gdGhlIG91dGNvbWUuCiAgICAgICAgICAgIGlmIChnID4gMSkgewogICAgICAgICAgICAgICAgICAvLyBkb250IGZvcmdldCB0byBwcmludCBleGFjdGx5IDQgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsLgogICAgICAgICAgICAgICAgICBjb3V0IDw8IG4gJSAyIDw8ICIgIiA8PCAobiAlIDIpIDw8ICIuMDAwMCIgPDwgZW5kbDsKICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIC8vIGludGlsaWF6ZSBtZW1vIGFycmF5IHdpdGggLTEsIGRlbm90aW5nIHN0YXRlIGlzIG5vdCBiZWVuIHByb2Nlc3NlZCB5ZXQuCiAgICAgICAgICAgIG1lbXNldChtZW1vLCAtMSwgc2l6ZW9mKG1lbW8pKTsKICAgICAgICAgICAgaW50IG9rID0gZmFsc2U7CiAgICAgICAgICAgIGlmIChpc1dpbm5pbmcoMCwgMCkpIG9rID0gdHJ1ZTsKICAgICAgICAgICAgaWYgKG9rKSBjb3V0IDw8IDEgPDwgIiAiOwogICAgICAgICAgICBlbHNlIGNvdXQgPDwgMCA8PCAiICI7CgogICAgICAgICAgICAvLyBpbnRpbGlhemUgbWVtbzEgYXJyYXkgd2l0aCAtMSwgZGVub3Rpbmcgc3RhdGUgaXMgbm90IGJlZW4gcHJvY2Vzc2VkIHlldC4KICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspCiAgICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgTjsgaisrKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtZW1vMVtpXVtqXSA9IC0xLjA7CgogICAgICAgICAgICBkb3VibGUgcmVzID0gcHJvYldpbm5pbmcoMCwgMCk7CgogICAgICAgICAgICAvLyBkb250IGZvcmdldCB0byBwcmludCBleGFjdGx5IDQgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsLgogICAgICAgICAgICBwcmludGYoIiUuNGZcbiIsIHJlcyk7CiAgICAgIH0KCiAgICAgIHJldHVybiAwOwp9Cg==

Runtime error #stdin #stdout 0.16s 3476KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/CHxnq7

language:

C++14 (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language