ichirin2501's diary


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)

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).

class LotteryTicket
  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
  int minimalChange(string ID) {
    int ret = 11;
    long long stop=1;
    for(int i=0; i<ID.size(); i++)stop*=10;
    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;