這場爭論還在持續中，活在什麼環境就會有什麼樣的想法，沒有全區的誰對誰錯。老子就是看那群台清交不爽啊！努力、聰明從來都不是問題，不能讓人佩服得心服口服就會不滿，認知差異、體諒差異，並非積極消除差異。

拿努力、聰明的成果當作區隔、拒絕的手段，倒不如說「空閒時間會嘗試用自己的方法。」不做其實沒差。等到沒了戰友，那又是什麼困境呢？

大家好，我是 morris (morris821028)，被點名來說對於 ACM-ICPC 競賽資源在各校分配不均的看法。

首先，有個共識台清交都有系統式訓練，若說沒有系統式訓練，至少還有一群默默在背後敲代碼的同學、學長一起奮鬥。訓練環境有資源、有伴、有敵，對於非台清交的學生大多數沒有這樣的方式學習，但我覺得沒必要用相同的模式運作、也辦不到。

有教授、學長們引領固然不錯，能在有限時間內達到競賽水平，從高中開始當 ACMer 的我來說，很多人大學才開始學這領域，兩年就能上戰場的牛人，當然會先精神崩潰一下，然後吵著、罵著「他們有資源啊！」當時也這麼暗地著罵著，仔細想想自己沒有辦法在所謂系統式訓練下苟延殘喘，已經在沒有督促下學習很久，把我關進籠子學習，大概只會見到越來越低落的 morris。

對我來說，講講自己有多討厭你們的才華、罵罵你們所擁有的資源，心裡才會舒坦點。間歇性地說這些，明白自己永遠不會跟你們用同一個方式做事、學習。「爭取」作為一個求上進的舉動？爭取到後，才發現自己多麼不合適，還不如讓適合的人運用這些資源。

我們被放上同一個架子上面比價，所以才會這麼不滿。「這麼不滿？那為什麼還要自找苦吃？」只是想學、還不想輸，願意用那數倍的時間來驗證自己的價值，也許不會被兜售出去，起碼價值還有機會留下，用不同的方式引領不一樣的人。

分配不均很正常，不然要拿什麼作為目標？等把自己所擁有的資源啃食完後，自然而然地就會找到、接觸新的資源，這樣比較有尋寶的樂趣？

我來自東部的花蓮，要說高中學習資源，少之又少！學長們也要在西部學校讀書，哪有空回學校教人，回來教一兩隻小貓？

高中－花蓮高中資優班，但也別想太多，咱們資優班不看整體分數的高低，考試靠單科成績決勝負，並且三年不換人。因此才有專題課選擇資訊的機會，從上高中開始才接觸這領域，一開始非常討厭寫程序，打從心底就排斥它。

靠著抄同學的作業活過來，老師教了語法基礎後，就發布挑戰－「寒暑假在 Zerojudge 完成 100 題」大家也知道 ZJ 很多水題，自然而然地成為生活中的一部分，水題寫個一天也不是問題，也許就是東部小孩的權力吧，不是為了競賽成績而學。

參加 NPSC、資訊科能力競賽，當時參加三年 NPSC 連一題都沒寫出來，根本不會讀檔操作，拿了錯誤訊息回來還真不知道是沒有讀檔成功還什麼的，就這麼度過三年比賽。在 NPSC 0 題，幾乎可以說是高中傳承的零題傳統。

在東區資訊科能力競賽中，程設部分都是數學模擬，跟西部的題目大相逕庭。決戰點都是在計概，那時不喜歡讀書的我幾乎都拿了期望值回來。最後一年進了全國賽，程設題目幾乎全寫，興沖沖地排隊等測試，那時還有「寫比較多題的人排前面」測試完後，拿了慘不忍睹的成績，早知道乾脆不寫。測試一結束，就趕緊搭車回花蓮，連頭都不想回。

(以上略－)

如果多少認識我，都明白我英文不好、中文理解也不行，出去比賽還需要一個高強度容忍的翻譯機，不然寫到一半的翻桌。這樣的能力絕對上不了台清交，大學就讀中興大學，隨後嘗試轉學到台清交成，但是沒有成功。最後在茵可的邀約才到中央大學。

