Morris' Blog

2013年1月4日星期五

[ZJ] d618. 有限狀態自動機（Finite State Machine）

http://zerojudge.tw/ShowProblem?problemid=d618

內容：

有限狀態自動機（Finite State Machine）是由有限個狀態以及在這些狀態之間的轉移和動作等行為所組成的數學模型。
有限狀態自動機可以使用狀態轉移圖（State Transition Diagram）來表示，例如下面的狀態轉移圖，表示的是一個可以用來判斷二進位數是否具有偶數個 0 的有限狀態自動機。「沒有起點的箭頭」指向狀態 S₁，表示狀態 S₁ 是開始狀態（Start State）；狀態 S₁ 為雙重圓圈，表示狀態 S₁ 是接受狀態（Accept State）。

輸入二進位數，例如 10101，一開始的狀態是狀態 S₁；讀到第一個 1 的時候，依然停留在狀態 S₁；讀到第一個 0 的時候，移動到狀態 S₂；讀到第二個 1 的時候，依然停留在狀態 S₂；讀到第二個 0 的時候，移動到狀態 S₁；讀到第三個 1 的時候，依然停留在狀態 S₁；因為狀態 S₁ 是接受狀態，表示輸入的二進位數 10101 具有偶數個 0。

如果輸入的二進位數是 10010，最後會停留在狀態 S₂。因為狀態 S₂ 不是接受狀態，所以我們可以知道二進位數 10010 不具有偶數個 0。

有限狀態自動機也可以使用狀態轉移表（State Transition Table）來表示，例如上面(上一頁)的狀態轉移圖可以表示為：

現在假設葆葆班長定義了以下狀態

立正 ( 起立 )
稍息
蹲下
坐下
向右轉
向左轉
向後轉

另外

狀態 2 時只能改變狀態為 1
狀態 3. 4 可以互換或改變為狀態 1

輸入說明：

第一行為一整數 T ( T ≤ 20 )
代表下面有 T 組測試資料
每組測試資料一行字串 ( 由 1 ~ 7 組成，字元長度不超過 100 )
代表一連串的狀態 ( 假設起始狀態為 1 )

輸出說明：

輸出最後的狀態 ( 一個數字 )

    範例輸入    ：  

31234162146121212121

    範例輸出    ：

提示：

¤ 相關題目內容取自 2009 NPSC 國中組決賽

出處：

葆葆 (管理：maxyuan)

