// Two-star problem // Problem 10176 Ocean Deep! - Make It Shallow!! /* This program is written by Prof. Chua-Huang Huang Department of Information Engineering and Computer Science Feng Chia University Taichung, Taiwan Disclaimer: The programming problem is downloaded from UVa Online Judge (https://uva.onlinejudge.org/). The program solution is provided for helping students to prepare Collegiate Programming Examination (CPE). The author does not guarantee the program is completely correct to pass UVa Online Judge platform or CPE examination platform. This program is not intended for a student to copy only. He/She should practice the programming problem himself/herself. Only use the program solution as a reference. The author is not responsible if the program causes any damage of your computer or personal properties. No commercial use of this program is allowed without the author's written permission. */ #include #include #include // The binary value of 131071 is 1 1111 1111 1111 1111 (17 ones). // Since the large number may have as many as 100 digits, it is better to represent // it as a string n. int main(void) { char n[102]; // Input binary number, up to 100 digits ending with '#'. int length; // Length of the input string. unsigned prefix; // Prefix bits of n. int bit_count; // Number of bits of prefix of n. int has_zero; // 0: prefix of n has no zeros; 1: prefix has at least one zeros. unsigned one; // Variable for search bit 1, only a single bit is 1. int i, j; // Loop variables. while (scanf("%s", &n)==1) { // Input a binary number if there is any. length = strlen(n); // Length of the binary number, including '#'. n[length-1] = '\0'; // Replace '#' by end of string. length--; // Substract length by 1. prefix = 0; // Reset the prefix of n to 0. bit_count = 0; // Initial bit count to 0. has_zero = 0; // No zero in the prefix yet. i = 0; // Initial i to 0. while (i0 && (prefix&one)==0) { // The bit under inspection is not 1. bit_count--; // One bit less in prefix. one = one >> 1; // Compare the next bit on the left. } j = 0; // Start from the least significant bit in the rest of prefix. one = 1; // Initial the check bit to 1. while (j