也不是說要多麼有系統的訓練，學校課程沒有台清交的課程繁重，我們一學期的課程內容說不定還比不上台清交幾周的內容，有比較多時間慢慢寫程式，即使進步很慢，寫得好 (易懂)、寫得快比起寫得正確來得有趣。

我不適合比賽，跟學長們玩了幾次全國競賽，創下學校成績新高之後，就這麼解散。不弄 Topcoder、Codeforces 及 Google Code Jam，一來是看完題目差不多比賽就結束，二來介面和流程一度讓我精神崩潰，所以窩在簡單的 UVa 裡面打混。

打混的方式－東抄抄西抄抄，因為想要 AC、想出題，所以才學某些噁心的算法。看代碼、看題解學習就是我的學習方式，看了也不見得懂，那為什麼還要怕去看別人寫的？所有都由自己想、自己解決對我來說是奢侈，有 CSDN 可以靠，對我來說資源很夠，就怕沒能力理解。

部落格的部分內容根本不是寫給別人看的，整個 google 就是我的 codebook，寫完就會忘、理解透徹也會忘、自己做的報告也會忘。

關於

跳樓這件事情越來越不稀奇，不只有在台灣，在中國大陸那邊也是頻頻出現的事件。

近年来，有关大学生以及研究生，博士生自杀的新闻经常见诸报端，以至于让人们产生审自杀疲劳。当下除了清华北大的硕士博士跳楼自杀还能称之为新闻外，一些名不见经传的普通学校里的学生自杀，已经不能算新闻。

而最引人关注和热议的，无疑是2009年研究生杨元元的自杀身亡。她的信念是“知识可以改变命运”，可是和蔡某某一样，她奋斗多年学到了许多知识，名牌大学也毕业了，研究生也考上了，到了可以改变人生的时候了，但却没有任何起色，但却找不到理想的工作，不仅养不好家人与自己、解决不了面对的种种人生难题，反而越来越糟──“都说知识改变命运，为什么我学了那么多知识，也没见有什么改变？”此一问的背后是：活着又有何益呢？自杀成了她可悲的选择。
大学生自杀频现，教育之责何在？

《我奋斗了18年才和你坐在一起喝咖啡》

統計

自殺不成的就沒有列，還有部分出現的新聞，但是網上缺資料。

• 2012年11月26日
  東吳大一女墜樓 發票留言:對不起
• 2013年02月20日
  台大大四女學生 校園內跳樓輕生
• 2013年12月08日
  台灣大學學生跳樓身亡「媽是否不要我」
• 2014年04月08日
  中央大學博士生上吊自殺
• 2014年05月20日
  中興大學 30 歲男碩士生校內 12 樓墜落身亡
• 2014年06月09日
  政治大學法律系延畢生當晚回家跳樓

求資料

序

本篇文章記錄身邊大神去面試時所遇到的神祕問題，對於現在大三的我只能旁觀，雖然在計算機組織這一類的硬體課程修完不久，但是看到這些問題，還真的不知所措。

面試的時候，可以帶上會協助您的小夥伴們一起面試，這一點相當地奇特，面試不再是單打獨鬥。當然，小夥伴有事也沒有關係，將可以使用線上 call out。

也是這些原因，才有機會參與這些問題的討論。

面試題目

以下附錄僅為討論，不代表正確答案。

面試採用漸進式，由高階至低階開始追問，同時也會問到 Hardware Algorithm。

• 用 C/C++ 寫一個九九乘法表

  這邊就不多加以描述，通常採用兩層迴圈的寫法和一個 printf

  1 2 3

  for(int i = 1; i <= 9; i++) for(int j = 1; j <= 9; j++) printf("%d x %d = %d\n", i, j, i * j);

