akhauriyash/Code-Regression huggingface dataset:
// Problem : B - 1%
// Contest : AtCoder - AtCoder Beginner Contest 165
// URL : https://atcoder.jp/contests/abc165/tasks/abc165_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}()); 
//int rnd(int x) { return mrand() % x;}
const ll mod=1000000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int maxn = 2e5 + 10; 

int main()
{
	fastIO;
	ll x; cin >> x;
	ll t = 100;
	for(int i = 1; ; ++i) {
		t *= 1.01;
		if(t >= x) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 3656
let () =
  Scanf.scanf "%s %s\n" @@ fun a b ->
  let num = int_of_string (a ^ b) in
  let ans = ref false in
  for n = 1 to 400 do
    if n * n = num then ans := true
  done;
  Printf.printf "%s\n" (if !ans then "Yes" else "No")

Measured memory_bytes: 3708
#include<bits/stdc++.h>
#define ll long long
#define ss second
#define ff first
#define pb push_back
using namespace std;

const int N = 1e6 + 6;

int n,m,k;
int x1,x2,Y1,y2;

int X[4] = {0,0,1,-1};
int Y[4] = {1,-1,0,0};

int main(){

        cin >> n >> m >> k;
        cin >> x1 >> Y1 >> x2 >> y2;

        char A[n+1][m+1]; int D[n+1][m+1],P[n+1][m+1][4];
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                        D[i][j] = 1e9;
                        for(int t = 0; t < 4; t++) P[i][j][t] = 0;
                        cin >> A[i][j];
                }
        }

        queue<pair<int,int>>q;
        q.push({x1,Y1});
        D[x1][Y1] = 0;

        while(q.size()){

                auto p = q.front();
                q.pop();
                int x = p.ff;
                int y = p.ss;
                //if(fix[x][y])continue;
                //cout << x << " " << y << endl;
                for(int j = 0; j < 4; j++){
                        for(int i = 1; i <= k; i++){
                                int nx = x + X[j]*i;
                                int ny = y + Y[j]*i;
                                if(nx < 1 || nx > n || ny < 1 || ny > m) break;
                                if((A[nx][ny] == '@')) break;
                                if(D[nx][ny] < D[x][y]+1) break;
                                if(D[nx][ny] == 1e9)q.push({nx,ny});
                                if(P[nx][ny][j]) break;
                                D[nx][ny] = D[x][y]+1;
                                P[nx][ny][j] = 1;
                        }
                }
        }

        if(D[x2][y2] == 1e9) D[x2][y2] = -1;

        cout << D[x2][y2] << endl;

}


Measured memory_bytes: 24704
#include"iostream"

using namespace std;

int main()
{
    int n;
    int a[100] = { 0 };
    float ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        ans += 1.0 / a[i];
    }
    cout << 1.0 / ans;
  
}

Measured memory_bytes: 256
a=input()
matrix=[]
for i in range(int(a)):
	matrix.append(list(map(int,input().split())))

# ?????????O(n)????????£?????????
class union_find(object):
 	"""union-find tree"""
 	def __init__(self, length):
 		self.length = length
 		self.unionnumber=0
 		self.unionlist=[[]]
 		self.num=list(-1 for i in range(length))

 	def unite(self,i,j):
 		if self.num[i]==-1:
 			if self.num[j]==-1:
 				self.unionlist[self.unionnumber].extend([i,j])
 				self.num[i]=self.unionnumber
 				self.num[j]=self.unionnumber
 				self.unionnumber+=1
 				self.unionlist.append([])
 			else:
 				tmp=i 
 				i=j 
 				j=tmp 
 		if self.num[i]!=-1:
 			if self.num[j]!=-1:
 				if self.num[i]==self.num[j]:
 					pass
 				else:
 					self.unionlist[self.num[i]].extend(self.unionlist[self.num[j]])
 					tmp=self.num[j]
 					for k in self.unionlist[self.num[j]]:
 						self.num[k]=self.num[i]
 					self.unionlist[tmp]="del"
 			else:
 				self.num[j]=self.num[i]
 				self.unionlist[self.num[i]].append(j)

 	def same(self,i,j):
 		if self.num[i]==-1 or self.num[j]==-1:
 			return(False)
 		else:
 			return(self.num[i]==self.num[j])

# ?????????=-1
def Kruskal(matrix):
	length=len(matrix)
	edgelist=[]
	for i in range(length):
		for j in range(i+1):
			if matrix[i][j]!=-1:
				edgelist.append([j,i,matrix[i][j]])
	edgelist.sort(key=lambda x:x[2],reverse=True)
	result=[[-1 for i in range(length)] for j in range(length)]
	union=union_find(length)
	while(edgelist!=[]):
		edge=edgelist.pop()
		i,j,score=edge
		if union.same(i,j):
			pass
		else:
			union.unite(i,j)
			result[i][j]=score
			result[j][i]=score
		
	return(result)

