読者です 読者をやめる 読者になる 読者になる

プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【AtCoder】ABC040 B. □□□□□

AtCoderの問題

B: □□□□□ - AtCoder Beginner Contest 040 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方**

・実装*

・面白さ***

問題概要

・大きさが同じn枚の正方形の紙がある
・何枚かを使って長方形(正方形も含む)を作る
・その時|縦の長さ-横の長さ|+使わないカードの枚数を最小にしたい
・最小値を求めよ

n≦100,000

方針

作れる長方形と余りを全探索で求める.
縦の長さを1からsqrt(n)まで探索する.
nまで探索する必要はない.
例えばn=10の時、 {1 \times 10}{10 \times 1}も同じだから.
このようにすれば {n \leq 10^{12}}くらいでも時間内に終わる.
素数かどうかの判定で使われる手法.

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    int n;
    cin>>n;
    int min_amari = 999999999;
    //全探索
    for(int i=1; i<=sqrt(n); ++i){
        int w, h, amari;
        w = i;
        h = n / i;
        amari = n % i;
        min_amari=min(min_amari,abs(w-h)+amari);
    }
    cout<<min_amari<<endl;
}