• printf(format, arg) 怎麼實作的？

  請準備 stdio.h 開始查閱，不過當下要想出來還真的挺難的，不過在 linux 下，stdin, stderr, stdout 都是一個檔案形式，這是在呼叫 printf後會去導入的目標所在。但如何解決 arg，要查閱一下 va_start 怎麼運作的，若上網搜尋得到。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  #include <libioP.h> #include <stdarg.h> #include <stdio.h> #undef printf /* Write formatted output to stdout from the format string FORMAT. */ /* VARARGS1 */ int __printf (const char *format, ...) { va_list arg; int done; va_start (arg, format); done = vfprintf (stdout, format, arg); va_end (arg); return done; } #undef _IO_printf ldbl_strong_alias (__printf, printf); /* This is for libg++. */ ldbl_strong_alias (__printf, _IO_printf);

  多變數到底是如何在這裡實作的，這一點要去考量 va_start，他會將參數位置丟入 va_list arg 中，但是如果參數個數或者是型態不符合 format，則運行的時候指針會指到錯誤的地方而噴出 RE，嘗試所及就到這裡了。

• CPU 怎麼實作這些？

  CPU 的 pipeline 的五個階段和實作，IF, ID, EX, MEM, WB
  擷取指令、指定解析、執行運算、寫入記憶體、寫回暫存器。
  然後如何 pipeline，如果有類型的不同的時候，pipeline 會猜測到底要不要 branch，如果真的要 branch，要將 branch 之後的指令清掉 … 計組忘得一乾二淨。

• 實作一個 n bits 加法器 adder，在平行的情況下，最多能多快。

  一般而言，要在 n 個 clock 後才能得到，這麼做就太慢了，之前上課有提到 carry lookahead adder, carry saved adder, … 等，這些雖然能在比一般時間更快得到是否要進位，但問題是要怎麼知道加完之後的結果！

  所以通常是切塊，然後賭前一塊到底會不會進位過來，把兩個答案都先算出，最後再利用 selector 去選擇正確的那個結果。

  如果單純是要得到是否會 overflow，最快可以在 O(log n) 時間內得到，採用分治的方式去考慮進位問題。

  分治算法看起來很接近線段樹的做法，藉由上一步，把兩種可能的答案都先算出，我們已經在 O(log n) 時間內把線段樹建出，接著對每一個元素做前綴的區間查詢，全部并行可以在 O(log n) 時間內完成，然後調用 selector 決定我們的答案。

  太多平行，平行處理的效能分析和處理資料的優先順序，很少在 ACM 使用，只好在此刻 yy 了。

• 給很多區間 [l, r]，接著詢問某個點 x 被多少區間覆蓋。

  線段樹處理，搭配區間的懶操作，直接對區間 [l, r] 所有元素 + 1 即可，在 O(n log n) 時間內建表，然後單點查詢 A[x] 的值為何，這種做法可以動態支持。

• 給一般圖進行匹配，假設不使用標準的帶花樹算法，使用自己的算法，請問誤差為多少。

  貪婪策略：
  每次對一個鄰居最少的點，找到其鄰居 (他的鄰居也最少) 進行匹配，然後把這些點都拿掉，繼續遞迴匹配。

  至於誤差－只能想辦法找到一個反例，來確定誤差一定大於某個值，要詳細證明什麼的，大概可以順便報一篇論文了。

  

  一群人在思考反例，想了很久都沒有結果，最後由天祥大神找到一個誤差有 20% 的反例，詳細如上圖所述，如果一開始拿到 AD 或者是 HI，則會把匹配數最多拿到 4 個，事實上為 5 個。

結論

相當可怕，學得都忘得一乾二淨，無法精準回答。

序

在此先感謝 inker 帶我出門！當然也感謝 彰師大 這次辦的程式競賽。這是一場久違的比賽，同時也是這學期最後一場，原因是因為太久沒參賽，導致往後的桂冠賽也無法參加。

至於討厭比賽的問題，這一篇就不多說了。記得下次繼續支持彰師大資工辦的活動，免得像靜宜大學被玩壞了。 CCPC 官網

賽前

比賽前日進發 inker 豪宅，中間歷經坐錯區間車，到比賽會場前，徒步走了三十分鐘到火車站搭車 … 各種經歷深感出門是件難事。跟我肯定是不幸的，應該多少有點關聯。

上次比賽是很久之前的事情，想到這次還會遭遇國手，還有清華交大的選手，深感害怕。在這情況下，要出門見人什麼的，讓我窩回宿舍吧！

