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

дистанційна підтримка освіти школярів


Gizilch
http://acm.pku.edu.cn/JudgeOnline/problem?id=1078

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

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

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

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

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

   Пример решения на 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;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)