akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
using namespace std;


int main(){
    long N;
    long K;
    scanf("%ld %ld",&N,&K);
    int p[N];
    for(int i=0;i<N;i++){
        scanf("%d",&p[i]);
    }
    long long sum=0;
    long long max_sum=0;
    for(int i=0;i<K;i++){
        sum += p[i];
    }
    max_sum = sum;
    for(int i=0;i<N-K;i++){ 
        sum += p[i+K]-p[i];
        max_sum = max(max_sum,sum);
    }
    double res = (double)(max_sum+K)/2.0;
    printf("%.10f\n",res);

}





Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

int main() {
	ios_base::sync_with_stdio( false );

	int H, N;
	cin >> H >> N;

	int sum = 0;
	for( int i = 0; i < N; ++i ) {
		int a;
		cin >> a;
		sum += a;
	}

	cout << (sum >= H ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 256
import scala.io.Source

object Main{
  def main(args: Array[String]){
    val line =
      for{
        in <- Source.stdin.getLines.toList
      } yield in.map(c => c.toLower)

      val filteredSting = line.mkString.map(_.toLower).filter(('a' to 'z').contains(_))
      println((filteredSting + ('a' to 'z').mkString).groupBy(n => n).toList.sorted.map{
        case (k,v) => s"$k : ${v.length - 1}"
      }.mkString("\n"))
  }
}

Measured memory_bytes: 46164
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;

int n,x;
int a[200];

int main()
{
    cin>>n>>x;
    for (int i=0; i<n; ++i)
        cin>>a[i];
    sort(a,a+n);
    int sum=0;
    for (int i=0; i<n; ++i)
    {
        if (x>=a[i])
        {
            x-=a[i];
            sum++;
        }
    }
    if (sum==n && x>0) sum--;
    cout<<sum<<endl;


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
using namespace std;

int main() {
  string s;
  size_t num=0;
  bool a = true;
  cin >> s;
  for (size_t i = 2; i < s.length() -1; i++) {
    if(s[i] == 'C') num++;
  }
  for (size_t i = 1; i < s.length(); i++) {
    if(s[i] == 'B' || s[i] == 'A' || (s[i] > 'C' && s[i] <= 'Z')) a = false;
  }
  if(s[0] == 'A' && a && num == 1) cout << "AC" << endl;
  else cout << "WA" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
int main(){
  int n,cnt=0;
  cin >> n;
  vector<pair<int,int>> red(n),blue(n);
  for(int i=0;i<n;i++){
    cin >> red[i].first >> red[i].second;
  }
  for(int i=0;i<n;i++){
    cin >> blue[i].first >> blue[i].second;
  }
  sort(red.begin(),red.end());
  sort(blue.begin(),blue.end());
  for(int i=0;i<n;i++){
    int tx=blue[i].first,ty=blue[i].second,mty=-1000000;
    auto it = red.end();
    for(auto j=red.begin();j!=red.end();j++){
      if(j->first<tx && j->second<ty && j->second > mty){
        it = j;
        mty = j->second;
      }
    }
    if(mty!=-1000000){
      red.erase(it);
      cnt++;
    }
  }
  cout << cnt << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for(ll i = 1; i < (ll)(n); i++)
const ll mo=1000000007;
ll ans=0;
ll dp[0][0];

int main()
{ 
ll h,w,d;
cin >> h>>w>>d; 
pair<ll, ll> t[h*w];
ll temp;
rep(i,h)rep(j,w) {
    cin >> temp;
    t[temp-1].first=j;
    t[temp-1].second=i;
}
ll q;
cin >> q; 
pair<ll, ll> p[q];
rep(i,q) {
    ll a,b;
    cin >> a>>b;
    p[i].first=a-1;
    p[i].second=b-1;
}
ll da[d][h*w/d+1]={};
rep(i,d)for(ll j=i+d;j<h*w;j+=d){
    da[i][j/d]=da[i][j/d-1]+abs(t[j].first-t[j-d].first)+abs(t[j].second-t[j-d].second);
}
/* for (int i = 0; i < 2; ++i){
for (int j = 0; j < 5; ++j) {
    cout << da[i][j] << " ";
}cout  << endl;} */
rep(i,q){
    cout << da[p[i].second%d][p[i].second/d]-da[p[i].first%d][p[i].first/d] << endl;
}

return 0;
} 

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

#define ll long long
#define endl '\n'

int n;

void test() {
    cin>>n;
    map<int,int> v;
    int a;
    ll sum=0;
    for (int i=0; i<n; ++i) {
        cin>>a;
        ++v[a];
        sum+=a;
    }
    int q,b,c;
    cin>>q;
    for (int i=0; i<q; ++i) {
        cin>>b>>c;
        sum+=v[b]*(c-b);
        cout<<sum<<endl;
        v[c]+=v[b];
        v[b]=0;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // int t;
    // cin >> t;
    // while (t--) {
    //     test();
    // }
    test();
    return 0;
}

Measured memory_bytes: 8080
#include <bits/stdc++.h>
#define Phuong_ ios_base::sync_with_stdio(0); cin.tie(0);

/// easy access -------------
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<int,int> pi;
///-------------------------


int main()
{
    Phuong_; /// <3333
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &x:a) cin >> x;
    sort(a.begin(), a.end());
    int ans=0;
    const int MAXN = 1e6;
    bitset<MAXN+5> f;
    f.reset();
    for(int i=0; i<n; ++i){
        if (i && a[i]==a[i-1]) {
            f[a[i]]=1;
            continue;
        }
        for(int j=2*a[i]; j<=MAXN; j+=a[i]) f[j] = 1;
    }
    for(int i=0; i<n; ++i) if (!f[a[i]]) ans++;
    cout << ans;
    return 0;
}


Measured memory_bytes: 4212
MOD = 10**9+7
n = int(input())
s = input()
p = input()
ans = 0
f = 0
i = 0
two = False
while i < n:
    if i == 0:
        if s[i] == p[i]:
            ans = 3
        else:
            ans = 6
            i += 1
            two = True
        i += 1
        continue
    if i >= n:break
    if s[i] == p[i]:
        if two:
            pass
        else:
            ans *= 2
        two = False
    else:
        if two:
            ans *= 3
        else:
            ans *= 2
        two = True
        i += 1
    i += 1
    ans %= MOD
print(ans)


Measured memory_bytes: 38384
//It doesn't matter how slow you go, Unless you don't stop.
#include<iostream>
#include<algorithm>
#include<bitset>
 
#include<cmath>
#include<cstring>
#include<climits>
 
#include<deque>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
 
#include<fstream>
#include<chrono>
using namespace std;
 
typedef long long LL;
typedef pair<LL,LL> p64;
typedef vector<LL> v64;
typedef map<LL,LL> mp64;
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,s,e) for(long long i=s;i<=e;i++)
#define brep(i,s,e) for(long long i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define DANGER std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
void solve()
{
    string s;cin>>s;
    if(s[2]==s[3] && s[4]==s[5])
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    

}
 
int main()
{
    DANGER;
    ofstream out("output.txt");
 
    auto start = chrono::high_resolution_clock::now();
    
    LL t = 1;
    // cin>>t;
    rep(test,1,t)
    {
        solve();
    }
    
    auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start); 
    // cout << "Time taken by function: " << duration.count() << " milliseconds" << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,n;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a>>b>>c;
        if(a*a==c*c+b*b||b*b==c*c+a*a||c*c==a*a+b*b)
        cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}



Measured memory_bytes: 3092
N = int(input())

a = list(map(int,input().split()))


dic = {}

for i in a:

    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

if len(dic) > 2:
    print ("No")

else:
    mi = float("inf")
    ma = -1

    for i in dic:
        mi = min(mi,i)
        ma = max(ma,i)

    if ma - mi > 1:
        print ("No")

    elif ma - mi == 1:
        

        if dic[mi] + dic[ma] // 2 == ma and dic[ma] > 1:
            print ("Yes")
        else:
            print ("No")

    else:

        if ma == N-1 or N // 2 >= ma:
            print ("Yes")
        else:
            print ("No")


Measured memory_bytes: 61420
#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
#define ld long double
 
using namespace std;
 
const int N = 1e5 + 12;
const ll mod = 1e9 + 7;

int dp[N], a[N], n;

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    ll n, x;
    cin >> n >> x;
    ll res = 3 * (n - __gcd(n, x));
    cout << res;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
a, w = 0, 0
P = set()
W = {}
for _ in range(M):
    p, S = map(str, input().split())
    if p in P:
        continue
    if S == 'WA':
        W.setdefault(p, 0)
        W[p] += 1
    if S == 'AC':
        a += 1
        P.add(p)
        if p in W:
            w += W[p]
print(a, w)

Measured memory_bytes: 19660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 305, INF = 1e9+9;
int n, m, l;

int adj[maxn][maxn];
int ng[maxn][maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m >> l;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            adj[i][j] = INF;
            ng[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; i++) {
        adj[i][i] = 0;
        ng[i][i] = 0;
    }
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a][b] = c;
        adj[b][a] = c;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (adj[i][j] > adj[i][k] + adj[k][j]) 
                    adj[i][j] = adj[i][k] + adj[k][j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (adj[i][j] <= l) {
                ng[i][j] = 1;
            }
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (ng[i][j] > ng[i][k] + ng[k][j]) 
                    ng[i][j] = ng[i][k] + ng[k][j];
            }
        }
    }
    int q; cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        cout << (ng[a][b] >= INF ? -1 : ng[a][b]-1) << '\n';
    }
}