題目

Problem A Non-boring sequences

UVa 1608 - Non-boring sequences

結果題目還是讀錯了，對於任意連續區間，都存在一個獨特的數字。

很容易誤解 connected subsequence 簡單的說就是相鄰兩個元素。
這題由於讀題錯誤，在全場第一個送出的同時拿下的 Wrong Answer。
在假解的情況下，居然通過了測試。

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

#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
int t, n, h1,h2;
int main(){
    scanf("%d", &t);
    while(t --){
        scanf("%d", &n);
        map<int, bool> mp;
        int i = 0;
        bool yes = true;
        int pre = -1;
        for(i = 0 ; i < n ; i ++)
        {
            scanf("%d", &h2);
            if(pre == h2){
            
                yes = false;
            }
            pre = h2;
        }
        printf(yes?"non-boring\n":"boring\n");
    }
    return 0;
}

Problem B Traffic Jam

UVa 1417 - Traffic Jam

這題是全場最噁心的題目，但是沒想到有人用 BFS 還是 DFS 在每個詢問就過了。

賽完看到記分板表示非常火。

猜測解法如下，採用線段樹的方式。

觀察

對於任兩點詢問假設這個區間是 [l, r]，不管同側還是異測，當然你也可以假設兩旁還有可以連的。發現對於區間 [l, r] 的點來說，會有左上無法到右下的情況或者左下無法到右上，兩者只有符合一個條件就可以說出 NO。

推倒

因此我們維護區間 [l, r] 的左上到右下、左下到右上的連通性。

對於區間 S 來說，可以切成 S1 和 S2，維護四條資訊，連通性有無 0/1。

• A(左上, 右下) =
  • S1.A & S2.A & (wx || yz)
  • S1.A & S2.D & (z || wxy)
  • S1.C & S2.A & (x || wyz)
  • S1.C & S2.D & (wz || xy)
• B(左下, 右上)
• C(左上, 右上)
• D(左下, 右下)

剩餘 BCD 三條類推，有空的時候再來填滿它，也就是說，之後的開邊跟閉邊都屬於單點更新，因此可以在 O(log n) 時間內完成。對於詢問兩點時，找到 [l, r] 查找 A || B 的結果，由於線段樹會切成數個區間，這個時候要由左而右依序組合即可。

Problem C Finding the Prime Implicants of a Boolean Function

這題就是單純複雜，但是輸入卻不明確。主辦單位有說會忽略空白比對，但是對於 Invaild input format 來說，題目也沒有說清楚輸入格式。

好吧，硬著頭皮做，至少把範例輸入輸出弄了一樣，但是卻砸了。

對了，關於 subset 有個快速地找法。

1
2
3

for(int j = (i-1)&i; j > 0; j--, j &= i) {
    // j 是 i 的 subset
}

這個寫法會在幾題的 UVa 中見到，速度快了 X 倍，不過這題測資沒有強成這樣，也許只是我寫太瘋狂了，想不到更好的解法來完成。最後掛了 Wrong Answer，直接默哀數分鐘。在我心中－她過了。

這題就是窮舉，將每一種組合拆成兩個去合併，而每一種組合(16 bits)如果能合併成一個 product item 則用一個 exist(4 bits) 和 mark(4 bits) 表示，

因此，對於每一個組合拆成 a, b，其中 a.exist == b.exist，同時變數差異只會有一個。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

