SZU  Problem(A13):Frog Mathematic

Judge Info

• Memory Limit: 32768KB
• Case Time Limit: 10000MS
• Time Limit: 10000MS
• Judger: Special Judge For Problem A13

Description

Frog loves mathematics. Let’s have a look on a frog mathematics problem. First, there are some definitions here. A is an n×n matrix. Mi,j is a (n−1)×(n−1) matrix from A by deleting the ith row and the jth column. To do it along row i, say

Task

You are given a  integer matrix  all numbers of matrix A are in the range of [ − 100,100]. Please calculate the Det(A) Mod 20082008. a Mod b both a and b are integer, the answer of a Mod b is the remainder of a divides by b.

Input

The first line of input contains  the number of test cases. There are n + 1 lines for each test case. The first line contains an integer number , the size of matrix A. The next n lines contain n integer numbers each, separated by a space.

Output

For each test case, print a line contains the solution.

Sample Input

230 2 -30 1 32 0 -121 11 1

Sample Output

180

1 #include 
     
       2 #define N 12 3 #define M 20082008 4 int matrix[N][N]; 5 int dfs( int, int[N][N] ); 6 int main() 7 { 8     int t, n, i, j; 9     scanf( "%d", &t );10     while( t-- )11     {12         scanf( "%d", &n );13         for( i=0; i
     

SZU  Problem(A38):A long stick

Judge Info

• Memory Limit: 32768KB
• Case Time Limit: 10000MS
• Time Limit: 10000MS
• Judger: Number Only Judger

Description

There are a lot of problems about sticks. Here is one. I have  sticks each with some length of  . I want to use those sticks to make a longer stick with length longer than or equal to . Furthermore, I want the length of the stick as close to  as possible.

Task

Now, it is your turn. I will tell you the length of those  sticks, and . Your job is let me know the length of stick which I can have, according the rule above.

Input

The first line of input contains ,the number of test cases. There are two lines for each test case. The first line contains two integer numbers  and . The second line contains  integer numbers(the length of sticks I have already,  ).

Output

For each test case, print a line contains the solution.

Sample Input

25 14 2 4 3 4 5

5 142 4 3 4 5

Sample Output

1414

