akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 2010
int gcd(int a,int b)
{
	while(b)
	{
		int t=a;a=b;b=t%b;
	}
	return a;
}
int a[MAXN],g[MAXN][MAXN],du[MAXN],vis[MAXN],n;
vector<int>G[MAXN];
void dfs(int u)
{
	vis[u]=1;
	for(int i=1;i<=n;i++)
		if(!vis[i]&&g[u][i])
		{
			G[u].push_back(i);
			du[i]++;
			dfs(i);
		}
}
priority_queue<int>Q;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(gcd(a[i],a[j])!=1)
				g[i][j]=g[j][i]=1;
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		if(!du[i])
			Q.push(i);
	while(!Q.empty())
	{
		int u=Q.top();Q.pop();
		printf("%d ",a[u]);
		for(int i=0;i<G[u].size();i++)
			Q.push(G[u][i]);
	}
}


Measured memory_bytes: 16256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<utility>
using namespace std;
int n,a[10][10],suma[10],kolona[10];   string str;
int main()
{
    for (int i=1;i<=3;i++)
    for (int j=1;j<=3;j++)
    {
        scanf("%d",&a[i][j]);
        suma[i]+=a[i][j];
        kolona[j]+=a[i][j];
    }
    int temp1 = suma[1]-suma[3];
    int temp2 = suma[2]-suma[3];
    int temp3 = suma[3]-suma[1];

    int cnt1 = kolona[1]-kolona[2];
    int cnt2 = kolona[2]-kolona[3];
    int cnt3 = kolona[3]-kolona[1];

    if (temp1%3==0&&temp2%3==0&&temp3%3==0&&cnt1%3==0&&cnt2%3==0&&cnt3%3==0)cout<<"Yes"<<endl;
    else    cout<<"No"<<endl;


return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> primes;
    queue<int> nums;
    for (int i = 2; i <= 55555; i++) {
        nums.push(i);
    }
    while (!nums.empty()) {
        int num = nums.front();
        primes.push_back(num);
        nums.pop();
        nums.push(num);
        while (nums.front() != num) {
            if (nums.front() % num != 0) {
                nums.push(nums.front());
            }
            nums.pop();
        }
        nums.pop();
    }
    int i = 0;
    while (n > 0) {
        if (primes[i] % 5 == 1) {
            cout << primes[i] << " ";
            n--;
        } 
        i++;
    }
    cout << endl;
}

Measured memory_bytes: 512
while True:
    
    H,W=map(int, input().split())
    
    if H==0 and W==0:
        break
    i=1

    a="#"
    b="."
    while i<=H:
        j=1
        while j<=W:
            if j%2==0:
                print(b, end="")
            else:
                print(a, end="")
            j+=1
        print()
        i+=1
        a,b=b,a
    print()


Measured memory_bytes: 7004
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, m;
    cin >> n >> m;
    int q;
    cin >> q;
    vector<int> A(q), B(q), C(q), D(q);
    for (int i = 0; i < q; ++i) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        A[i]--; B[i]--;
    }
    vector<int> d;
    int ans = 0;
    auto dfs = [&](int cur, int val, auto &&f) -> void {
        if(cur == n){
            int a = 0;
            for (int i = 0; i < q; ++i) {
                if(d[B[i]] - d[A[i]] == C[i]) a += D[i];
            }
            ans = max(ans, a);
            return;
        }
        for (int i = val; i <= m; ++i) {
            d.emplace_back(i);
            f(cur+1, i, f);
            d.pop_back();
        }
    };
    dfs(0, 1, dfs);
    cout << ans << "\n";
    return 0;
}

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

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

using namespace std;

int main() {
  long long N, K;
  cin >> N >> K;
  N %= K;
  cout << min(abs(N - K), N) << endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)

int main() {
    int n; cin >> n;
    vector<string> s(n);
    REP(i, n) cin >> s[i];
    sort(s.begin(), s.end());

    string tmp = s[0];
    int count = 1;
    REP(i, n) {
        if (s[i] != tmp) {
            tmp = s[i];
            ++count;
        }
    }

    cout << count << endl;

    return 0;
}

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

int main() {
	int n,i,ans=0;
	cin >> n;
	vector<int> a(n),b(n,0);
	for(i=0; i<n; i++){
		cin >> a[i];
		a[i]--;
	}
	i=0;
	while(i!=1){
		if(b[i]>0){
			cout << -1; return 0;
		}
		b[i]++;
		i=a[i];
		ans++;
	}
	cout << ans;
}

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

using namespace std;


int n;
vector<int> a;

int check(int mid){
    vector<int> b = a;
    for(int i = 0; i < n; i++){
        b[i] -= mid;
        b[(i + n - 1) % n] -= mid;
        mid = b[i];
    }
    if(b[n - 1] > 0) return 1;
    return 0;
}

