akhauriyash/Code-Regression huggingface dataset:
import math
A, B, H, M = map(int, input().split())

a = (H / 6 + M / 360) * math.pi
ax = math.cos(a) * A
ay = math.sin(a) * A

b = M / 30 * math.pi
bx = math.cos(b) * B 
by = math.sin(b) * B

print(math.sqrt((ax - bx)**2 + (ay - by)**2))


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

/* メモリ食い過ぎ注意 */
#define int long long

typedef long long ll;

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

signed main()
{
    int i, n;
    cin >> n;

    for (i = n; i < 1000; i++)
    {
        int i1 = (i / 1) % 10;
        int i2 = (i / 10) % 10;
        int i3 = (i / 100) % 10;
        if (i1 == i2 && i2 == i3)
            break;
    }
    cout << i << endl;
}


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

using namespace std;

int main()
{
    string s;
    cin >> s;
    int cnt = -1;
    for(int i = 0;i < s.length();i++){
        if(s[i] == 'C'){
            cnt = i;
            break;
        }
    }
    if(cnt == -1){
        cout << "No\n";
        return 0;
    }else {
        for(int i = cnt;i < s.length();i++){
            if(s[i] == 'F'){
                cnt = -1;
                break;
            }
        }
        if(cnt!=-1){
            cout << "No\n";
        }else cout << "Yes\n";
    }
    return 0;
}


Measured memory_bytes: 256
from fractions import gcd

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
    
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct


A, B = map(int, input().split())

g = gcd(A, B)

result_set = set(factorize(g))

print(len(result_set) + 1)



Measured memory_bytes: 64876
#include<functional>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <string.h>
#include <string>
#include <math.h>
#include <time.h>
#include <vector>
#include <queue>
#include<stack>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
vector<vector<int>> g;
int n, m;
int dp[100005];
int calc(int u) {
	int &ret = dp[u];
	if (ret != 0)
		return ret;
	for (int v = 0; v < g[u].size(); ++v)
		ret = max(ret, 1 + calc(g[u][v]));
	return ret;
}

int main() {
	//freopen("src.txt", "r", stdin);
	memset(dp, 0, sizeof dp);
	cin >> n >> m;
	g.resize(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		--u; --v;
		g[u].push_back(v);
	}
	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans = max(ans, calc(i));
	cout<< ans << endl;
	return 0;
}

Measured memory_bytes: 7424
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,l;
    cin>>n>>l;
    string s[105];
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    sort(s,s+n);
    for(int i=0;i<n;i++)
    {
        cout<<s[i];
    }
}


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

#define fir first
#define sec second
using namespace std;
typedef long long LL;

template <typename T> inline bool cmin(T & a, const T & b) { return a > b ? a = b, 1 : 0;}
template <typename T> inline bool cmax(T & a, const T & b) { return a < b ? a = b, 1 : 0;}
int inp() {
	int x = 0, f = 1;char ch;
	for(ch = getchar(); !isdigit(ch); ch = getchar())
		if(ch == '-') f = -1;
	for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	return x * f;
}

const int MaxN = 101234, MaxM = 201234;

struct edge{
	int to, nxt, v;
}e[MaxM]; int cnt, lst[MaxN];
void ins(int a, int b, int c){
	e[++cnt] = (edge){b, lst[a], c}; lst[a] = cnt;
}
void lnk(int a, int b, int c){
	ins(a, b, c);
	ins(b, a, c);
}

LL ans;
int n, siz[MaxN], f[MaxN], hug[MaxN], c1, c2, G;
void dfs(int x, int fa){
	siz[x] = 1;
	for(int i = lst[x], b; b = e[i].to, i; i = e[i].nxt){
		if(b == fa) continue;
		dfs(b, x);
		siz[x] += siz[b];
		ans += ((LL) e[i].v * min(siz[b], n - siz[b])) << 1;
		cmax(hug[x], siz[b]);	
	}
	cmax(hug[x], n - siz[x]);
	cmin(G, hug[x]);
} 
int main() {
	int i; 
	n = G = inp();
	for(i = 1; i < n; i++){
		int u = inp(), v = inp(), w = inp();
		lnk(u, v, w);
	}
	
	dfs(1, 0);
	for(i = 1; i <= n; i++)
		if(hug[i] == G)
			if(c1) c2 = i; else c1 = i;
	if(c2){
		for(i = lst[c1]; i; i = e[i].nxt) if(e[i].to == c2)
			ans -= e[i].v;
	}
	else{
		int mn = ~0U >> 1;
		for(i = lst[c1]; i; i = e[i].nxt) cmin(mn, e[i].v);
		ans -= mn;
	}
	cout << ans;
	return 0;
}




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

const int mn=2e5+7,mod=1e9+7;
long long a[mn],sum[mn],ans;
int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {scanf("%lld",a+i);sum[i]=(sum[i-1]+a[i])%mod;}
    for(int i=1;i<=n;++i) ans=(ans+a[i]*(sum[n]-sum[i]+mod)%mod)%mod;
    cout<<ans;
}