1 #include 
     
       2 #include 
      
        3 #define INF 0x7fffffff 4 #define N 27 5 int stick[N]; 6 int sticksum[N]; // 用来记录棍子的长度; 7 int over[N]; // 用来记录已经遍历过的棍子的长度; 8 void dfs( int ); // 递归求符合要求的最短棍子; 9 int goal, n, min, sum;10 // 降序排序11 int cmp( const void* a, const void* b )12 {13     return *(int*)b - *(int*)a;14 }15 int main()16 {17     int t, i;18     scanf( "%d", &t );19     while( t-- )20     {21         // 初始化22         sum = 0;23         scanf( "%d%d", &n, &goal );24         for( i=0; i
       
        = goal )40     {41         if( sticksum[cur-1] < min )42             min = sticksum[cur-1];43     }44     else45     {46         if( cur == n )47             return;48         // 选49         if( cur == 0 )50             sticksum[cur] = stick[cur];51         else52             sticksum[cur] = sticksum[cur-1]+stick[cur];53         if( cur == 0 )54             over[cur] = stick[cur]; // 已经遍历过的棍子的长度和55         else56             over[cur] = over[cur-1]+stick[cur];57         //printf( "**%d %d\n", cur, sticksum[cur] );58         if( sticksum[cur]+sum-over[cur] < goal ) // 怎样都没办法到达的话，就停止递归吧59             return;60         else61             dfs( cur+1 );62         // 不选63         if( cur == 0 )64             sticksum[cur] = 0;65         else66             sticksum[cur] = sticksum[cur-1];67         //printf( "^^%d %d\n", cur, sticksum[cur] );68         dfs( cur+1 );69     }70 }
       
      
     

SZU  Problem(B07):Go

Judge Info

• Memory Limit: 32768KB
• Case Time Limit: 10000MS
• Time Limit: 10000MS
• Judger: Normal

Description

In the game of Go, two players alternate placing black and white stones on lattice points of an n × n grid, each attempting to surround as much territory (i.e., regions of unfilled lattice points) as possible. At the end of the game, the score for each player is the total area of the territory surrounded by his or her stones. Given the locations of black and white stones on a Go board at the end of a match, your task is to compute the score of each player in order to determine the winner.(Note that the scoring of Go boards described here does not correspond exactly to the real game of Go: we make the simplifying assumptions that all “disputes” have been settled so that any territories surrounded by stones of both colors are considered neutral, and that all groups on the board are considered “alive.”)

Formally, two grid lattice points with coordinates (r, c) and (r', c') are adjacent if | r − r' | + | c − c' | = 1. A connected region of unfilled lattice points belongs to one player’s territory if all adjacent filled lattice points contain stones belonging to that player (see Figure 1). Finally, a player’s score consists of the number of unfilled lattice points in his or her territory.

Input

The input test file will contain multiple cases, each consisting of three lines. Each test case begins with a line containing three integers, n (where ), b, and w (where  and ). Here, n denotes the size of the board, b is the number of black pieces placed, and w is the number of white pieces placed. The second line of each test case contains b pairs of integers  (where ) indicating the positions of the b black stones. The third line of each test case contains w pairs of integers  (where ) indicating the positions of the w white stones. No two stones will be located at the same lattice point. Input is terminated by a single line containing only the number 0; do not process this line.

Output

For each test case, print either “White wins by ”, “Black wins by ”, or “Draw”.

Sample Input

1 1 01 12 0 11 15 12 41 1 1 2 1 3 2 1 2 3 3 1 3 3 4 1 4 3 5 1 5 2 5 31 4 2 4 3 4 3 50

Sample Output

DrawWhite wins by 3Black wins by 1

1 #include 
     
       2 #include 
      
        3 #define N 25 4 int flag[N][N]; /// 用来标记已经走过的路 5 char array[N][N];  /// 输入围棋的图 6 int dx[] = { 1, -1, 0, 0 }; // x的可能变化 7 int dy[] = { 0, 0, 1, -1 }; // y的可能变化 8 void recursion( int, int ); 9 int num = 0; // 每一次循环中用来记录空格的数目10 int blackNum = 0,  whiteNum = 0; // 用来记录黑子白子所占空格的总数11 int bl = 0, wl = 0; // 用来标记遇到黑子和白子没有12 int n;13 int main()14 {15     int i, j;16     int numb, numw; // 用来记录黑子和白子的数目17     int a, b; // 变量，用来记录坐标18     while( scanf( "%d", &n ) && n != 0 )19     {20         blackNum = 0,  whiteNum = 0;21         memset( flag, 0, sizeof(flag) );22         memset( array, 0, sizeof(array) );23         scanf( "%d%d", &numb, &numw );24         // 记录黑子所在的坐标25         for( i=0; i
       
         whiteNum )58             printf( "Black wins by %d\n", blackNum - whiteNum );59         else if( whiteNum > blackNum )60             printf( "White wins by %d\n", whiteNum - blackNum );61     }62  63     return 0;64 }65 void recursion( int a, int b )66 {67     int i, j;68     int xx, yy;69     for( i=0; i<4; i++ )70     {71         xx = a + dx[i];72         yy = b + dy[i];73         if( xx>0 && xx<=n && yy>0 && yy<=n && flag[xx][yy] == 0 )74         {75             num++;76             flag[xx][yy] = 1;  /// 我到此一游;77             recursion( xx, yy );78         }79         if( xx>0 && xx<=n && yy>0 && yy<=n && flag[xx][yy] == 1 )80         {81             if( array[xx][yy] == 'w' )82                 wl = 1;83             if( array[xx][yy] == 'b' )84                 bl = 1;85         }86     }87 }
       
      
     

SZU  Problem(D89):The Settlers of Catan

Judge Info

• Memory Limit: 65536KB
• Case Time Limit: 3000MS
• Time Limit: 3000MS
• Judger: Number Only Judger

Description

Within Settlers of Catan, the 1995 German game of the year, players attempt to dominate an island by building roads, settlements and cities across its uncharted wilderness.

You are employed by a software company that just has decided to develop a computer version of this game, and you are chosen to implement one of the game's special rules:

When the game ends, the player who built the longest road gains two extra victory points.

The problem here is that the players usually build complex road networks and not just one linear path. Therefore, determining the longest road is not trivial (although human players usually see it immediately).

Compared to the original game, we will solve a simplified problem here: You are given a set of nodes (cities) and a set of edges (road segments) of length 1 connecting the nodes. The longest road is defined as the longest path within the network that doesn't use an edge twice. Nodes may be visited more than once, though.

Example: The following network contains a road of length 12.

o        o -- o        o \      /      \      /  o -- o        o -- o /      \      /      \o        o -- o        o -- o               \      /                o -- o

Input

The input file will contain one or more test cases. The first line of each test case contains two integers: the number of nodes n (2<=n<=25) and the number of edges m (1<=m<=25). The next m lines describe the m edges. Each edge is given by the numbers of the two nodes connected by it. Nodes are numbered from 0 to n-1. Edges are undirected. Nodes have degrees of three or less. The network is not neccessarily connected.

Input will be terminated by two values of 0 for n and m.

Output

For each test case, print the length of the longest road on a single line.

Sample Input

3 20 11 215 160 21 22 33 43 54 65 76 87 87 98 109 1110 1211 1210 1312 140 0

Sample Output

212

1 #include 
     
       2 #include 
      
        3 #define N 30 4 int array[N][N]; 5 int distance = 0; //用来记录路径的多少  6 int n, m; 7 int step; 8 void recursion( int , int ); 9 int main()10 {11     int a, b;12     int i, j;13     int max = 0;14     while( scanf( "%d%d", &n, &m ) && n != 0 && m != 0 )15     {16         max = 0;17         memset( array, 0, sizeof(array) );18         // 把路径都打表打出来19         for( i=0; i
       
         step )37                         step = distance;38                     array[i][j]--; // 标记已经走过这段路了。。39                     array[j][i]--;40                     recursion( i, j );41                     array[i][j]++;42                     array[j][i]++;43                 }44                 if( step > max )45                     max = step;46             }47  48         }49         printf( "%d\n", max );50     }51     return 0;52 }53 void recursion( int a, int b )54 {55     int i;56     for( i=0; i
        
          step )64                 step = distance;65             recursion( b, i );66             array[b][i]++;67             array[i][b]++;68             distance--;69         }70     }71 }
        
       
      
     

