【AtCoder】ABC040 B. □□□□□
AtCoderの問題
B: □□□□□ - AtCoder Beginner Contest 040 | AtCoder
参考書
難しさ(初心者目線)
・考え方**
・実装*
・面白さ***
問題概要
・大きさが同じn枚の正方形の紙がある
・何枚かを使って長方形(正方形も含む)を作る
・その時|縦の長さ-横の長さ|+使わないカードの枚数を最小にしたい
・最小値を求めよ
n≦100,000
方針
作れる長方形と余りを全探索で求める.
縦の長さを1からsqrt(n)まで探索する.
nまで探索する必要はない.
例えばn=10の時、もも同じだから.
このようにすればくらいでも時間内に終わる.
素数かどうかの判定で使われる手法.
コード
#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; }