Measured memory_bytes: 6780
#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int R,G;
int main(){
    read(R),read(G);
    cout<<G*2-R<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

bool dp[7][100505];

int main(void){
	memset(dp,false,sizeof(dp));
	int x;
	scanf("%d",&x);
	dp[0][0]=true;
	for(int i=0;i<6;i++){
		int c=100+i;
		for(int j=0;j<=x;j++){
			dp[i+1][j]|=dp[i][j];
			if(dp[i+1][j]){
				dp[i+1][j+c]=dp[i+1][j];
			}
		}
	}
	printf("%d\n",dp[6][x]?1:0);
	return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <cstdio>
#include <cmath>
  
#define PI 3.1415926535
  
using namespace std;
  
int main() {
    int a, b, C;
  
    cin >> a >> b >> C;
  
  
    double S = a*b*sin(C / 180.0 * PI) / 2;
    double L = sqrt(a*a + b*b - 2 * a*b*cos(C / 180.0 * PI)) + a + b;
    double h = 2 * S / a;
  
    printf("%.4f\n", S);
    printf("%.4f\n", L);
    printf("%.4f\n", h);
  
    return 0;
}

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

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	vector<string> S(N);
	set<string> st;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
		int n = S[i].size();
		for (int l = 0; l <= 4; l++) {
			for (int j = 0; j + l <= n; j++) {
				st.insert(S[i].substr(j, l));
			}
		}
	}
	string s = "a";
	for (s[0] = 'a'; s[0] <= 'z'; s[0]++) {
		if (st.count(s) == 0) {
			cout << s << endl;
			return 0;
		}
	}
	s = "aa";
	for (s[0] = 'a'; s[0] <= 'z'; s[0]++) {
		for (s[1] = 'a'; s[1] <= 'z'; s[1]++) {
			if (st.count(s) == 0) {
				cout << s << endl;
				return 0;
			}
		}
	}
	s = "aaa";
	for (s[0] = 'a'; s[0] <= 'z'; s[0]++) {
		for (s[1] = 'a'; s[1] <= 'z'; s[1]++) {
			for (s[2] = 'a'; s[2] <= 'z'; s[2]++) {
				if (st.count(s) == 0) {
					cout << s << endl;
					return 0;
				}
			}
		}
	}
	s = "aaaa";
	for (s[0] = 'a'; s[0] <= 'z'; s[0]++) {
		for (s[1] = 'a'; s[1] <= 'z'; s[1]++) {
			for (s[2] = 'a'; s[2] <= 'z'; s[2]++) {
				for (s[3] = 'a'; s[3] <= 'z'; s[3]++) {
					if (st.count(s) == 0) {
						cout << s << endl;
						return 0;
					}
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 42400
class SumofThreeIntegers:
    def calculate(self, K, S):
        self.counter = 0
        for x in range(K+1):
            for y in range(K+1):
                z = S - x - y
                if z < 0 or K < z:
                    pass
                elif x + y + z == S:
                    self.counter += 1
        return self.counter
            
if __name__ == "__main__":
    K, S = map(int, input().split())
    sti = SumofThreeIntegers()
    res = sti.calculate(K, S)
    print(str(res))


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 20001
#define MCONS 1001

using namespace std;

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    string str; cin >> str;
    int ret = 0;
    int temp = 0;
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == 'A' || str[i] == 'C' || str[i] == 'G' || str[i] == 'T')
            temp += 1;
        else
        {
            ret = max(ret, temp);
            temp = 0;
        }
    }
    ret = max(ret, temp);

    cout << ret << endl;
    return 0;
}




Measured memory_bytes: 256
/// In the name of God
#include <bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
const int maxn = 500 + 10;
int a[maxn][maxn];
bool col[maxn];
int main()
{
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(int j=0; j<n; j++){
            a[i][j] = (s[j] == '#');
            if(a[i][j]) col[j] = 1;
        }
	}
	int bad = 0;
	bool toh = 1;
	int mn = n + 1;
	for(int i=0; i<n; i++){
        int sm = 0;
        for(int j=0; j<n; j++)
            sm += a[i][j];
        int tt = 0;
        for(int j=0; j<n; j++)
            tt += a[j][i];
        bad += (tt != n);
        if(tt) toh = 0;
        if(sm == 0) continue;
        int ned = n - sm + (col[i] == 0);
        mn = min(mn, ned);
	}
    int ans;
    if(toh) ans = -1;
    else ans = mn + bad;
    cout << ans << endl;
}


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

int main() {
   int n;
   cin>>n;
   vector <int>v;
   while(n>0){
       v.push_back(n%10);
       n=n/10;
   }
   int flag=0;
   for(auto it=v.begin();it!=v.end();it++){
       if(*it==7){
           flag=1;
           break;
       }
   }
   if(flag==1) cout<<"Yes"<<endl;
   else if(flag==0) cout <<"No"<<endl;
   return 0;
}


Measured memory_bytes: 3600
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, A = map(int, input().split())
    X = [int(c) - A for c in input().split()]
    d = defaultdict(lambda: 0)

    for x in X:
        d_ = defaultdict(lambda: 0)
        for key in d.keys():
            d_[key + x] += d[key]

        for key in d_.keys():
            d[key] += d_[key]

        d[x] += 1

    return d[0]


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3572
#include <stdio.h>

int main(void) {
  int ans[4], a;
  ans[0] = ans[1] = ans[2] = ans[3] = 0;
  char c[10];
  while(scanf("%d,%s", &a, c) != EOF) {
    if(c[1]) ans[2]++;
    else if(c[0] == 'A') ans[0]++;
    else if(c[0] == 'B') ans[1]++;
    else ans[3]++;
  }
  printf("%d\n%d\n%d\n%d\n", ans[0], ans[1], ans[2], ans[3]);
  return 0;
}


Measured memory_bytes: 2584
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const ll MOD=1e9+7;
const int MAX=1e5+10;
const ll INF=1e18;
const double PI=acos(-1);


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

    int n;
    cin >> n;
    string ans;
    rep(i,n) {
        ans.push_back('A');
        ans.push_back('C');
        ans.push_back('L');
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(j,n) for(int j = 0; j < (n); ++j)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define drep2(j,n) for(int j = (n)-1; j >= 0; --j)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define srep2(j,s,t) for (int j = s; j < t; ++j)
#define srep3(k,s,t) for (int k = s; k < t; ++k)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}

v(ll) p(51);
v(ll) a(51);

ll dfs(int N,ll X) {
  if(N==0) {
    if(X > 0) return 1;
    return 0;
  }
  if(X <= 1 + a[N-1]) return dfs(N-1,X-1);
  return p[N-1] + 1 + dfs(N-1,X-2-a[N-1]);
}

int main() {
  ll N,X;
  cin >> N >> X;
  a[0] = 1;
  p[0] = 1;
  srep(i,1,51) {
    a[i] = 2 * a[i-1] + 3;
    p[i] = 2 * p[i-1] + 1;
  }
  cout << dfs(N,X) << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;


public class Main{
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        String n = sc.next();
        int carry = 0;
        int res = 0;
        for(int i=n.length()-1;i>=0;i--){
            int a = n.charAt(i)-48;
            if(carry==1){
                if(a == 9){
                    a = 0;
                }
                else{
                    a++;
                    carry = 0;
                }
            }
            if(a<5){
                res += a;
            }
            else if(a==5){
                if(i==0 || n.charAt(i-1)-48<5){
                    carry = 0;
                    res += 5;
                }
                else{
                    carry = 1;
                    res += 5;
                }
            }
            else{
                res += 10 - a;
                carry = 1;
            }
        }
        res += carry;

        out.println(res);
        out.flush();
    }

}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}


Measured memory_bytes: 29780
#include <bits/stdc++.h>
using namespace std;
#define lint long long
//#define P pair<int, int>

lint Len(lint a, lint b, lint x){
    return abs(a - b) + abs(b - x);
}

int main(){
    int A, B, Q;
    cin >> A >> B >> Q;
    
    vector<lint> s(A), t(B), x(Q);
    
    for(int i = 0; i < A; ++i){
        cin >> s[i];
    }
    for(int i = 0; i < B; ++i){
        cin >> t[i];
    }
    for(int i = 0; i < Q; ++i){
        cin >> x[i];
    }
    
    
    for(int i = 0; i < Q; ++i){
        auto its = lower_bound(s.begin(), s.end(), x[i]);
        auto itt = lower_bound(t.begin(), t.end(), x[i]);
        lint s1, s2, t1, t2;
        
        s1 = *(max(its - 1, s.begin()));
        s2 = *(min(its, s.end() - 1));
        
        t1 = *(max(itt - 1, t.begin()));
        t2 = *(min(itt, t.end() - 1));
        
        vector<lint> List = {Len(s1, t1, x[i]), Len(s1, t2, x[i]), Len(s2, t1, x[i]), Len(s2, t2, x[i]), Len(t1, s1, x[i]), Len(t1, s2, x[i]), Len(t2, s1, x[i]), Len(t2, s2, x[i])};
        
        cout << *min_element(List.begin(), List.end()) << endl;
    }
}

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

using namespace std;

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

    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < n; i++) {
        cout << s[i] << t[i];
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>

using namespace std;

long long N;
long long h, n, w;

int main()
{
    scanf("%I64d", &N);
    for(h = 1; h <= 3500; h++)
    {
        for(n = 1; n <= 3500; n++)
        {
            long long x = N * h * n;
            long long y = 4 * h * n - h * N - n * N;
            if(y <= 0) continue;
            if(x % y == 0)
            {
                printf("%I64d %I64d %I64d", h, n, x / y);
                return 0;
            }
        }
    }
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

bool s[200050];
bool d[200050];
set<pair<int, int>> e;
int n, m, a, b;

int main() {
  cin >> n >> m;
  rep(i, m) {
    cin >> a >> b;
    e.insert({a, b});
  }

  for (int i = 1; i < n; ++i) {
    if (e.count({1, i}) && e.count({i, n})) {
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}

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

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  if (b - a + 1 >= 2 * k) {
    for (int i = 0; i < k; i++) {
      cout << a + i << endl;
    }
    for (int i = k - 1; i >= 0; i--) {
      cout << b - i << endl;
    }
  } else {
    for (int i = a; i <= b; i++) {
      cout << i << endl;
    }
  }
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

struct DoubleLinkedList {
    struct Node {
        ll prev = -1;
        ll next = -1;

        ll value = -1;
    };

    DoubleLinkedList(ll num) {
        mNodeTbl.resize(num);
        FOR(i, num, 2) {
            mNodeStack.push(i);
        }
        mpFirst = &mNodeTbl[0];
        mpLast = &mNodeTbl[1];

        mpFirst->next = 1;
        mpLast->prev = 0;
    }

    ~DoubleLinkedList() {
    }

    void insert(ll x) {
        ll index = mNodeStack.top();
        mNodeStack.pop();
        Node *pNewNode = &mNodeTbl[index];

        pNewNode->prev = 0;
        pNewNode->next = mpFirst->next;
        pNewNode->value = x;

        mNodeTbl[mpFirst->next].prev = index;
        mpFirst->next = index;
    }

    void eraceIndex(ll x) {
        ll index = mpFirst->next;
        while (index != 1) {
            if (mNodeTbl[index].value == x) {
                erace(index);
                break;
            }
            index = mNodeTbl[index].next;
        }
    }

    void eraceLast() {
        ll index = mpLast->prev;
        erace(index);
    }

    void eraceFirst() {
        ll index = mpFirst->next;
        erace(index);
    }

    void erace(ll index) {
        Node *pNode = &mNodeTbl[index];

        mNodeTbl[pNode->prev].next = pNode->next;
        mNodeTbl[pNode->next].prev = pNode->prev;

        mNodeStack.push(index);
    }

    void print() {
        ll index = mpFirst->next;
        while (index != 1) {
            cout << mNodeTbl[index].value;
            index = mNodeTbl[index].next;
            if (index != 1)
                cout << " ";
        }
        cout << endl;
    }

    Node *mpFirst;
    Node *mpLast;

    vector<Node> mNodeTbl;

    stack<ll> mNodeStack;
};

string S[4] = {"insert", "delete", "deleteLast", "deleteFirst"};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    DoubleLinkedList lst(1000005);
    string com;
    REP(_, N) {
        cin >> com;
        if (com == S[0]) {
            ll x;
            cin >> x;
            lst.insert(x);
        }
        else if (com == S[1]) {
            ll n;
            cin >> n;
            lst.eraceIndex(n);
        }
        else if (com == S[2]) {
            lst.eraceLast();
        }
        else if (com == S[3]) {
            lst.eraceFirst();
        }
    }

    lst.print();
    return 0;
}


Measured memory_bytes: 34492
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,n) for(int i = (a); i < (n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define debug_v(v,N) for(int i=0;i<N;i++) { cout << v[i] << " "; } cout << endl;
#define debug_vv(v,H,W) for(int i=0;i<H;i++) { for(int j=0;j<W;j++) { cout << v[i][j] << " "; } cout << endl; }

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
    int INF = 2000000000;
    int N; cin >> N;
    vi H(N);
    rep(i, N) cin >> H[i];
    vi dp(N, INF);
    dp[0] = 0;
    dp[1] = abs(H[0] - H[1]);
    REP(i, 2, N) {
        dp[i] = min((dp[i - 1] + abs(H[i] - H[i - 1])), (dp[i - 2] + abs(H[i] - H[i - 2])));
    }
    cout << dp[N - 1] << endl;
}

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


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
    long long a,b,c,d,e;
	cin>>d>>e;
		a=d;
		b=e;
		while(b!=0)
		{
			c=a%b;
			a=b;
			b=c;
		}
	     cout<<d*e/a;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int W, H, N; cin >> W >> H >> N;
	int x[110], y[110], a[110];
	for(int i=0; i<N; ++i) cin >> x[i] >> y[i] >> a[i];
	int C[4];
	C[0]=0; C[1]=W; C[2]=0; C[3]=H;
	for(int i=0; i<N; ++i){
	    if(a[i]==1 && C[0]<x[i]) C[0]=x[i]; 
	    if(a[i]==2 && C[1]>x[i]) C[1]=x[i]; 
	    if(a[i]==3 && C[2]<y[i]) C[2]=y[i]; 
	    if(a[i]==4 && C[3]>y[i]) C[3]=y[i]; 
	}
	if(C[0]>=C[1] || C[2]>=C[3]) cout << 0 << endl;
	else cout << (C[1]-C[0])*(C[3]-C[2]) << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int h = sc.nextInt();
		int w = sc.nextInt();


		String list[][] = new String[h][w];
		for(int i=0;i<h;i++){
				String s = sc.next();
			// System.out.println(s);
				if(s.contains("#")){
						for (int j = 0; j < s.length(); j++) {
						list[i][j]= String.valueOf(s.charAt(j));
					}
				}
		}

		for(int i=0;i<w;i++){
			boolean isIn=false;
			for(int j=0;j<h;j++){
				String ss = list[j][i];

			// System.out.print("h" +j + " w"+i + " ");
			// System.out.println(ss);
				if(Objects.nonNull(ss) && ss.contains("#")){
					isIn =true;
				}
			}

			if(!isIn){
				for(int k=0;k<h;k++){
					list[k][i]="";
				}
			}
		}


		for(int i=0;i<list.length;i++){
			for(int j=0;j<list[i].length;j++){
				if(Objects.nonNull(list[i][j])){
					System.out.print(list[i][j]);
				}
			}

				if(Objects.nonNull(list[i][0])){
			System.out.println("");
				}
		}
	}
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define rep(i, a) for (int i=0; i<(a); i++) 
#define ub        upper_bound            // first element >  val(itr)
#define lb        lower_bound            // first element >= val(itr)

#define mp make_pair
#define pb push_back
#define pi 3.141592653589793
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define bitcount(a) __builtin_popcount(a) // count set bits
#define all(x) (x).begin(),(x).end()

const ll MOD = 1e9 + 7;
const int inf = 1e9+9;
const long long INF = 1e18+3;

//to debug 
#define dbg(x) cout << "Line " << __LINE__ << " | " #x ": " << (x) << endl

template<typename T> T gcd(T a,T b){ if(b>a) return gcd(b,a);return b==0?a:gcd(b,a%b); }
template<typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template<typename T> T fast_power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

inline ll mod(ll x,ll n) {if (x < n) return x; if (x >= n) return x - n;}
string IntToString(ll a){ ostringstream temp; temp << a; return temp.str();}
ll findMMI_fermat(ll n,ll M) {ll ans= fast_power(n,M-2,M);return ans;}//i.e In (a/b)%M..it calculates MMI of b wrt M
ll add(ll a,ll b,ll M)  { return ( mod(a,M ) + mod(b,M ))%M;     }
ll sub(ll a, ll b,ll M) { return (mod(a,M ) + M - mod(b,M ))%M;   }
ll mult(ll a,ll b,ll M) { return  ( mod(a,M)*mod(b,M) ) %M ; }
bool isprime(ll a){ if(a==2) {return 1;}if(!(a&1) ) {return 0;}for(ll i=3;i*i<=a;i+=2){if(a%i==0) {return 0;} } return 1;} 

  
               /* -------------------------------Main Code------------------------------- */



int main(){
	FAST;
	int n;cin>>n;
	vector <int> hgt(n);
	for(int i=0;i<n;i++) cin>>hgt[i];
	vector <int> dp(n); //where dp[i] represents min cost of frog reaching from beginning to i'th
	//Base cases
	dp[0] = hgt[0];
	dp[1] = abs(hgt[1] - dp[0]);
	dp[2] = 	min( abs(hgt[2] - hgt[2-2]) , abs(hgt[2] - hgt[2-1]) + dp[1]);
	
	//Rec Cases
	for(int i=3;i<n;i++){
		dp[i] = min(  abs(hgt[i] - hgt[i-2]) + dp[i-2 ], abs(hgt[i] - hgt[i-1]) + dp[i-1] );
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

	

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n, k;
  cin >> n >> k;
  int a[n];
  for (int i = 0; i < n; ++i) cin >> a[i];
  ll sum[n + 1];
  sum[0] = 0;
  for (int i = 0; i < n; ++i) {
    sum[i + 1] = sum[i] + a[i];
  }
  map<ll, ll> mp;
  ll ans = 0;
  for (int i = 0; i <= n; ++i) {
    if (0 <= i - k) {
      mp[(sum[i - k] - (i - k)) % k]--;
    }
    ans += mp[(sum[i] - i) % k];
    mp[(sum[i] - i) % k]++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 15104
from collections import deque

h, w = map(int, input().split())
m = []
cnt_sharp = 0
for i in range(h):
    tmp = input()
    cnt_sharp += tmp.count('#')
    m.append(tmp)

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# print(m)
q = deque([])
seen = [[0 for _ in range(w)] for _ in range(h)]
q.append((0, 0, 0))
road = 0
while q:
    y, x, cnt = q.popleft()
    seen[y][x] = 1
    if y == h - 1 and x == w - 1:
        road = cnt + 1
        break
    for ny, nx in zip(dy, dx):
        if 0 <= y + ny < h and 0 <= x + nx < w:
            if seen[y + ny][x + nx] == 0 and m[y + ny][x + nx] == '.':
                seen[y + ny][x + nx] = 1
                # print(y + ny, x + nx, cnt)
                q.append((y + ny, x + nx, cnt + 1))

if road == 0:
    print(-1)
else:
    print(h * w - road - cnt_sharp)


Measured memory_bytes: 3316
MOD = 10 ** 9 + 7

N, M = map(int, input().split())

f = []
p = 2
while p * p <= M:
    if M % p != 0:
        p += 1
        continue
    c = 0
    while M % p == 0:
        c += 1
        M //= p
    f.append(c)
    p += 1
if M != 1:
    f.append(1)

ans = 1
for i in f:
    c = 1
    for j in range(i):
        c = c * (N + j) // (j + 1)
    ans = ans * c % MOD
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define zy -2147382637
#define bql 2147483647
#define ll long long
#define ull unsigned long long
#define ld long double
#define il inline
#define sz(x) x.size()
#define maxn 100010
#define rp(i, l, r) for (int i = l; i <= r; i++)
#define rb(i, r, l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a<b)return a;else return b;}
ll lowbit(ll x){return x&(-x);}
ll prime(ll x){
   if(x<=1)return false;
   for(int i=2;i<=int(sqrt(x));i++){
	   if(x%i==0)return false;
   }return true;
}
bool cmp(ll a,ll b){return a>b;}
ll gcd(ll a,ll b){ll r;while(b>0){r=a%b;a=b;b=r;}return a;}
ll powmod(ll a,ll b,ll mod) {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;}
inline ll read() {
	char c = getchar(); ll w = 1; ll x = 0;
	while (!isdigit(c))
		(c == '-') && (w = -w), c = getchar();
	while (isdigit(c))
		x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
	x *= w;
}
void fl(){
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
const int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1},
		  dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int main(){
	fast;
	ll n,a,b,c;
	string s;
	cin>>a>>b>>c;
	ll d=a+b+c;
	if(d>=22)cout<<"bust"<<endl;
	else cout<<"win"<<endl;
	return 0;
	return 0; 
}/*『你强归你强，我永不示弱』*/




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, n) for (int i = 1; i < (int)(n+1); i++)
#define rep4(i, s, n) for (int i = (s); i < (int)(n+1); i++)
#define repr(i,n) for (int i = (n-1); i>=0;i--)
#define repr3(i,n) for(int i = (n);i>0;i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
#define INF const ll INF = 1001001001;
#define PI const ld PI = 3.14159265358979323846;



int main() {
   ld W,H,x,y;
   cin>>W>>H>>x>>y;
   cout(10)<<W*H/2<<" ";
   if((x==W/2)&&(y==H/2)){
       cout<<1<<endl;
   }
   else{
       cout<<0<<endl;
   }
}

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

int main() {
  int n, m, ab;
  cin >> n >> m;
  
  vector<int> vec(n);
  
  for (int i = 0; i < 2*m; i++){
    cin >> ab;
    vec.at(ab-1)++;
  }
  
  for (int i = 0; i < n; i++) cout << vec.at(i) << endl;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val h = readLine()?.toLong() ?: return
    val cache = hashMapOf<Long, Long>()
    fun count(h: Long): Long {
        if(h == 1L){
            return 1L
        }
        cache[h]?.let{
            return it
        }
        val c = count(h/2) * 2 + 1
        cache[h] = c
        return c
    }
    println(count(h))
}

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

const long long MOD = 1E9 + 7;

std::string str;
int A[110000], C[110000], Q[110000];
long long p3[110000];

int main () {
	std::ios::sync_with_stdio (0);
	std::cin >> str;
	for (int i = 0; i < str.size (); ++i) {
		if (str[i] == 'A') ++A[i + 1];
		if (str[i] == 'C') ++C[i + 1];
		if (str[i] == '?') ++Q[i + 1];
	}
	for (int i = 1; i <= str.size (); ++i) A[i] += A[i - 1], C[i] += C[i - 1], Q[i] += Q[i - 1];
	p3[0] = 1;
	for (int i = 1; i < 110000; ++i) p3[i] = p3[i - 1] * 3 % MOD;
	long long ans = 0;
	for (int i = 0; i < str.size (); ++i) { 
		if (str[i] == 'B') {
			ans = (ans + 1LL * (A[i] - A[0]) * (C[str.size ()] - C[i + 1]) % MOD * p3[Q[str.size ()]]) % MOD;
			if (Q[str.size ()] >= 1) ans = (ans + 1LL * (Q[i] - Q[0]) * (C[str.size ()] - C[i + 1]) % MOD * (p3[Q[str.size ()] - 1])) % MOD;
			if (Q[str.size ()] >= 1) ans = (ans + 1LL * (A[i] - A[0]) * (Q[str.size ()] - Q[i + 1]) % MOD * (p3[Q[str.size ()] - 1])) % MOD;
			if (Q[str.size ()] >= 2) ans = (ans + 1LL * (Q[i] - Q[0]) * (Q[str.size ()] - Q[i + 1]) % MOD * (p3[Q[str.size ()] - 2])) % MOD;
		} else if (str[i] == '?') {
			if (Q[str.size ()] >= 1) ans = (ans + 1LL * (A[i] - A[0]) * (C[str.size ()] - C[i + 1]) % MOD * (p3[Q[str.size ()] - 1])) % MOD;
			if (Q[str.size ()] >= 2) ans = (ans + 1LL * (Q[i] - Q[0]) * (C[str.size ()] - C[i + 1]) % MOD * (p3[Q[str.size ()] - 2])) % MOD;
			if (Q[str.size ()] >= 2) ans = (ans + 1LL * (A[i] - A[0]) * (Q[str.size ()] - Q[i + 1]) % MOD * (p3[Q[str.size ()] - 2])) % MOD;
			if (Q[str.size ()] >= 3) ans = (ans + 1LL * (Q[i] - Q[0]) * (Q[str.size ()] - Q[i + 1]) % MOD * (p3[Q[str.size ()] - 3])) % MOD;
		}

	}
	std::cout << ans << "\n";
}

Measured memory_bytes: 2512
def main():
  S = str(input())
  s = []
  i = 0
  while i <= len(S)-1:
    if i == len(S)-1:
      s.append(S[i])
      break
    if S[i] == "B" and S[i+1] == "C":
      s.append("D")
      i += 2
    else:
      s.append(S[i])
      i += 1
  ans = 0
  flag = True
  for i in range(len(s)-1, -1, -1):
    if flag and s[i] == "D":
      posi = i
      flag = False
    if not flag and s[i]=="A":
      ans += posi-i
      posi-= 1
    if s[i] == "B" or s[i] == "C":
      flag = True
  print(ans)
  
  
if __name__ == "__main__":
  main()

Measured memory_bytes: 10824
//itp1_topic5_d
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin>>n;
 
  int i = 1;
  while(1){
    int x = i;

    if(x % 3 == 0){
      cout<<" "<<i;
    }
    else {
      while(1){
        if(x % 10 == 3){
           cout<<" "<<i;
           break;
        }
        x /= 10;
        if(x == 0) break;
      }
    }
  
    if(++i > n) break;
  }
  cout<<endl;

  return 0;

}


Measured memory_bytes: 3088
#include <stdio.h>

#define N 10000

int cal(int,int);

int main()
{
  int A,B;
  int num;
  
  scanf("%d %d",&A,&B);

  if(A>B)//B yo ri A ga o o ki i to ki
    {
      A = A % B;
      num = cal(A,B);
    }

  else if(B>A)//A yo ri B ga o o ki i to ki
    {
      B = B % A;
      num = cal(B,A);
    }
  else
    {
      num=A;
    }
printf("%d\n",num);
  
  return 0;
}

int cal(int A,int B)//A ga o o ki i ho u no a ta i
{
  int n[N],num=0;
  int i,j;
  
      for(i=1,j=0;A>=i;i++)//A no ya ku su wo mo to me ru
	{
	  if(A%i==0)
	    {
	      n[j]=i;
	      //printf("%d ",n[j]);
	      j++;
	    }
	}

      for(i=0;B>n[i],i<j;i++)
	{
	  if(B%n[i]==0)
	    {
	      num = n[i];
	    }
	}
      return num;
}



Measured memory_bytes: 2104
#include <iostream>
#include <vector>
using namespace std;
int main(void){
	int a,b,c,d,e,f;
	int itr=0;
	int ansa,ansb;
	double max;
	vector<int> aa,bb;
	cin >> a >> b >> c >> d >> e >> f ;
	ansa=a*100;
	ansb=0;
	for(int i=0;i<=(f/100+1);i++){
		for(int j=0;j<=(f/100+1);j++){
			if((a*i+b*j)<=30){
				aa.push_back(i);
				bb.push_back(j);
				itr++;
			}
		}
	}
	
	for(int i=0;i*c<=f-100;i++){
		for(int j=0;i*c+j*d<=f-100;j++){
			for(itr=0;itr<aa.size();itr++){
				if(aa[itr]*a*100+bb[itr]*b*100+i*c+j*d<=f){
					if((i*c+j*d)/(double)(aa[itr]*a+bb[itr]*b)<=e){
						if((i*c+j*d)*100/(double)(aa[itr]*a*100+bb[itr]*b*100+i*c+j*d)>max){
							ansa=aa[itr]*a*100+bb[itr]*b*100+i*c+j*d;
							ansb=i*c+j*d;
							max=(i*c+j*d)*100/(double)(aa[itr]*a*100+bb[itr]*b*100+i*c+j*d);
						}
					}
				}
			}
		}
	}
	cout << ansa << " " << ansb ;
}		


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int x,y,a,b,c; cin >> x >> y >> a >> b >> c;
	vector<ll> aa(a),bb(b),cc(c);
	for(int i=0;i<a;i++){
		cin >> aa[i];
		//cna[i+1]=cna[i]+aa[i];
	}
	for(int i=0;i<b;i++){
		cin >> bb[i];
		//cnb[i+1]=cnb[i]+bb[i];
	}
	for(int i=0;i<c;i++){
		cin >> cc[i];
		//cnc[i+1]=cnc[i]+cc[i];
	}
	sort(aa.rbegin(),aa.rend());
	sort(bb.rbegin(),bb.rend());
	sort(cc.rbegin(),cc.rend());
	priority_queue<ll> q;
	for(int i=0;i<x;i++){
		q.push(aa[i]);
	}
	for(int i=0;i<y;i++){
		q.push(bb[i]);
	}
	for(int i=0;i<c;i++){
		q.push(cc[i]);
	}
	ll ans=0;
	for(int i=0;i<x+y;i++){
		ans+=q.top();
		q.pop();
	}
	cout << ans << endl;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

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; }

const ll MRINF = 5000000000000000;

int main() {

    ll N, K;
    cin >> N >> K;
    K--;
    vector<ll> A(N);
    REP(i, N){
        cin >> A[i];
    }
    ll ans = (N-1) / K;
    if((N-1) % K != 0)ans++;
    cout << ans << endl;

    

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 3960
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

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

int main()
{
    char c;
    cin >> c;

      if ('a'<=c && 'z'>=c)  c='a';
  else if ('A'<=c && 'Z'>=c) c='A';
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 3592
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
inline bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
inline bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

ll dp[4][3002][3002];
ll v[3002][3002];

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll r, c, K;
  cin >> r >> c >> K;
  rep(i, K){
    ll a, b, p;
    cin >> a >> b >> p;
    a--; b--;
    v[a][b] = p;
  }
  rep(i, 4)rep(j, r)rep(k, c){
    dp[i][j][k] = -INF;
  }
  dp[0][0][0] = 0;
  rep(j, r+1)rep(i, 4)rep(k, c){
    chmax(dp[0][j+1][k], dp[i][j][k]);
    if(i < 3 && v[j][k] > 0) chmax(dp[0][j+1][k], dp[i][j][k]+v[j][k]);
    chmax(dp[i][j][k+1], dp[i][j][k]);
    if(i < 3 && v[j][k] > 0) chmax(dp[i+1][j][k+1], dp[i][j][k]+v[j][k]);
  }
  ll ans = -INF;
  rep(i, 4) chmax(ans, dp[i][r][c-1]);
  print(ans);
}


Measured memory_bytes: 355364
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
cin.tie(0);
ios::sync_with_stdio(false);
}
int abct(string &s){
  int res = 0;
  int now = 0;
  while(now<(int)s.size()&&((now = s.find("AB",now)) != -1)){
    res++;
    now+=2;
  }
  return res;
}
signed main(){
  int n;
  cin >> n;
  vector<string> s(n);
  int a=0,b=0,id=0;
  int ans = 0;
  REP(i,n) {
    cin >> s[i];
    ans += abct(s[i]);
    if(s[i].back()=='A'&&s[i].front()=='B') id++;
    if(s[i].back()=='A') ++a;
    if(s[i].front()=='B') ++b;
  }
  if(n==1){
    cout << abct(s[0]) << endl;
    return 0;
  }
  if(id==a&&id==b) a--,b--;
  ans += max(min({a,b,n-1}),0);
  cout << ans << endl;
}


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

#define inf 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector <ull> vu;
typedef vector <vector <int>> vvi;
typedef pair <int, int> pi;
typedef vector <pair <int, int>> vpi;

string s;

int n, l, r;

vi ans;

void read() {
  cin >> l >> r;
}

void preSolve() {
  int nr = 0;
  ans.pb(0);
  for(int i = 1; i < n; ++i) {
    if (s[i] == 'C' && s[i - 1] == 'A') {
      ++nr;
    }
    ans.pb(nr);
  }
}
void solve() {
  cout << ans[r - 1] - ans[l - 1] << "\n";
}

int main() {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> n >> t >> s; //please do not forget to comment this if there are no queries
  preSolve();
  while(t) {
    --t;
    read();
    solve();
  }
  return 0;
}


Measured memory_bytes: 1480
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
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...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  cout << n / 2 * (n - n / 2) << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;
int main(){
int N; cin >> N;
  
  multiset<ll> mp;
  
  for(int i = 0; i < N; i++){
    ll a; cin >> a;
    auto itr = mp.lower_bound(a);
    if( itr == mp.begin()){
      mp.insert(a);}
    else{ itr--;
      mp.erase(itr); mp.insert(a);}
  }
  
  cout << (ll) mp.size() << endl; return 0;}

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

using namespace std;

int main()
{
    int M;
    while(cin>>M)
    {
        int a[100000];
        int i;
        for(i=0; i<M; i++)
            cin>>a[i];
        sort(a,a+M);
        int amin=a[0],amax=a[M-1];
        for(i=1; i<M-1; i++)
        {
            if(a[i]>=0)
                amin-=a[i];
            else
                amax-=a[i];
        }
        cout<<amax-amin<<endl;
        amin=a[0];
        amax=a[M-1];
        for(i=1; i<M-1; i++)
        {
            if(a[i]>=0)
            {
                cout<<amin<<' '<<a[i]<<endl;
                amin-=a[i];
            }
            else
            {
                cout<<amax<<' '<<a[i]<<endl;
                amax-=a[i];
            }
        }
        cout<<amax<<' '<<amin<<endl;
    }
    return 0;
}


Measured memory_bytes: 2304