Measured memory_bytes: 1280
#include "bits/stdc++.h"

// Begin {{{
using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0; i < (n); ++i)
#define reps(i, b, e) for (i64 i = (b); i <= (e); ++i)
#define repr(i, b, e) for (i64 i = (b); i >= (e); --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)

#ifdef DEBUG
#define dump(...) dump_(#__VA_ARGS__, __VA_ARGS__);
#else
#define dump(...)
#endif

using i64 = int_fast64_t;
using pii = pair<i64, i64>;

template <class A, class B>
inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }

template <class A, class B>
inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

// input
void input() {}
template <class Head, class... Tail>
void input(Head&& head, Tail&&... tail) {
  cin >> head;
  input(forward<Tail>(tail)...);
}

// outs
void outs() {}
template <class Head, class... Tail>
void outs(Head&& head, Tail&&... tail) {
  cout << head << " \n"[sizeof...(tail)==0];
  outs(forward<Tail>(tail)...);
}

template <class T>
void outs(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e==&vec.back()]; }

template <class T>
void outs(vector<vector<T>> &df) { for (auto &vec : df) OUTS(vec); }

// outl
void outl() {}
template <class Head, class... Tail>
void outl(Head&& head, Tail&&... tail) {
  cout << head << "\n";
  outl(forward<Tail>(tail)...);
}

