QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#465365 | #4523. It's Raining, Man / Ancient Cards | Dimmyt | AC ✓ | 28ms | 3580kb | C++17 | 6.3kb | 2024-07-06 20:22:56 | 2024-07-06 20:22:56 |
Judging History
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