Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream"  
#include "iomanip"  
using namespace std;
unsigned* factorList(unsigned n, unsigned& size) 
{ 
  unsigned listSize = 100; 
  unsigned* fact = new unsigned[listSize]; 
  unsigned nFacts = 0; 
  fact[nFacts++] = 1; 
  unsigned i; 
  for (i = 2; i*i <= n; ++i) 
    if (n % i == 0) 
      { 
        if (nFacts == listSize) 
          { 
            unsigned* old = fact; 
            listSize *= 2; 
            fact = new unsigned[listSize]; 
            for (unsigned j = 0; j < nFacts; ++j) 
              fact[j] = old[j]; 
            delete[] old; 
          } 
        fact[nFacts++] = i; 
      } 
  { 
    unsigned* old = fact; 
    listSize = 2*nFacts; 
    if (fact[nFacts-1] * fact[nFacts-1] == n) 
      --listSize; 
    fact = new unsigned[listSize]; 
    for (unsigned j = 0; j < nFacts; ++j) 
      fact[j] = old[j]; 
    delete[] old; 
  } 
  for (i = 0; i < nFacts; ++i) 
    fact[listSize-1-i] = n/fact[i]; 
  size = listSize; 
  return fact; 
} 
int main() { 
  unsigned score1, score2; 
  while (cin >> score1 >> score2) 
    { 
      if (score1 > score2) 
        { unsigned t = score1; score1 = score2; score2 = t; } 
      unsigned size1; 
      unsigned* factors1 = factorList(score1, size1); 
      unsigned size2; 
      unsigned* factors2 = factorList(score2, size2); 
      // after num==k, feasible[i,j] is k > 0 if the score pair (i,j) is possible 
      // with only "grapes" labelled 1 to k (and not 1 to k-1), 0 otherwise 
      unsigned tblsize = size1*size2; 
      unsigned* feasible = new unsigned[tblsize]; 
      for (unsigned i = tblsize; i--; ) 
        feasible[i] = 0; 
      feasible[0] = 1; 
      unsigned f1next = 0; 
      unsigned f2next = 0; 
      while (f1next < size1 || f2next < size2) 
        { 
          unsigned num; 
          if (f1next == size1) 
            num = factors2[f2next++]; 
          else if (factors1[f1next] < factors2[f2next]) 
            num = factors1[f1next++]; 
          else 
            { 
              if (factors1[f1next] == factors2[f2next]) 
                ++f1next; 
              num = factors2[f2next++]; 
            } 
          if (num > 100) 
            break; 
          unsigned k = 0; 
          for (unsigned i = 0; i < size1; ++i) 
            for (unsigned j = 0; j < size2; ++j, ++k) 
              if (feasible[k] && feasible[k] < num) 
                // see what new pairs can be validated with grape "num" 
                { 
                  unsigned ii, f1 = factors1[i]*num; 
                  for (ii = i+1; factors1[ii] != f1 && ii < size1; ++ii) 
                    {} 
                  if (ii < size1) 
                    { 
                      unsigned p = ii*size2+j; 
                      if (! feasible[p]) feasible[p] = num; 
                    } 
  
                  unsigned jj, f2 = factors2[j]*num; 
                  for (jj =  j+1; factors2[jj] != f2 && jj < size2; ++jj) 
                    {} 
                  if (jj < size2) 
                    { 
                      unsigned p = i*size2+jj; 
                      if (! feasible[p]) feasible[p] = num; 
                    } 
                } 
          if (feasible[tblsize-1] == num) 
            break; 
        } 
      // see what is possible... 
      unsigned winscore; 
      if (feasible[tblsize-1]) 
        winscore = score2;      // both could be honest 
      else if (!feasible[(size1-1)*size2]) 
        winscore = score2;      // 1 definitely lied 
      else 
        winscore = score1;      // they can't both be honest, so 1 wins 
  
      cout << winscore << "\n"; 
      delete[] feasible; 
      delete[] factors2; 
      delete[] factors1; 
    } 
  return 0; 
}