|
2011年9月18日
#
應(yīng)刁哥多年前的約稿，外加結(jié)合編譯原理系列連載，整理一下上一篇文章，寫一個簡易的匯編教程…… 盡管謬誤，疏漏若干，但是本文的目的不在于培養(yǎng)學(xué)霸，而在于讓不會匯編的人簡單看看就能寫出個基本能用的匯編程序…… 在程序設(shè)計中，我們知道一項基本原理：語言越高級，一般來講容易編寫，形式簡潔，可移植性強(qiáng)，效率低…… 反過來，語言越低級，越難編寫，代碼越容易是又臭又長還看不懂，越難移植，但是效率會很高…… 匯編就是比較低級的語言了，由于其不太好移植，匯編版本又多種多樣 因此，本著活學(xué)活用，到時候不會就查手冊的原則，本文不會太著重強(qiáng)調(diào)語法，語法以intel語法為主…… Chapter1：一些基本知識 首先，CPU有若干寄存器，在32位CPU中，形如eax，ebx，ecx，edx……64位CPU則為rax，rbx…… 雖然寄存器這個名字很NB，其實它的本質(zhì)上就是int，為了向下兼容的需要，一些老的程序，也有可能能在新型的CPU上運(yùn)行（詳見DOS老游戲，有的能玩，有的不能玩） 以64位舉例： 64位寄存器rax，低32位是eax，eax低16位是ax，ax高8位叫ah，低8位叫al…… CPU只能直接對寄存器進(jìn)行運(yùn)算……因為電路結(jié)構(gòu)就是那樣的……因此，所有的操作，都需要經(jīng)過寄存器 譬如賦值：A = 1，實際上是 AX = 1; A = AX; 譬如 A = A + B，應(yīng)該是 AX = A; AX += B; A = AX; 這樣 我是比較不求甚解的，99%功能（運(yùn)算，判斷，指針）等，使用eax，ebx，ecx，edx都能搞定……于是咱們也就不說別的了…… Chapter2：匯編的基本語法： 匯編語言大概分為四個段，其中比較需要記住的就是代碼段和數(shù)據(jù)段…… 用類似高級語言的思路來講，數(shù)據(jù)段用于定義一些全局變量，代碼段用于寫程序…… 來看一個簡單的 Hello World（環(huán)境：yasm，64位） global main extern printf section .data ctrlout db '%s', 10, 0 hw db 'Hello World', 0 ; this is a comment section .text main: mov rax, 0 mov rdi, ctrlout mov rsi, hw call printf mov rax, 0 ret 其中，剛開始global main 表示程序入口，由于這里直接調(diào)用了Linux的函數(shù)printf，之后需要gcc編譯，所以叫做main，如果只使用中斷輸出的話，可以搞成_start 之后extern意義和C++類似，表示這個函數(shù)在別處，叫編譯器以為他有就行…… section .data 表示數(shù)據(jù)段，后面是一些定義，以及初始化 注意這里定義的東西類型都像是指針一樣，ctrlout，hw 實際上是地址…… 初始化必須搞的干凈一點，有一次調(diào)了半天不對，就是因為一個64位int，前4位沒有初始化成0…… 之后 section .text 表示代碼段，這里調(diào)用C語言函數(shù)，網(wǎng)上說，64位匯編中，參數(shù)傳遞方式有了修改，大概是有4~5個寄存器專門保存參數(shù)，如果參數(shù)過多，再放入棧，rax存放棧中的參數(shù)個數(shù)……我們想printf("%s","Hello World")，就要調(diào)用兩個參數(shù)，于是，我們把第一個參數(shù)，字符串ctrlout的指針mov進(jìn)rdi，hw mov進(jìn)rsi，rax賦值為0 ，然后，調(diào)用…… （實現(xiàn)時，需要手冊自行查閱一下本機(jī)怎么搞） 函數(shù)的返回值在rax，于是return 0 然后 yasm -f elf64 XXX.asm gcc -o XXX XXX.o ./XXX 一個嶄新的hello world 出現(xiàn)了…… Chapter3：匯編的一些簡單指令： 由于這是速成教程，選取一部分指令……要記住，CPU只能直接對寄存器進(jìn)行運(yùn)算…… mov：相當(dāng)于賦值， mov eax，b 相當(dāng)于eax = b； 注意：mov 后面的兩個東西至少要有一個是寄存器…… 同時，和高級語言一樣，不能搞什么 mov 10，eax…… add：add eax，b 相當(dāng)于eax+=b sub：基本同上…… mul || imul：前面是無符號的乘，后面是有符號的乘，默認(rèn)被乘數(shù)在AX，于是指令形如：mul BX，如果有溢出，則高位溢出到DX，記得備份DX的東西…… div || idiv：前面是無符號整除，后面是有符號整除，默認(rèn)被除數(shù)是DX（高16位）和AX（低16位），因此，除法之前記得把DX清零，否則數(shù)會不對…… 之后商在AX，余數(shù)在DX 指令形如：div BX push/pop：每個程序都有棧，或者是在程序中定義堆棧段，或者使用默認(rèn)棧 push eax，表示把eax放進(jìn)棧里，pop ebx，表示取出棧頂，放在ebx中…… push和pop異常重要，一個重要作用就是保護(hù)寄存器，譬如DX中有內(nèi)容，但是現(xiàn)在要做乘法，沒準(zhǔn)會破壞DX（見上），于是，先PUSH DX，然后，乘法，然后POP DX，又好比你要調(diào)用一個函數(shù)，但是寄存器里有有用的信息，不保證這個函數(shù)不會破壞，于是，把所有寄存器先push進(jìn)去，運(yùn)行函數(shù)，然后再pop出來，這是常用技巧…… 另外也可以用來給函數(shù)傳參數(shù)，傳時倒序壓入，用時順序取出，棧，先進(jìn)后出，你們懂的…… Chapter4：if以及循環(huán) 首先我們要記得，被Dijkstra老爺子罵的一文不值的goto…… jmp語法和C++里的goto基本一樣 start： XXX jmp start 然后，匯編沒有if then，但是有條件goto 有個語句叫做cmp cmp X，Y （老原則，這兩個得有一個寄存器……如果和常數(shù)比較，常數(shù)必須在后面） 傳說中具體實現(xiàn)是減法…… 這個的效果是可能改變?nèi)舾蓸?biāo)識位的值……譬如：0標(biāo)識，進(jìn)位標(biāo)識，溢出標(biāo)識……等等…… 然后，有若干指令 jl XX（l==less） 相當(dāng)于 if (x<y) goto XX; 下同 jg XX（g==greater） jle XX（ne==less or equal） jge XX（ge==greter or equal） jnle XX（n==no->nle==g） jnge XX（n==no->nge==l） 有了if then，各種運(yùn)算，我們就能做出來&&,||的邏輯 有了if then，我們也能做出循環(huán)…… 很多的功能就有了…… Chapter5：實戰(zhàn) 看看 int main() { int a,b,c; input(a); input(b); if (a < b) { c = a; } else { c = b; } print(c); } 用匯編翻譯出來啥樣： global main extern printf extern scanf section .data ctrlout db '%lld', 10, 0 ctrlin db '%lld', 0 _a db 0,0,0,0,0,0,0,0 _b db 0,0,0,0,0,0,0,0 _c db 0,0,0,0,0,0,0,0 section .text main: mov rax, 0 mov rdi, ctrlin mov rsi, _a call scanf mov rax, 0 mov rdi, ctrlin mov rsi, _b call scanf MOV rax, [_a] CMP rax, [_b] jl @0 jmp @2 @0: MOV rax, [_a] MOV [_c], rax jmp @1 @2: MOV rax, [_b] MOV [_c], rax @1: mov rax, 0 mov rdi, ctrlout mov rsi, [_c] call printf mov rax, 0 ret Chapter6：其它 由于現(xiàn)實生活中，我需要寫匯編時候?qū)嵲谑巧伲虼艘矝]啥經(jīng)驗……盡管借助手冊，可以對付著寫一點匯編代碼，但是那是不科學(xué)的……對我來講，匯編告訴我們的一些底層的東西更有價值，可以在高級語言中有所體現(xiàn)：譬如一些表達(dá)式的寫法，可以考慮寫的更科學(xué)一些，譬如 c = a / b, q = a % b，記得寫成 c = a / b; q = a - c * b，譬如靈活使用switch，等等……
最近，做OS大作業(yè)，編譯大作業(yè)，和進(jìn)行實驗室工作，強(qiáng)烈認(rèn)識到了自己對C語言的了解不多……
于是今天老圖借了本書，學(xué)習(xí)一下……
來看一下我最頭疼的define……
define的作用：
一是直接定義一個東西……類似標(biāo)記
譬如：
1 #ifndef test
2 #define test
3 /*
4 balabalabala .
5 */
6 #endif
劉JX老師在大一C＋＋課上教育我們，寫頭文件一定要加上這么個東西……為什么呢……
再提一下include的事情…… #include<XXXX>，實際上是直接把XXXX整個文件COPY了進(jìn)來……
如果出現(xiàn)這樣的情況：
1 #include <set>
2 #include <map>
我們知道，Cpp的 map 實際上是用 set 做的，map的頭文件里肯定有一個 #include <set>，那么，相當(dāng)于set這個文件在這段程序里面出現(xiàn)了兩次……
如果沒有ifndef這套的話，相當(dāng)于將set中的代碼重復(fù)貼了兩次，就粗大事了……
代碼第一段ifndef test 代表：如果沒有define test，則執(zhí)行下面的那段，先 define test，然后balabala，最后endif，下次再看到這段代碼的時候，ifndef test ，此時會發(fā)現(xiàn)test已經(jīng)define過了，直接endif，中間balabala的代碼不會重復(fù)兩次……
二是直接定義一些……怎么說呢，類似替換規(guī)則的東西……
譬如：直接定義常量：
1 #define MAXN 10000
這個實際上就是直接在程序編譯之前，將里面的MAXN都替換成10000
預(yù)先定義一些常量，好處大家都懂：避免程序內(nèi)部太多的“magic number”，增強(qiáng)可讀性，也便于修改……這里相當(dāng)于直接替換，貌似C的數(shù)組，定義的時候不能用int做下標(biāo)，const int也不行，只能通過這個方法，用立即數(shù)……
譬如：給一些東西改個名字：
1 #include <stdio.h>
2 #define Q scanf
3
4 int main() {
5 int a;
6 Q("%d",&a);
7 printf("%d\n",a);
8 return 0;
9 }
這里有一些玄機(jī)： 1：#似乎是因為沒有轉(zhuǎn)義？所以不能胡用…… 譬如：#define USEMATH #include <math.h> 是不能達(dá)到預(yù)期效果的…… 2：如果這一行太長，可以用\表示和下一行連起來…… 貌似這個'\'也沒轉(zhuǎn)義， #define BACKSLASH \ 也是不行的…… 譬如：可以定義一些簡單的函數(shù)： #define max(a,b) ((a) > (b) ? (a) : (b)) 某種意義上這比template NB... 這樣，int c ＝ max(a,b); 就自動替換成 int c ＝((a) > (b) ? (a) : (b)); 了 此處有一個技巧：有的時候，咱們需要用大括號來實現(xiàn)這個"函數(shù)"，但是，由define直接替換知道，這個替換出來，相當(dāng)于{/*balabala*/};這樣，語法是錯的…… 于是怎么辦呢……咱們可以用 do {/*balabala*/} while(0) 這樣的形式，繞開這個問題…… 在上次OS大作業(yè)上咱們都見到了…… 此處還有兩個玄機(jī)：一是千萬記得要加括號……為什么呢…… 譬如： #define mul(a,b) a * b 看著挺好，mul(1,2 + 3)就出事了…… 直接替換出來，是 1 * 2 + 3，就錯了…… 正確方法是：#define mul(a,b) ((a) * (b))，萬無一失…… 另一個玄機(jī)是避免++,--之類的，譬如 #define sqr(a) ((a) * (a)) sqr(a++)，如果sqr是真的函數(shù)的話，計算出沒有問題……但是define會忠實的給你替換成((a++) * (a++))……怎么加的不重要，結(jié)果就不是你想的了…… 最后有兩個用法，一個是#，#會將你作為“函數(shù)”的“參數(shù)”傳入的東西轉(zhuǎn)化為字符串；一個是...，作用一看便知： 1 #include <stdio.h> 2 #define max(a,b) ((a) > (b) ? (a) : (b)) 3 #define PRINT( ) printf(__VA_ARGS__) 4 #define debug(x) do { \ 5 PRINT(#x); \ 6 PRINT(" = %d\n",(x)); \ 7 } while (0) 8 9 int main() { 10 int a,b; 11 scanf("%d%d",&a,&b); 12 debug(a); 13 debug(b); 14 debug(a + b); 15 debug(max(a,b)); 16 return 0; 17 }
題意很簡單……雙方給N個人（N<=6）打三國殺1V1，你知道對手每個人能克制你哪些人，我們認(rèn)為兩個人對打，他能克你則他勝利，否則你勝利；某人的N個人死光就輸了……你需要組織陣容按照順序?qū)箤κ?#8230;…求有沒有一個順序，無論對手順序如何，你都能勝…… N！枚舉自己的順序，然后N！枚舉對方的順序，O（N）驗證即可…… 注意字典序最小…… 1 #include <cstdio>
2 #include <cstring>
3 #include <string>
4 #include <map>
5 #include <algorithm>
6 #include <iostream>
7
8 using namespace std;
9
10 map<string,int> mp;
11 int n;
12 int res[10];
13 int my[10];
14 char buf[50];
15 char name[10][50];
16 string ans;
17
18 void check() {
19 int enemy[] = {0,1,2,3,4,5,6,7,8,9};
20 do {
21 int i = 0;
22 int j = 0;
23 while (i < n && j < n) {
24 if ((1 << my[i]) & res[enemy[j]]) i ++; else j++;
25 }
26 if (i == n) return;
27 } while (next_permutation(enemy,enemy + n));
28 string tmp;
29 for (int i = 0; i < n; i++) {
30 if (i) tmp += " ";
31 tmp += name[my[i]];
32 }
33 if (ans == "" || ans > tmp) ans = tmp;
34 }
35
36 int main() {
37 int nn; scanf("%d",&nn);
38 for (int ii = 1; ii <= nn; ii++) {
39 mp.clear();
40 memset(res,0,sizeof(res));
41 scanf("%d",&n);
42 for (int i = 0; i < n; i++) {
43 scanf("%s",name[i]);
44 mp[string(name[i])] = i;
45 }
46 for (int i = 0; i < n; i++) {
47 int m; scanf("%d",&m);
48 for (int j = 0; j < m; j++) {
49 scanf("%s",buf);
50 int tmp = mp[string(buf)];
51 res[i] |= 1 << tmp;
52 }
53 }
54 for (int i = 0; i < n; i++) {
55 my[i] = i;
56 }
57 ans = "";
58 do {
59 check();
60 } while (next_permutation(my,my + n));
61 printf("Case %d: ",ii);
62 if (ans == "") {
63 puts("No");
64 } else {
65 puts("Yes");
66 for (int i = 0; i < ans.length(); i++) putchar(ans[i]);
67 putchar(10);
68 }
69 }
70 return 0;
71 }
這題比賽時候過得很糾結(jié)……最后還是學(xué)長過的……比賽時候腦子可能不夠清楚，一直WA……
首先，這個題要分成兩個部分解決：
第一部分：從n個東西里面取出r個，每個間距至少為 k （1～K不行，1～K ＋ 1行）
第二部分：將這r個東西分成至多m組，可以有空組
第二部分貌似好久之前搞OI的時候干過……貼過來：
N球放在M個盒子里，求共有多少種放法
但是有3個不同的條件 ：N個球是否相同，M個盒子是否相同，是否允許有盒子空著
|
球和球
|
盒和盒
|
空盒
|
情況數(shù)
|
|
有區(qū)別
|
有區(qū)別
|
有空盒
|
mn
|
|
有區(qū)別
|
有區(qū)別
|
無空盒
|
M！s（n,m）
|
|
有區(qū)別
|
無區(qū)別
|
有空盒
|
S(n,1)+s(n,2)+…+s(n,m),n>=m
S(n,1)+s(n,2)+…+s(n,n),n<=m
|
|
有區(qū)別
|
無區(qū)別
|
無空盒
|
S(n,m)
|
|
無區(qū)別
|
有區(qū)別
|
有空盒
|
C(n+m-1,n)
|
|
無區(qū)別
|
有區(qū)別
|
無空盒
|
C(n-1,m-1)
|
|
無區(qū)別
|
無區(qū)別
|
有空盒
|
F(m,n)
|
|
無區(qū)別
|
無區(qū)別
|
無空盒
|
F(m,n-m)
|
|
然后，其中的F(m,n)貌似是當(dāng)時寫過的一個DP，S(M,N)是第二類stirling數(shù)…… 遞推公式： 1 int S(int n,int m) {
2 if (n == m || m == 1) return 1;
3 return m * S(n - 1, m) + S(n - 1, m - 1);
4 } 第一部分：可以看作這么一個生成函數(shù)的相關(guān)問題：由于每個東西之間都隔了>=K－1的一段距離，因此一個可行解可以看作，長度為K，K + 1，K + 2的棍子r － 1個（我們認(rèn)為每個棍子的頭是我們?nèi)〉狞c），拼接成長度為Len的一個大段，之后再堵上一個，就是一個Len ＋１的可行解…… 而r - 1根棍子，拼成長度為Len 的可行解數(shù)目，就是(X^K + X^(K + 1) + X^(K + 2) + .....) ^ (r - 1)，這個多項式，展開之后，X^Len項前面的系數(shù)…… 不過……由于數(shù)據(jù)范圍，直接搞是不成的…… 于是提取，變形：X^(K * (r - 1)) * (1 + X + X^2 + X ^3 +....)^(r - 1) 然后再變形：X^(K * (r - 1)) * (1/(1 - x))^(r - 1)…… 然后參照Matrix67大神的日志，展開后面那項：
1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+... 我們知道，要求長度為len的可行數(shù)目，也就是要X^Len項前面的系數(shù)，然后，由于前面提取出來了一個K * (r - 1)，也就是去后面找len - K * (r - 1) 項的系數(shù)…… 也就是說，令pow = len - K * (r - 1)，答案就是C(r - 1 + pow - 1, pow)…… 不過這還沒完，因為咱們要拼成的長度是len，而總的長度是N，需要乘上這個長度len的開頭位置的可能數(shù)…… 另外還需要特殊處理：咱們在處理的時候，是先用r - 1個拼接成長度為Len的一個大段，再堵上最后一個……當(dāng)r == 1需要特判…… 代碼： 1 #include <cstdio>
2 #include <cstring>
3
4 typedef long long Long;
5 const Long MOD = 1000000007;
6
7 Long F[1010][1010];
8 Long C[2010][2010];
9 Long S(int n,int m) {
10 if (n == m || m == 1) return 1LL;
11 if (F[n][m] > 0) return F[n][m];
12 return F[n][m] = (m * S(n - 1, m) % MOD + S(n - 1, m - 1)) % MOD;
13 }
14 void init() {
15 for (int i = 0; i <= 2000; i++) {
16 for (int j = 0; j <= i; j++) {
17 if (j == 0) C[i][j] = 1;
18 else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
19 }
20 }
21 }
22 int n,r,k,m;
23
24 int main() {
25 memset(F,0xff,sizeof(F));
26 init();
27 while (scanf("%d%d%d%d",&n,&r,&k,&m) > 0) {
28 if (r == 1) {printf("%d\n",n); continue;}
29 Long ans = 0;
30 for (int i = 1; i <= m && i <= r; i++) {
31 ans = (ans + S(r,i)) % MOD;
32 }
33 Long tmp = 0;
34 for (int len = k * (r - 1); len < n; len++) {
35 int left = n - len;
36 int pow = len - k * (r - 1);
37 // r > 1 !!
38 tmp = (tmp + left * C[r - 1 + pow - 1][pow]) % MOD;
39 }
40 ans = ans * tmp % MOD;
41 printf("%lld\n",ans);
42 }
43 return 0;
44 }
思路是維護(hù)每個字母開頭，長度為3的串是不是wbw…… 這樣相當(dāng)于將長度為N的字符串變成長度為N－2的序列，然后一系列修改就是將序列中1變0，0變1，查詢就是求一段的和 BIT，大家都懂的…… 1 #include <cstdio>
2 #include <cstring>
3
4 int n,m;
5 char str[50010];
6 int arr[50010];
7
8 inline int lowbit(int x) {return x & -x;}
9
10 void update(int x,int delta) {
11 for (int i = x; i <= n; i += lowbit(i)) {
12 arr[i] += delta;
13 }
14 }
15
16 int sum(int x) {
17 int ret = 0;
18 while (x) {ret += arr[x]; x -= lowbit(x);}
19 return ret;
20 }
21
22 int sum(int l,int r) {
23 if (l > r) return 0;
24 if (l == 0) return sum(r);
25 return sum(r) - sum(l - 1);
26 }
27
28 int main() {
29 int nn; scanf("%d",&nn);
30 for (int ii = 1; ii <= nn; ii++) {
31 scanf("%d%d",&n,&m);
32 memset(str,0,sizeof(str));
33 memset(arr,0,sizeof(arr));
34 scanf("%s",str + 1);
35 for (int i = 1; i + 2 <= n; i++) {
36 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
37 update(i,1);
38 }
39 }
40 printf("Case %d:\n",ii);
41 while (m--) {
42 int ctrl; scanf("%d",&ctrl);
43 if (ctrl == 0) {
44 int l,r; scanf("%d%d",&l,&r); printf("%d\n",sum(l + 1,r - 1));
45 } else {
46 int pos; char buf[10]; scanf("%d",&pos); scanf("%s",buf); pos ++;
47 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
48 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
49 update(i,-1);
50 }
51 }
52 str[pos] = buf[0];
53 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
54 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
55 update(i,1);
56 }
57 }
58 }
59 }
60 }
61 return 0;
62 }
數(shù)學(xué)苦手……一通推，無法可行…… 于是只能想沒有辦法的辦法：打表…… 1 #include <cstdio>
2 #include <algorithm>
3
4 using namespace std;
5 typedef long long Long;
6
7 int arr[20];
8 Long ans = 0;
9 int n;
10
11 void dfs(int now,int sum) {
12 if (sum < 0) return;
13 if (now == n) {ans ++; return;}
14 dfs (now + 1, sum + (1 << arr[now] ));
15 dfs (now + 1, sum - (1 << arr[now] ));
16 }
17
18 int main() {
19 for (n = 1; n <= 10; n++) {
20 for (int i = 0; i < n; i++) {
21 arr[i] = i;
22 }
23 Long cnt = 0;
24 ans = 0;
25 do {
26 dfs(0,0);
27 cnt ++;
28 } while (next_permutation(arr,arr + n));
29 printf("%lld ",ans);
30 printf("%lld\n",cnt << n);
31 }
32 return 0;
33 } 輸出： 1 2 3 8 15 48 105 384 945 3840 10395 46080 135135 645120 2027025 10321920 34459425 185794560 654729075 3715891200 然后大家都懂了…… 1 import java.util.*;
2 import java.io.*;
3 import java.math.BigInteger;
4
5
6 class Main {
7
8 BigInteger[] ans1 = new BigInteger [501];
9 BigInteger[] ans2 = new BigInteger [501];
10 final BigInteger TWO = BigInteger.valueOf(2);
11
12 void solve() throws Exception {
13 MyReader in = new MyReader();
14 int nn = in.nextInt();
15 ans1[1] = BigInteger.ONE;
16 ans2[1] = TWO;
17 for (int i = 2; i <= 500; i++) {
18 ans1[i] = ans1[i - 1].multiply(BigInteger.valueOf(i + i - 1));
19 ans2[i] = ans2[i - 1].multiply(BigInteger.valueOf(i)).multiply(TWO);
20 BigInteger gcd = ans1[i].gcd(ans2[i]);
21 ans1[i] = ans1[i].divide(gcd);
22 ans2[i] = ans2[i].divide(gcd);
23 }
24 PrintWriter out = new PrintWriter(System.out);
25 while (nn-- > 0) {
26 int n = in.nextInt();
27 out.print(ans1[n]);
28 out.print("/");
29 out.println(ans2[n]);
30 }
31 out.flush();
32 }
33
34 public static void main(String args[]) throws Exception {
35 new Main().solve();
36 }
37
38 void debug(Objectx) {
39 System.out.println(Arrays.deepToString(x));
40 }
41 }
42
43 class MyReader {
44 BufferedReader br = new BufferedReader (
45 new InputStreamReader (System.in));
46 StringTokenizer in;
47 String next() throws Exception {
48 if (in == null || !in.hasMoreTokens()) {
49 in = new StringTokenizer(br.readLine());
50 }
51 return in.nextToken();
52 }
53 int nextInt() throws Exception {
54 return Integer.parseInt(next());
55 }
56 }
|