QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#465365#4523. It's Raining, Man / Ancient CardsDimmytAC ✓28ms3580kbC++176.3kb2024-07-06 20:22:562024-07-06 20:22:56

Judging History

你现在查看的是最新测评结果

  • [2024-07-06 20:22:56]
  • 评测
  • 测评结果:AC
  • 用时:28ms
  • 内存:3580kb
  • [2024-07-06 20:22:56]
  • 提交

answer

/**
 * CTU Open 2016
 * Problem Solution: It's Raining
 * 
 * Case analysis. Main (but not the only) approach is to play 
 * colors one by one.
 * @author Josef Cibulka
 */

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

static const string colorList { "SDHC" };
static const string rankList { "23456789XJQKA" };
static const int rankCnt { 13 };

vector<vector<int> > rows;
vector<vector<int> > pairCnt;
vector<int> tripleCnt;
int quadCnt;

struct VectorComparer
{
  bool operator ()(const vector<int>& a, const vector<int>& b) const
  {
    return a.size() > b.size();
  }
};

  template <typename T>
bool vectorContains(const vector<T> &vec, T item)
{
  return (std::find(vec.begin(), vec.end(), item) != vec.end());
}

/** Exactly two card colors are present (they are colors 0 and 1). 
 * Solution exists iff there is at least one pair on these two colors. */
bool check2Colors()
{
  return (pairCnt[0][1] >=1);
}

/** Exactly three card colors are present (0, 1 and 2). 
 * Solution exists iff either:
 * a) "Path": two distinct pairs of colors, or one pair and a triple or two triples.
 * b) "Jump": row 2 has only one element and this element is part of a triple. */
bool check3Colors()
{
  int pairCntCnt = (pairCnt[0][1]>=1) + (pairCnt[0][2]>=1) + (pairCnt[1][2]>=1);
  if(pairCntCnt + tripleCnt[3] >= 2) // path
    return true;
  if(rows[2].size() == 1 && tripleCnt[3] >= 1) // jump
    return true;
  return false;
}

bool check4ColorsPath()
{   
  int pairCntCnt = 0;
  int pairCntSum = 0;
  for(int a=0; a<4; ++a)
    for(int b=a+1; b<4; ++b)
      if(pairCnt[a][b]>=1)
      {
        pairCntCnt++;
        pairCntSum += pairCnt[a][b];
      }
  int tripleCntSum = 0;
  for(int a=0; a<4; ++a)
    tripleCntSum += tripleCnt[a];

  if(quadCnt>=1)
    return (quadCnt + tripleCntSum + pairCntCnt >= 2);

  if(tripleCntSum >= 1)
    return (tripleCntSum + pairCntCnt >= 3);

  // Star centered in a.
  for(int a=0; a<4; ++a) 
  {
    bool isStar = true;
    for(int b=0; b<4; ++b) 
      for(int c=b+1; c<4; ++c)
        if(b!=a && c!=a && pairCnt[b][c] >= 1)
          isStar = false;
    // Since the star covers all 4 colors, solution exists iff at least one edge of the star is at least double.
    if(isStar)
      return (pairCntSum >= 4); 
  }
  return (pairCntCnt >= 3); // Three edges not forming a star and covering all colors => path.
}

bool check4ColorsRowWith1()
{
  int pairCntCnt = 0;
  for(int a=0; a<4; ++a)
    for(int b=a+1; b<4; ++b)
      if(pairCnt[a][b]>=1)
        pairCntCnt++;
  int tripleCntCnt = 0;
  for(int a=0; a<4; ++a)
    if(tripleCnt[a]>=1)
      tripleCntCnt++;
  if(quadCnt >= 1)
  {
    if(rows[2].size() == 1)
      return true;
    return (pairCntCnt + tripleCntCnt >= 1);
  }
  if(tripleCnt[0] + tripleCnt[1] + tripleCnt[2] >= 1) // A triple covering the single card in row 3.
    return true;
  if(rows[2].size() == 1 && tripleCntCnt >= 1) // Observe that the triple covers the single card in row 2.
    return true;
  return false;
}