template <class T>
void outl(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

// outn
void outn() {}
template <class Head, class... Tail>
void outn(Head&& head, Tail&&... tail) {
  cout << head;
  outn(forward<Tail>(tail)...);
}

template <class T>
void outn(vector<T> &vec) { for (auto &e : vec) cout << e; }

// dump
template <class T>
void dump_(const char *s, T&& x) {
  clog << '{';
  while(*s != '\0') clog << *(s++);
  clog << ": " << x << '}' << "\n";
}

template <class Head, class... Tail>
void dump_(const char *s, Head&& head, Tail&&... tail) {
  clog << '{';
  while(*s != ',') clog << *(s++);
  clog << ": " << head << "}, ";
  for (++s; !isgraph(*s); ++s);
  dump_(s, forward<Tail>(tail)...);
}
// }}} End

i64 calc(i64 x) {
  return x * x * x;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  var(i64, N, K);

  i64 res = calc(N / K);

  if (!(K % 2)) {
    i64 cnt = 0;
    reps(i, 1, N) {
      if (i % K == K / 2) ++cnt;
    }

    res += calc(cnt);
  }

  outl(res);

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    if (s[0]==s[1] || s[1]==s[2] || s[2]==s[3]) {
        cout<<"Bad"<<endl;}
    else{
        cout<<"Good"<<endl;}
return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
map<int,int>ma;
vector<int>vec;
int main()
{
    int n,x;
    long long ans=0,sum=0,mod,a;
    scanf("%d%lld",&n,&mod);
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&a);
        sum+=a;
        x=sum%mod;
        if(ma[x]==0)vec.push_back(x);
        ma[x]++;
    }
    int len=vec.size();
    for(int i=0; i<len; i++)
    {
        sum=ma[vec[i]];
        if(vec[i])sum--;
        ans+=sum*(sum+1)/2;
    }
    cout << ans<<endl;
    return 0;
}

Measured memory_bytes: 3452
#include <iostream>
#include <cstring>
#include <sstream>
#include <cctype>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){

	int n;
	cin >> n;

	int a,min;
	cin >> min;
	int t = 0,tmax=0;
	cin >> a;
	t = a - min; tmax = t;
	if (a < min)min = a;
	for (int i = 0; i < n-2; i++){
		cin >> a;
		t = a - min;
		if (tmax < t)tmax = t;
		if (a < min)min = a;
	}

	cout << tmax << endl;

	return 0;
}


Measured memory_bytes: 3096
//https://twitter.com/chokudai/status/1267093176973549571
#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long N;
    long long A[1000000];
    long long sum = 1;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        if (A[i] == 0)
        {
            cout << "0" << endl;
            return 0;
        }
    }

    for (int i = 0; i < N; i++)
    {
        if (sum * A[i] < sum || sum * A[i] > 1000000000000000000) //pow(10, 18)
        {
            cout << "-1" << endl;
            return 0;
        }
        else
        {
            sum = sum * A[i];
        }
    }
    //cout << pow(10, 18) << endl;
    printf("%llu\n", sum);
    return 0;
}

/*#include <bits/stdc++.h>
using namespace std;

int solve(long long N, std::vector<long long> A)
{
    long long sum = A[0];
    for (int i = 1; i < N; i++)
    {
        sum = sum * A[i];
    }

    if (1000000000000000000 < sum)
    {
        cout << "-1" << endl;
    }
    else
    {
        printf("%lld\n", sum);
    }

    //cout << fixed << setprecision(20) << sum << endl;
    return 0;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &A[i]);
    }
    solve(N, std::move(A));
    return 0;
}
*/

Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 555;
const int MOD = 1e9 + 7;
vector<int> V[maxn];
set<int> row[maxn];
set<int> col[maxn];
int n, m, k;
const int INF = 0x3f3f3f3f;
void del(int a, int b) {
    row[a].erase(b);
    col[b].erase(a);
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    cout << fixed;
    cin >> n >> m >> k;
    int a1, b1, a2, b2;
    cin >> a1 >> b1 >> a2 >> b2;
    a1--;
    b1--;
    a2--;
    b2--;
    vector<string> mp(n);
    vector<vector<int>> dis(n, vector<int>(m, INF));
    for (auto &i : mp)
        cin >> i;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            row[i].insert(j);
            col[j].insert(i);
        }
    }
    queue<tuple<int, int, int>> Q;
    Q.push(make_tuple(a1, b1, 0));
    del(a1, b1);
    dis[a1][b1] = 0;
    while (!Q.empty()) {
        auto [x, y, d] = Q.front();
        // cout << x << ' ' << y << ' ' << d << endl;
        Q.pop();
        auto pos = row[x].lower_bound(y);
        vector<int> lazy;
        for (auto i = pos; i != row[x].end() && abs(*i - y) <= k; i++) {
            if (mp[x][*i] == '@')
                break;
            if (dis[x][*i] > d + 1) {
                lazy.push_back(*i);
                dis[x][*i] = d + 1;
                Q.push(make_tuple(x, *i, d + 1));
            }
        }
        // cout << 1 << endl;
        for (auto i = pos;;) {
            if (i == row[x].begin())
                break;
            i--;
            if (mp[x][*i] == '@')
                break;
            if (abs(*i - y) > k)
                break;
            if (dis[x][*i] > d + 1) {
                lazy.push_back(*i);
                dis[x][*i] = d + 1;
                Q.push(make_tuple(x, *i, d + 1));
            }
        }
        // cout << 2 << endl;
        for (int i : lazy) {
            del(x, i);
        }
        lazy.clear();

        pos = col[y].lower_bound(x);
        for (auto i = pos; i != col[y].end() && abs(*i - x) <= k; i++) {
            if (mp[*i][y] == '@')
                break;
            if (dis[*i][y] > d + 1) {
                lazy.push_back(*i);
                dis[*i][y] = d + 1;
                Q.push(make_tuple(*i, y, d + 1));
            }
        }
        // cout << 3 << endl;

        for (auto i = pos;;) {
            if (i == col[y].begin())
                break;
            i--;
            if (abs(*i - x) > k)
                break;
            if (mp[*i][y] == '@')
                break;
            if (dis[*i][y] > d + 1) {
                lazy.push_back(*i);
                dis[*i][y] = d + 1;
                Q.push(make_tuple(*i, y, d + 1));
            }
        }
        // cout << 4 << endl;
        for (int i : lazy) {
            del(i, y);
        }
    }
    cout << (dis[a2][b2] == INF ? -1 : dis[a2][b2]) << endl;
    return 0;
}


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