/**********************************************************************************/
/* Problem: d618 "有限狀態自動機（Finite State Machine）" from 葆葆   */
/* Language: C                                                                   */
/* Result: AC (4ms, 270KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-05-30 21:32:58                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   int T, a;
   int Map[8][8] = {{0,0,0,0,0,0,0,0},
                   {1,1,1,1,1,1,1,1},
                   {0,1,1,0,0,0,0,0},
                   {0,1,0,1,1,0,0,0},
                   {0,1,0,1,1,0,0,0},
                   {0,1,1,1,1,1,1,1},
                   {0,1,1,1,1,1,1,1},
                   {0,1,1,1,1,1,1,1}
                   };
   char S[101];
   scanf("%d", &T);
   while(T--) {
       scanf("%s", S);
       int now = S[0] - '0';
       for(a = 1; S[a]; a++) {
           if(Map[now][S[a] - '0'])
               now = S[a] - '0';
       }
       printf("%d\n", now);
   }
   return 0;
}

[ZJ] d730. 升旗典礼 ——加强版

http://zerojudge.tw/ShowProblem?problemid=d730

內容：

幼稚園老師帶小朋友最頭痛的就是在昇旗典禮的時候。
小朋友在典禮中很容易亂動，要令他們都朝向旗子所在的方向卻是困難的。
現在簡化問題。總共有9個小朋友，小朋友面朝的方向只有北東南西四個方向。
我們定義0為北方, 1為東方, 2為南方, 3為西方, 從北方開始, 順時針方向轉一圈為0 -> 1 -> 2 -> 3 -> 0。
老師則使用9種口令來同時讓數位小朋友順時針轉90度
口令　　　那幾個小朋友順時針轉90度(數字代表第幾個)
1　　　　1, 2, 4, 5
2　　　　1, 2, 3
3　　　　2, 3, 5, 6
4　　　　1, 4, 7
5　　　　2, 4, 5, 6, 8
6　　　　3, 6, 9
7　　　　4, 5, 7, 8
8　　　　7, 8, 9
9　　　　5, 6, 8, 9

例如：如果原本第1, 2, 4, 5個小朋友面朝北方(0)，老師喊口令1，第1, 2, 4, 5個小朋友會變成面朝東方(1)
旗子永遠在北方，而老師要使用口令讓所有小朋友都朝向北方。口令使用次數不限，請你求出其一連串的口令所形成的最短序列，並列印出來。

輸入說明：

输入包含许多组测资。
测资第一行有一个整数，代表共有几组测资。
每组测资为1行，这一行里有9个整数，范围0到3，代表9位小朋友原本所朝的方向。
这9个整数的每个整数之间以一个空白字元隔开。

輸出說明：

输出为口令所形成的最短序列，每组输出为1行，其口令序列中的每个口令间以一个空白字元隔开。
如果有2组(含)以上的最短序列，请输出字典排序最小者。
例如：1 1 3 4 5 和1 2 3 4 5 两序列，要输出1 1 3 4 5。

    範例輸入    ：  

12 3 1 1 1 3 0 0 0

    範例輸出    ：

1 1 2 2 2 4 8 8 8 9

提示：

这题是 d298: 升旗典礼加强版。
测试数据可能会非常庞大，所以你的程序一定要跑得非常快。//一共大约100000笔
为这题抓狂吧！

出處：

IOI'94 The Clocks 再次加强 (管理：liouzhou_101)

作法 : 回朔法
用BFS從 0 0 0 0 0 0 0 0 0 開始倒推回去
在mark的部份，採用進制轉換，用4進制

/**********************************************************************************/
/* Problem: d730 "升旗典礼 ——加强版" from IOI'94 The Clocks 再次加强*/
/* Language: C                                                                   */
/* Result: AC (352ms, 3072KB) on ZeroJudge                                       */
/* Author: morris1028 at 2011-05-30 22:59:54                                     */
/**********************************************************************************/

#include<stdio.h>
char mark[270000] = {}, ans[270000], best[270000], dir[4] = {3,0,1,2}, dirp[4] = {-3,1,1,1};
int next[270000] = {};
int s4[10] = {1}, Queue[270000];
char Map[10][7] = {{},
               {1,2,4,5,0},
               {1,2,3,0},
               {2,3,5,6,0},
               {1,4,7,0},
               {2,4,5,6,8,0},
               {3,6,9,0},
               {4,5,7,8,0},
               {7,8,9,0},
               {5,6,8,9,0}
               };
void Change(int N, int flag, char C[]) {
   while(N) {
       C[flag] = N%4, N /= 4, flag++;
   }
}
void Build() {
   int a, b, c, qt = 0, t, p;
   Queue[qt++] = 0, best[0] = 0, ans[0] = 10, mark[0] = 1;
   for(a = 0; a < qt; a++) {
       t = Queue[a], p;
       char C[10] = {};
       Change(t, 0, C);
       for(b = 1; b < 10; b++) {
           for(c = 0, p = t; Map[b][c]; c++) {
               p -= s4[Map[b][c]-1] * dirp[C[Map[b][c]-1]];
           } /*c*/
           if(mark[p] == 0) {
               mark[p] = 1,Queue[qt++] = p;
               next[p] = t, best[p] = best[t] + 1, ans[p] = b+'0';
           }
           else {
               if(best[p] > best[t]+1) {
                   Queue[qt++] = p;
                   next[p] = t, best[p] = best[t] + 1, ans[p] = b;
               }
           }
       } /*b*/
   } /*a*/
}
void Print(int now) {
   if(now) {
       Print(next[now]);
       putchar(ans[now]), putchar(' ');
   }
}
main() {
   int t, a, s, x;
   for(a = 1; a < 10; a++)
       s4[a] = s4[a-1] * 4;
   Build();
   scanf("%d", &t);
   while(t--) {
       for(a = 0, s = 0; a < 9; a++) {
           scanf("%d", &x);
           s += x * s4[a];
       }
       Print(s), puts("");
   }
   return 0;
}