a=Kruskal(matrix)
count=0
for i in range(len(a)):
	for j in range(i):
		if a[i][j]!=-1:
			count+=a[i][j]

print(count)

Measured memory_bytes: 8300
n=int(input())
l=list(map(int,input().split()))
a1=0
a2=0
s1=0
s2=0
for i,j in enumerate(l):
    s1+=j
    s2+=j
    if i%2:
        if s1>=0:
            a1+=s1+1
            s1=-1
        if s2<=0:
            a2+=-s2+1
            s2=1
    else:
        if s2>=0:
            a2+=s2+1
            s2=-1
        if s1<=0:
            a1+=-s1+1
            s1=1
print(min(a1,a2))

Measured memory_bytes: 63216
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
long n;
long a[1000000];
long G[100];
long cnt;
// O(g)
void insertionSort(long g){
	for (long i = g; i < n; ++i){
		long v = a[i];
		long j = i - g;
		while (j >= 0 && a[j] > v){
			a[j + g] = a[j];
			j = j - g;
			++cnt;
		}
		a[j + g] = v;
	}
}
void shellSort(){
	G[0] = 1;
	for (int i = 1; i < 100; ++i) G[i] = 2*G[i-1];
	int m=1;
	for (int i = 0; i < 100; ++i){
		if (G[i]>n) break;
		m = i + 1;
	}
	for (int i = m-1; i >=0; --i) insertionSort(G[i]);
	cout << m << '\n';
	for (int i = m-1; i >=0; --i){
		if (i != m-1) cout << ' ';
		cout << G[i];
	}
	cout << '\n';
	cout << cnt << '\n';
}

int main(){
	cin >> n;
	for (long i = 0; i < n; ++i) cin >> a[i];
	shellSort();
	for (long i = 0; i < n; ++i){
		cout << a[i] << '\n';
	}
}

Measured memory_bytes: 8972
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);
    int n; ll z, w;
    cin >> n >> z >> w;
    V<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    ll ans = abs(a[n-1] - w);
    if (n > 1) {
        ans = max(ans, abs(a[n-1] - a[n-2]));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 892
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	vector<long long> B(N + 1, 0); //累積和テーブル
	int mod = 1000000007;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		B[i + 1] = B[i] + A[i];
	}

	long ans = 0;

	//i について全探索する
	for (int i = 0; i < N; i++)
	{
		//累積和を使ってA[i+1] + ... + A[N] を求める
		long long sum = (B[N] - B[i + 1]) % mod;

		ans += (A[i]%mod) * sum;
		ans %= mod;
	}

	cout << ans << endl;
}

Measured memory_bytes: 5612
n = gets.chomp.to_i
d = gets.chomp.split(" ").map(&:to_i)
m = gets.chomp.to_i
t = gets.chomp.split(" ").map(&:to_i)
d = d.sort
t = t.sort
count = 1
ookisa = t.size
hash = Hash.new(0)
d.each do |i|
    hash[i] += 1
end
t.each do |j|
    hash[j] -= 1
    count -= 1 if hash[j] < 0
end

puts count == 1 ? "YES" : "NO"

Measured memory_bytes: 57888
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;

#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define pi  3.14159265359
#define mod 1000000007

int main()
{
    ll n;
    cin>>n;
    ll arr[n]; ll pre[n];
    for(ll i=0;i<n;i++)
    {
        cin>>arr[i];
        if(i==0){
            pre[i]=arr[i];
        }else{
        pre[i]=(pre[i-1]+arr[i]);
        }
    }
    ll ans=0;
    for(ll i=0;i<n-1;i++)
    {
        ans=(ans+(((pre[n-1]-pre[i])%mod*(arr[i]%mod))))%mod;

    }
    cout<<ans<<endl;

}


Measured memory_bytes: 6632
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
typedef long long ll;