using namespace std;

int main() {
    int n;
    while (scanf("%d", &n), n) {
        int a[15][15] = {}, x = n / 2, y = x + 1;
        a[y][x] = 1;

        for (int i = 2; i <= n * n; i++) {
           y = (y + 1) % n, x = (x + 1) % n;
           if (a[y][x]) y = (y + 1 + n) % n, x = (x - 1 + n) % n;
           a[y][x] = i; 
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                printf("%4d", a[i][j]);
            printf("\n");
        }
    }

    return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int n;
char str[15];
map<ll, int> cnt;





int main() {
   cin>>n;
   for(int i=0;i<n;i++) {
       scanf("%s", str);
       ll tmp = 0;
       sort(str, str + 10);
    //   for(int i=0;i<10;i++) 
    //         cout<<str[i];
    //     cout<<endl;
       for(int i=0;i<10;i++) {
           tmp = tmp * 26 + (str[i] - 'a');
       }
       cnt[tmp] += 1;
   }
   
   ll ans = 0;
   
   map<ll,int>::iterator iter = cnt.begin();
    for(; iter !=cnt.end(); iter++)
    {
        ll tmp = iter->second;
        ans += ((tmp - 1) * tmp / 2);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 6528
import java.util.*;

public class Main {

    public static void main(String arg[]) {
        try {
            Scanner scan = new Scanner(System.in);
            int x[] = new int[3];
            int i = 0;
            for (int k = 0; k < 3; k++) {
                int y = scan.nextInt();
                if (0 < y && y < 10001) {
                    x[i] = y;
                    i++;
                } else {
                    System.out.println("1??????10000?????§???????????§???");
                    break;
                }
            }
            if (x.length == 3) {
                int j;
                for (i = x.length - 1; 0 <= i; i--) {
                    for (j = i; j < x.length - 1; j++) {
                        if (x[j] > x[j + 1]) {
                            int y = x[j];
                            x[j] = x[j + 1];
                            x[j + 1] = y;
                        }
                    }
                }
                for (i = 0; i < x.length - 1; i++) {
                    System.out.print(x[i]+ " ");
                }
                System.out.println(x[x.length - 1]);
            }
        } catch (InputMismatchException ex) {
            System.out.println("1??????100?????§????????¶??°?????\?????????????????????");
        }
    }
}

Measured memory_bytes: 26204
from itertools import product

N, A, B, C = map(int, input().split())
target = {'A': A, 'B': B, 'C': C}
L = [int(input()) for _ in range(N)]

mp = 10**9
cand = ['A', 'B', 'C', 'discard']
for t in product(cand, repeat=N):
    prepared = {'A': [], 'B': [], 'C': []}
    for i, p in enumerate(t):
        if p != 'discard':
            prepared[p].append(L[i])
    if prepared['A'] == [] or prepared['B'] == [] or prepared['C'] == []:
        continue
    temp = 0
    for p in ['A', 'B', 'C']:
        temp += abs(sum(prepared[p]) - target[p]) + (len(prepared[p]) - 1)*10
    if temp < mp:
        mp = temp
print(mp)

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

ll p2[70];
void pow2(){
    p2[0]=1;
    for(int i=0; i<69; i++){
        p2[i+1]=2*p2[i];
    }
}

template<typename T>
void cout_vec(vector<T> &vec){
    for(int i=0; i<vec.size(); i++){
        if (i!=0){
            cout << ' ';
        }
        cout << vec[i];
    }
    cout << endl;
}

template<typename T>
void cout_mat(vector<vector<T>  > &mat){
    for(int i=0; i<mat.size(); i++){
        vector<T> vec = mat[i];
        cout_vec(mat[i]);
    }
}

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

    vector<vector<ll>> dest(N,vector<ll>(70));
    for(int i=0; i<N; i++){
        int a;
        cin >> a;
        a--;
        dest[i][0]=a;
    }

    pow2();    
    for(int i=0; i<69; i++){
        for(int j=0; j<N; j++){
            dest[j][i+1]=dest[dest[j][i]][i];
        }
    }

    //cout_mat(dest);

    ll cnt=0;
    int x=0;
    while(cnt<K){
        int p=dest[x][0];
        ll tmp=1;
        for(int i=0; K-cnt-p2[i+1]>=0; i++){
            p=dest[x][i+1];
            tmp=p2[i+1];
        }
        x=p;
        cnt+=tmp;
        //cout << x << ' ' << K-cnt << endl;
    }
    cout << x+1 << endl;
}

Measured memory_bytes: 120472
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int a,p; cin >> a >> p;
    cout << (3*a+p)/2 << endl; return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var num1 int
	var num2 int
	for {
		fmt.Scan(&num1, &num2)
		if num1 == 0 && num2 == 0 {
			break
		}
		if num1 < num2 {
			fmt.Println(num1, num2)
		} else {
			fmt.Println(num2, num1)
		}
	}
}



Measured memory_bytes: 1260
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	ll n; cin>>n;
	ll cnt=0;
	rep(i,1,n+1){
		ll a; cin>>a;
		if(a!=i)cnt++;
	}
	if(cnt==2 || cnt==0) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
	return 0;
}

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

