Programing/Algorithm

algospot - Divisibility

sosal 2014. 5. 6. 07:38
반응형

/*
 http://sosal.tistory.com/
 * made by so_Sal
 */


On the planet Zoop, numbers are represented in base 62, using the digits


0, 1, . . . , 9, A, B, . . . , Z, a, b, . . . , z, where


A (base 62) = 10 (base 10)

B (base 62) = 11 (base 10)

z (base 62) = 61 (base 10).

Given the digit representation of a number x in base 62, your goal is to determine if x is divisible by 61.


입력


The input test file will contain multiple cases. Each test case will be given by a single string containing only

the digits ‘0’ through ‘9’, the uppercase letters ‘A’ through ‘Z’, and the lowercase letters ’a’ through ’z’. All

strings will have a length of between 1 and 10000 characters, inclusive. The end-of-input is denoted by a

single line containing the word “end”, which should not be processed.


출력


For each test case, print “yes” if the number is divisible by 61, and “no” otherwise.


In the first example, 1v3 = 1 × 622 + 57 × 62 + 3 = 7381, which is divisible by 61.

In the second example, 2P6 = 2 × 622 + 25 × 62 + 6 = 9244, which is not divisible by 61.


예제 입력


1v3

2P6

IsThisDivisible

end

예제 출력


yes

no

no


62진수 숫자를 문제에서 정의해주었으며,

62진수가 들어왔을때 61로 나눈 나머지가 0일때 'yes'를, 그렇지 않으면 'no'를 출력하는 문제입니다.


62는 61로 나누었을 때, 나머지가 1이므로

모든 x에 대한 62^x는 나머지가 1입니다.


따라서 입력되는 62진수의 61 나머지 값은

각 자리수의 숫자를 합과 동일합니다.


convert 함수는 입력으로 주어진 string에 대해서 62진수로 바꿔주는 함수이며

메인에서는 단순히 end가 입력될때까지 입력 string을 받으며

그것의 모든 자리수의 합이 61의 배수인지 확인해주는 작업만이 존재합니다.



#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int convert(char a){
if(a >= 48 && a <= 57)
a-=48;
if( a >= 97 && a<= 122){
a-=61;
}//소문자
if( a >= 65 && a<= 90){
a-=55;
}//대문자

return a;
}

int main(){

while(1){

string input;
cin>>input;
if(input == "end")
break;
int sum = 0;

for(int i=0;i<input.size();i++){
sum+= convert(input[i]);
if(sum >= 61)
sum-=61;
}
if(sum == 0)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}


'Programing > Algorithm' 카테고리의 다른 글

poj 2140 Herd Sums  (0) 2014.05.06
algospot - HAMMINGCODE  (0) 2014.05.06
poj 2608 Soundex  (0) 2014.05.06
poj 2105 IP Adress  (0) 2014.04.30
acmicpc 수찾기: 1920  (0) 2014.04.30