Algorithm
problem Link : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1117
Ocean deep I’m so afraid to show my feelings, I have sailed a million ceilings In my solitary room Ocean deep The lines above are from a very popular song of Cliff Richard. In this problem we will be dealing with a similar type of person. His name is Rampell-Stilt-Skin and another important thing is that he is a dead man. Someone has killed him a few days ago and you are the detective to solve the mystery. The problem with this guy is that he always tried to hide his information and feelings under the sea (I mean out of reach). He wrote a diary, which contained some statements and then a large binary number (May have as many as 10000 digits). If the number is divisible by a large prime number 131071 then the statement is true, otherwise the statement is false. In this problem you will be given large binary numbers as input and you will have to verify if that number is divisible by 131071 or not. Your algorithm needs to be very efficient. Input The input file contains several binary numbers. Each binary number starts in a new line but may expand in several lines. Each number is terminated by a ‘#’ symbol. No line contains more than 100 digits. Output For every binary number print ‘YES’ if the number is divisible by the given prime number, print ‘NO’ if the binary number is not divisible by the given prime number. Sample Input 0# 1010101# Sample Output YES NO
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
// modulo works for binary conversion if we only need partial result
int main()
{
char c;
long long res = 0;
while(scanf("%c",&c) != EOF) {
if(c == '1' || c == '0') {
res <<= 1;
if(c == '1') res += 1;
res %= 131071;
} else if (c == '#') {
cout << (res == 0 ? "YES" : "NO") << endl;
res = 0;
}
}
}Input
1010101#
Output
NO
Demonstration
UVA Online Judge solution - 10176 - Ocean Deep! - Make it shallo - UVA Online Judge solution in C,C++,Java!!