SZU  Problem(I77):repeatless

Judge Info

• Memory Limit: 65535KB
• Case Time Limit: 3000MS
• Time Limit: 3000MS
• Judger: Normal

Description

A repeatless number is a positive integer containing no repeated digits. For instance, the first 25 repeatless numbers are

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, . . .

Given an integer n, your goal is to compute the nth repeatless number.

Input

The input test file will contain multiple test cases, each consisting of a single line containing the integer n, where 1 ≤ n ≤ 1000000. The end-of-file is marked by a test case with n = 0 and should not be processed.

Output

For each input case, the program should print the nth repeatless number on a single line.

Sample Input

25100000

Sample Output

2726057

1 #include 
     
       2 #define N 1001000 3 int array[N]; 4 int flag[N]; 5 int buffer[10]; 6 int p = 0; 7 int q = 0; 8 int bl ,k = 1; // 位数 9  10 void recursion( int k );11  12 int main()13 {14     bl = 1;15     for( k=1; k<=8; k++ )16     {17         p = 0;18         recursion( k );19     }20     int n;21     while( scanf( "%d", &n ) && n != 0 )22         printf( "%d\n", array[n-1] );23     return 0;24 }25  26 void recursion( int k )27 {28     if( bl == 0 ) 29         return ;30     int i, j;31     int a, b;32     if( p == k )33     {34         int sum = 0;35         int temp;36         for( i=0; i
     

SZU  Problem(J41):Back To The Start

Judge Info

• Memory Limit: 32768KB
• Case Time Limit: 1000MS
• Time Limit: 1000MS
• Judger: Normal

Description

回到原点。仅用此题纪念已经远离我们的高考。 一个迷宫中有一个机器人，机器人的起始位置在左上角（0,0）处。 迷宫中有障碍物`#`，不能走动，`.`代表可以走动，迷宫中只有`.` 或`#`两种符号。迷宫左上角保证为`.`。 然后接受了一堆指令，U（上），D（下），L（左），R（右），做出相应的方向移动，注意碰到障碍物或走出迷宫则原地不动，该移动方向是相对于迷宫，而不是相对自身的方向。 机器人每走一步，会自动记录当前回到起点的一条最短路。机器人收到RETURN指令，则从当前位置开始根据记录的最短路返回起点。 你的任务就是输出机器人返回时候的路线。 特殊说明：由于机器人的记忆力有限，每一步记录的最短路根据前一步记录的路径结果来更新最短路。

Input

包含多组测试，读取以EOF结束。 第一行 告诉你2个正整数n和m（n,m<=10），接下来有n*m的矩阵输入。 接下来有一堆由空格隔开的指令，当接受到RETURN指令，代表这组数据的结束(总指令个数不多于100)。

Output

对于每个测试数据，输出机器人的返回路线。 输出路线以(x,y)这种形式输出，每组数据后面，输出一个空行。

Sample Input