#include <stdio.h>
#include <map>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
//int A[105] = {0, 2, 3, 5,7 ,8, 9, 10, 11, 13, 15}, n = 11;
//int A[105] = {0, 1, 2, 5, 6, 7, 8, 9, 10, 14}, n = 10;
int A[1024], n;
unsigned int result[1<<16] = {};
unsigned int mergeV[1<<16] = {};
struct cmp {
    bool operator()(const int a, const int b) const {
        for(int i = 0; i < 16; i++) {
            int ia, ib;
            ia = (a>>i)&1;
            ib = (b>>i)&1;
            if(ia != ib)
                return ia > ib;
        }
        return a < b;
    }
};
void solv() {
    map<unsigned int, int> combine;
    map<unsigned int, int> combineN;
    for(int i = 0; i < (1<<16); i++) {
        result[i] = mergeV[i] = 0;
    }
    for(int i = 0; i < n; i++) {
        unsigned int mark = 15; // exits
        unsigned int ssss = A[i];
        combine[(ssss<<16)|mark]++;
        combineN[(ssss<<16)|mark] = 1<<A[i];
        result[1<<A[i]] = (ssss<<16)|mark;
        mergeV[1<<A[i]] = 1;
    }
    for(int i = 1; i < (1<<16); i++) {
        if((i&(-i)) == i)
            continue;
        int ok = 0;
        unsigned int V;
        for(int j = 1; j < i; j++) {
            if((i&j) == j) {
                int a, b;
                a = j, b = i^j;
                if(mergeV[a] && mergeV[b]) {
                    unsigned int markA, markB;
                    unsigned int ssssA, ssssB;
                    markA = result[a]&((1<<16)-1);
                    markB = result[b]&((1<<16)-1);
                    ssssA = result[a]>>16;
                    ssssB = result[b]>>16;
                    if(markA == markB) {
                        unsigned int diff = ssssA ^ ssssB;
                        if((diff&(-diff)) == diff) {
                            unsigned int markC = (markA) ^ diff;
                            unsigned int ssssC = min(ssssA, ssssB);
                            ok = 1;
                            combine[result[a]]++;
                            combine[result[b]]++;
                            V = (ssssC<<16)|markC;
                            combineN[(ssssC<<16)|markC] = i;
                            result[i] = (ssssC<<16)|markC;
                            mergeV[i] = 1;
                        }
                    }
                }
            }
        }
        if(ok)
            combine[V]++;
    }
    set< int, cmp > output[20];
    for(map<unsigned int, int>::iterator it = combine.begin();
        it != combine.end(); it++) {
        if(it->second > 1)
            continue;
        /*printf("merge %d: count %d \n", it->first, it->second);*/
        
        unsigned int markA;
        unsigned int ssssA;
        markA = it->first&((1<<16)-1);
        ssssA = it->first>>16;
        int cc = combineN[it->first];
        /*for(int i = 0; i < 4; i++) {
            printf("%d ", (markA>>i)&1);
        }
        puts("  e ");
        for(int i = 0; i < 4; i++) {
            printf("%d ", (ssssA>>i)&1);
        }
        puts("");
        for(int i = 0; i < 16; i++) {
            if((cc>>i)&1)
                printf("%d ", i);
        }
        puts("");*/
        int osize = 0;
        for(int i = 0; i < 16; i++) {
            if((cc>>i)&1)
                osize++;
        }
        output[osize].insert(cc);
    }
    int f = 0;
    for(int k = 16; k >= 0; k--)
        for(set< int >::iterator it = output[k].begin();
            it != output[k].end(); it++) {
            int cc = (*it);
            if(f)	printf(",");
            f = 1;
            putchar('(');
            int f2 = 0;
            for(int i = 0; i < 16; i++) {
                if((cc>>i)&1) {
                    if(f2)	printf(", ");
                    f2 = 1;
                    printf("%d", i);
                }
            }
            putchar(')');
        }
    puts("");
}
int main() {
    char in[1024];
    while(gets(in)) {
        int error = 0;
        for(int i = 0; in[i]; i++) {
            if(in[i] == ')')
                in[i] = ' ';
            else if(in[i] == '(')
                in[i] = ' ';
            else if(in[i] == ',')
                in[i] = ' ';
            else if(in[i] <= '9' && in[i] >= '0')
                continue;
            else
                error = 1;
        }
        stringstream sin(in);
        int number;
        n = 0;
        while(sin >> number) {
            A[n++] = number;
        }
        if(n >= 1024)
            while(1);
        sort(A, A+n);
        int ok = 1;
        for(int i = 0; i < n; i++)
            if(A[i] < 0 || A[i] > 15)
                ok = 0;
        if(ok == 0 || error) {
            printf("Invalid input format");
            continue;
        }/*
        printf("%d\n", n);
        for(int i = 0; i < n; i++)
            printf("%d\n", A[i]);*/
        solv();
    }
    return 0;
}
/*
(0,2,5,8,10)
(0,2,3,5,7,8,9,10,11,13,15)
(0,1,2,5,6,7,8,9,10,14)
(0,1,2,4,5,6,8,9,12,13,14)
(0,1,2,5,6,7,8,9,10,16)
*/