int     main() {
        int N, X;
        cin >> N >> X;
        int L;
        int D=0;
        int S=1;
        for (int i=1; i<=N; i++) {
                cin >> L;
                D += L;
                if (D <= X) S++;
        }
        cout << S << endl;
        return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import defaultdict


class PrimeFactor():

    def __init__(self, n):                  # エラトステネス　O(N loglog N)
        self.n = n
        self.table = list(range(n+1))
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                self.table[p * p::2 * p] = [p] * ((n - p * p - 1) // (2 * p) + 1)

    def is_prime(self, x):  # 素数判定　O(1)
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             # 素因数分解 O(logN)
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             # 素因数分解（個数のリスト）
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X):                 # n個の最大公約数　X:n個のリスト
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp)
        return res

    def prime_lcm(self, X, mod=None):       # n個の最小公倍数　X:n個のリスト
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

mod = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
A.sort()
table = PrimeFactor(10**6)
num = table.prime_lcm(A,mod)

res = 0
for a in A:
    res += num * pow(a, mod - 2, mod)

print(res % mod)

Measured memory_bytes: 90224
P = 10**9 + 7

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

x1 = 0
x2 = 0
for i in range(N-1):
  for j in range(i+1, N):
    if A[i] > A[j]:
      x1 += 1
    elif A[i] < A[j]:
      x2 += 1

y1 = (K * (K+1) // 2) % P
y2 = ((K-1) * K // 2) % P

ans = (x1*y1 + x2*y2) % P
print(ans)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
int main(void){
    int n,m;
    while(cin>>n>>m,n){
        vi t(n),h(m);
        rep(i,n) cin>>t[i];
        rep(i,m) cin>>h[i];
        sort(all(t));
        sort(all(h));
        int diff=accumulate(all(h),-accumulate(all(t),0));
        if(abs(diff)%2==1){
            cout<<-1<<endl;
            continue;
        }
        diff/=2;
        int found=-1;
        for(auto i:t){
            if(binary_search(all(h),i+diff)){
                found=i;
                break;
            }
        }
        if(found==-1){
            cout<<-1<<endl;
        }else{
            cout<<found<<" "<<found+diff<<endl;
        }
    }
}

Measured memory_bytes: 3044
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ll n,a,b;
    cin>>n>>a>>b;
    ll ans = n/(a+b) *a;
    ll remainder = n%(a+b);
    if( remainder >= a)
        ans+=a ;
    else ans+= remainder;
    cout<<ans;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N; cin>>N;
    vector<int> a(N+2);
    a[0] = 0;
    a[N+1] = 0;
    vector<int> b(N+2);
    b[0] = 0;
    for(int i=1; i<N+1; ++i) {
        cin>>a[i];
        b[i] = abs(a[i] - a[i-1]);
    }
    b[N+1] = abs(a[N]);
    ll tot = accumulate(b.begin(), b.end(), 0LL);
    for(int i=1; i<N+1; ++i){
        cout<<tot - b[i] - b[i+1] + abs(a[i+1] - a[i-1])<<endl;
    }


    return 0;
}



Measured memory_bytes: 2048
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String ns = sc.next();
    String[] s = ns.split("");
    int sum = 0;
    for (int i = 0; i < s.length; i++) {
      sum = sum + Integer.parseInt(s[i]);
    }
    if (sum % 9 == 0) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 65116
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b, c, d;
  cin >> a >> b >> c;

  if (a > b) {
    d = a;
    a = b;
    b = d;
  }
  if (b > c) {
    d = b;
    b = c;
    c = d;
  }
  if (a > b) {
    d = a;
    a = b;
    b = d;
  }

  cout << a << " " << b << " " << c << endl;
}


Measured memory_bytes: 3084
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}

int main()
{
	int n=read(),x=read(),t=read();
	if(n%x==0)printf("%d\n",n/x*t);
	else printf("%d\n",n/x*t+t);
	return 0;
}
/*

*/

Measured memory_bytes: 3192
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    c=0
    for j in a[i:]:
        c+=j
        l.append(c)
t=0
for i in range(40,-1,-1):
    s=2**i
    b=[u for u in l if s&u!=0]
    if len(b)>=k:
        l=b
        t+=s
print(t)

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

