fork(1) download 
  1. #include <cstdio>
  2.  
  3. int calc_min_dist(int mn, int dist_table[], int tcount, int tpos[]) {
  4.   int min_dist = mn; // possible max+1
  5.   for (int i=0; i < tcount; ++i) {
  6.     const int dist = dist_table[tpos[i]];
  7.     if (dist < min_dist)
  8.       min_dist = dist;
  9.   }
  10.   return min_dist;
  11. }
  12.  
  13. int main(int argc, const char* argv[]) {
  14.   int m, n, tcount, nm;
  15.   if (scanf("%d %d %d\n", &n, &m, &tcount) < 3) {
  16.     return 1;
  17.   }
  18.   nm = n*m;
  19.  
  20.   int dist_table[2][nm], i=0;
  21.   for (int y=0; y<n ; ++y) {
  22.     for (int x=0; x<m ; ++x) {
  23.       dist_table[0][i] = x*n+y;
  24.       dist_table[1][i] = i;
  25.       i++;
  26.     }
  27.   }
  28.  
  29.   int tpos[tcount], placed = 0;
  30.   tpos[0] = 0;
  31.  
  32.   long pw=0, qw=0, even=0;
  33.   while (1) {
  34.     // check if current loop is end
  35.     if (tpos[placed] >= nm) { // end for
  36.       if (placed == 0)
  37.         break;
  38.       placed--; // pop to outer loop
  39.     } else {
  40.       if (placed < tcount-1) {
  41.         // dig into inner loop
  42.         placed++;
  43.         tpos[placed]=tpos[placed-1];
  44.       } else {
  45.       	// deepest loop body
  46.         int pdist = calc_min_dist(nm, dist_table[0], tcount, tpos);
  47.         int qdist = calc_min_dist(nm, dist_table[1], tcount, tpos);
  48.  
  49.         if (pdist < qdist) {
  50.           pw++;
  51.         } else if (pdist > qdist) {
  52.           qw++;
  53.         } else {
  54.           even++;
  55.         }
  56.       }
  57.     }
  58.     tpos[placed]++; // next
  59.   }
  60.  
  61.   printf("shape(%dx%d), tcount=%d --->  pwin:%ld, qwin:%ld, even:%ld\n", n, m, tcount, pw, qw, even);
  62.   main(argc, argv); //  dirty loop trick
  63. }
Success #stdin #stdout 4.26s 15232KB
comments (?)
stdin 
3 4 2
5 6 15
stdout 
shape(3x4), tcount=2 --->  pwin:26, qwin:27, even:13
shape(5x6), tcount=15 --->  pwin:25463979, qwin:25488051, even:104165490
https://ideone.com/HaAqJO
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!