3 3..#.#....R R D L D D U D R RETURN3 3..#.#....R R RETURN2 2....D R U L R D RETURN

Sample Output

(2,1)(2,0)(1,0)(0,0)(0,1)(0,0)(1,1)(0,1)(0,0)

1 #include 
     
        2 #include 
      
         3 #define N 150  4 char buffer[N][N]; // 用来记录地图  5 int array[N][N];  6 int stackx[N*N];  7 int stacky[N*N];  8 int h=0;  9 int main() 10 { 11     int a, b; 12     int m, n; 13     int i, j; 14     int p = 0; 15     char command[10]; 16     while( scanf( "%d%d", &m, &n ) != EOF ) 17     { 18         memset( array, 0, sizeof(array) ); 19         // 输入地图 20         for( i=0; i
       
        = 0 && buffer[i-1][j] != '#' ) 31             { 32                 i--; 33                 if( array[i][j] == 0 ) 34                 { 35                     stackx[p] = i; 36                     stacky[p++] = j; 37                     array[i][j]=1; 38                 } 39                 else 40                 { 41                     a = i; 42                     b = j; 43                     while( stackx[p-1] != a || stacky[p-1] != b && p > 0 ) 44                     { 45                         array[stackx[p-1]][stacky[p-1]] = 0; 46                         p--; 47                     } 48                 } 49             } 50             if( strcmp( command, "D" ) == 0 && i+1 < m && buffer[i+1][j] != '#' ) 51             { 52                 i++; 53                 if( array[i][j] == 0 ) 54                 { 55                     stackx[p] = i; 56                     stacky[p++] = j; 57                     array[i][j] = 1; 58                 } 59                 else 60                 { 61                     a = i; 62                     b = j; 63                     while( stackx[p-1] != a || stacky[p-1] != b  && p > 0 ) 64                     { 65                         array[stackx[p-1]][stacky[p-1]] = 0; 66                         p--; 67                     } 68                 } 69             } 70             if( strcmp( command, "L" ) == 0 && j-1 >= 0 && buffer[i][j-1] != '#' ) 71             { 72                 j--; 73                 if( array[i][j] == 0 ) 74                 { 75                     stackx[p] = i; 76                     stacky[p++] = j; 77                     array[i][j] = 1; 78                 } 79                 else 80                 { 81                     a = i; 82                     b = j; 83                     while( stackx[p-1] != a || stacky[p-1] != b && p > 0 ) 84                     { 85                         array[stackx[p-1]][stacky[p-1]] = 0; 86                         p--; 87                     } 88                 } 89             } 90             if( strcmp( command, "R") == 0 && j+1 < n && buffer[i][j+1] != '#' ) 91             { 92                 j++; 93                 if( array[i][j] == 0 ) 94                 { 95                     stackx[p] = i; 96                     stacky[p++] = j; 97                     array[i][j] = 1; 98                 } 99                 else100                 {101                     a = i;102                     b = j;103                     while( stackx[p-1] != a || stacky[p-1] != b && p > 0 )104                     {105                         array[stackx[p-1]][stacky[p-1]] = 0;106                         p--;107                     }108                 }109             }110         }111         while( p >= 1 )112         {113             printf( "(%d,%d)\n", stackx[p-1], stacky[p-1] );114             p--;115         }116         puts("");117     }118     return 0;119 }
       
      
     

SZU Problem(J50):Train Problem I

 

Judge Info

• Memory Limit: 65536KB
• Case Time Limit: 10000MS
• Time Limit: 10000MS
• Judger: Normal

Description

As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.

Input

The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.

Output

The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.".

Sample Input

3 123 3213 123 312

Sample Output

Yes.No.

1 #include 
     
       2   3 char array[11]; 4 char buffer[11]; 5 char station[11]; 6   7 int main() 8 { 9     int num;10     int t;11     int i;12     int p = 0;13     int q = 0;14     while( scanf( "%d", &t ) != EOF )15     {16         scanf( "%s", array );17         scanf( "%s", buffer );18         q = 0;19         p = 0;20         i = 0;21         int flag = 1;22         while( flag != 0 )23         {24             flag = 1;25             if( ( p == 0 || station[p-1] != buffer[q] ) && p < t && i < t )26             {27                 flag = 2;28                 station[p++] = array[i++];29             }30             if( station[p-1] == buffer[q] && q < t && p >=0 )31             {32                 flag = 2;33                 p--;34                 if( p == 0 && i == t )35                    flag = 0;36                 q++;37             }38             if( flag == 1 )39                flag = 0;40         }41         if( p == 0 && i == t )42             printf( "Yes.\n");43         else44             printf( "No.\n" );45     }46     return 0;47 }
     