[ZJ] a097. PARKET

http://zerojudge.tw/ShowProblem?problemid=a097

內容：

Ivica家的客廳地板最近正在整修,整個矩形地板面積長L英吋,寬W英吋.

而他家的正方形地磚則每一個大小剛好為1*1平方英吋,地磚顏色則有黑色及灰色兩種.

而在黑灰色千千萬萬種組合中,他決定選擇中間為一黑色矩形(總數R平方英吋)邊框則由灰色磚塊(總數B平方英吋)排列而成的圖案樣式.四面的邊框厚度需相同.

底下便是範例測資2的圖示-外層為灰色磚塊形成的邊框,內層則為2個黑色磚塊形成的矩形圖案:

有一天Marica去拜訪Ivica家.她邊吃著她的餅乾並數著各種顏色的磚塊數量.她回家時又想起了這B,R兩個數字並要你寫一個程式根據B,R的值算出Ivica家客廳地板的大小(L,W).

輸入說明：

本題包含多組測試資料,每組測資各占一行,包含B,R兩個整數(<=2^30).

輸出說明：

對於每組測資請輸出對應的L,W(L>=W)以空白分隔,若有多組L,W解請輸出L,W值相差最大的那組解.你可以假設對於每組輸入都必有一組或一組以上的L,W解

    範例輸入    ：  

8 110 2

    範例輸出    ：

3 34 3

提示：

出處：

SPOJ改 (管理：pcsh710742)

作法 : 暴力
硬拆吧，然後利用判別式找出整數解

/**********************************************************************************/
/* Problem: a097 "PARKET" from SPOJ改                                           */
/* Language: C                                                                   */
/* Result: AC (2ms, 274KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-05-31 21:55:14                                     */
/**********************************************************************************/

#include<stdio.h>
#include<math.h>
main() {
   long long B, R, a, b, A, D, t;
   while(scanf("%lld %lld", &B, &R) == 2) {
       long long sq = (long long)sqrt(R);
       for(a = 1; a <= sq; a++) {
           if(R%a == 0) {
               b = R/a;
               A = a + b;
               D = 4 * (A*A + 4*B);
               t = (long long)sqrt(D);
               if(t * t == D && (-2*A + t)%8 ==0 ) {
                   printf("%lld %lld\n", b + (-2*A + t)/4, a + (-2*A + t)/4);
                   break;
               }
           }
       }
   }
   return 0;
}

[ZJ] d297. 算算算....Lunatic

http://zerojudge.tw/ShowProblem?problemid=d297

內容：

請求正三角形中有多少個正三角形？

輸入說明：

每一行有一個數字 n 表示正三角形的邊長。

輸出說明：

對每一行輸出答案。答案小於二十二億。

d297: 算算算....Lunatic

    範例輸入    ：  

    範例輸出    ：

15132748

提示：

正三角形的邊長皆為正整數，最小為一。

出處：

me (管理：asas)

分成正立跟倒立兩個部份，去導公式
ans = [(a+1)*a/2 + a*(a-1)/2]
+ [a*(a-1)/2 + (a-2)*(a-3)/2] + [(a-1)*(a-2)/2 + (a-4)*(a-5)/2] ....
L 小三角形邊長
[(a+1)*a/2 + a*(a-1)/2] L = 1 => 前面是正立後面是倒立的個數
[a*(a-1)/2 + (a-2)*(a-3)/2] L = 2 ... 類推
切記，如果個數乘出來為負，請不要記入

