#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
#define Y second
#define X first
typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
const ll INF=1e18;
const int inf=1e9;
const int N=2e5+505;
const int M=3e3+10;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
/*From Benq:
stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH*/
int n,k;
pair<int,int>vls[N];
void solve(){
cin>>n>>k;
for(int i=1; i<=k; ++i){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
vls[i]={x1,y1};
}vt<int>lst;
for(ll d=1; d*d<=n; ++d){
if(n%d==0){
lst.pb(d);
if(n/d!=d)lst.pb(n/d);
}
}ll ans=INF;
for(int del:lst){
ll heh=n/del;
heh*=heh;
ll cnt=heh-(heh/2),cnt2=heh/2;
cnt*=del*del;
cnt2*=del*del;
//cout<<del<<' '<<cnt<<' '<<cnt2<<endl;
for(int i=1; i<=k; ++i){
ll x,y;
x=vls[i].X;
y=vls[i].Y;
x=(x+(del-1))/del;
y=(y+(del-1))/del;
if(((x+y)%2)==0) {
cnt--;
cnt2++;
}else{
cnt++;
cnt2--;
}
}if(del==n){
ans=min(ans,cnt);
continue;
}
ans=min({ans,cnt,cnt2});
//cout<<del<<' '<<cnt<<' '<<cnt2<<endl;
}cout<<ans<<endl;
}
int main(){
//srand(time(0));
//freopen("hotel.in","r",stdin);
//freopen("hotel.out","w",stdout);
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tt=1,lolol=0;
// cin>>tt;
while(tt--) {
//cout<<"Case "<<++lolol<<": ";
solve();
}
}
Compilation message
chessboard.cpp: In function 'int main()':
chessboard.cpp:79:11: warning: unused variable 'lolol' [-Wunused-variable]
79 | int tt=1,lolol=0;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
2196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
10 ms |
480 KB |
Output is correct |
17 |
Correct |
22 ms |
876 KB |
Output is correct |
18 |
Correct |
29 ms |
1008 KB |
Output is correct |
19 |
Correct |
55 ms |
972 KB |
Output is correct |
20 |
Correct |
64 ms |
980 KB |
Output is correct |
21 |
Correct |
22 ms |
932 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
26 ms |
600 KB |
Output is correct |
24 |
Correct |
25 ms |
988 KB |
Output is correct |
25 |
Correct |
4 ms |
340 KB |
Output is correct |
26 |
Correct |
19 ms |
724 KB |
Output is correct |
27 |
Correct |
22 ms |
724 KB |
Output is correct |
28 |
Correct |
39 ms |
972 KB |
Output is correct |
29 |
Correct |
9 ms |
492 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
2196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Incorrect |
21 ms |
2196 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |