SRM 466 :: DIV2

Class Name	Method Name	Difficulty	Coding Time	Status	Points
LotteryTicket	buy	Level One	0:05:33.226	Passed System Test	240.90
LotteryCheating	minimalChange	Level Two	1:07:21.682	Opened	0.00
MatrixGame	getMinimal	Level Three	0:43:32.749	Compiled	0.00

Rate : 737 -> 812 (+75)
最大の敵は英語。
500pt問題は終始理解できなかった。

Level One

Nick likes to play the lottery. The cost of a single lottery ticket is price. Nick has exactly four banknotes with values b1, b2, b3 and b4 (some of the values may be equal). He wants to know if it's possible to buy a single lottery ticket without getting any change back. In other words, he wants to pay the exact price of a ticket using any subset of his banknotes. Return "POSSIBLE" if it is possible or "IMPOSSIBLE" if it is not (all quotes for clarity).
問題概要
b1〜b4の4つの値の組み合わせから、合計値がpriceと同じになるなら"POSSIBLE"
生成できないなら"IMPOSSIBLE"

class LotteryTicket
{
public:
  string buy(int price, int b1, int b2, int b3, int b4)
  {
    for(int i=1; i<(1<<4); i++){
      int sum = 0;
      if( i&1 )sum += b1;
      if( i&2 )sum += b2;
      if( i&4 )sum += b3;
      if( i&8 )sum += b4;
      if( sum==price )
        return "POSSIBLE";
    }
    return "IMPOSSIBLE";
  }
};

Level Two

Bob likes to play the lottery, but it's so hard to win without cheating. Each lottery ticket has an identifier which contains exactly n decimal digits. If an identifier contains only '0's, it is considered a winning ticket. Otherwise, the identifier is interpreted as a positive integer X written in decimal notation (possibly with leading zeros). If X has an odd number of positive integer divisors, it is a winning ticket, otherwise, it is not. A positive integer is a divisor of X if it divides X evenly.
Unfortunately, Bob only has enough money to buy one ticket, and he cannot see the identifier before buying a ticket. Therefore, he decides to cheat by buying a ticket and modifying its identifier to make it a winning ticket. In a single change operation, he can choose one digit, erase it, and print some other digit in the same position. No other types of modifications are allowed. He can perform any number of these change operations, but he wants to perform as few as possible to minimize the risk of getting caught.
You are given a String ID, the initial identifier on Bob's ticket. Return the minimal number of change operations necessary to transform the identifier into a winning one. If the initial identifier is already a winner, return 0.

class LotteryCheating
{
public:
  int minimalChange(string ID) {
    int ret = 11;
    long long stop=1;
    for(int i=0; i<ID.size(); i++)stop*=10;
    stop--;
    
    for(long long i=0; i<100000; i++){
      if( i*i > stop )break;
      string str(ID.size(),'0');
      for(long long k=i*i,j=0; k>0; k/=10,j++)
        str[ID.size()-j-1] = (k%10)+'0';
      
      int cnt = 0;
      for(int j=ID.size()-1; j>=0; j--){
        if( ID[j]!=str[j] )cnt++;
      }
      ret = min(ret,cnt);
      if( ret==0 )return 0;
    }
    return ret;
  }
};