/**********************************************************************************/
/* Problem: d297 "算算算....Lunatic" from me                                  */
/* Language: C                                                                   */
/* Result: AC (4ms, 266KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-05-31 22:03:10                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   long long N, t, U, L;
   while(scanf("%lld", &N) == 1) {
       U = (N*N*N+3*N*N+2*N-(N*(N+1)*(2*N+4)/3))/2;
       t = N / 2;
       L = (t*(N*N+3*N+2)+(t*(t+1)*(4*t-6*N-7))/3)/2;
       printf("%lld\n", U+L);
   }
   return 0;
}

[ZJ] d411. 算了好久......

http://zerojudge.tw/ShowProblem?problemid=d411

內容：

某一天，恆恆、衡衡要一決算數的速度，
他們想比一比某一個數字M是否為2的N次方的倍數，
而每次的M都是高達9999位的大數字呀!!!
但他們相信他們的數學能力。
我想說，那嚜大的數字電腦跑就好啦~
於是我也加入了戰局~~
但...............
我不會寫程式呀!!!!!
好心人幫幫我打贏他們兩人吧~~~
我們一共比了10場

輸入說明：

每行輸入2個正整數M、N，
M代表上述的某數，N代表2的N次
0=<M<10^9999
0<=N<10

輸出說明：

若M為2的N次的倍數請輸出 YA!!終於算出M可被2的N次整除了!!
若不是請輸出可惡!!算了這麼久M竟然無法被2的N次整除

    範例輸入    ：  

6 216 3

    範例輸出    ：

可惡!!算了這麼久6竟然無法被2的2次整除YA!!終於算出16可被2的3次整除了!!

提示：

2^N = pow(2,N)
記得加 #include<math.h>

出處：

愷愷 (管理：kevin830222)

大數除小數，直接模擬硬做就好了

/**********************************************************************************/
/* Problem: d411 "算了好久......" from 愷愷                                */
/* Language: C                                                                   */
/* Result: AC (10ms, 292KB) on ZeroJudge                                         */
/* Author: morris1028 at 2011-05-31 22:08:39                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   char S[10001];
   int a, N, s2[10]={1};
   for(a = 1; a < 10;s2[a]=s2[a-1]*2,a++);
   while(scanf("%s %d", S, &N) == 2) {
       int t = S[0]-'0';
       for(a = 1; S[a]; a++) {
           t = t*10 + S[a]-'0';
           t %= s2[N];
       }
       if(t)   printf("可惡!!算了這麼久%s竟然無法被2的%d次整除\n", S, N);
       else   printf("YA!!終於算出%s可被2的%d次整除了!!\n", S, N);
   }
   return 0;
}

[ZJ] d316. Quadrangle！

http://zerojudge.tw/ShowProblem?problemid=d316

內容：

已知四边形ABCD的面积为S。E，F，G，H各点分别在四边形ABCD的AB，BC，CD，DA边上。
当 AE:EB=BF:FC=CD:GD=DH:HA=k 时，求四边形EFGH的面积。

輸入說明：

每行一组数据：S，k（它们都是小于2的31次方的正整数）。

輸出說明：

对于每组数据，输出四边形EFGH的面积。
如果面积是整数，就直接输出；
如果面积是分数，就按照 5 / 9 输出，分数要化简。
参考 Sample output.

    範例輸入    ：  

1 1

    範例輸出    ：

1 / 2

提示：

答案中，所有的数字小于2的64次方。
测试数据很弱，不久之后将加强XXD
不完善的程序只能得到暂时的AC

出處：

经典题目 (管理：liouzhou_101)

/**********************************************************************************/
/* Problem: d316 "Quadrangle！" from 经典题目                               */
/* Language: C                                                                   */
/* Result: AC (6ms, 266KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-05-31 22:19:15                                     */
/**********************************************************************************/