Problem D Binary String

雖然詢問每個參數最大上限後，發現在 m = 100 的情況下，窮舉有點刺激，但是題目卻是要求輸出每一種組合，所以想必組合也不會太多，所以直接亂來吧！

至於以下代碼的正確性就交給神吧，反正都是亂做過的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int n, m, s_ones;
char s[105], ret[105];
int slen = 0;
void dfs(int idx, int ones, int has) {
    if(ones > m)
        return;
    if(has == 0 && idx - slen >= 0) {
        int ok = 1;
        for(int i = idx - slen, j = 0; j < slen; j++, i++) {
            ok &= ret[i] == s[j];
        }
        if(ok)
            has = 1;
    }
    if(idx == n) {
        if(ones != m || !has)
            return;
        ret[n] = '\0';
        puts(ret);
        return;
    }
    ret[idx] = '0';
    dfs(idx+1, ones, has);
    ret[idx] = '1';
    dfs(idx+1, ones+1, has);
}
int main() {
    while(scanf("%d %d %s", &n, &m, s) == 3) {
        s_ones = 0;
        for(int i = 0; s[i]; i++)
            s_ones += s[i] == '1';
        slen = strlen(s);
        dfs(0, 0, 0);
    }
    return 0;
}

Problem E Digits Count

這題在 UVa 見過，但是要在比賽中打出來，卻卡死兩個很久沒用腦的人，直到鎖版 (最後一個小時) 才湊出來。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int mpow(int n, int m) {
    int ret = 1;
    for(int i = 1; i <= m; i++)
        ret *= n;
    return ret;
}
void calc(int n, int cnt[]) {
    if(n <= 0)
        return;
    //printf("%d\n", n);
    char buf[105];
    sprintf(buf, "%d", n);
    int len = strlen(buf);
    int prev = 0, suffix;
    calc(mpow(10, len-1)-1, cnt);
    //for(int i = 0; i < 10; i++)
    //	cnt[i] = 0;
    int prev10 = 1;
    for(int i = 0; i < len; i++) {
        int d = buf[i] - '0';
        sscanf(buf+i+1, "%d", &suffix);
        
        if(i != len-1)
            cnt[d] += suffix + 1;
        else
            cnt[d]++;
        if(i != 0)
            cnt[d] += (prev - prev10/10) * mpow(10, len-i-1);
    //	pritnf("%d \n", );
    //	puts("");
        for(int j = i == 0; j < 10; j++) {
            if(j == d)	continue;
            if(j < d) {
                if(prev > 0) {
                    cnt[j] += (prev - prev10/10 + 1) * mpow(10, len-i-1);
                    //printf("%d %d\n", j, (prev - prev10/10 + 1) * mpow(10, len-i-2));
                } else {
                    cnt[j] += mpow(10, len-i-1);
                    //printf("%d %d\n", j, mpow(10, len-i-1));
                }
            } else {
                if(prev > 0 && prev - prev10/10 > 0) {
                    cnt[j] += (prev - prev10/10) * mpow(10, len-i-1);
                    //printf("%d %d\n", j, (prev - prev10/10 + 1) * mpow(10, len-i-2));
                }
            }
        }
        prev10 *= 10;
        prev = prev * 10 + d;
    }
    /*for(int i = 0; i < 10; i++)
		printf("%d ", cnt[i]);
	puts("");*/
}
void brute(int n) {
    int cnt[10] = {};
    char buf[105];
    for(int i = 1; i <= n; i++) {
        sprintf(buf, "%d", i);
        for(int j = 0; buf[j]; j++)
            cnt[buf[j]-'0']++;
    }
    for(int i = 0; i < 10; i++)
        printf("%d ", cnt[i]);
    puts("");
}
int main() {
    
    
    int l, r;
    /*while(scanf("%d", &l) == 1) {
		brute(l);
		int cnt[10] = {};
		calc(l, cnt);
		for(int i = 0; i < 10; i++)
			printf("%d ", cnt[i]);
		puts("");
	}*/
    while(scanf("%d %d", &l, &r) == 2) {
        if(l == 0 && r == 0)
            break;
        int A[10] = {}, B[10] = {};
        calc(l-1, A);
        calc(r, B);
        for(int i = 0; i < 10; i++)
            printf("%d%c", B[i] - A[i], i ==  9 ? '\n' : ' ');
        
    }
    return 0;
}

