[Assorted-commits] SF.net SVN: assorted:[1620] problems/gcj/2006
Brought to you by:
yangzhang
Menu
▾
▴
[Assorted-commits] SF.net SVN: assorted:[1620] problems/gcj/2006
|
From: <yan...@us...> - 2010-04-05 14:26:01
|
Revision: 1620
http://assorted.svn.sourceforge.net/assorted/?rev=1620&view=rev
Author: yangzhang
Date: 2010-04-05 14:25:55 +0000 (Mon, 05 Apr 2010)
Log Message:
-----------
added more to gcj06
Added Paths:
-----------
problems/gcj/2006/matrixpermanent.txt
problems/gcj/2006/squarecounting.py
problems/gcj/2006/squarecounting.txt
Property Changed:
----------------
problems/gcj/2006/cjam.cpp
Property changes on: problems/gcj/2006/cjam.cpp
___________________________________________________________________
Deleted: svn:executable
- *
Added: problems/gcj/2006/matrixpermanent.txt
===================================================================
--- problems/gcj/2006/matrixpermanent.txt (rev 0)
+++ problems/gcj/2006/matrixpermanent.txt 2010-04-05 14:25:55 UTC (rev 1620)
@@ -0,0 +1,92 @@
+Problem Statement
+
+The permanent of a nxn matrix A is equal to the sum of A[1][p[1]] * A[2][p[2]] * ... * A[n][p[n]] over all permutations p of the set {1, 2, ... , n}.
+You will be given a String[] matrix, where each element contains a single space delimited list of integers. The jth integer in the ith element represents the value of A[i][j]. Return the int represented by the last four digits of the permanent of the given matrix.
+Definition
+
+Class:
+PermanentComputation
+Method:
+compute
+Parameters:
+String[]
+Returns:
+int
+Method signature:
+int compute(String[] matrix)
+(be sure your method is public)
+
+
+Constraints
+-
+matrix will contain between 1 and 16 elements, inclusive.
+-
+Each element of matrix will contain a list of integers, each separated by exactly one space.
+-
+Each element of matrix will contain exactly n integers, where n is the number of elements in matrix.
+-
+Each element will have length between 1 and 50 characters, inclusive.
+-
+Each element of matrix will contain no leading or trailing spaces.
+-
+Each integer in matrix will be between 0 and 10000, inclusive, and contain no leading zeroes.
+Examples
+0)
+
+
+{
+ "1 1",
+ "1 1"}
+Returns: 2
+The permanent is equal to 1*1 + 1*1 = 2.
+1)
+
+
+{
+ "1 2 3",
+ "4 5 6",
+ "7 8 9"}
+Returns: 450
+The permanent is equal to 1*5*9 + 1*6*8 + 2*4*9 + 2*6*7 + 3*4*8 + 3*5*7 = 450.
+2)
+
+
+{
+ "1 2 3 4",
+ "2 3 4 5",
+ "3 4 5 6",
+ "4 5 6 7"}
+Returns: 4276
+
+3)
+
+
+{
+ "1 1 1",
+ "2 2 2",
+ "3 3 3"}
+Returns: 36
+
+4)
+
+
+{
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
+ "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"}
+Returns: 8000
+
+This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Added: problems/gcj/2006/squarecounting.py
===================================================================
--- problems/gcj/2006/squarecounting.py (rev 0)
+++ problems/gcj/2006/squarecounting.py 2010-04-05 14:25:55 UTC (rev 1620)
@@ -0,0 +1,105 @@
+#!/usr/bin/env python
+
+import sys
+
+debug = False
+def dbg(*x):
+ if debug:
+ print ' '.join(map(str,x))
+
+class Square:
+ def __init__(self,xmin,xmax,ymin,ymax):
+ self.xmin = xmin
+ self.ymin = ymin
+ self.xmax = xmax
+ self.ymax = ymax
+ def __str__(self):
+ return '%d %d %d %d' % (self.xmin, self.xmax, self.ymin, self.ymax)
+
+class E(Exception): pass
+
+class SquareCounting:
+ def howMany(self, grid):
+ squares = set()
+ Y = len(grid)
+ X = len(grid[0])
+ for ymin in xrange(Y):
+ for xmin in xrange(X):
+ c = grid[ymin][xmin]
+ dbg( c )
+ d = 1
+ try:
+ if c == 'B':
+ #print 'ooga'
+ pass
+ for d in xrange(1,min(Y-ymin,X-xmin)+1):
+ xmax = xmin+d
+ ymax = ymin+d
+ if xmax >= X or ymax >= Y:
+ raise E
+ for xx in xrange(xmin,xmax+1):
+ dbg( 'xx',ymax,xx )
+ if grid[ymax][xx] != c:
+ raise E
+ for yy in xrange(ymin,ymax+1):
+ dbg( 'yy',yy,xmax )
+ if grid[yy][xmax] != c:
+ raise E
+ else:
+ raise E
+ except E:
+ dbg( 'E' )
+ xmax = xmin+d-1
+ ymax = ymin+d-1
+ #print xmin, xmax, ymin, ymax
+ for square in squares:
+ #print '\t',square
+ if square.xmin <= xmin and square.xmax >= xmax and square.ymin <= ymin and square.ymax >= ymax:
+ break
+ elif square.xmin >= xmin and square.xmax <= xmax and square.ymin >= ymin and square.ymax <= ymax:
+ #print 'removing'
+ squares.remove(square)
+ else:
+ s = Square(xmin,xmax,ymin,ymax)
+ squares.add(s)
+ #print 'added square', s
+ return len(squares)
+
+sc=SquareCounting()
+print sc.howMany(
+'''AB
+CD'''.split('\n'))
+print sc.howMany(
+'''AAB
+AAB
+BBB'''.split('\n'))
+print sc.howMany(
+'''AAA
+AAA
+AAA'''.split('\n'))
+print sc.howMany( [
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA",
+"AAAAAAAAAA"
+])
+print sc.howMany([
+"AAAAAABBB",
+"AAAAAABBB",
+"AAAAAABBB",
+"AAAAAABBB",
+"AAAAAABBB",
+"BBBAAAAAA",
+"BBBAAAAAA",
+"BBBAAAAAA",
+"BBBAAAAAA",
+"BBBAAAAAA"
+])
+
+#main()
Property changes on: problems/gcj/2006/squarecounting.py
___________________________________________________________________
Added: svn:executable
+ *
Added: problems/gcj/2006/squarecounting.txt
===================================================================
--- problems/gcj/2006/squarecounting.txt (rev 0)
+++ problems/gcj/2006/squarecounting.txt 2010-04-05 14:25:55 UTC (rev 1620)
@@ -0,0 +1,24 @@
+You are given a grid of characters, where each element describes a row.
+A solid square is a contiguous n x n section of characters,
+all of which have the same value. Return the number of solid
+squares in grid that aren't contained in larger solid squares.
+
+Constraints
+-
+grid will contain between 1 and 10 elements, inclusive.
+-
+Each element of grid will contain between 1 and 10 characters, inclusive.
+-
+Each element grid will contain the same number of characters.
+-
+Each character in grid will be an uppercase letter ('A'-'Z').
+
+
+Examples
+1)
+
+{"AAB",
+"AAB",
+"BBB"}
+Returns: 6
+Here we have a 2 x 2 square of 'A's and 5 squares of 'B's (each 1 x 1). Thus we return 6.
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