#include<stdio.h>
unsigned long long gcd(unsigned long long x, unsigned long long y) {
   unsigned long long t;
   while(x%y) {
       t = x, x = y, y = t%y;
   }
   return y;
}
main() {
   int s, k;
   while(scanf("%d %d", &s, &k) == 2) {
       unsigned long long U = (2*k), L = (k+1);
       unsigned long long t;
       t = gcd(U, L), U /= t, L /= t;
       L *= k+1;
       t = gcd(U, L), U /= t, L /= t;
       U = L - U;
       t = gcd(U, L), U /= t, L /= t;
       U *= s;
       t = gcd(U, L), U /= t, L /= t;
       if(U%L == 0)
           printf("%llu\n", U/L);
       else
           printf("%llu / %llu\n", U, L);
   }
   return 0;
}

[ZJ] a064. SPOJ 4580.ABCDEF

http://zerojudge.tw/ShowProblem?problemid=a064

內容：

You are given a set S of integers between -30000 and 30000 (inclusive).
Find the total number of sextuples

that satisfy:

輸入說明：

The first line contains integer N (1 ≤ N ≤ 100), the size of a set S.
Elements of S are given in the next N lines, one integer per line. Given numbers will be distinct.

輸出說明：

Output the total number of plausible sextuples.

    範例輸入    ：  

112232-1135710

    範例輸出    ：

提示：

Added by:	Luka Kalinovcic
Date:	2009-07-13
Time limit:	2s
Source limit:	50000B
Languages:	All except: ERL JS PERL 6
Resource:	own problem

题目来源SPOJ 4580，输入只有一笔，不用EOF判断结束。

出處：

SPOJ 4580 (管理：liouzhou_101)

以下是 O(n^4)
要看O(n^3) 請用"百度"搜尋，是用HASH的

/**********************************************************************************/
/* Problem: a064 "SPOJ 4580.ABCDEF" from SPOJ 4580                               */
/* Language: C                                                                   */
/* Result: AC (780ms, 737KB) on ZeroJudge                                        */
/* Author: morris1028 at 2011-05-31 22:36:21                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#define move 60000
main() {
   int N, S[100], i, j, k, l;
   while(scanf("%d", &N) == 1) {
        for(i = 0; i < N; i++)
            scanf("%d", &S[i]);
        int ef[120001] = {};
        long long A = 0;
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                ef[(S[i]+S[j]+move)]++;
        for(i = 0; i < N; i++) {
            for(j = i+1; j < N; j++)
                for(l = 0; l < N; l++)
                    for(k = 0; k < N; k++){
                        if(S[k] != 0 && (S[i]*S[j]+S[l])%S[k] == 0 && abs((S[i]*S[j]+S[l])/S[k]) < 60000 )
                        A+=2*ef[(S[i]*S[j]+S[l])/S[k]+move];
                    }
            j = i;
                for(l = 0; l < N; l++)
                    for(k = 0; k < N; k++){
                        if(S[k] != 0 && (S[i]*S[j]+S[l])%S[k] == 0 && abs((S[i]*S[j]+S[l])/S[k]) < 60000 )
                        A+=ef[(S[i]*S[j]+S[l])/S[k]+move];
                    }
        }
        printf("%lld\n", A);
   }
   return 0;
}

訂閱：文章 (Atom)

2013年1月4日 星期五

[ZJ] d618. 有限狀態自動機（Finite State Machine）

[ZJ] d730. 升旗典礼 ——加强版

[ZJ] a097. PARKET

[ZJ] d297. 算算算....Lunatic

[ZJ] d411. 算了好久......

[ZJ] d316. Quadrangle！

[ZJ] a064. SPOJ 4580.ABCDEF

2013年1月4日星期五