[教學] Programming 12: "Looping"

題目網址

時間限制：3秒

題目大意：

有一個5x5方陣，1 <= a ~ y <= 9，已知橫排(5 Rows)、縱列(5 Columns)、對角線(2 Diagonals)之各別總和，求出符合這些條件的 a ~ y。

+-Square------+-Rows----------------+-Cols----------------+-Diagonals----+
|  a b c d e  |  Row 1 = a+b+c+d+e  |  Col 1 = a+f+k+p+u  |  Diagonal 1  |
|  f g h i j  |  Row 2 = f+g+h+i+j  |  Col 2 = b+g+l+q+v  |  = a+g+m+s+y |
|  k l m n o  |  Row 3 = k+l+m+n+o  |  Col 3 = c+h+m+r+w  |              |
|  p q r s t  |  Row 4 = p+q+r+s+t  |  Col 4 = d+i+n+s+x  |  Diagonal 2  |
|  u v w x y  |  Row 5 = u+v+w+x+y  |  Col 5 = e+j+o+t+y  |  = u+q+m+i+e |
+-------------+---------------------+---------------------+--------------+

解法：

以漩渦方式由外而內(a->e->y->u->f->i) iteration 猜測，有時候可能會超過3秒，只要重新執行即可。

以下程式使用 Ruby 執行。

# Author      : mashimaro
# Last Modify : 2008/01/01

require 'net/http'
require 'net/https'

host = 'www.bright-shadows.net'
path = '/challenges/programming/looping/tryout.php'
cookie = 'PHPSESSID=**********************************'

http = Net::HTTP.new(host, 80)
#http.use_ssl = true
headers = {
'Cookie' => cookie,
#  'Referer' => 'http://profil.wp.pl/login.html',
#  'Content-Type' => 'application/x-www-form-urlencoded'
}

resp, data = http.get(path, headers);

data.sub!('<pre>', '');
data.sub!('</pre>', '');

arr = [];

data.split('<br />').each { |line|
 if(line[0..2]=='Sum')
  arr.push(line[-2..-1]);
  puts line[-2..-1];
 end
}

puts '';
# puts arr[0];
# puts arr[1];
# puts arr[2];
# puts arr[3];
# puts arr[4];
# puts arr[5];
# puts arr[6];
# puts arr[7];
# puts arr[8];
# puts arr[9];
# puts arr[10];
# puts arr[11];

[1,2,3,4,5,6,7,8,9].each { |a|
 [1,2,3,4,5,6,7,8,9].each { |b|
  [1,2,3,4,5,6,7,8,9].each { |c|
   [1,2,3,4,5,6,7,8,9].each { |d|
    e = arr[0].to_i - a - b - c - d;
    break if(e < 1);
    next  if(e > 9);

    [1,2,3,4,5,6,7,8,9].each { |j|
     [1,2,3,4,5,6,7,8,9].each { |o|
      [1,2,3,4,5,6,7,8,9].each { |t|
       y = arr[9].to_i - e - j - o - t;
       break if(y < 1);
       next  if(y > 9);

        [1,2,3,4,5,6,7,8,9].each { |x|
         [1,2,3,4,5,6,7,8,9].each { |w|
          [1,2,3,4,5,6,7,8,9].each { |v|
           u = arr[4].to_i - v - w - x - y;
           break if(u < 1);
           next  if(u > 9);

            [1,2,3,4,5,6,7,8,9].each { |p|
             [1,2,3,4,5,6,7,8,9].each { |k|
              f = arr[5].to_i - a - k - p - u;
              break if(f < 1);
              next  if(f > 9);

              [1,2,3,4,5,6,7,8,9].each { |g|
               [1,2,3,4,5,6,7,8,9].each { |h|
                i = arr[1].to_i - f - g - h - j;
                break if(i < 1);
                next  if(i > 9);

                [1,2,3,4,5,6,7,8,9].each { |m|
                 q = arr[11].to_i - e - i - m - u;
                 break if(q < 1);
                 next  if(q > 9);
                 r = arr[7].to_i - c - h - m - w;
                 break if(r < 1);
                 next  if(r > 9);
                 s = arr[10].to_i - a - g - m - y;
                 break if(s < 1);
                 next  if(s > 9);
                 next  if(s != arr[3].to_i - p - q - r - t);

                 l = arr[6].to_i - b - g - q - v;
                 next  if(l < 1 || l > 9);
                 n = arr[8].to_i - d - i - s - x;
                 next  if(n < 1 || n > 9);
                 next  if(n != arr[2].to_i - k - l - m - o);

                 arr2=[];
                 puts [].push(a,b,c,d,e).join(' ');
                 puts [].push(f,g,h,i,j).join(' ');
                 puts [].push(k,l,m,n,o).join(' ');
                 puts [].push(p,q,r,s,t).join(' ');
                 puts [].push(u,v,w,x,y).join(' ');
                 puts '';

                 ret_path = [].push('http://www.bright-shadows.net/challenges/programming/looping/solution.php?solution=',a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y).join('');

                 puts ret_path;
                 resp, data = http.get(ret_path, headers);
                 puts data;

                 exit(0);
                }

               }
              }

             }
            }

           }
          }
         }

       }
      }
     }

   }
  }
 }
}

消息來源