int main() {
    int D;
    cin >> D;
    string res = "Christmas";
    rep(i, 25-D) {
        res += " Eve";
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main() {
	string s;
	int n, r, r_count, l, l_count;
	int i = 0;

	cin >> s;
	n = (int)s.size();
	vector<int> m(n,0);

	while(i < n) {
		l_count = 0;
		r_count = 0;

		if (s[i] == 'R') {
			while (s[i] == 'R' && i < n)r_count++, i++;
			r = i - 1;
			l = i;
			m[r] += (r_count + 1) / 2;
			m[l] += r_count / 2;
		}
		if (s[i] == 'L') {
			r = i - 1;
			l = i;
			while ( i < n && s[i] == 'L')l_count++, i++;
			m[l] += (l_count + 1) / 2;
			m[r] += l_count / 2;
		}
	}

	for (int i = 0; i < n; i++) {
		cout << m[i];
		if (i != n - 1)cout << ' ';
		else cout << endl;
	}
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

int main() {
  
  string S;
  cin >> S;
  
  if (S.at(0) == S.at(1) || S.at(1) == S.at(2) || S.at(2) == S.at(3)) {
    cout << "Bad" << endl;
  }
  else {
    cout << "Good" << endl;
  }
  
  

return 0;
}

Measured memory_bytes: 3620
def shaku(K,lists):
    ans=0
    SUMS=0
    index=0
    for  l  in range(len(lists)):
        while index < l or index< len(lists) and SUMS +lists[index] < K:
            SUMS += lists[index]
            index+= 1
        ans += index-l
        SUMS -= lists[l]

    return ans


n,k=map(int,input().split())
lists=list(map(int,input().split()))

uselist=[0 for i in range(n+1)]
for i in range(n):
    uselist[i+1]=(uselist[i]+lists[i])
anslist=[0 for i in range(n+1)]
for j in range(1,n+1):
    anslist[j]=(uselist[j]-j)%k
dic={}
for i in range(n+1):
    if anslist[i] in  dic.keys():
        dic[anslist[i]].append(i+1)
    else:
        dic[anslist[i]]=[1+i]
#answerに答えを格納することにする
answer=0
for lis in dic.values(): 
    sublis=[lis[0]]
    for a in range(1,len(lis)):
        sublis.append(lis[a]-lis[a-1])
    P=shaku(k,sublis)

    for some in lis:
      if some<k:
        answer-=1
    answer+=P
print(answer)

Measured memory_bytes: 69000
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch Test | diff Test.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address Test.cpp && ./a.out

/*

 5/22/2020

 8:50-

 */

const int MAX_N=1e6+1;
int N;
VI G[MAX_N];

int D[2][MAX_N];
void dfs(int u, int pre, int c, int d) {
  D[c][u]=d;
  FORR(v,G[u]) if(v!=pre) dfs(v,u,c,d+1);
}
void solve() {
  dfs(0,-1,0,0),dfs(N-1,-1,1,0);
  VI cnt(2,0);
  REP(u,N) cnt[(D[0][u]<=D[1][u])?0:1]++;
  cout<<(cnt[0]>cnt[1]?"Fennec":"Snuke")<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;

  cin>>N;
  REP(i,N-1) {
    int u,v; cin>>u>>v;
    --u,--v;
    G[u].push_back(v),G[v].push_back(u);
  }
  solve();

  return 0;
}


Measured memory_bytes: 39296
#include "bits/stdc++.h"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/operators.hpp>
#include <boost/dynamic_bitset.hpp>

namespace adaptor = boost::adaptors;
using index_t = std::size_t;

void Main()
{
	std::int64_t K;
	int N;
	std::cin >> K >> N;
	std::int64_t first, prev;
	std::cin >> first;
	prev = first;
	std::int64_t max = 0;
	for (auto i : boost::irange(1, N))
	{
		std::int64_t v;
		std::cin >> v;
		max = std::max(max, v - prev);
		prev = v;
	}
	max = std::max(max, K - prev + first);
	std::cout << K - max << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define NP next_permutation
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;

const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;

template<class T> bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T> void decimal(T a){cout<<fixed<<setprecision(a);}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}

void YesNo(bool a){if(a) out("Yes"); else out("No");}
void yesno(bool a){if(a) out("yes"); else out("no");}
void YESNO(bool a){if(a) out("YES"); else out("NO");}
ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){ll c=1; while(b>0){if(b&1){c=a*c %mod;}a=a*a %mod;b>>=1;}return c;}
vi calc(ll x){vi res; while(x>0){res.eb(x%10);x/=10;}reverse(all(res)); return res;}

void solve() {
  vector<string> v={"Christmas","Christmas Eve","Christmas Eve Eve","Christmas Eve Eve Eve"};
  int d; cin>>d;
  out(v[25-d]);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#define ll long long int
#define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n)

using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    if (n * a >= b)
        cout << b << endl;
    else
        cout << n * a << endl;

    return 0;
}


Measured memory_bytes: 256
// AtCoder ABC105: C - Base -2 Number
// 2019.9.11 bal4u

#include <stdio.h>

#define B 2  // マイナス進数  
char b[55];

char *trans(int n)
{
	int i, a, c;

	if (n == 0) { b[0] = '0'; return b; }
	
	i = 50; while (n) {
		c = 0;
		a = n % B;
		if (a == 0) b[i] = '0';
		else {
			b[i] = '1';
			if (i & 1) {
				if (a > 0) c = 1;
			} else {
				if (a < 0) c = -1;
			}
		}			
		i--, n /= B, n += c;
	}
	return b+i+1;
}

int main()
{
	int N;
	scanf("%d", &N);
	puts(trans(N));
	return 0;
}

Measured memory_bytes: 128
#pragma region kyomukyomupurin

/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-05-02 20:45:12
 **/

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int flag = 0;
  for (auto e : vec) os << (flag++ ? ", " : "{") << e;
  return os << (vec.empty() ? "{}" : "}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int flag = 0;
  for (auto e : st) os << (flag++ ? ", " : "{") << e;
  return os << (st.empty() ? "{}" : "}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int flag = 0;
  for (auto e : mp) os << (flag++ ? ", " : "{") << e;
  return os << (mp.empty() ? "{}" : "}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

#pragma endregion kyomukyomupurin

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int64 a, b, n; cin >> a >> b >> n;

  if (b > n) {
    cout << (a * n / b) << endl;
  } else {
    int64 mx = n / b;
    int64 ans = b;
    ans *= mx;
    --ans;
    debug(ans);
    cout << a * (ans) / b - a * (ans / b) << endl;
  }

  return 0;
}

Measured memory_bytes: 3652
// Problem : E - Logs
// Contest : AtCoder - AtCoder Beginner Contest 174
// URL : https://atcoder.jp/contests/abc174/tasks/abc174_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

bool check(int mid,vi &v,int k)
{
	int cut=0;
	for(int i:v)
	{
		//want <=mid each of it
		if(i>mid)
		cut+=i/mid;
	}
	return cut<=k;
}
void solve()
{
	int n,k;cin>>n>>k;
	vi v(n);cin>>v;
	int l=1,h=*max_element(all(v));
	int ans;
	while(l<=h)
	{
		int mid=(l+h)/2;
		//cout<<mid<<" ";
		if(check(mid,v,k))
		{
			ans=mid;
			h=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<ans;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 4752
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
    vl v(3,0);
    string s;cin >> s;
    rep(i,s.size()){
        v[s[i]-'a']++;
    }
    sort(all(v));
    ll t=v[2]-v[0];
    if(t==0||t==1)cout <<"YES" <<endl;
    else cout << "NO" <<endl;
}

Measured memory_bytes: 3764
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18

def dfs1(cur):
    for to in G1[cur]:
        if done1[to]: continue
        done1[to] = True
        dfs1(to)

def dfs2(cur):
    for to in G2[cur]:
        if done2[to]: continue
        done2[to] = True
        dfs2(to)

N, M, P = map(int, input().split())
G = []
G1 = [[] for i in range(N)]
G2 = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
    G1[a].append(b)
    G2[b].append(a)
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
done1 = [False]*N
done1[0] = True
dfs1(0)
done2 = [False]*N
done2[N-1] = True
dfs2(N-1)
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
            if done1[to] and done2[to]:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])


Measured memory_bytes: 59484
#include<bits/stdc++.h>

using namespace std;



#define MAX_N 110
int n;
int x[MAX_N], y[MAX_N], h[MAX_N];

int main(){
    while(cin >> n){
        for(int i = 1; i <= n; ++i){
            cin >> x[i] >> y[i] >> h[i];
            if(h[i] > 0) {
                swap(h[i], h[1]);
                swap(x[i], x[1]);
                swap(y[i], y[1]);
            }
        }
        for(int cx = 0; cx <= 100; ++cx){
            for(int cy = 0; cy <= 100; ++cy){
                int ch = h[1] + abs(x[1] - cx) + abs(y[1] - cy);
                bool is = true;
                for(int i = 2; i <= n; ++i){
                    if(max(ch - abs(x[i] - cx) - abs(y[i] - cy), 0) != h[i]) {
                        is = false;
                        break;
                    }
                }
                if(is){
                    cout << cx << " " << cy << " " << ch << endl;
                    return 0;
                }
            }
        }
    }
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int K, X;
  cin >> K >> X;

  int i = 0;
 
  while (i < K - 1) {
    cout << X - K +1 + i;
    cout << " " ;
    i++;
  }

  i = 0;
 
  while (i < K) {
    cout << X + i;
    cout << " ";
    i++;
  }
  cout << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;


public class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		int a,b,c;
		int n = sc.nextInt();
		for(int i=0;i<n;i++)
		{
			a = sc.nextInt();
			b = sc.nextInt();
			c = sc.nextInt();
			if(a*a+b*b==c*c||a*a+c*c==b*b||b*b+c*c==a*a) System.out.println("YES");
			else System.out.println("NO");
		}
	}
}

Measured memory_bytes: 12000
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,L,a[MAX];
int main()
{
	n=read();L=read();
	for(int i=1;i<=n;++i)a[i]=read();
	bool fl=false;int pos;
	for(int i=1;i<n;++i)if(a[i]+a[i+1]>=L)fl=true,pos=i;
	if(!fl){puts("Impossible");return 0;}
	puts("Possible");
	for(int i=1;i<pos;++i)printf("%d\n",i);
	for(int i=n-1;i>pos;--i)printf("%d\n",i);
	printf("%d\n",pos);
	return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    double a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort( a , a+n);
    double ans =( a[0] + a[1] )/2;
    for(int i=2;i<n;i++)
    {
        ans =( ans + a[i] )/2;
    }
    cout<<ans;
}

Measured memory_bytes: 3792
#include <stdio.h>
  
int main(){
  //入力
  int N,A,B;
  //全て正整数でNは20以下、A,Bは50以下からok
  scanf("%d %d %d", &N,&A,&B);

  //計算・出力
  printf("%d", A*N>B ? B : A*N);
  //A*NとBの小さい方を出力
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;
typedef pair<Int, Int> P;

int main(){
    int X; cin >> X;

    if(X < 600){
        cout << 8 << endl;
    } else if (X < 800){
        cout << 7 << endl;
    } else if (X < 1000){
        cout << 6 << endl;
    } else if (X < 1200){
        cout << 5 << endl;
    } else if (X < 1400){
        cout << 4 << endl;
    } else if (X < 1600){
        cout << 3 << endl;
    } else if (X < 1800){
        cout << 2 << endl;
    } else if (X < 2000){
        cout << 1 << endl;
    }
}


Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
    int k;
    cin>>k;
    string s;
    cin>>s;
    string ans;
    if(s.size()>k) {
        ans=s.substr(0,k);
        ans+="...";
    }
    else ans=s;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3632
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
a, b, c, d = map(int, input().split())
a -= 1
r = b - a
e = lcm(c, d)
print(r - b // c + a // c + r - b // d + a // d - r + b // e - a // e)

Measured memory_bytes: 5048
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

int main()
{
    ll n,p,q,r,s;
    cin>>n;
    p=n/3;
    q=n/5;
    s=n/15;
    r=(p*(p+1)/2)*3+(q*(q+1)/2)*5-(s*(s+1)/2)*15;
         cout<<(n*(n+1)/2)-r;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int arr[15];
int N,k;int ans=0;
int check(int x){
    while(x){
        if(arr[x%10]==1){
            return 0;
        }
        x/=10;
    }
    return 1;
}
int main(){
    for(int i=0;i<15;i++){
        arr[i]=0;
    }
    scanf("%d%d",&N,&k);
    for(int i=0;i<k;i++){
        int temp;
        scanf("%d",&temp);
        arr[temp]=1;
    }
    for(int i=N;i<=100010;i++){
        if(check(i)){
            printf("%d\n",i);
            //system("pause");
            return 0;
        }
    }
}

Measured memory_bytes: 256
# AtCoder Beginner Contest 175
# C - Walking Takahashi

X,K,D =map(int,input().split())

KOE=K%2

A=abs(X)//D
M=abs(X)%D

# print(A)

if K<=A:
    print(abs(X)-K*D)
    exit()

else :
    if A%2==KOE:
        print(M)
    else :
        print(min(abs(M+D),abs(M-D)))

Measured memory_bytes: 9104
void main() {
    int[] tmp = readln.split.to!(int[]);
    int x = tmp[0], t = tmp[1];
    max(0, x-t).writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
#include <stdio.h>
#include <inttypes.h>

int get(uint64_t x, int pos) {
	if (pos == 0) {
		return x % 4 == 1 || x % 4 == 2;
	} else {
		return (x >> pos) & ~x & 1;
	}
}

uint64_t getto(uint64_t x) {
	uint64_t mizuhasu = 0;
	int i;
	for (i = 0; i < 64; i++) {
		if (get(x, i)) mizuhasu |= UINT64_C(1) << i;
	}
	return mizuhasu;
}

int main(void) {
	uint64_t A, B;
	if (scanf("%" SCNu64 "%" SCNu64, &A, &B) != 2) return 1;
	printf("%" PRIu64 "\n", getto(B) ^ (A > 0 ? getto(A - 1) : 0));
	return 0;
}

/*

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

*/


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int n,d,aa[1100][4000],ab[1100][10],cnt=0,a,b;
pair<int,int> p[220000];
string s,t,u;
char c;
signed main(){
    cin>>s>>t>>a>>b>>u;
    if(u==s){
        cout<<a-1<<' '<<b;
    }else{
        cout<<a<<' '<<b-1;
    }
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int main(){
  int N;
  cin >> N;

  vector<int> v(N);
  vector<int> n(N);
  vector<int> ans(N);

  for(int i = 0; i < N; i++){
    cin >> v[i];
  }

  for(int i = 0; i < N; i++){
    if((N - i - 1) % 2 == 0){
      n[i] = (N - i - 1) / 2;
      //cout << "i:" << i << " n[i]:" << n[i] << endl;
    }
    else{
      n[i] = (N - i - 1) / 2 + i + 1;
      //cout << "i:" << i << " n[i]:" << n[i] << endl;
    }
  }

  for(int i = 0; i < N; i++){
    ans[n[i]] = v[i];
  }

  for(int i = 0; i < N; i++){
    if(i == 0){
      cout << ans[i];
    }
    else{
      cout << " " << ans[i];
    }
  }

  cout << endl;

  return 0;
}


Measured memory_bytes: 4480
from math import floor
N,M=map(int,input().split())
p= floor(M**0.5)
kumi=[]

for i in range(1,p+1):
  if M%i==0:
    kumi.append((i,M//i))
    
ans=1
for pair in kumi:
  if pair[0]>=N:
    ans = max(ans,pair[1])
  if pair[1]>=N:
    ans = max(ans,pair[0])
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <list>

using namespace std;

int main() {
  string s;
  int q;
  cin >> s >> q;

  list<char> li;
  for (auto &v : s)
    li.push_back(v);

  bool rev = false;
  while (q--) {
    int t;
    cin >> t;

    if (t == 1) {
      rev = not rev;
      continue;
    }

    int f;
    char c;
    cin >> f >> c;

    if ((f == 1 && rev == false) || (f == 2 && rev == true))
      li.push_front(c);
    else
      li.push_back(c);
  }

  if (rev)
    reverse(li.begin(), li.end());

  for (auto &v : li)
    cout << v;
  cout << endl;
}

Measured memory_bytes: 9984
/* ex7_3
   cy_an  */

#include <stdio.h>
#include <stdlib.h>

int main(void){

    // 変数の宣言
    char **memory;
    int num_r, num_c, i, j, r_flag, c_flag, printflag;

    // numの入力
    scanf("%d %d", &num_r, &num_c);

    // 二次元配列領域の動的確保
    memory = (char**)calloc(num_r, sizeof(char*));
    if(memory == NULL){
        fprintf(stderr, "memory allocation error.\n");
        exit(1);
    }
    for(i=0; i<num_r; i++){
        memory[i] = (char*)calloc(num_c, sizeof(char));
        if(memory[i] == NULL){
            fprintf(stderr, "memory allocation error.\n");
            exit(1);
        }
    }

    // 配列の宣言
    char matrix[num_r+1][num_c+1];

    // raw,colの入力
    for(i=0; i<num_r; i++){
        scanf("%s", matrix[i]);
    }

    // 行の削除
    for(i=0; i<num_r; i++){
        r_flag = 1;
        for(j=0; j<num_c; j++){
            if(matrix[i][j] == '#'){
                r_flag = 0;
                break;
            }
        }
        // 全て'.'のとき
        if(r_flag){
            for(j=0; j<num_c; j++){
                matrix[i][j] = '-';
            }
        }
    }
    // 列の削除
    for(j=0; j<num_c; j++){
        c_flag = 1;
        for(i=0; i<num_r; i++){
            if(matrix[i][j] == '#'){
                c_flag = 0;
                break;
            }
        }
        // 全て'.'のとき
        if(c_flag){
            for(i=0; i<num_r; i++){
                matrix[i][j] = '-';
            }
        }
    }

    // matrixの出力
    for(i=0; i<num_r; i++){
        printflag = 0;
        for(j=0; j<num_c; j++){
            if(matrix[i][j] != '-'){
                printf("%c", matrix[i][j]);
                printflag = 1;
            }
        }
        if(printflag){
            printf("\n");
        }
    }

    // メモリの解法
    for(i=0; i<num_r; i++){
        free(memory[i]);
    }
    free(memory);

    return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a,const void *b){
  return *(long long*)a-*(long long*)b;
}

int main(void){
  long N;
  scanf("%ld",&N);
  long long A[N+2],B[N+2],C[N+2];
  long long ans = 0;

  for(int i = 0;i < N;i++) scanf("%lld",&A[i+1]);
  for(int i = 0;i < N;i++) scanf("%lld",&B[i+1]);
  for(int i = 0;i < N;i++) scanf("%lld",&C[i+1]);
  B[0] = -1; C[0] = -1; A[0] = -1;
  A[N+1] = 1000000001; B[N+1] = 1000000001; C[N+1] = 1000000001;

  qsort(A,N+2,sizeof(long long),compare_int);
  qsort(B,N+2,sizeof(long long),compare_int);
  qsort(C,N+2,sizeof(long long),compare_int);


  for(int i = 1;i < N+1;i++){
    long low = 0;
    long high = N+1;
    long middle = (low+high)/2;

    while(high-low > 1){
      middle = (low+high)/2;
      if(A[middle] >= B[i])
        high = middle;
      else
        low = middle;
    }

    long sample = low;

    low = 0; high = N+1; middle = (low+high)/2;
    while(high-low > 1){
      middle = (low+high)/2;
      if(C[middle] > B[i]) high = middle;
      else low = middle;
    }
    ans += sample*(N-high+1);
  }

  printf("%lld\n",ans);

  return 0;
}

Measured memory_bytes: 3324
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) < (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*) array, (T*) (array + N), val);
}
pii Dir[8] = { //移動
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};

ll mod_pow(ll x, ll n, int mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x%mod;
		x = x*x%mod;
		n >>= 1;
	}
	return res;

}
#define int ll

signed main() {
	int n;
	scanf("%lld", &n);
	vector<int> ax;
	map<int, int> ar;
	map<int, int> ac;
	REP(i, n) {
		int a;
		scanf("%lld", &a);
		if(!ar.count(a))
			ar[a] = i;
		else
			ar[a] = min(ar[a], i);
		ac[a]++;
		ax.push_back(a);
	}
	ax.push_back(0);
	sort(ALL(ax));
	ax.erase(unique(ALL(ax)), ax.end());
	sort(ALL(ax),greater<int>());
	vector<int> ans(n);
	int axc = 0;
	auto itr = ar.rbegin();
	for (axc = 0; axc < ax.size()-1; itr++) {
		pii cur = *itr;
		ans[itr->second] += (ax[axc] - ax[axc + 1]) * ac[itr->first];
		ac[ax[axc + 1]]+= ac[ax[axc]];
		ar[ax[axc + 1]] = min(ar[ax[axc + 1]], itr->second);
		axc++;
	}
	REP(i, n) {
		printf("%lld\n", ans[i]);
	}
	return 0;
}

Measured memory_bytes: 15092
#include<iostream>
#include<string>

using namespace std;



int main()
{
    int N, K;
    string S;
    int i, j, k = 0;
	int happy = 0;
	cin>>N>>K>>S;
	i = 0;
	j = i + 1;
	while(j < N)
	{
		if(S[i] == S[j])
		{
			j++;
			happy++;
		}
		else
		{
			i = j;
			j++;
		}
	}
	for(k = K; k > 0; k--)
	{
		happy += 2;
	}
	if(happy >= N-1)
		happy = N-1;
	cout<<happy;
	return 0;
}



Measured memory_bytes: 512
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int n; cin>>n;
  PII A[n];
  rep(i,n){
    cin>>A[i].first;
    A[i].second = i;
  }
  sort(A, A+n);
  int ans= 0;
  rep(i,n){
    if(i%2!=A[i].second%2) ans++;
  }
  cout << ans/2 << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <chrono>
using namespace std;

using _i64 = int64_t;
using _u64 = uint64_t;
using _f64 = double;

#define endl "\n"

#define _for(i, start, end) for(_i64 i = (_i64)start; i < (_i64)end; ++i)
#define _rep(i, number) _for(i, 0, number)
#define _foreach(e, data) for(auto& e : data)
#define _all(data) data.begin(), data.end()

template<typename type>
_i64 _size(const type& data) { return static_cast<_i64>(data.size()); }
template<typename type, size_t size>
_i64 _size(const type (&)[size]) { return static_cast<_i64>(size); }

enum _flag : bool { able = true, disable = false };

struct _time {
    _time(_flag flag) { check = flag; if(!check) { return; } gettime(start); }
    ~_time() {
        if(!check) { return; }; gettime(end);
        _i64 elapse = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cout << endl << "Time: " << elapse << " ms" << endl;
    }
    private:
    using _timer = chrono::time_point<chrono::system_clock>;
    _timer start, end; bool check;
    void gettime(_timer& time) { time = chrono::system_clock::now(); }
};

struct _ini { _ini() { ios::sync_with_stdio(false); cin.tie(nullptr); } } _ini;

int main() {
    {
        _time time(disable);
        _i64 n, q, query, element1, element2; vector<vector<_i64>> A;
        cin >> n >> q; A.resize(n);
        _rep(i, q) {
            cin >> query;
            switch(query) {
                case 0:
                    cin >> element1 >> element2;
                    A[element1].push_back(element2);
                    break;
                case 1:
                    cin >> element1;
                    _rep(j, _size(A[element1])) {
                        cout << (j != 0 ? " " : "") << A[element1][j];
                    }
                    cout << endl;
                    break;
                case 2:
                    cin >> element1;
                    A[element1].clear(); A[element1].shrink_to_fit();
                    break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 8960
n,x,y = map(int,input().split())

temp = [min( j-i, abs(x-i) + 1 + abs(y-j) ) for i in range(1,n+1) for j in range(i+1,n+1)]

from collections import Counter
c = Counter(temp)

for i in range(1,n):
    print(c[i])

Measured memory_bytes: 116436
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 30;
const int INF = 1000;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0,  0,-1, 1};

int N, M;
int d[MAXN][MAXN];

string G[MAXN];

bool out(int i, int j) { return i < 0 || j < 0 || i >= N || j >= M; }

pair<int,int> bfs(int start_x, int start_y) {

	queue< pair<int,int> > q;
	q.push({start_x, start_y});

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			d[i][j] = -1;

	d[start_x][start_y] = 0;

	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		
		q.pop();

		for (int i = 0; i < 4; ++i) {
			int r = dx[i] + x;
			int c = dy[i] + y;
			if (out(r, c) || G[r][c] == '#' || d[r][c] != -1) 
				continue;

			d[r][c] = 1 + d[x][y];
			q.push({r, c});
		}
	}

	int x = start_x, y = start_y;
	int mx_D = d[start_x][start_y];

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			int dist = d[i][j];
			if (mx_D < dist) {
				x = i;
				y = j;
				mx_D = dist;
			}
		}
	}

	return {x, y};
}


int main () {

	ios_base::sync_with_stdio(false); cin.tie(NULL); 	
		
	cin >> N >> M;

	for (int i = 0; i < N; ++i) cin >> G[i];

	int ans = 0;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			pair<int,int> one = bfs(i, j);			
			pair<int,int> two = bfs(one.first, one.second);
			ans = max(ans, d[two.first][two.second]);
		}
	}

	cout << ans << '\n';

	return 0;
}
 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define db double
#define pb push_back
#define nl '\n'
#define X first
#define Y second
#define nimble ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v) (v).begin(),(v).end()
#define mod(x,m) ((((x)%(m))+(m))%(m))
#define _sz(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(v) for(int i=0;i<_sz(v);i++)
#define rep1(i,b,a) for(int i=b;i>=a;i--)
#define preci(x) fixed<<setprecision(x)
#define tc int tt=1;cin>>tt;while(tt--)

#define TRACE
#ifdef TRACE
#define see(...) __f(#__VA_ARGS__,__VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr<<name<<" : "<<arg1<<nl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma=strchr(names+1,',');cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1, args...);
}
#else
#endif

int inf=0x3f3f3f3f;
ll infl=0x3f3f3f3f3f3f3f3fLL;
ld infd=1.0/0.0;
const ll MOD=1e9+7;// 998244353 // = (119<<23)+1
const ld pi=2*acos(0.0);

int main(){
    nimble
    int a;
    cin>>a;
    a=a+a*a+a*a*a;
    cout<<a;
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>

#define rep(i, n) for(int i=0; i < (int)n; i++)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

int main(void) {
  double x[3]={0}, y[3]={0};
  double p=0;

  rep(i, 2) cin >> x[i] >> y[i];

  x[2] = abs(x[0]-x[1]);
  y[2] = abs(y[0]-y[1]);
  p = pow(x[2], 2) + pow(y[2], 2);
  p = sqrt(p);

  printf("%.10lf", p);
}



Measured memory_bytes: 3276
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main(){
  int N, K;
  cin >> N;
  cin >> K;

  long double prob_sum = 0;
  REP(i, 1, N+1){
    int init_point = i;
    if (init_point >= K){
      prob_sum += ((long double)1.0 / N);
    }
    else{
      int need_count = ceil(log2((long double)K / init_point));
      prob_sum += ((long double)1.0 / N) * pow(0.5, need_count);
    }
    // cout << "i: " << i << "prob_sum: " << prob_sum << endl;
  }

  cout << setprecision(100) << prob_sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vec.at(i);
    }
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (i < j && j < k && i < k)
                {
                    if (vec.at(i) != vec.at(j) && vec.at(j) != vec.at(k) && vec.at(k) != vec.at(i))
                    {
                        if (vec.at(i) + vec.at(j) > vec.at(k) && vec.at(j) + vec.at(k) > vec.at(i) && vec.at(k) + vec.at(i) > vec.at(j))
                        {
                            ++count;
                        }
                    }
                }
                
            }
            
        }
        
    }
    
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct info{
	int ac, pn, id;
	vector<int> wa;

	info(): ac(0), pn(0), id(0) {}

	bool operator< (const info &i) const{
		if(ac != i.ac){ return ac < i.ac; }
		if(pn != i.pn){ return pn > i.pn; }
		return id < i.id;
	}
};

int main(){
	int T, P, R;
	int m, t, p, j;
	while(scanf("%*d%d%d%d", &T, &P, &R), T){
		vector<info> team(T + 1);
		for(int i = 1; i <= T; ++i){
			team[i].wa.assign(P + 1, 0);
			team[i].id = i;
		}
		
		for(int i = 0; i < R; ++i){
			scanf("%d%d%d%d", &m, &t, &p, &j);
			info &tm = team[t];
			if(j == 0){
				++tm.ac;
				tm.pn += m + 20 * tm.wa[p];
			}
			else{
				++tm.wa[p];
			}
		}
		
		sort(team.begin() + 1, team.end());
		for(int k = T; k > 0; --k){
			char ch = ',';
			if(k == 1){
				ch = '\n';
			}
			else if(team[k].ac == team[k - 1].ac && team[k].pn == team[k - 1].pn){
				ch = '=';
			}
			printf("%d%c", team[k].id, ch);
		}
	}
}

Measured memory_bytes: 1064