Advertisement
najimCseJu

APAC 2014 round 4 D

Nov 9th, 2014
435
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.37 KB | None | 0 0
  1. #include<algorithm>
  2. #include<bitset>
  3. #include<cctype>
  4. #include<math.h>
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7. #include<string.h>
  8. #include<iostream>
  9. #include<iterator>
  10. #include<map>
  11. #include<queue>
  12. #include<set>
  13. #include<sstream>
  14. #include<stack>
  15. #include<strstream>
  16. #include<string>
  17. #include<utility>
  18. #include<vector>
  19. #include <cstdarg>
  20. using namespace std;
  21. /***************************************************************************************************************************************/
  22. typedef long long int LLI;
  23. typedef unsigned long long int ULLI;
  24. #define MP(X,Y) make_pair(X,Y)
  25.  
  26. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  27.  
  28. #define fill(a,v) memset(a,v,sizeof(a))
  29. #define DEBUG(x) cout << #x << ": " << x << endl;
  30. #define all(x) (x).begin(),(x).end()
  31. #define SORT(x) sort(all(x))
  32. #define VI vector<int>
  33. #define VS vector<string>
  34. #define PB push_back
  35. #define REV(a) reverse(all(a))
  36. typedef pair<int, int>PII;
  37.  
  38.  
  39. #define BRPS(n,bit) bitset<bit>(n)
  40. template<class T> inline T BIGMOD(T n, T m, T mod)
  41. {
  42.     LLI ans = 1;
  43.     LLI k = n;
  44.     while(m)
  45.     {
  46.         if(m & 1)
  47.         {
  48.             ans *= k;
  49.             if(ans>mod) ans %= mod;
  50.         }
  51.         k *= k;
  52.         if(k>mod) k %= mod;
  53.         m >>= 1;
  54.     }
  55.     return ans;
  56. }
  57. #define eps 1e-11
  58. template<class T> string toString(T n)
  59. {
  60.     ostringstream ost;
  61.     ost << n;
  62.     ost.flush();
  63.     return ost.str();
  64. }
  65. template<class T> string toBinary(T n)
  66. {
  67.     string ret="";
  68.     while(n)
  69.     {
  70.         if(n%2==1)ret+='1';
  71.         else ret+='0';
  72.         n>>=1;
  73.     }
  74.     reverse(ret.begin(),ret.end());
  75.     return ret;
  76. }
  77. void combination(int n,vector< vector<int> > &ret)
  78. {
  79.     ret.resize(n+1, vector<int>(n+1, 0));
  80.     for(int i=1; i<=n; i++)
  81.     {
  82.         ret[i][0]=ret[i][i]=1;
  83.         for(int j=1; j<i; j++)
  84.         {
  85.             ret[i][j]=ret[i-1][j]+ret[i-1][j-1];
  86.         }
  87.     }
  88. }
  89. int toInt(string s)
  90. {
  91.     int r = 0;
  92.     istringstream sin(s);
  93.     sin >> r;
  94.     return r;
  95. }
  96. LLI toLInt(string s)
  97. {
  98.     LLI r = 0;
  99.     istringstream sin(s);
  100.     sin >> r;
  101.     return r;
  102. }
  103. double toDouble(string s)
  104. {
  105.     double r = 0;
  106.     istringstream sin(s);
  107.     sin >> r;
  108.     return r;
  109. }
  110. vector<string> parse(string temp)
  111. {
  112.     vector<string> ans;
  113.     ans.clear();
  114.     string s;
  115.     istringstream iss(temp);
  116.     while (iss >> s)ans.PB(s);
  117.     return ans;
  118. }
  119. template<class T> inline T gcd(T a, T b)
  120. {
  121.     if (a < 0)return gcd(-a, b);
  122.     if (b < 0)return gcd(a, -b);
  123.     return (b == 0) ? a : gcd(b, a % b);
  124. }
  125. template<class T> inline T lcm(T a, T b)
  126. {
  127.     if (a < 0)return lcm(-a, b);
  128.     if (b < 0)return lcm(a, -b);
  129.     return a*(b / gcd(a, b));
  130. }
  131. template<class T> inline T power(T b, T p)
  132. {
  133.     if (p < 0)return -1;
  134.     if (b <= 0)return -2;
  135.     if (!p)return 1;
  136.     return b*power(b, p - 1);
  137. }
  138.  
  139. template<class T> inline int asd(T &ret)
  140. {
  141.     char r;
  142.     bool start=false,neg=false;
  143.     ret=0;
  144.     while(true)
  145.     {
  146.         r=getchar();
  147.         if(r==EOF)return 0;
  148.         if((r-'0'<0 || r-'0'>9) && r!='-' && !start)
  149.         {
  150.             continue;
  151.         }
  152.         if((r-'0'<0 || r-'0'>9) && r!='-' && start)
  153.         {
  154.             break;
  155.         }
  156.         if(start)ret*=10;
  157.         start=true;
  158.         if(r=='-')neg=true;
  159.         else ret+=r-'0';
  160.     }
  161.  
  162.     if(neg)
  163.         ret*=-1;
  164.     return 1;
  165. }
  166.  
  167. template<class T> inline void asdasd(T x,char y)
  168. {
  169.     // 0- print+newline, 1 - print ' ',2 - nothing;
  170.     if (x < 0)
  171.     {
  172.         putchar('-');
  173.         x = -x;
  174.     }
  175.     char buf[21], *p = buf;
  176.     do
  177.     {
  178.         *p++ = '0' + x % 10;
  179.         x /= 10;
  180.     }
  181.     while (x);
  182.     do
  183.     {
  184.         putchar(*--p);
  185.     }
  186.     while (p > buf);
  187.     if(y==0)putchar('\n');
  188.     else if(y==1)putchar(' ');
  189. }
  190. #define filein(x) freopen(x,"r",stdin)
  191. #define fileout(x) freopen(x,"w",stdout)
  192. #define fst first
  193. #define snd second
  194. //istringstream(temp) >> data >> value >> stamp;
  195. //mod1 = 1000000007, mod2 = 1000000009;
  196. //.016-.040-.900-2.48
  197. /***************************************************************************************************************************************/
  198.  
  199. vector<PII>V;
  200. int chess[70][70];
  201. char P[]= {'K','Q','R','B','N','P'};
  202. int Piece(char p)
  203. {
  204.     for(int i=0; i<6; i++)if(P[i]==p)return i;
  205. }
  206.  
  207. int Grid(char x,char y,char pc)
  208. {
  209.     //if(pc!='K' && pc!='P')cout << "->" << pc << endl;
  210.     chess[x-'A'][y-'1']=Piece(pc);
  211.     V.PB(MP(x-'A',y-'1'));
  212. }
  213.  
  214. char p,q,r;
  215. int n;
  216.  
  217.  
  218. bool CanKingGo(int px,int py,int qx,int qy)
  219. {
  220.     if(abs(px-qx)<=1 && abs(py-qy)<=1)return true;
  221.     return false;
  222. }
  223.  
  224. bool CanPawnGo(int px,int py,int qx,int qy)
  225. {
  226.     if(px+1==qx && abs(py-qy)==1)return true;
  227.     return false;
  228. }
  229.  
  230. bool CanRookGo(int px,int py,int qx,int qy)
  231. {
  232.     if(px!=qx && py!=qy)return false;
  233.     if(px==qx)
  234.     {
  235.         if(py>qy)swap(py,qy);
  236.         while(py<qy)
  237.         {
  238.             py++;
  239.             if(py==qy)return true;
  240.             if(chess[px][py]!=-1)return false;
  241.         }
  242.         return true;
  243.     }
  244.     else
  245.     {
  246.         if(px>qx)swap(px,qx);
  247.         while(px<qx)
  248.         {
  249.             if(px==qx)return true;
  250.             px++;
  251.             if(chess[px][py]!=-1)return false;
  252.         }
  253.         return true;
  254.     }
  255. }
  256. bool CanKnightGo(int px,int py,int qx,int qy)
  257. {
  258.     for(int i=-2;i<=2;i++)
  259.     {
  260.         for(int j=-2;j<=2;j++)
  261.         {
  262.             if((abs(i)==2 && abs(j)==1) || (abs(i)==1 && abs(j)==2))
  263.             {
  264.                 if(px+i==qx && py+j==qy)return true;
  265.             }
  266.         }
  267.     }
  268.     return false;
  269. }
  270.  
  271. bool CanBishopGo(int px,int py,int qx,int qy)
  272. {
  273.     if(abs(px-qx)!=abs(py-qy))return false;
  274.     while(px!=qx)
  275.     {
  276.  
  277.         if(px<qx)px++;
  278.         else px--;
  279.         if(py<qy)py++;
  280.         else py--;
  281.         if(px==qx)return true; // is this wrong?
  282.         if(chess[px][py]!=-1)
  283.         {
  284.             return false;
  285.         }
  286.     }
  287.     return true;
  288. }
  289. bool CanQueenGo(int px,int py,int qx,int qy)
  290. {
  291.     int a=CanRookGo(px,py,qx,qy);
  292.     int b=CanBishopGo(px,py,qx,qy);
  293.     return a||b ;
  294. }
  295. bool Take(int idx,int idy)
  296. {
  297.     int px,py,qx,qy;
  298.     px=V[idx].fst;
  299.     py=V[idx].snd;
  300.  
  301.     qx=V[idy].fst;
  302.     qy=V[idy].snd;
  303.  
  304.     if(chess[px][py]==0)return CanKingGo(px,py,qx,qy);
  305.     if(chess[px][py]==1)return CanQueenGo(px,py,qx,qy);
  306.     if(chess[px][py]==2)return CanRookGo(px,py,qx,qy);
  307.     if(chess[px][py]==3)return CanBishopGo(px,py,qx,qy);
  308.     if(chess[px][py]==4)return CanKnightGo(px,py,qx,qy);
  309.     if(chess[px][py]==5)return CanPawnGo(px,py,qx,qy);
  310. }
  311.  
  312.  
  313. int main()
  314. {
  315.     //freopen("D-large.in","r",stdin);
  316.     //freopen("D-small-attempt0.in","r",stdin);
  317.     //freopen("D-large.txt","w",stdout);
  318.     int kase,ks=0;
  319.     asd(kase);
  320.     while(kase--)
  321.     {
  322.         fill(chess,-1);
  323.         asd(n);
  324.         V.clear();
  325.         for(int i=0; i<n; i++)
  326.         {
  327.             p=getchar();
  328.             q=getchar();
  329.             getchar();
  330.             r=getchar();
  331.             getchar();
  332.             Grid(p,q,r);
  333.         }
  334.         int res=0;
  335.         for(int i=0;i<V.size();i++)
  336.         {
  337.             for(int j=0;j<V.size();j++)
  338.             {
  339.                 if(i!=j && Take(i,j))
  340.                 {
  341.                     res++;
  342.                 }
  343.             }
  344.         }
  345.         printf("Case #%d: %d\n",++ks,res);
  346.     }
  347.     return 0;
  348. }
  349. /*
  350. 2
  351. 3
  352. A1-N
  353. C2-Q
  354. C3-Q
  355. 3
  356. B2-K
  357. A1-P
  358. H8-Q
  359. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement