Google Code Jam Round 1C 2015 Problem A. Brattleship

Problem
You're about to play a simplified "battleship"game with your little brother. The board for this game is a rectangular grid with R rows and C columns. At the start of the game, you will close your eyes, and you will keep them closed until the end of the game. Your little brother will take a single rectangular 1 x W ship and place it horizontally somewhere on the board. The ship must always fit entirely on the board, with each cell of the ship occupying exactly one of the grid's cells, and it can never be rotated.In each turn of the game, you name a cell on the board, and your little brother tells you whether that is a hit (one of the cells occupied by the ship) or a miss. (Your little brother doesn't say which part of the ship was hit -- just that the cell you named has a part of the ship in it.) You have perfect memory, and can keep track of all the information he has given you. Once you have named all of the cells occupied by the ship, the game is over (the ship is sunk), and your score is the number of turns taken. Your goal is to minimize your score.Although the ship is not supposed to be moved once it is placed, you know that your little brother, who is a brat, plans to cheat by changing the location of the ship whenever he wants, as long as the ship remains horizontal and completely on the board, and the new location is consistent with all the information he has given so far. For example, for a 1x4 board and 1x2 ship, your little brother could initially place the ship such that it overlaps the leftmost two columns. If your first guess was row 1, column 2, he could choose to secretly move the ship to the rightmost two columns, and tell you that (1, 2) was a miss. If your next guess after that was (1, 3), though, then he could not say that was also a miss and move the ship back to its original location, since that would be inconsistent with what he said about (1, 2) earlier.Not only do you know that your little brother will cheat, he knows that you know. If you both play optimally (you to minimize your score, him to maximize it), what is the lowest score that you can guarantee you will achieve, regardless of what your little brother does?
 

A：



  r*c     ，     1*w         ，         ，
     x y，          x y，     YES，
          ，        ，   no，              ，
          ，           1*w        。
          ，    ，          。

문제 해결 방법:
한 줄만 있다고 가정하면,
c% w==0일 때 줄마다 w의 한 단락에 따라 한 번, 한 단락의 중간에서 선택하면 최악의 경우 c/w의 한 단락에서 마지막 단락에 잠길 수 있다.
　　c % w != 0시, c/w번에 하나를 맞히면 양쪽 중 어느 방향으로 판단할 수 있습니다. 여기서 한 번 더 틀리게 할 수 있습니다.
여러 줄의 경우 사실 다른 r-1줄에 배가 없는 경우입니다. 줄마다 c/w회가 필요합니다.
 

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

#include <stack>

#include <string>

#include <map>

#include <set>

#include <list>

#include <queue>

#include <vector>

#include <algorithm>

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

#define pi acos(-1.0)



using namespace std;



typedef long long           ll      ;

typedef unsigned long long  ull     ;

typedef unsigned int        uint    ;

typedef unsigned char       uchar   ;



template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}

template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}



const double eps = 1e-7      ;

const int N = 210            ;

const int M = 1100011*2      ;

const ll P = 10000000097ll   ;

const int MAXN = 10900000    ;



int main() {

    ofstream fout ("A-large-practice.out");

    ifstream fin ("A-large-practice.in");

    int i, j, k, T;

    int R, C, W;



    fin >> T;

    while (T--) {

        fin >> R >> C >> W;

        int Ret = R * (C / W);

        if (C % W == 0) {

            Ret += W - 1;

        } else {

            Ret += W;

        }

        static int numCase = 0;

        fout << "Case #" << ++numCase << ": " << Ret << endl;

    }



    return 0;

}