SZU Problem(L02):全排列

Judge Info

• Memory Limit: 65536KB
• Case Time Limit: 3000MS
• Time Limit: 3000MS
• Judger: Normal

Description

给定N,输出字典序1-N的全排列

Input

第一行为测试组数T，接下来T行，每行一个数字N1<=T,N<=8

Output

输出结果,每组N!行数与数之间一个空格

Sample Input

13

Sample Output

1 2 31 3 22 1 32 3 13 1 23 2 1

1 #include 
     
       2 #include 
      
        3 #define N 10 4 int stack[N];  /// 栈的结构。记录每一个东西 5 int flag[N];  /// 标记是否被访问过 6 int p = 0; 7 int t, n; 8 void recursion( int current ); 9 int main()10 {11     scanf( "%d", &t );12     while( t-- )13     {14         scanf( "%d", &n ); /// 数字的多少15         recursion( 0 );16     }17     return 0;18 }19 void recursion( int current )20 {21     int i, j;22     if( n == p )23     {24         for( j=0; j
      
     

SZU Problem(L91):Checker Challenge

Judge Info

• Memory Limit: 65536KB
• Case Time Limit: 3000MS
• Time Limit: 3000MS
• Judger: Number Only Judger

 

Description

Examine the 6x6 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal. (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.)

Column    1   2   3   4   5   6  -------------------------1 |   | O |   |   |   |   |  -------------------------2 |   |   |   | O |   |   |  -------------------------3 |   |   |   |   |   | O |  -------------------------4 | O |   |   |   |   |   |  -------------------------5 |   |   | O |   |   |   |  -------------------------6 |   |   |   |   | O |   |  -------------------------

The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6:

ROW	1	2	3	4	5	6
COLUMN	2	4	6	1	3	5

This is one solution to the checker challenge. Write a program that finds all unique solution sequences to the Checker Challenge (with ever growing values of N). Print the solutions using the column notation described above. Print the the first three solutions in numerical order, as if the checker positions form the digits of a large number, and then a line with the total number of solutions.

Input

The first number  means how many test cases will followed. For every test case will be a single line that contains a single integer N (6 <= N <= 13) that is the dimension of the N x N checkerboard.

Output

For each test cases, print the follow contains: The first three lines show the first three solutions found, presented as N numbers with a single space between them. The fourth line shows the total number of solutions found.

Sample Input

16

Sample Output

2 4 6 1 3 53 6 2 5 1 44 1 5 2 6 34 刚开始，超时了，我超二，我先判断了O(n)，再判断了0(1) = =

1 #include 
     
       2 #include 
      
        3 #define N 15 4 int flag[N][N]; // 标记有没有访问过和能不能访问 5 int wahaha[N]; 6 int stack[N]; // 栈的结构，记录皇后在的位置 7 void dfs( int, int ); 8 int n; // 记录皇后有多少个 9 int p; // 记录栈中的数字个数10 int num = 0;11 int main()12 {13     int t, i, j;14     scanf( "%d", &t );15     while( t-- )16     {17         scanf( "%d", &n );18         // 初始化呀初始化19         for( i=1; i<=n; i++ )20             for( j=1; j<=n; j++ )21                 flag[i][j] = 0;22         memset( wahaha, 0, sizeof(wahaha) );23         p = 0;24         num = 0;25  26         dfs(1, 1);27         printf( "%d\n", num );28     }29     return 0;30 }31  32 void dfs( int row, int column )  // row是行, column是列33 {34     int i;35     int a;36     int tempx, tempy;37     if( p == n )38     {39         if( ++num <= 3 )40         {41             for( i=0; i
       
        = 1 && tempy >= 1 )60                 if( flag[tempx--][tempy--] == 1 )61                 {62                     a = 1;63                     break;64                 }65             if( a == 0 )66             {67                 // 右对角线68                 tempx = row;69                 tempy = i;70                 while( tempx >= 1 && tempy <= n )71                     if( flag[tempx--][tempy++] == 1 )72                     {73                         a = 1;74                         break;75                     }76                     else77                         continue;78             }79             else80                 continue;81             if( a == 0 )82             {83                 flag[row][i] = 1; // 钟老大到此一游84                 wahaha[i] = 1;85                 stack[p++] = i;86                 dfs( row+1, i );87                 p--;88                 flag[row][i] = 0; // 老大走了再见89                 wahaha[i] = 0;90             }91             else92                 continue;93         }94     }95 }