poj_2190_ISBN.cpp

Problem Links:

poj2190,

Problem:

ISBN

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11815		Accepted: 4078

Description

Farmer John's cows enjoy reading books, and FJ has discovered that his cows produce more milk when they read books of a somewhat intellectual nature. He decides to update the barn library to replace all of the cheap romance novels with textbooks on algorithms and mathematics. Unfortunately, a shipment of these new books has fallen in the mud and their ISBN numbers are now hard to read.

An ISBN (International Standard Book Number) is a ten digit code that uniquely identifies a book. The first nine digits represent the book and the last digit is used to make sure the ISBN is correct. To verify that an ISBN number is correct, you calculate a sum that is 10 times the first digit plus 9 times the second digit plus 8 times the third digit ... all the way until you add 1 times the last digit. If the final number leaves no remainder when divided by 11, the code is a valid ISBN.

For example 0201103311 is a valid ISBN, since
10*0 + 9*2 + 8*0 + 7*1 + 6*1 + 5*0 + 4*3 + 3*3 + 2*1 + 1*1 = 55.

Each of the first nine digits can take a value between 0 and 9. Sometimes it is necessary to make the last digit equal to ten; this is done by writing the last digit as X. For example, 156881111X is a valid ISBN number.

Your task is to fill in the missing digit from a given ISBN number where the missing digit is represented as '?'.

Input

* Line 1: A single line with a ten digit ISBN number that contains '?' in a single position

Output

* Line 1: The missing digit (0..9 or X). Output -1 if there is no acceptable digit for the position marked '?' that gives a valid ISBN.

Sample Input

15688?111X

Sample Output

1

Source

USACO 2003 Fall Orange

Solution:

Basically, it's a very easy simulation.
PS:
1. if the unknown number is 10, you need to use 'X' to represent it.
2. the 'X' can only exist as the last digit.

Source Code:

//Wed Apr 14 13:57:18 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    string str;
    while (cin >> str)
    {
        int idx;
        int sum = 0;
        for (int i = 0; i < (int) str.size(); i++)
        {
            if (isdigit(str[i]))
                sum += (10 - i) * (str[i] - '0');
            else if (str[i] == 'X')
                sum += (10 - i) * 10;
            else
            {
                idx = i;
            }
        }
        sum %= 11;
        bool flag = false;
        for (int i = 0; i < 10; i++)
        {
            if ((sum + (10 - idx) * i) % 11 == 0)
            {
                cout << i << endl;
                flag = true;
                break;
            }
        }
        if((sum + (10 - idx) * 10) % 11 == 0 && idx == 9)
        {
            cout << "X" << endl;
            flag = true;
        }
        if(flag == false)
            cout << -1 << endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}