//0 1->codeforces
#define LL "%lld"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define PN printf("\n")
#define MODV 1000000007

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef pair<int, int> pi;
void addmod(int &a, ll b){a=(a+b); if(a>=MODV)a-=MODV;}
void mulmod(int &a, ll b){a=(a*b)%MODV;}
int gi(){int a;scanf("%d",&a);return a;}
ll gll(){ll a;scanf(LL,&a);return a;}

int main() {
  int n=gi(), b=MODV,t;
  vi a(n);
  for(auto i=0;i<n;i++){ a[i]=gi(); }
  sort(a.begin(), a.end());
  
  for(int i=a[0];i<=a[n-1];i++){
    t=0;
    for(int j=0;j<n;j++){
      t+=((a[j]-i)*(a[j]-i));
    }
    if(t<b)b=t;
  }
  cout<<b<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,x; 
	cin>>n>>x;
	vector<int>a(n);
	for(int i=0;i<n;i++)
		cin>>a[i];
	long long ret=0;
	for(int i=1;i<n;i++){
		if(a[i-1]+a[i]>x){
			int diff=a[i]+a[i-1]-x;
			ret+=diff;
			if(a[i]<diff){
				diff-=a[i];
				a[i]=0;
				a[i-1]-=diff;
			}
			else{
				a[i]-=diff;
			}
		}
	}
	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#define N 100

int main(){

  int a[N],b,c,d,i,j,count=0;

  scanf("%d",&b);
  for(i=0;i<b;i++){
    scanf("%d",&a[i]);
  }
  for(i=0;i<b;i++){
    c = i;
      for(j=i;j<b;j++){
	if(a[j] <a[c]){
	  c = j;
	}
      }
      	if(c!=i){
	  d = a[i];
	  a[i] = a[c];
	  a[c] = d;
	  count++;
  }
}
  for(i=0;;i++){
    printf("%d",a[i]);
    if(i==b-1){break;}
    printf(" ");
    }
  printf("\n");
  printf("%d",count);
  printf("\n");
  

  return 0;
}
	  

Measured memory_bytes: 604
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
すべて出すのはTLEだな
マイナスとプラスと0の個数は出る
全部プラスだったら、結局一緒か
1 2 3 4 5
1,2,3,4,5,6,8,10,12,15,20

-5 -4 -3 -2 -1 0 1 2 3 4 5
マイナス25通り
-10以上は何通り？
1 2 3 4 5
-1 -2 -3 -4 -5
毎回lowerして個数出す？まにあう？
logN=5.3とか余裕か。すごい
正の場合も同じか。
しゃくとり
二分探索かな
N*logn*18くらい
10以上が10個
9以上が14個
とかいう場合
にいたるのか
正の場合、どうもとめよう
負の中で10以上がいくつ
正の中でいくつ
合算してNにいたるか、かな
*/
int main(){
  ll N,K; cin>>N>>K;
  vector<ll> P,M,Z;
  for(ll i=0; i<N; i++){
    ll a; cin>>a;
    if(a<0) M.emplace_back(-a);
    else if(!a) Z.emplace_back(0);
    else if(a>0) P.emplace_back(a);
  }
  sort(M.begin(), M.end());
  sort(P.begin(), P.end());
  ll Msz=M.size(), Zsz=Z.size(), Psz=P.size();
  ll m=Msz*Psz;
  ll z=Zsz*(Zsz-1)/2+Zsz*(Msz+Psz);
  ll p=Msz*(Msz-1)/2+Psz*(Psz-1)/2;
  //負なら
  if(K<=m){
    ll high=1e18, low=0;
    while(high-1>low){
      ll mid=(high+low)/2;
      ll hit=0;
      for(ll i=0; i<Msz; i++){//負から1個
        ll n=mid/M[i];
        n+=(mid%M[i]!=0);
        auto IT=lower_bound(P.begin(), P.end(), n);
        hit+=P.end()-IT;
      }
      if(hit>=K) low=mid;
      else high=mid;
    }
    cout<<-low<<endl;
  }
  else if(K>m && K<=m+Zsz) cout<<0<<endl;
  else{//正
    K-=m+z;
    ll high=1e18, low=0;
    while(high-1>low){
      ll mid=(high+low)/2;
      ll hit=0;
      for(ll i=0; i<Msz; i++){//負から2個
        ll n=mid/M[i];
        n+=(mid%M[i]!=0);
        auto IT=lower_bound(M.begin(), M.end(), n);
        hit+=M.end()-IT;
        if(M[i]>=n) hit--;//自分とった場合ひく
      }
      for(ll i=0; i<Psz; i++){//正から2個
        ll n=mid/P[i];
        n+=(mid%P[i]!=0);
        auto IT=lower_bound(P.begin(), P.end(), n);
        hit+=P.end()-IT;
        if(P[i]>=n) hit--;//自分とった場合ひく
      }
      hit/=2;//2回とってる
      hit=p-hit;
      if(hit>=K) high=mid;
      else low=mid;
    }
    cout<<low<<endl;
  }
}

Measured memory_bytes: 5428
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>

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

int N;
int one, two, three;
double dp[301][301][301];

double rec(int i,int j,int k){
    if (dp[i][j][k] > -1) return dp[i][j][k];
    if (i == 0 and j == 0 and k == 0) return 0.0;

    double r = 0.0;
    if (i > 0) r += rec(i-1,j,k) * i;
    if (j > 0) r += rec(i+1,j-1,k) * j;
    if (k > 0) r += rec(i,j+1,k-1) * k;
    r += N;
    r *= 1.0/(i+j+k);
    return dp[i][j][k] = r;
}

int main(void){
    cin >> N;
    rep(i,N){
        int a; cin >> a;
        if (a == 1) one++;
        else if(a == 2) two++;
        else three++;
    }
    memset(dp,-1,sizeof(dp));
    printf("%.12f\n", rec(one,two,three));
    return 0;
}


Measured memory_bytes: 213376
def gcd(a,b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b
def main():
    A,B,C,D=map(int,input().split())
    if A%C!=0:
        C_min=A-A%C+C
    else:
        C_min=A
    C_max=B-B%C
    if A%D!=0:
        D_min=A-A%D+D
    else:
        D_min=A
    D_max=B-B%D
    mod=C*D//gcd(C,D)
    if A%mod!=0:
        CD_min=A-A%mod+mod
    else:
        CD_min=A
    CD_max=B-B%mod
    C_sum=(C_max-C_min)//C
    D_sum=(D_max-D_min)//D
    CD_sum=(CD_max-CD_min)//mod
    sum= B-A+1-int(C_sum+D_sum-CD_sum+1)
    return sum
print(int(main()))

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

int main() {
  int N;
  cin >> N;
  string S;
  for (int i=0; i < N; i++){
    cin >> S;
    if (S == "Y"){
      cout << "Four" << endl;
      break;
    }
    else if (i == N-1){
      if(S != "Y"){
        cout << "Three" << endl;
      }
    }
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<numeric>
#include<utility>
#include<unordered_map> //hash map
#include<cmath>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 10000007

typedef  long long ll;

using namespace std;

ll gcd(ll a,ll b){
    if (b==0)return a;
    return gcd(b,a%b);
}

ll deg(int i){
  ll ret = 1;
  while(i != 0){
    if(i/10 == 0){
      break;
    }
    i/=10;
  }
  
  return i;
}

void solve(){
  ll n,x,y;
  cin >> n >> x >> y;
  x--;
  y--;
  ll ans[n];
  for(int i = 0;i < n;i++) ans[i] = 0;

  for(ll i = 0;i < n-1;i++){
    for(ll j = i+1; j < n;j++){
      ll t = min(abs(i-j), min(abs(x-i)+abs(y-j)+1, abs(x-j)+abs(y-i)+1));
      ans[t]++;
    }
  }
 
  for(int i = 1;i < n;i++){
    cout << ans[i] << endl;
  }

}


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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i = a:i<b;i++)
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
#define ALL(s) (s).begin(), (s).end()
using namespace std;
typedef long long unsigned int llu;
typedef long long ll;

const string D_blue    = "\x1b[36m";
const string D_green   = "\x1b[32m";
const string D_red     = "\x1b[31m";
const string D_yellow  = "\x1b[33m";
const string Db_red    = "\x1b[41m";
const string Db_yellow = "\x1b[43m";
const string D_end     = "\x1b[39m";
const string Db_end    = "\x1b[49m";

int main (){
  int A,B,C,X;
  while (cin >> A >> B >> C >> X){
    int ans = 0;
    X /= 50;
    REP(a,A+1){
      REP(b,B+1){
	REP(c,C+1){
	  if(a*10 + b * 2 + c == X)ans++;
	}
      }
    }
    cout << ans << endl;
  }
  return 0;
}


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

const int N = 100010;
typedef std::pair <int, int> pii;
typedef long long ll;

std::pair <pii, pii> p[N];
std::priority_queue <int> pq;
int a, b, c;
ll sumleft[N], sumright[N];

int main(){
	scanf("%d%d%d", &a, &b, &c);
	int n = a + b + c;
	for (int i = 0, a, b, c; i < n; ++ i){
		scanf("%d%d%d", &a, &b, &c);
		p[i] = {{a - b, a}, {b, c}};
	}
	std::sort(p, p + n);
	for (int i = 0; i < n; ++ i){
		sumleft[i] = (i ? sumleft[i - 1] : 0) + p[i].second.first;
		pq.push(p[i].second.second - p[i].second.first);
		if (pq.size() > b){
			sumleft[i] += pq.top();
			pq.pop();
		}
	}
	while (!pq.empty()){
		pq.pop();
	}
	for (int i = n - 1; ~i; -- i){
		sumright[i] = sumright[i + 1] + p[i].first.second;
		pq.push(p[i].second.second - p[i].first.second);
		if (pq.size() > a){
			sumright[i] += pq.top();
			pq.pop();
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; ++ i){
		if (i + 1 >= b && n - i - 1 >= a){
			ans = std::max(ans, sumleft[i] + sumright[i + 1]);
		}
	}
	return printf("%lld\n", ans), 0;
}

Measured memory_bytes: 3832
#include<bits/stdc++.h>							
typedef long long ll;
#define pb push_back
#define mod 1000000007ll
const ll maxn = 9e18;
using namespace std;
const ll maxsize = 100000009;

bool d(ll n) {
	for(int i = 1; i <= sqrt(n); ++i) {
		if(n % i == 0) {
			if(n / i <= 9 && i <= 9) return true;
			}
		}
		return false;
}

void solve() {
	int n;
	cin >> n;
	if(d(n)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return;
}

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout.precision(35);
	solve();
	return 0;
}
 
 
 



Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, x, ans;
priority_queue<int> pq;

int32_t main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>x, pq.push(x);
    while(m--){
        int xd=pq.top();
        pq.pop();
        xd/=2;
        pq.push(xd);
    }
    for(int i=1; i<=n; i++){
        int xd=pq.top();
        pq.pop();
        ans+=xd;
    }
    cout<<ans;
}

Measured memory_bytes: 1400
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> a(N);
  for (int i=0; i<N; i++) cin >> a[i];

  cout << (N-1)/(K-1) + (((N-1)%(K-1))? 1: 0) << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int MAXN=5e5+5;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int n,q,a[MAXN],val[MAXN],lst[MAXN],ans[MAXN];vector<pint>Q[MAXN];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int k){for(x++;x<=n+1;x+=lowbit(x))val[x]+=k;}
inline int ask(int x){int ans=0;for(x++;x;x-=lowbit(x))ans+=val[x];return ans;}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),q=read();
	Rep(i,1,n)a[i]=read();
	Rep(i,1,q){
		int l=read(),r=read();
		Q[r].push_back(mk(i,l));
	}Rep(i,1,n)add(0,1);
	Rep(i,1,n){
		add(lst[a[i]],-1),lst[a[i]]=i,add(lst[a[i]],1);
		for(auto o:Q[i])ans[o.fir]=ask(n)-ask(o.sec-1);
	}Rep(i,1,q)cout<<ans[i]<<"\n";
	return 0;
}