Problem F Math Problem

大數二分開 n 方，根據別組的討論，才發現數字其實還挺小的，用 double 型態做 log 運算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
public class A {
    public static void main(String args[]) throws Exception { // µ{¦¡¶i¤JÂI
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int n = cin.nextInt();
            String p = cin.next();
            if(n == 1) {
                System.out.println(p);
                continue;
            }
            BigInteger bigp = new BigInteger(p);
            BigInteger l = BigInteger.ZERO;
            BigInteger r = new BigInteger(p);
            BigInteger m = l, mid, mmid;
            while(l.compareTo(r) <= 0) {
                mid = l.add(r).shiftRight(1);
                mmid = mid.pow(n);
                if(mmid.compareTo(bigp) <= 0) {
                    l = mid.add(BigInteger.ONE);
                    m = mid;
                } else
                    r = mid.subtract(BigInteger.ONE);
            }
            System.out.println(m);
        }
    }
}

Problem G Better Method

聽說是曾經的萬年測試題，這次難得變成主角，肯定是想要每組至少都能帶一題回去。跟 ICPC 一樣的設計方式呢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <stdio.h>
#include <algorithm>
using namespace std;
int f(int n) {
    int ret = n;
    while(n >= 3) {
        ret += n/3;
        n = n%3 + n/3;
    }
    return ret;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        int v = max(f(n), f(n+1)-1);
        printf("%d\n", v);
    }
    return 0;
}

Problem H K-Anonymous Sequence

本次第二難的題目，但比賽時也是用假解過的，實質為單調對列，可以在 O(n) 時間內完成。至於假解的方式就不方便提供。

賽後

UVa 2000+ 才到這了，腦部硬體的差距就是如此地遙遠，即使捨去其他應用軟體，仍然趕不上嗎？

1
2
3
4
5
6
7
8
9
10

Rank	Name	Solved	Time	    A    	    B    	    C    	    D    	    E    	    F    	    G    	    H    	Total att/solv
1	team22	6	608	1/11	2/58	0/--	3/141	1/221	1/50	1/67	5/--	14/6
2	team2	6	844	2/32	7/--	14/--	1/108	1/244	1/19	1/11	8/270	35/6
3	team4	5	530	1/7	1/281	26/--	1/217	1/--	1/9	1/16	0/--	32/5
4	team17	5	698	2/13	1/105	1/--	4/296	0/--	1/167	1/37	3/--	13/5
5	team1	5	958	3/286	0/--	4/240	4/--	1/178	1/69	1/85	0/--	14/5
6	team12	4	177	1/11	0/--	3/--	0/--	1/138	1/17	1/11	0/--	7/4
7	team3	4	359	1/108	0/--	5/--	0/--	1/188	1/35	1/28	0/--	9/4
8	team23	4	776	1/12	7/278	0/--	0/--	0/--	1/57	5/229	0/--	14/4
9	team20	4	815	8/131	4/159	0/--	0/--	0/--	1/164	1/161	0/--	14/4

1
2
3
4
5
6
7

名次	學校學系	隊名
第一名	國立成功大學資訊工程學系	ItsNotCode
第二名	國立中央大學資訊工程學系	Morri$
第三名	國立清華大學資訊工程學系	ISeaTeL
佳作	國立成功大學資訊工程學系	Insert
佳作	國立臺北大學資訊工程學系	Forward Thinking
佳作	國立清華大學資訊工程學系	JustInTime