bool check4ColorsRowWith2()
{ 
  for(int row2=0; row2<4; ++row2)
  {
    int tripleCntCnt = 0;
    if(rows[row2].size() != 2)
      continue;
    for(int a=0; a<4; ++a)
      if(a!=row2 && tripleCnt[a]>=1)
        tripleCntCnt++;
    if(tripleCntCnt>=2)
      return true; // Two distinct triples cover the two cards.
  }
  return false;
}



bool check4Colors()
{
  vector<bool> covered (4, false);
  for(int a=0; a<4; ++a)
    for(int b=a+1; b<4; ++b)
      if(pairCnt[a][b]>=1)
        covered[a]=covered[b]=true;
  for(int a=0; a<4; ++a)
    if(tripleCnt[a] >= 1)
      for(int i=0; i<4; ++i)
        if(i!=a)
          covered[i] = true;
  if(quadCnt>=1)
    for(int i=0; i<4; ++i)
      covered[i] = true;

  bool allCovered = !vectorContains(covered, false);
  if(!allCovered)
    return false;

  if(rows[3].size() == 1)
    if(check4ColorsRowWith1())
      return true;
  if(rows[3].size() == 2)
    if(check4ColorsRowWith2())
      return true;
  return check4ColorsPath();  
}

int main(void)
{
  int cardCnt;
  while(cin >> cardCnt)
  {
    rows = vector<vector<int> >(4, vector<int>());
    pairCnt = vector<vector<int> >(4, vector<int>(4, 0));
    tripleCnt = vector<int>(4, 0);
    quadCnt = 0;
    for(int i=0; i<cardCnt; ++i)
    {
      string card;
      cin >> card;
      int rank = rankList.find(card[0]);
      int color = colorList.find(card[1]);
      rows[color].push_back(rank);
    } 
    sort(rows.begin(), rows.end(), VectorComparer());
    /*cout << endl;
      for(auto &row : rows)
      if(row.size() > 0)      
      {
      for(int i : row)
      cout << i << " ";
      cout << endl;
      }*/

    for(int i=0; i<rankCnt; i++)
    {
      auto contFunction = bind(vectorContains<int>, placeholders::_1, i);
      int rankCardCnt = count_if(rows.begin(), rows.end(), contFunction);
      //      cout << "ranks cnt: " << rankCardCnt << endl;
      for(int a=0; a<4; ++a)
        for(int b=a+1; b<4; ++b)
        {
          if(vectorContains(rows[a], i) &&
              vectorContains(rows[b], i))
          {
            if(rankCardCnt == 2)
            {
              pairCnt[a][b]++;
              pairCnt[b][a]++;
            }
            for(int c=b+1; c<4; ++c)
            {
              if(vectorContains(rows[c], i))
              {
                if(rankCardCnt == 3)
                  tripleCnt[6-a-b-c]++;
                if(c==2 && vectorContains(rows[3], i))
                  quadCnt++;
              }
            }
          }
        }
    }

    /*cout << "Pairs:" << endl;
      for(int a=0; a<3; ++a)
      {
      for(int b=a+1; b<4; ++b)
      cout << pairCnt[a][b] << ", ";
      cout << endl;
      }
      cout << "Triples:" << endl;
      for(int a=0; a<4; ++a)
      cout << tripleCnt[a] << ", ";
      cout << endl;
      cout << "Quadruples: " << quadCnt << endl;*/

    bool result = false;
    if(rows[1].size() == 0)
      result = true;
    else if(rows[2].size() == 0)
      result = check2Colors();
    else if(rows[3].size() == 0)
      result = check3Colors();
    else
      result = check4Colors();
    cout << (result ? "YES" : "NO") << endl;
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 28ms
memory: 3580kb

input:

37 2S 3S 4S 6S 7S 8S 9S XS JS QS KS AS 5D 2H 3H 4H 6H 7H 8H 9H XH JH QH KH AH 2C 3C 4C 6C 7C 8C 9C XC JC QC KC AC
36 3S 4S 6S 7S 8S 9S XS JS QS KS AS 5D 2H 3H 4H 6H 7H 8H 9H XH JH QH KH AH 2C 3C 4C 6C 7C 8C 9C XC JC QC KC AC
36 2S 4S 6S 7S 8S 9S XS JS QS KS AS 5D 2H 3H 4H 6H 7H 8H 9H XH JH QH KH AH ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 5838 lines