Measured memory_bytes: 33180
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

long long power(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int lft[200004],rgt[200005];

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    stack<pair<int,int> >s;
    for(int i=1;i<=n;i++)
    {
        lft[i]=1;
        rgt[i]=n;
    }
    for(int i=1;i<=n;i++)
    {
        while (!s.empty())
        {
            if(s.top().first<a[i])
                break;
            else
            {
                rgt[s.top().second]=i-1;
                s.pop();
            }
        }
        s.push({a[i],i});        
    }

        while (!s.empty())
        {
            s.pop();
        }

    for(int i=n;i>=1;i--)
    {
        while (!s.empty())
        {
            if(s.top().first<a[i])  
                break;
            else
            {
                lft[s.top().second]=i+1;
                s.pop();
            }
        }
        s.push({a[i],i});        
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int x=rgt[i]-i+1;
        int y=i-lft[i]+1;
        ans+=x*y*a[i];
    }
    cout<<ans;


} 
    
 


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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// chmax, chmin
template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

void solve(const long long N, const long long K, const std::vector<long long> a, const bool f = false) {
    deque <pair<int, int>> bs;
    for (int i = 0; i < a.size(); i++) bs.push_back({a[i], i});

    vector<int> ans;
    long long KK = K;
    auto use = [&](int x) {
//        cout << x << " u" << endl;
        if (bs[x].first == 0) {
            assert(0);
        }
        bs[x].first--;
        ans.push_back(bs[x].second);
    };

    bool dp[52][52] = {};
    pair<int, int> prv[52][52];

    dp[0][K] = true;
    for (int i = 0; i < N; i++) {
        for (int x = 0; x <= K; x++) {
            for (int j = 0; j <= min<int>(x, (K + 1) / 2); j++) {
                if (bs[i].first - 1 >= K - j) {
                    if (dp[i][x]) {
                        dp[i + 1][x - j] |= dp[i][x];
                        prv[i + 1][x - j] = {i, x};
                    }

                }
            }
        }
    }
    if (!dp[N][0]) {
        cout << -1 << endl;
        return;
    }

    auto use_all_except_for = [&](int x, int y) {
        for (int i = 0; i < N; i++) {
            if (i != x && i != y) {
                use(i);
            }
        }
    };

    {
        int i = N;
        int x = 0;

        vector <pair<int, int>> assign;
        while (i > 0) {
            auto p = prv[i][x];
            assign.push_back({p.second - x, i - 1});
            i = p.first;
            x = p.second;
        }

        int prv = -1;
        vector<int> ord;
        while (true) {
            sort(assign.rbegin(), assign.rend());
            if (assign.front().first == 0) {
                break;
            }
            for (int i = 0; i < assign.size(); i++) {
                if (assign[i].second == prv) continue;
                ord.push_back(assign[i].second);
                assign[i].first--;
                prv = assign[i].second;
                break;
            }
        }
//        for (auto o : ord) cout << o << " <<< " << endl;

        use_all_except_for(ord.front(), -1);
//        cout << "===" << endl;
        use(ord.front());
        for (int i = 0; i + 1 < ord.size(); i++) {
            use_all_except_for(ord[i], ord[i + 1]);
            use(ord[i + 1]);
//            cout << "====" << endl;
        }
        use_all_except_for(ord.back(), -1);

    }

    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] + 1 << " ";
    cout << endl;
    exit(0);

}

int main() {
    long long N;
    scanf("%lld", &N);
    long long K;
    scanf("%lld", &K);
    std::vector<long long> a(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &a[i]);
    }
    solve(N, K, std::move(a));
    return 0;
}


Measured memory_bytes: 256
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

X = I()

if 400 <= X <= 599:
    print('8')
elif 600 <= X <= 799:
    print('7')
elif 800 <= X <= 999:
    print('6')
elif 1000 <= X <= 1199:
    print('5')
elif 1200 <= X <= 1399:
    print('4')
elif 1400 <= X <= 1599:
    print('3')
elif 1600 <= X <= 1799:
    print('2')
elif 1800 <= X <= 1999:
    print('1')
else:
    pass

Measured memory_bytes: 65616