int main(){
    cin >> n;
    a.resize(n);
    for(auto&& i : a){
        cin >> i;
    }
    int start = 0, end = min(a[0], a[n - 1]) + 1;
    while(start < end){
        int mid = (start + end) / 2;
        int score = check(mid);
        if(score == 0){
            end = mid;
        }
        if(score == 1){
            start = mid + 1;
        }
    }
    for(int i = 0; i < n - 1; i++){
            cout << start * 2 << " ";
            start = a[i] - start;
    }
    cout << start * 2 << "\n";
}

Measured memory_bytes: 2040
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]

s = [0]*(n+1)
t = [0]*(n+1)
for i in ab:
  if i[0] == 1:
    s[i[1]] = 1
    
for i in ab:
  if i[1] == n:
    t[i[0]] = 1

for i in range(2,n):
  if s[i] == 1 and t[i] == 1:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")
  

  

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

long long n, W, dp[105][100005], w[105], v[105], ans;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> W;
    for(int i=1; i<=n; i++)
        cin >> w[i] >> v[i];

    for(int i=0; i<=n; i++)
        for(int j=0; j<=100000; j++)
            dp[i][j] = 1e18;
    dp[0][0] = 0;

    for(int i=1; i<=n; i++)
        for(int j=0; j<=100000; j++) {
            if(j>=v[i]) {
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
            }
            else dp[i][j] = dp[i-1][j];
        }
    for(int i=0; i<=100000; i++) {
        //cout << dp[n][i] << endl;
        if(dp[n][i]<=W) ans = i;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 80128
#include <stdio.h>
#include <iostream>
#include <string.h>

using namespace std;

int main(){
    string name;

    // cout << "Please input your name.\n>>";
    cin >> name;

    if(3 <= name.length() && name.length() <= 20){
        // cout << "Your name is [" << name << "].\n";
        string nickname;
        nickname = name.substr(0,3);
        cout << nickname << "\n";
    } else {
        cout << "Your name is invalid data...\n";
        return 0;
    }    
}

Measured memory_bytes: 3088
#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
input:
11
7
8
9
10
11
12
13
14
15
16
17

output:
4
"""

import sys
import math


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    i = 3
    n_sqrt = math.sqrt(n)
    while i <= n_sqrt:
        if not n % i:
            return False
        i += 2
    return True


def solve(_c_list):
    cnt = 0
    for ele in _c_list:
        if is_prime(ele):
            cnt += 1
    return cnt


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_num = int(_input[0])
    c_list = list(map(int, _input[1:]))
    ans = solve(c_list)
    print(ans)

Measured memory_bytes: 8640
S = input()


def f(index, cur):
    if index == 4:
        if eval(cur) == 7:
            print(cur + '=7')
            return True
        return False

    for a in ['-', '+']:
        if f(index + 1, cur + a + S[index]):
            return True
    return False


f(1, S[0])


Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdint.h>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29) 
#define MAX_N 101
#define MAX_M 101
#define MAX_Damage 1000005
using namespace std;

int N,M;
int HP[MAX_N];
vector<int> MP[2],Damage[2];
bool Target[MAX_M];//false -> Single, true -> All
uint64_t dp[2][MAX_Damage];

int main()
{
  while(cin >> N,N)
    {
      rep(i,N)cin >> HP[i];
      cin >> M;
      string Name,target;
      int mp,damage;
      rep(i,2)MP[i].clear(),Damage[i].clear();
      rep(i,M)
	{
	  cin >> Name >> mp >> target >> damage;
	  if(damage == 0)continue;
	  if(target[0] == 'S')
	    {
	      Target[i] = 0;
	      MP[0].push_back(mp),Damage[0].push_back(damage);
	    }
	  else
	    {
	      Target[i] = 1;
	      MP[1].push_back(mp),Damage[1].push_back(damage);
	    }
	}

      rep(i,2)rep(j,MAX_Damage)dp[i][j] = inf;
      dp[0][0] = dp[1][0] = 0;

      rep(i,2)rep(j,MP[i].size())rep(k,MAX_Damage)
	{
	  if(dp[i][k] == inf || k+Damage[i][j] >= MAX_Damage)continue;
	  dp[i][k+Damage[i][j]] = min(dp[i][k+Damage[i][j]],
				      dp[i][k] + MP[i][j]);
	}
      
      rep(i,2)for(int j=MAX_Damage-2;j>=0;j--)dp[i][j] = min(dp[i][j],dp[i][j+1]);

      uint64_t ans = inf;
      rep(i,MAX_Damage)//All
	{
	  if(dp[1][i] == inf)continue;
	  uint64_t cnt = dp[1][i];
	  bool ok = true;
	  rep(j,N)//Single
	    {
	      if(HP[j]-i <= 0)continue;
	      if(dp[0][HP[j]-i] == inf)
		{
		  ok = false;
		  break;
		}
	      cnt += dp[0][HP[j]-i];
	    }
	  if(!ok)continue;
	  ans = min(ans,cnt);
	}

      int mex = -inf;
      uint64_t cnt = 0;
      rep(i,N)//Single
	{
	  mex = max(mex,HP[i]);
	  cnt += dp[0][HP[i]];
	}
      ans = min(ans,cnt);
      ans = min(ans,dp[1][mex]);//All
      cout << ans << endl;

    }
  return 0;
}

Measured memory_bytes: 16852
#include<cstdio>
using namespace std;

int main(){
  int n,m,a,b,comb;
  bool g[30][30],f,flag,vis[30];

  while(scanf("%d%d",&n,&m) !=EOF , n||m){
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)g[i][j] = 0;
    for(int i=0;i<m;i++){
      scanf("%d%d",&a,&b);
      g[a][b] = g[b][a] = 1;
    }

    if(n<=0)return 0;
    else{
      for(int num=1;num<=n;num++){
	comb = (1<<num)-1;
	flag = 1;
	while(flag && comb < (1<<n)){
	  for(int i=0;i<n;i++)vis[i] = 0;

	  for(int i=0;i<n;i++){
	    if( (comb>>i)&1){
	      vis[i] = 1;
	      for(int j=0;j<n;j++){
		if(g[i][j])vis[j] = 1;
	      }
	    }
	  }
	  bool f = 1;
	  for(int i=0;i<n;i++)f &= vis[i];
	  if(f){
	    flag = 0;
	    printf("%d\n",num);
	    break;
	  }
	  int x = comb & -comb, y = comb + x;
	  comb = ( ( (comb & ~y) /x ) >> 1) | y;
	}
	if(!flag)break;
      }
    }
  }
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int N,M;

int s,t;

struct edge{
  int to;
  i64 idx;
};

vector<edge> G[101010];

vector<i64> A(101010);
vector<i64> B(101010);

vector<i64> dijkstra(int s,vector<i64>& cost){
  vector<i64> dist(101010,1e18);
  dist[s] = 0;
  using P = pair<i64,i64>;
  priority_queue<P,vector<P>,greater<P>> que;
  que.push({dist[s],s});

  while(!que.empty()){
    int v = que.top().second;
    i64 d = que.top().first;
    que.pop();
    if(dist[v] < d) continue;

    for(auto & e : G[v]){
      if(dist[e.to] > dist[v] + cost[e.idx]){
        dist[e.to] = dist[v] + cost[e.idx];
        que.push({dist[e.to],e.to});
      }
    }
  }
  return dist;
}
int main(){
  cin >> N >> M >> s >> t;
  rep(i,0,M - 1){
    int u,v;
    cin >> u >> v >> A[i] >> B[i];
    G[u].push_back({v,i});
    G[v].push_back({u,i});
  }

  auto money = dijkstra(s,A);
  auto snuuk = dijkstra(t,B);

  i64 ans = 0;
  vector<i64> re;
  i64 base = 1e15;

  for(int i = N;i >= 1;i--){
    re.push_back(ans = max(ans , base - money[i] - snuuk[i]));
  }

  reverse(all(re));

  for(auto x : re){
    cout << x << endl;
  }
}


Measured memory_bytes: 14204
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		if(br.readLine( ).matches("^((dreamer)|(eraser)|(dream)|(erase))+$") ){
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 38580
import java.util.Scanner;
public class Main {
    public static void main(String args[]) {
        String answer = "YES";
        Scanner s = new Scanner(System.in);
        int a = Integer.parseInt(s.next());
        int b = Integer.parseInt(s.next());
        int c = Integer.parseInt(s.next());
        if(a == b || b == c || c == a){
            if( a == b && b == c ){
                System.out.println("No");
                return;
            }
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 22356
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define repn(i, x) for (int i = 1; i <= (int)(x); i++)
#define repr(i, x) for (int i = ((int)(x) - 1); i >= 0; i--)
#define reprn(i, x) for (int i = ((int)(x)); i > 0; i--)
#define all(x) (x).begin(),(x).end()
typedef long long int64;
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
typedef pair<int, int> P;
map<P, int> freq;

int64 gcd(int64 a, int64 b) {
    return b != 0 ? gcd(b, a % b) : a;
}

int64 lcm(int64 a, int64 b) {
		return a / gcd(a, b) * b;
}

//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

P f(int x) {
	int a = x % 10;
	int b = 0;
	while (x > 0) {
		b = x;
		x /= 10;
	}
	return P(b, a);
}

void solve() {
		int n; cin >> n;
		for (int i = 1; i <= n; ++i) {
			P p = f(i);
			freq[p]++;
		}
		int64 ans = 0;
		for (int i = 1; i <= n; ++i) {
			P p = f(i);
			P q(p.second, p.first);
			ans += freq[q];
		}
		cout << ans << endl;
    return;
}

int main() {
    solve();
    return 0;
}



Measured memory_bytes: 256
#include <fstream>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <random>

using namespace std;

#define INT_MAX_VALUE 2147483647
#define LONG_LONG_MAX_VALUE 9223372036854775807
#define ll long long

template <class T>
T mymax(T a,T b){
    if(a>=b) return a;
    return b;
}
template <class T>
T mymin(T a,T b){
    if(a<=b) return a;
    return b;
}

ll gcd(ll a, ll b){
    if(a<b){
        swap(a,b);
    }
    while(b){
        ll r = a%b;
        a=b;
        b=r;
    }
    return a;
}

ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}

struct XX{
    ll a;
    int b;
    int j;
    int i;
};

class xxGreater {
public:
    bool operator()(const XX& riLeft, const XX& riRight) const {
        //第2条件
        if((riLeft.a) == (riRight.a)){
            return riLeft.i < riRight.i;//<:昇順(小さいものから順番)、>:降順(大きいものから順番)
            //プライオリティキューの場合は > で、top()すると値の小さいものがとれる
        }
        //第1条件
        return (riLeft.a) < (riRight.a);
    }
};


//map<long long,long long> prime_f(long long n){
//    map<long long,long long>res;
//    for(int i=2;i*i<=n;i++){
//        while(n%i==0){
//            ++res[i];
//            n/=i;
//        }
//    }
//    if(n!=1)res[n]=1;
//    return res;
//}


int main(int argc, const char * argv[])
{
    //scanf("%s",S);
    //scanf("%d",&N);
    //scanf("%lld %lld",&target1,&target2);
    //sscanf(tmp.c_str(),"%dd%d%d",&time[i], &dice[i], &z[i]);
    //getline(cin, target);
    //ifstream ifs( "1_06.txt" );//テスト用
    //ifs >> a;
    //ここから
    
    //入力高速化
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    if(s.size()==1){
        cout << s << endl;
        return 0;
    }
    int ans=0;
    for(int i=0;i<s.size()-1;i++){
        ans+=9;
    }
    ans+=(*s.substr(0,1).c_str()-'0')-1;
    
    int ans2=0;
    for(int i=0;i<s.size();i++){
        ans2+=(*s.substr(i,1).c_str()-'0');
    }
    cout << max(ans,ans2) << endl;

    //ここまで
    //cout << "ans" << endl;改行含む
    //printf("%.0f\n",ans);//小数点以下表示なし
    //printf("%.7f\n",p);
    
    return 0;
}



Measured memory_bytes: 256
import java.io.*;

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		for (int i = 1; i <= n; i++) {
			// CHECK_NUM  3??§???????????????
			if (i%3 == 0) {
				System.out.print(" " + i);
				continue;
			}
			
			// INCLIDE 3  ??°??????3?????????
			for (int tmp = i; tmp > 0; tmp/=10) {
				if (tmp % 10 == 3) {
					System.out.print(" " + i);
					break;
				}
			}
		}
		
		System.out.println();
	}
}

Measured memory_bytes: 26756
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
const int MOD = 1e9 + 7;

int N, M, K, Q, W, H, R, C;
string S;

int main() {
    cin >> N;
    vector<ll> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    for (int i = 0; i < N; i++) {
        cin >> B.at(i);
    }

    priority_queue<pair<ll, ll>> que;
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) que.push(make_pair(B[i], i));
        if (B[i] < A[i]) {
            cout << -1 << endl;
            return 0;
        }
    }

    ll cnt = 0;
    while (!que.empty()) {
        pair<ll, ll> p = que.top();
        que.pop();
        ll b = p.first;
        int id = p.second;
        ll a = B[(N - 1 + id) % N];
        ll c = B[(1 + id) % N];
        if (b > a + c) {
            int low = b % (a + c);
            if (A[id] >= low) {
                if ((b - A[id]) % (a + c) == 0) {
                    cnt += (b - A[id]) / (a + c);
                    B[id] = A[id];
                } else {
                    cout << -1 << endl;
                    return 0;
                }
            } else {
                cnt += (b - low) / (a + c);
                B[p.second] = low;
                que.push(make_pair(low, id));
            }
        } else {
            cout << -1 << endl;
            return 0;
        }
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 9200
/*
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<limits.h>
#include<cmath>
#include<queue>
#include<stack>

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

#define rep(i,n) for(ll i = 0; i < (ll)n; i++)
#define swap(a,b) a^=b;b^=a;a^=b;
#define chmax(a,b) {if(a < b) a = b;}
#define chmin(a,b) {if(a > b) a = b;}

using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

ll factor(ll x) {
	ll ret = 1;
	ll tmp = 0;
	for (ll p = 2;;p++) {
		if (x == 1) {
			ret *= tmp + 1;
			break;
		}
		if (x % p == 0) {
			tmp += 1;
			x /= p;
			p--;
			continue;
		}
		ret *= tmp + 1;
		tmp = 0;
	}
	return ret;
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//Program Start

	ll N;
	cin >> N;
	ll ans = 0;

	for (ll i = 1; i <= N; i++) {
		ll ret = factor(i);
		ll tmp = ret;
		ans += i * tmp;
	}

	cout << ans << endl;



EndPoint:;

	//Program End
#ifndef DEBUG
	system("pause");
#endif // !DEBUG

	return 0;
}


*/

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<limits.h>
#include<cmath>
#include<queue>
#include<stack>

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

#define rep(i,n) for(ll i = 0; i < (ll)n; i++)
#define swap(a,b) a^=b;b^=a;a^=b;
#define chmax(a,b) {if(a < b) a = b;}
#define chmin(a,b) {if(a > b) a = b;}

using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//Program Start	

	int N;
	cin >> N;

	if (N % 1000 == 0) {
		cout << "0" << endl;
	}
	else {
		cout << 1000 - (N % 1000) << endl;
	}
\
EndPoint:;

	//Program End
#ifndef DEBUG
	system("pause");
#endif // !DEBUG

	return 0;
}




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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

const int CASES = 2;

void solve(){
    ll N; cin >> N;
    ll ans = 0;
    ll res = 0;
    for(int i = 0; i < N; ++i){
        ll a; cin >> a;
        ll tmp = min(a, res);
        ans += tmp;
        a -= tmp;

        ans += a/2;
        res = a%2;
    }
    cout << ans << endl;
    return;
}

int main() {
    #ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
    #else

    solve();

    #endif
    return 0;
}



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


ll fact(ll n){
	if(n==1) return 1;
	else return (n * fact(n-1))%MOD;
}
int n;
int main(){
	cin >> n;
	cout << fact(n)  << endl;
	return 0;
}


Measured memory_bytes: 1792
# -*- coding: utf-8 -*-

def get_input() -> list:
    """
    標準入力を取得する.

    Returns:\n
        list: 標準入力
    """
    A = list(map(int, input().split()))

    return A


def main(A: list) -> None:
    """
    メイン処理.

    Args:\n
        A (list): 整数列(1 <= A_i <= 100)
    """
    # 求解処理
    ans = max(A) - min(A)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    A = get_input()

    # メイン処理
    main(A)


Measured memory_bytes: 9148
import sys
sys.setrecursionlimit(10**9)

N, M, Q = map(int, input().split())
abcds = []
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    a, b = a-1, b-1
    abcds.append((a, b, c, d))

def check():
    score = 0
    for a, b, c, d in abcds:
        if As[b]-As[a] == c:
            score += d
#    print(As, score)
    return score

def dfs(i, mx):
    if i == N:
        return check()
    score = 0
    for x in range(mx, M+1):
        As[i] = x
        s = dfs(i+1, x)
        if s > score:
            score = s
    return score

As = [0] * N
ans = dfs(0, 1)

print(ans)


Measured memory_bytes: 9228
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
#define vi vector<int>
#define vl vector<long long>
#define vii vector<vector<int>>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{
    int N,Z,W;
    cin >> N >> Z >> W;
    vi a(N);
    in(N,a);
    
    if(N==1) {
        out(abs(a[0]-W));
        return 0;
    }
    
    int ans = 0;
    ans = max(abs(W-a.back()),abs(a[N-1]-a[N-2]));
    
    
    
    out(ans);

    return 0;
}


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

int main(){
    ll x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    ll x3,y3,x4,y4;
    ll diffx = x2-x1;
    ll diffy = y2-y1;
    x3=x2-diffy;
    y3=y2+diffx;
    x4=x3-diffx;
    y4=y3-diffy;
    cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;

}



Measured memory_bytes: 3600
n, q = map(int, input().split())
s = input()
# table = [0] * 100005
table = [0] * n
for i in range(1, n):
    table[i] = table[i - 1]
    if s[i] == "C" and s[i - 1] == "A":
        table[i] += 1

for i in range(q):
    first, last = map(int, input().split())
    print(table[last - 1] - table[first - 1])


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

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

    int n, q, l, r, tmp=0; cin >> n >> q;
    string s; cin >> s;
    vector<int> count_ac(n+2,0);

    for (int i=0; i<s.size()-1; i++){
        if ("AC"==s.substr(i,2)) {
            count_ac[i+2] = tmp + 1;
            tmp = count_ac[i+2];
            i += 1;
        }
    }

    for (int i=1; i<=s.size(); i++) {
        if (count_ac[i]==0) count_ac[i] = count_ac[i-1];
    }

    for (int i=1; i<=q; i++) {
        cin >> l >> r;
        cout << count_ac[r] - count_ac[l] << "\n";
    }


    return 0;
}

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert
#define endl '\n'
#define all(x) x.begin(), x.end()

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
using vvll = vector< vector<ll> >;
using vll = vector<ll> ;
using vb = vector<bool> ;
using pll = pair<ll, ll> ;

const ll maxs = 1e6+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e18;


void pre(){



}

int n;
long k;
int a[maxs];

bool check(ll MAX){
    ll c=0;
    for(int i=1;i<=n;i++){
        if(a[i] > MAX and a[i] > 0)
            break;

        if(a[i] > 0){
            int l = i+1,r=n;
            int res=i;
            while(l<=r){
                int mid = (l+r)/2;
                if(a[i]*1ll*a[mid] <= MAX){
                    res = mid;
                    l = mid+1;
                }else r = mid-1;
            }
            c += res-i;
        }else if(a[i] < 0){
            int l=i+1,r=n;
            int res=n+1;
            while(l<=r){
                int mid = (l+r)/2;
                if(a[i]*1ll*a[mid] <= MAX){
                    res = mid;
                    r = mid-1;
                }else l = mid+1;
            }
            c += n-res+1;
        }else{
            if(MAX >= 0){
                c += n-i;
            }
        }
    }
    return c >= k;
} 

void solve(){

    cin >> n >> k;
    for(int i=1;i<n+1;i++){
        cin >> a[i];
    }
    sort(a+1,a+n+1);
    ll l = -1e18 , r = 1e18;
    ll ans=1e18;
    while(l <= r){
        ll mid = (l+r)/2;
        bool res = check(mid);
        if(res){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << ans << endl;


}

int main(){
    // #ifndef ONLINE_JUDGE
    // freopen("input00.txt","r",stdin);
    // #endif
    IOS;
    pre();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();   
    }
    return 0;
}

Measured memory_bytes: 4396
#include <iostream>

using namespace std;

int main()
{
    int t,flag=0;
    cin>>t;
    int num[t];
    for(int i=0;i<t;i++)
    {
        cin>>num[i];
        if(num[i] != i+1)
        {
            flag +=1;
        }
    }
    if(flag>2)
    {
        cout<<"NO"<<endl;
    }
    else
    {
        cout<<"YES"<<endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
//#include<unordered_map>
#include<string>
#include<cstdlib>
using namespace  std;

int main(){
  //std::string nday; 
  //std::unordered_map<std::string, int>
  //  wd{
  //     {"SUN",7},{"MON",6},{"TUE",5},{"WED",4},{"THU",3},{"FRI",2},{"SAT",1} };
 
  string strn;
  int    n;
  int    max;
  int    sum;
  
  cin >> strn;
  n = std::atoi(strn.c_str());

  max = strn.length();
  sum =0 ;
  for(int i=0; i<max; i++){
    sum += (strn[i] - '0');
  }
  
  if( (n % sum) == 0 ){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
	char X,Y;
	cin >> X >> Y;
	if(X < Y){
		cout << '<' << endl;
	}else if(X > Y){
		cout << '>' << endl;
	}else{
		cout << '=' << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a, b, n, sco=0;
    cin >> a >> b >> n;
    if(b-1>n) sco=floor(a*n/b)-a*floor(n/b);
    else sco=floor(a*(b-1)/b)-a*floor((b-1)/b);
    cout << sco <<endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

    int N;cin>>N;
    int p[N];REP(i,N)cin>>p[i];

    int a[N],b[N];
    REP(i,N)a[i]=4*10000*(i+1);
    REP(i,N)b[i]=4*10000*(N+1-i);

    REP(i,N)b[--p[i]]+=i;

    REP(i,N)cout<<a[i]<<" ";
    cout<<endl;
    REP(i,N)cout<<b[i]<<" ";
    cout<<endl;

    return 0;
}

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

using namespace std;

int main() {
    string N;
    cin >> N;
    for (int i = 0; i < 2; i++) {
        if (N[i] == N[i + 1] && N[i + 1] == N[i + 2]) {
            cout << "Yes" << endl;
            break;
        }
        else if (i == 1) {
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define MOD(x) ((x)%mod)
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
int n,k;
int a[105];
int win[100002];
bool check(int x)
{
	for(int i=1;i<=n;i++)
	{
		int y=x-a[i];
		if(y<0) continue;
		if(win[y]==-1) win[y]=check(y);
		if(win[y]==0) return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	memset(win,-1,sizeof win); 
	int ans=check(k);
	if(check(k)) printf("First");
	else printf("Second");
	return 0;
}



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

string s;
vector<ll> sums;

void dfs(ll i, ll lsum, ll sum)
{
    lsum += s.at(i) - '0';
    if(i == s.length() - 1)
    {
        sums.push_back(sum + lsum);
        return;
    }
    // 次が+の場合
    dfs(i+1, 0, sum+lsum);
    // スルーの場合
    dfs(i+1, lsum*10, sum);

    return;
}

int main()
{
    cin >> s;
    dfs(0,0,0);
    cout << accumulate(sums.begin(), sums.end(), 0LL) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
main(){int n,m,i,a,c[1000001];for(std::string s;std::cin>>n>>m>>s,n;printf("%d\n",a))for(a=0,i=m;--i;a+=c[i]>=n)c[i]=s.substr(i,3)=="IOI"?c[i+2]+1:0;}

Measured memory_bytes: 5916
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	debug("debug test\n");
   	ll n,m;cin>>n;
	if(n % 2 == 1){
		cout << 0 << endl;
		return 0;
	}
	ll t = n;
	ll couten = 0;
	int cou = 1;
	while(true){
		ll po = n/((ll)pow(5, cou)*2);
		if(po == 0)break;
		couten += po;
		cou++;
	}
	ll coutwo = 0;
	cou = 1;
	while(true){
		ll po = n/(ll)pow(2, cou);
		if(po == 0)break;
		coutwo += po;
		cou++;
	}
	cout << min(couten, coutwo) << endl;
	return 0;
}


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

using ll = long long;

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

int main() {
    int N;
    cin >> N;
    vector<int> L(N);
    rep(i, N) cin >> L[i];

    int ans = 0;

    rep(i, N) rep(j, N) rep(k, N) {
        if (i < j && j < k) {
            if (L[i] == L[j]) continue;
            if (L[j] == L[k]) continue;
            if (L[k] == L[i]) continue;
            if ((ll)L[i] + L[j] + L[k] <= max({L[i], L[j], L[k]}) * 2) continue;
            ans++;
        }
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cmath>
#include <bitset>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 1e9+7
using namespace std;
typedef long long ll;
const double pi=acos(-1);

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    ll n,k;
    cin >> n >> k;
    vector<ll> A(n+1);
    for(int i=1;i<=n;i++) cin >> A[i];
    map<ll,ll> mp;
    mp[1]=0;
    ll cycle1,cycle2,after_i=1;
    for(int i=1;i<=n;i++){
        after_i=A[after_i];
        if(mp.find(after_i)==mp.end()){
            mp[after_i]=i;
        }else{
            cycle1=mp[after_i];
            cycle2=i;
            break;
        }
    }
    ll place=1;
    if(k<=n){
        for(ll i=0;i<k;i++){
            place=A[place];
        }
    }else{
        if(cycle1!=0) k-=cycle1;
        k%=(cycle2-cycle1);
        if(cycle1!=0) k+=cycle1;
        for(ll i=0;i<k;i++){
            place=A[place];
        }
    }
    cout << place << endl;
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

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

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

template <class T, class U>
void chmax(T &a, U b) {
  if (a < b) a = b;
}

template <class T, class U>
void chmin(T &a, U b) {
  if (b < a) a = b;
}

template <class T>
T Sq(const T &t) {
  return t * t;
}

signed main() {
  int d, n;
  cin >> d >> n;
  if (d == 0 && n == 100)
    print(101);
  else if (d == 0)
    print(n);
  else if (n == 100)
    print(pow(100, d) * n + pow(100, d));
  else
    print(pow(100, d) * n);
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args){

		Scanner scan = new Scanner(System.in);

		while(true){
			int h = scan.nextInt();
			int w = scan.nextInt();

			if(h == 0 && w == 0){
				break;
			}else{
				for(int a = 0; a < h; a++){
					for(int b = 0; b < w; b++){
						System.out.print('#');
					}
					System.out.println();
				}
				System.out.println();
			}
		}
	}
}

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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define dbg(var) {std::cout << #var << "  = " << var << nl;}
#define vi vector<int>
typedef long long ll;

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(11); 
	cout.setf(ios::fixed);

	int n;
	cin >> n;
	
	vector<vector<double>> dp(n + 1 , vector<double>(n + 1));
	dp[0][0] = 1.;
	
	repi(i , n)
	{
		double p;
		cin >> p;
		
		rep(j , i + 1)
		{
			dp[i][j] = (j > 0 ? dp[i - 1][j - 1] * p : 0.) + dp[i - 1][j] * (1. - p);
		}
	}
	
	double ans = 0.;
	repf(i , 1 + n / 2 , n + 1)
		ans += dp[n][i];
		
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 70784
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		String[] heightStrArr = sc.nextLine().split(" ");
		sc.close();
		int[] heightArr = new int[n];
		for(int i = 0; i < n; i++) {
			heightArr[i] = Integer.parseInt(heightStrArr[i]);
		}
		
		
		if(heightArr[0] > 0) {
			heightArr[0] = heightArr[0] - 1;
		}
		for(int i = 1; i < n; i++) {
			if(heightArr[i] > heightArr[i-1]) {
				heightArr[i] = heightArr[i] - 1;
			}
			if(heightArr[i] < heightArr[i-1]) {
				System.out.println("No");
				return;
			}
		}
		
		System.out.println("Yes");
	}
}

Measured memory_bytes: 48244
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
using namespace std;


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

    string substr1 = s.substr(0, 2);
    string substr2 = s.substr(2, 2);

    if ((stoi(substr1) >= 01 && stoi(substr1) <= 12) && (stoi(substr2) >= 01 && stoi(substr2) <= 12))print("AMBIGUOUS");
    else if (stoi(substr1) >= 01 && stoi(substr1) <= 12)print("MMYY");
    else if (stoi(substr2) >= 01 && stoi(substr2) <= 12)print("YYMM");
    else print("NA");
}

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

typedef long long ll;
int n,k;
int a[100005];
ll mx,mn;

ll fact[1000006], inv[1000006];

ll fp(ll base, ll exp)
{
    if (exp == 0)
        return 1;
    ll ans = fp(base, exp / 2);
    ans = (ans * ans) % mod;
    if (exp % 2 != 0)
        ans = (ans * (base % mod)) % mod;
    return ans;
}

void facninv(ll n)
{
    fact[0] = inv[0] = 1;
    for (ll i = 1; i <= n; i++)
    {
        fact[i] = (i * fact[i - 1]) % mod;
        inv[i] = fp(fact[i], mod - 2);
    }
}

ll ncr(ll n, ll r)
{
    return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}

int main()
{
    facninv(100000);
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(i>=k-1){
            ll tmp = ncr(i,k-1);
            mx = (mx%mod + (tmp*a[i])%mod)%mod;
        }
        if(n-i-1>=k-1){
            ll tmp = ncr(n-i-1,k-1);
            mn = (mn%mod + (tmp*a[i])%mod)%mod;
        }
    }
    cout<<(((mx-mn)+mod)%mod)%mod;

    return 0;
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int X, A, B;
	cin >> X >> A >> B;
	cout << (X - A)%  B << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e5+10;
int n;
int main() {
  //  freopen("test.txt","r",stdin);
    int n,k;
    int a[maxn];
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=1;i<=n-k;i++) {
        ans+=a[i];
    }
    cout<<ans<<endl;
    return 0;
}

/*
1.变量范围经常搞错，也就是临界情况不清晰
  1.1 加上一点，诸如下标从0~n-1的情况，对于某个其中的值，经常搞错个数和下标
2.经常性读错题目，尤其是看英文题面的情况下
3.结合上一点，如果是英文题面，一定要英文，只准翻译单个单词，逼着自己看英文题面
4.for循环中的i爆LL可能很难注意到
5.千万不要忽视轻视简单的问题
*/





Measured memory_bytes: 1024
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    search = [-1] * N
    search[v0] = 0
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if search[nv] == -1:
                q.append(nv)
                search[nv] = search[v] + 1

    return search


def bfs2(N, v0, edge, dis):

    q = deque()
    q.append(v0)

    ret = []

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if dis[v] > dis[nv] and dis[nv] != 0:
                q.append(nv)
                ret.append(nv)

    return ret[::-1]


def bfs3(N, v0, edge, color, x):

    search = [False] * N
    search[v0] = True
    q = deque()
    q.append(v0)

    ret = 0

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if not search[nv]:
                if color[nv] == -1:
                    ret += 1
                    q.append(nv)
                elif color[nv] == x:
                    q.append(nv)
                search[nv] = True

    return ret


def main():

    N = in_n()
    edge = [[] for _ in range(N)]

    for i in range(N - 1):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    dis = bfs(N, 0, edge)
    color_v = bfs2(N, N - 1, edge, dis)

    color = [-1] * N
    color[0] = 1
    color[-1] = 0

    color_v = deque(color_v)
    teban = 1

    while color_v:

        if teban == 1:
            v = color_v.popleft()
            color[v] = 1
            teban = 0

        elif teban == 0:
            v = color_v.pop()
            color[v] = 0
            teban = 1

    fen = bfs3(N, 0, edge, color, 1)
    sun = bfs3(N, N - 1, edge, color, 0)

    # print(color, fen, sun)

    if teban == 1:
        if fen > sun:
            ans = 'Fennec'
        else:
            ans = 'Snuke'
    elif teban == 0:
        if sun > fen:
            ans = 'Snuke'
        else:
            ans = 'Fennec'

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 32232
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0)
#define END return EXIT_SUCCESS
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR(I,0,N)
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) std::cin>>(P)
#define IN2(P1,P2) std::cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) std::cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP(I,N) std::cin>>V[I]
#define OUT(P) std::cout<<P<<std::endl
#define OUT2(P1,P2) std::cout<<P1<<" "<<P2<<std::endl
#define OUT3(P1,P2,P3) std::cout<<P1<<" "<<P2<<" "<<P3<<std::endl
#define OUTS(I,N,V) REP(I,N) std::cout<<V[i]<<std::endl
#define ALL(C) (C).begin(),(C).end()
using namespace std;
using namespace __gnu_pbds;
int N;
int h[100001];
int dp[100001];
int i;
inline void solve(){
  IN(N);
  UP(i,1,N){
    IN(h[i]);
  }
  dp[1]=0;
  dp[2]=abs(h[2]-h[1]);
  UP(i,3,N){
    dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]));
  }
  OUT(dp[N]);
}

int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 1024
from itertools import product

def solve(NUM, LIST):
    lst = [l[i] for i, li in enumerate(LIST) if li == NUM]
    if len(lst) == 0:
        return 10 ** 5
    ANS = (len(lst) - 1) * 10
    ANS += abs(sum(lst) - target[NUM])
    return ANS

target = list(map(int, input().split()))
l = [int(input()) for _ in range(target[0])]

ans = 10 ** 5
for pat in product([0, 1, 2, 3], repeat=target[0]):
    tmp = sum(solve(i + 1, pat) for i in range(3))
    ans = min(ans, tmp)
print(ans)


Measured memory_bytes: 92484
si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N = ii()
A = lmii()

B = [A[0]]
for i in range(1, N):
    if B[-1] != A[i]:
        B.append(A[i])

if len(B) <= 2:
    print(1)
    exit()

ans = 1
i = 2
while i < len(B):
    if (B[i]-B[i-1]) * (B[i-1]-B[i-2]) < 0:
        ans += 1
        i += 1
    i += 1

print(ans)

Measured memory_bytes: 14480