簽到難題（signed‑inproblem）
問題敘述
Are you signed in?
No, I’m unsigned int!
剛抵達高中生邀請賽的參賽者unsignedint 很疑惑，明明自己的名牌上就寫著大大的
unsigned int，為何工作人員都問自己是不是 signed int?
以下我們將故事主角unsigend int 稱為 ui，且之後出現的所有”unsigned int” 都是指
unsigned int 這個變數型態而不是 ui。
ui 實際表示的unsigned int 的值稱為 a，現在給你a的初始值和b這兩正整數，你有
q 次操作，每次可以選擇+-*/中其中一個為運算子opt，並使a變為signed(a)optb。
由於ui 討厭被認錯，他希望你找出在最好的操作順序下，最多可以有幾次操作，在
該次操作結束後a的結果能被認出是unsignedint 而不是signed int?
對於一個unsigned int x 來說，可以被認出是 unsigned int 的條件是：在相同 32 bit
下，signed(x) 跟 unsigned(x) 表示的值不同。
例如，11111111111111111111111111111111（32 個1）在unsignedint對應的是4,294,967,295，
而在signed int 對應的則是-1，所以認的出來，而 00000000000000000000000000000000
（32 個0）在signed 和 unsigned int 對應的都是 0，所以認不出來。
輸入說明
第一行有兩正整數a和b
第二行有一正整數q
輸出說明
輸出一整數，代表在最好的操作順序下，最多有幾次操作後的a能被認出？
測資限制
• 1≤a,b≤231−1
1
•1≤q≤106
範例測資
範例輸入1
1010
2
範例輸出1
1
範例輸入2
335544322
100
範例輸出2
95
對於範例一來講，最好的操作順序為
1.a=signed(a)-b，此時a=0，signed(a)=0
2.a=signed(a)-b，此時a=4294967286，signed(a)=-10
由於只有在第二次操作後，a!=signed(a)，所以答案就是1
2 |
