akhauriyash/Code-Regression huggingface dataset:
def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    max_dp = max(A) + 1
    dp = [0] * max_dp


    for a in A:
        if dp[a] >= 2:
            continue
        dp[a] += 1
        for i in range(a << 1, max_dp, a):
            dp[i] += 2
    print(dp.count(1))


if __name__ == '__main__':
    main()


Measured memory_bytes: 32164
from collections import defaultdict,deque, Counter
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
ans = 0

S = input()
ct = Counter(S)
if len(ct) == 2 and ct[S[0]] == 2:
    print('Yes')
else: print('No')

Measured memory_bytes: 21644
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let mut a = vec![0];
    for _ in 0..n {
        a.push(read::<i32>());
    }
    a.push(0);

    let mut default = 0;
    for i in 0..n + 1 {
        default += (a[i + 1] - a[i]).abs();
    }

    let ans: Vec<i32> = a
        .windows(3)
        .map(|x| default - (x[2] - x[1]).abs() - (x[1] - x[0]).abs() + (x[2] - x[0]).abs())
        .collect();

    for ans in ans {
        println!("{}", ans);
    }
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 5244
#include<cstdio>
#include<vector>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
	for(int n,m,c,s,g;scanf("%d%d%d%d%d",&n,&m,&c,&s,&g),n;){
		s--;
		g--;
		static int d[20][100][100];
		rep(k,c) rep(i,n) rep(j,n) d[k][i][j]=(i==j?0:INF);
		rep(_,m){
			int x,y,dd,cc; scanf("%d%d%d%d",&x,&y,&dd,&cc); x--; y--; cc--;
			d[cc][x][y]=d[cc][y][x]=min(d[cc][x][y],dd);
		}

		int len[20];
		vector< pair<int,int> > poly[20];
		rep(i,c) scanf("%d",len+i);
		rep(i,c){
			poly[i].assign(len[i]+1,make_pair(0,-1));
			rep(j,len[i]-1){
				int x; scanf("%d",&x);
				poly[i][j+1].first=x;
			}
			rep(j,len[i]){
				int a; scanf("%d",&a);
				poly[i][j+1].second=a;
			}
			poly[i].back().first=INF;
		}

		// 距離のグラフについて Floyd
		rep(l,c){
			rep(k,n) rep(i,n) rep(j,n) d[l][i][j]=min(d[l][i][j],d[l][i][k]+d[l][k][j]);
		}
		// 会社ごとにコストのグラフを作る
		static int p[20][100][100];
		rep(l,c){
			rep(i,n) rep(j,n) {
				int D=d[l][i][j];
				if(D==INF){ p[l][i][j]=INF; continue; }
				int cost=0;
				rep(k,poly[l].size()-1){
					cost+=poly[l][k+1].second*max(min(poly[l][k+1].first,D)-poly[l][k].first,0);
				}
				p[l][i][j]=cost;
			}
		}

		// コストのグラフをマージしたグラフについて Floyd
		int ans[100][100];
		rep(i,n) rep(j,n) ans[i][j]=INF;
		rep(i,n) rep(j,n) rep(k,c) ans[i][j]=min(ans[i][j],p[k][i][j]);
		rep(k,n) rep(i,n) rep(j,n) ans[i][j]=min(ans[i][j],ans[i][k]+ans[k][j]);

		printf("%d\n",ans[s][g]<INF?ans[s][g]:-1);
	}

	return 0;
}

Measured memory_bytes: 2416
main :: IO ()
main = do
  k <- readLn :: IO Integer
  print $ fst $ solve k (1, 0)

solve :: Integer -> (Integer, Integer) -> (Integer, Integer)
solve k (i, x)
  | i > 1000000 = (-1, 0)
  | otherwise =
    if tmp == 0
      then (i, x)
      else solve k ((i + 1), tmp)
  where
    tmp = (10 * x + 7) `mod` k

Measured memory_bytes: 5004
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define Mod 1000000007
using namespace std;
void add(int& x,int y)
{
	x+=y;
	if(x>=Mod)x-=Mod;
	return ;
}
int n;
char s[100010];
int f[100010];
vector<int>vec[3],pos;
int dp[100010];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		f[i]=(f[i-1]+s[i]-'a'+1)%3;
	for(int i=1;i<n;i++)
		if(s[i]==s[i+1])pos.push_back(i);
	pos.push_back(n);
	if(pos.size()==1){
		printf("1\n");
		return 0;
	}
	for(int i=1;i<=n;i++)
		vec[f[i]].push_back(i);
	vec[0].push_back(n+1);
	vec[1].push_back(n+1);
	vec[2].push_back(n+1);
	dp[0]=1;
	for(int i=0;i<n;i++)
	{
		add(dp[i+1],dp[i]);
		int x=(*lower_bound(pos.begin(),pos.end(),i+1))+1;
		int c=((3-s[i+1]+'a'-1)%3+f[i])%3;
		x=*lower_bound(vec[c].begin(),vec[c].end(),x);
		if(x>n)continue;
		add(dp[x],dp[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(f[n]==f[i])add(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define PI acos(-1)
#define EPS 1e-5
#define sz(v) ((int)(v).size())
#define all(v) v.begin(),v.end()
#define forn(i, n) for(ll i=0;i<(ll)n;i++)
#define fi first
#define se second
 

int main() {
	int a, b, h, m;
	cin >> a >> b >> h >> m;
	double degh =(h +m/60.0)* 30;
	double degm = m * 6;
	double diff = abs(degh - degm);
	double deg = min(diff, 360-diff);
	double res = sqrt(a*a + b*b - 2*a*b*cos(PI*deg / 180));
	cout << fixed << setprecision(11) << res << endl;
	return 0;
}



Measured memory_bytes: 4200
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using namespace std;
typedef long long ll;
using ld = long double;
typedef pair<int,int> P;
typedef vector<int> vi;

int main(){
  ll n,m,d;
  cin >> n >> m >> d;
  if(n<=2*d){
    cout << (ld)2*(n-d)*(m-1)/(n*n) << "\n";
    return 0;}
  if(d==0){cout << (ld)(m-1)/n << "\n";return 0;}
  cout(10)<<(ld)2*(n-d)*(m-1)/(n*n)<<endl;
  
  return 0;
}

Measured memory_bytes: 3788
//Problem *
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100005;
int n,w;
ll dp[N][2];
ll add(ll a,ll b){return (a+b)%1000000007;}
ll sub(ll a,ll b){return (a-b+1000000007)%1000000007;}
int main(){
	scanf("%d%d",&n,&w);
	for(int i=0;i<=w;i++)dp[i][0]=1;//printf("%d %d\n",n,w);
	for(int i=1;i<=n;i++){
		int a;scanf("%d",&a);
		for(int k=0;k<=w;k++){
			if(k<=a)dp[k][1]=dp[k][0];
			else dp[k][1]=sub(dp[k][0],dp[k-a-1][0]);
		}
		dp[0][0]=dp[0][1];
		for(int k=1;k<=w;k++)dp[k][0]=add(dp[k-1][0],dp[k][1]);
		//for(int j=w;j>=a;j++)dp[j]=max(dp[j],dp[j-a]+b);
	}
	printf("%lld",dp[w][1]);
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h> 
using namespace std;
#define int long long int
#define float double
#define pb push_back
#define FF first
#define SS second
#define N 100005
#define MOD 1000000007
#define fn(i,n) for(int i=0;i<n;i++)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define pii pair<int,int>
#define mp make_pair
#define INF 1000000000000000000
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

signed main() 
{
    speed;
    //freopen("input.tXt","r",stdin);
    //freopen("output.tXt","w",stdout);
    
    int n;
    cin>>n;
    int A[n+1];
    map<int,int> m1,m2;
    for(int i=1;i<=n;i++) 
    {
        cin>>A[i];
        m1[i+A[i]]++;
        m2[i-A[i]]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++) 
    {
        ans+=m2[i+A[i]];
        //cout<<i<<" "<<ans<<endl;
    }
    cout<<ans<<endl;
}   

Measured memory_bytes: 39476
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <math.h>
#include <complex>
#include <cassert>
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define repd(i,a,b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long int ll;
typedef complex<double> com;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const ll INF = 4e18;



int main() {
	int n; cin >> n;
	vector<ll> cnt(26,INF);
	rep(i, 0, n) {
		string s; cin >> s;
		vector<ll> sum(26, 0);
		rep(j, 0, s.size()) {
			sum[s[j] - 'a']++;
		}
		rep(j, 0, 26) {
			cnt[j] = min(cnt[j], sum[j]);
		}
	}
	string ans;
	rep(i, 0, 26) {
		rep(j, 0, cnt[i]) {
			ans += ('a'+i);
		}
	}
	printf("%s", ans.c_str());
	return 0;
}


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

#define rep(i, N) for(int i = 0; i < (int)N; i++)
#define ll long long
const ll INF = 2LL<<60;

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

    vector<int> p(N);
    rep(i, N)   cin >> p[i];

    int ans = 0;
    for(int i = 1; i < N - 1; i++)
    {
        if(p[i] > p[i - 1] && p[i] < p[i + 1])  ans++;

        if(p[i] < p[i - 1] && p[i] > p[i + 1])  ans++;
    }

    cout << ans << endl;
}

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

int mod = 998244353;

int main(){
    int N, S;
    std::cin >> N >> S;
    std::vector< int > A(N);
    for(int i=0; i<N; i++){
        std::cin >> A[i];
    }
    
    std::vector< std::vector< long long > > dp(N+1, std::vector< long long >(S+1, 0));
    for(int i=1; i<=N; i++){
        for(int j=0; j<=S; j++){
            dp[i][j] = (2 * dp[i-1][j]) % mod;
            if(j >= A[i-1]){
                dp[i][j] = (dp[i][j] + dp[i-1][j-A[i-1]]) % mod;
            }
            if(j == 0 || j == A[i-1]){
                dp[i][j] = (dp[i][j] + 1) % mod;
            }
        }
        //for(int j=0; j<=S; j++){
        //    std::cout << dp[i][j] << " ";
        //}
        //std::cout << std::endl;
    }
    
    std::cout << dp[N][S] << std::endl;;
    
    
    return 0;
    
}


Measured memory_bytes: 73660
package main

import "fmt"

type data struct {
	n, m       int
	nImg, mImg []string
}

func main() {
	d := newData()
	if d.exist() {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func newData() data {
	var n, m int
	fmt.Scanf("%d %d", &n, &m)
	nImg := load(n)
	mImg := load(m)

	return data{n: n, m: m, nImg: nImg, mImg: mImg}
}

func load(cnt int) []string {
	ret := make([]string, cnt)
	for i := 0; i < cnt; i++ {
		fmt.Scanf("%s", &ret[i])
	}

	return ret
}

func (d data) exist() bool {
	for i := 0; i <= d.n-d.m; i++ {
		for j := 0; j <= d.n-d.m; j++ {
			if d.match(i, j) {
				return true
			}
		}
	}

	return false
}

func (d data) match(x, y int) bool {
	for i := 0; i < d.m; i++ {
		for j := 0; j < d.m; j++ {
			if d.nImg[x+i][y+j] != d.mImg[i][j] {
				return false
			}
		}
	}

	return true
}

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


int solve(int n){
    vector<int> w(n);
    for(int i=0;i<n;i++) cin>>w[i];
    vector<vector<int>> dp(n+1,vector<int>(n+1,false));
    for(int i=0;i<=n;i++) dp[i][i]=true;
    for(int i=1;i<=n;i++){
        for(int j=0;j+i<=n;j++){
            for(int k=j+1;k<j+i;k++){                
                dp[j][i+j]|=(abs(w[j]-w[k])<=1) && dp[j+1][k] && dp[k+1][i+j];
            }
        }
    }
    vector<int> res(n+1,0);
    for(int i=0;i<n;i++){
        res[i+1]=max(res[i+1],res[i]);
        for(int j=0;j<=n;j++){
            if(dp[i][j]) res[j]=max(res[j],res[i]+j-i);
        }
    }
    return res[n];
}

int main(){
    int n;
    while(cin>>n,n){
        cout<<solve(n)<<endl;
    }
    return 0;
}


Measured memory_bytes: 3212
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseFloat(x::SubString{String}) = parse(Float64, x)
parseFloat(x::Char) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    a,b,c=parseMap(split(readline()))
    println(ifelse(a<=c<=b,"Yes","No"))
end
main()

Measured memory_bytes: 123316
$n = gets.to_i
$col = $n.to_s.length
$a = []

def find(i, num)
    if i == 0
        if num <= $n
            $a << num.to_s
        end
        return
    end
    find(i-1, num+3*10**(i-1))
    find(i-1, num+5*10**(i-1))
    find(i-1, num+7*10**(i-1))
end

(3..$col).to_a.reverse.each{|i|
    find(i, 0)
}

puts $a.select{|i| i.include?('7')&&i.include?('5')&&i.include?('3') }.count



Measured memory_bytes: 3964
#include <bits/stdc++.h>
#define ll long long
#define MODV 998244353
#define INFLL (1LL<<62) // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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 namespace std;

int main(){
    Init();
    ll n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> lr(k);
    rep(i, k) cin >> lr[i].first >> lr[i].second;
    sort(all(lr));

    vi dp(n*2+1, 0), sect(n*2+1, 0);
    dp[1] = 1, sect[1] = 1;

    for(ll i=1; i<=n; i++){
        dp[i] = dp[i-1] + sect[i];
        dp[i] %= MODV;
        for(auto &range: lr){
            sect[i+range.first] = (sect[i+range.first]+dp[i])%MODV;
            sect[i+range.second+1] = ((sect[i+range.second+1]-dp[i])%MODV+MODV)%MODV;
        }
    }
    cout << sect[n] << endl;
    return 0;
}

Measured memory_bytes: 9504
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
using graph = vector<vector<ll>>;

int main() {
	ll n;
	cin >> n;
	n = n % 1000;
	if (n == 0)cout << 0 << endl;
	else cout << 1000 - n << endl;
	
}

Measured memory_bytes: 3624
/*
Author: Racer5x
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include<bits/stdc++.h>
#define int         long long
#define double      long double
#define pb          emplace_back
#define pf          emplace_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX         2000000000000000000
#define M           1000000007
 
using namespace std;
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int power(int x,int n){
    int result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x) % hell;
        x=(x*x) % hell;
        n=n/2;
    }
    return result % hell;
}
 
class dsu{
    vi p,rank;
    vi set_count;
  
  public:
    dsu(int n){
        p.assign(n,0); 
        rank.assign(n,0);
        set_count.assign(n,1);
        for(int i=0;i<n;i++) p[i] = i;
    }
    int findSet(int x){
        return (p[x] == x) ? x:(p[x] = findSet(p[x]));
    }
    bool isSame(int i, int j){
        return (findSet(i) == findSet(j));
    }
    void unionSet(int i, int j){
        if(!isSame(i,j)){
            int x = findSet(i), y = findSet(j);
            if(rank[x] > rank[y]) {p[y] = x; set_count[x]+=set_count[y];}
            else{
                p[x] = y;
                set_count[y]+=set_count[x];
                if(rank[x] == rank[y]) rank[y]++;
            }
        }
    }
    int count(int x){
        return set_count[findSet(x)];
    }
};

int S[105][105];
int T[105][105];

// code copied from god_arham
int mod_inv(int a,int m){
    a=a%m;
    return power(a,m-2)%hell;
}
int fact[200005];
void count_fact(){
    int i,x=1;
    fact[0]=1;
    for(int i=1;i<200002;i++){
        
        x=(x*i)%hell;
      //  cout<<x<<" ";
        fact[i]=x;
        
    }
}
 
int ncr(int n,int r){
    int a=fact[n],b=fact[r],c=fact[n-r];
    
    return (a*mod_inv(b*c,hell))%hell;
} 
//copied code ends here
 
signed main()
{
    tezz
 
    int n;
    cin>>n;
    if(n&1) {cout<<0; return 0;}

    int ans = 0;
    int res = 10;

    while(n / res){
        ans += n/res;
        res *= 10;
    }

    int temp = 50;
    while(n / temp){
        res = temp;
        while(n / res){
            ans += ceil((double)(n/res)/2);
            res *= 10;
        }
        temp *= 5;
    }

    cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
void ABC60(void);
void ABC61(void);
void ABC62(void);
void ABC63(void);
void ABC64(void);
void ABC65(void);
void ABC66(void);
void ABC67(void);
void ABC68(void);
void ABC69(void);

int main(void){
    ABC68();
}

void ABC68(){
    int i,n,ans=2;
    cin>>n;
    if(n==1)cout<<1<<endl;
    else{
    while(ans*2<=n){
        ans*=2;
    }
    cout<<ans<<endl;
    }
}


Measured memory_bytes: 256
def f(x,y,z):
    n=x**2 + y**2 + z**2 + x*y + y*z + z*x
    return n

N=int(input())

anslist=[0]*60100

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            n= f(x,y,z)
            anslist[n-1]+=1

for i in range(N):
    print(anslist[i])

Measured memory_bytes: 9408
#include<stdio.h>
#include<math.h>
#define df 0


int main(){
  int n,d;
  scanf("%d%d",&n,&d);
  
  int pos[100],i;
  for(i=0;i<n*d;i++)
    scanf("%d",&pos[i]);
  int j,count=0,a,b,k;
  for(i=0;i<n-1;i++){
    for(j=i+1;j<n;j++){
      a=0;
      for(k=0;k<d;k++){
        a+=(pos[i*d+k]-pos[j*d+k])*(pos[i*d+k]-pos[j*d+k]);
      }
      b=sqrt(a);
      b=b*b;
      if(df)printf("%d %d\n",a,b);
      if(a==b)count++;
    }
  }

  printf("%d",count);
  return 0;
}


/// confirm df==0 ///


Measured memory_bytes: 128
N = int(input())
S = input()
unclosedBra = 0 #( num
unclosedKet = 0 #) num
for i in range(N):
  if S[i] == '(':
    unclosedBra += 1
  else:
    if unclosedBra > 0:
      unclosedBra -= 1
    else:
      unclosedKet += 1
ans = ('(' * unclosedKet ) + S + (')' * unclosedBra)
print(ans)      

Measured memory_bytes: 3060
from sys import stdin
input = stdin.readline
n, m = map(int, input().split())

ans = sorted([list(map(int, input().split()))+[i] for i in range(m)], key=lambda x:x[1])

built = [1]*n
for i in range(m):
    ans[i][1] = built[ans[i][0]-1]
    built[ans[i][0]-1] += 1

for i in sorted(ans,key=lambda x:x[2]): print("%06d%06d" % (i[0],i[1]))

Measured memory_bytes: 26340
import sys
sys.setrecursionlimit(100000)


def P(n):
    print(n)
    if n <= 2:
        yield []
        return
    if n <= 5:
        yield [n]
        return

    for p in P(n-3):
        #print("p", p)
        p.append(3)
        yield p
        p.pop()
        if p and (len(p) < 2 or p[-2] > p[-1]):
            p[-1] += 1
            yield p


def partition(number):
    answer = set()
    if number < 3:
        return answer
    answer.add((number, ))
    for x in range(1, number):
        if x < 3:
            continue
        for y in partition(number - x):
            answer.add(tuple(sorted((x, ) + y)))

    return answer


mod = 10**9+7

S = int(input())

dp = [0]*(S+1)
#dp[3] = 1
dp[0] = 1
for i in range(3, S+1):
    sm = 0
    for j in range(i-2):
        sm += dp[j]
    dp[i] = sm % mod

print(dp[-1] % mod)

# print(dp)


Measured memory_bytes: 9192
using static System.Math;
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        var c = int.Parse(line[2]);
        var d = int.Parse(line[3]);
        Console.WriteLine((Abs(a - c) <= d) | (Abs(a - b) <= d && Abs(b - c) <= d) ? "Yes" : "No");
    }
}


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

using namespace std;

int main(){
	int N,D; cin>>N>>D;
	vector<vector<int>> X(N,vector<int>(D));
	for(int i=0;i<N;++i){
		for(int j=0;j<D;++j){
			cin>>X[i][j];
		}
	}
	int ans = 0;
	for(int i=0;i<N;++i){
		for(int j=i+1;j<N;++j){
			int norm = 0;
			for(int k=0;k<D;++k){
				int diff = abs(X[i][k]-X[j][k]);
				norm += diff*diff;
			}
			
			bool flag = false;
			for(int k=0;k<=norm;++k){
				if(k*k==norm){
					flag = true;
				}
			}
		if(flag) ++ans;
		}
	}
	cout<<ans<<endl;
}

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

int main() {
  int D, T, S;
  cin >> D >> T >> S;

  if (D % S == 0 && D / S <= T) {
    cout << "Yes" << endl;
  }
  
  else if (D % S != 0 && D / S + 1 <= T) {
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define ll long long
#define MOD1 1e9+7;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

using namespace std;
ll mymod(ll a,ll b, ll MOD){
    a%=MOD;
    ll result=1;
    while(b>0){
        if(b&1){
            result=(result*a)%MOD;
        }
        a=(a*a)%MOD;
        b>>=1;
    }
    return result;
    
}

int main(){
    ll N,P;
    string S;
    cin>>N>>P>>S;
    vector<ll> r(N+1,0);
    map<ll,ll> mp;
    mp[0]=1;
    if (P == 5 || P == 2) {
        ll ans = 0;
        for(int i=0;i<N;i++){
            if ((S[i] - '0') % P == 0) {
                ans += i+1;
            }
        }
        cout << ans << endl;
        return 0;
    }
    ll counts[P]; F0R(i, P) counts[i] = 0;
    counts[0] = 1;
    int cur = 0;
    ll MOD = P;
    F0R(i, N) {
        cur *= 10; cur += S[i] - '0'; cur %= MOD;
        int val = mymod(10, N-1-i,P) * cur; val %= MOD;
        counts[val]++;
    }
 
    ll ans = 0;
    F0R(i, P) ans += (counts[i] * (counts[i] - 1)) / 2;
 
    cout << ans << endl;
    /*for(int i=0;i<N;i++){
        for(int j=i+1;j<N+1;j++){
            if(r[i]==r[j]){
                count++;
            }
        }
    }*/
    return 0;

}


Measured memory_bytes: 2308
mm = 1000000007

fact :: Integer -> Integer -> Integer
fact n x
  | n == 0 = x
  | otherwise = fact (n - 1) $ (x * n) `mod` mm

solve :: [Integer] -> Integer
solve (n:m:_)
  | diff == 0 = (2 * c) `mod` mm
  | otherwise = c
  where
    diff = abs $ n - m
    c = if diff > 1 then 0 else (fact n 1 * fact m 1) `mod` mm

main = getContents >>= print . solve . map read . words. last . lines


Measured memory_bytes: 19964
s = list(input())

for i in range(len(s)):
    if s[i] == 'A':
        tmp1 = i
        break
        
for i in range(1,len(s)):
    if s[-i] == 'Z':
        tmp2 = len(s) - i
        break

   
print((tmp2+1)-tmp1)
        

Measured memory_bytes: 10568
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int_Max 2147483647
#define ll_Max 9223372036854775807
#define REP(i,f,n) for(int i=f; i<(n); i++)

int main()
{
  int ans = 0;
  cin >> ans;
  REP(i,0,ans)cout << "ACL";
  cout << endl;

  //--debug : end_stoper
  //string end_stoper; cin >> end_stoper;

  return 0;
}

Measured memory_bytes: 3548
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

int main() {
  int n;
  std::string s;
  std::cin >> n >> s;
  int ans = n;
  int a = 0;
  int b = 0;
  for (int i = 0; i < n; ++i) b += s[i] == 'E' ? 1 : 0;
  for (int i = 0; i < n; ++i) {
    if (s[i] == 'E') --b;
    if (i > 0 and s[i - 1] == 'W') ++a;
    ans = std::min(ans, a + b);
  }
  std::cout << ans << std::endl;
  return 0;
}


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


def main():
    from fractions import gcd

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    max_a = max(a)
    max_gcd = a[0]

    for i in range(n - 1):
        max_gcd = min(max_gcd, gcd(a[i], a[i + 1]))

    if k <= max_a and k % max_gcd == 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()


Measured memory_bytes: 16048
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;

struct Data{
    char name[100];
    int time;
};

Data p[100001];
int head, tail, n;

void enqueue(Data x){
    p[tail] = x;
    if(tail + 1 >100001){
        tail = 0;
    } else {
        tail++;
    }
}

Data dequeue(){
    Data x = p[head];
    if(head + 1 > 100001){
        head = 0;
    } else {
        head++;
    }
    return x;
}

int main(){
    int q;
    //scanf("%d %d", &n, &q);
    cin >> n >> q;
    Data ans[100001];
    head = 0;
    tail = n; 
    
    for(int i = 0; i < n; i++){
        cin >> p[i].name >> p[i].time;
    }
    
    int time2;
    int t = 0;
    
    Data u;
    while(tail != head){
     
        u = dequeue();
        if(u.time <= q){
            //cout << t << endl;
            time2 = t + u.time;
            t += u.time;
            printf("%s %d\n", u.name, time2);
        } else {
            t += q;
            u.time -= q;
            enqueue(u);
        }
        
    }
    
    return 0;
}


Measured memory_bytes: 13248
#include <iostream>
#include <vector>
#include <string>

using namespace std;

constexpr long long D = 1000000007;

long long* factMemo;
long long* modInvMemo; // 数字で割るとき
long long* modInvFactMemo; // 階乗で割るとき

long long Mul(long long a, long long b) {
	long long c = a * b;
	c %= D;
	return c;
}

long long CalcModInv(long long a) {
	long long u = 1, v = 0;
	long long b = D;
	while (b) {
		long long t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= D;
	if (u < 0)
		u += D;
	return u;
}

int main() {

	constexpr int SIZE = 2000002;

	// 階乗の初期化
	factMemo = new long long[SIZE];
	modInvMemo = new long long[SIZE];
	modInvFactMemo = new long long[SIZE];

	factMemo[0] = 1;
	for (int i = 1; i < SIZE; i++) {
		factMemo[i] = Mul(factMemo[i - 1], i);
	}
	
	modInvMemo[0] = 1;
	for (int i = 1; i < SIZE; i++) {
		modInvMemo[i] = CalcModInv(i);
	}

	modInvFactMemo[1] = modInvMemo[1];
	modInvFactMemo[0] = 1;
	for (int i = 2; i < SIZE; i++) {
		modInvFactMemo[i] = Mul(modInvFactMemo[i - 1], modInvMemo[i]);
	}

	long long K;
	cin >> K;
	string S;
	cin >> S;

	long long* powMemo25;
	long long* powMemo26;
	powMemo25 = new long long[K + 1];
	powMemo26 = new long long[K + 1];
	powMemo25[0] = 1;
	powMemo26[0] = 1;
	for (int i = 1; i <= K; i++) {
		powMemo25[i] = Mul(powMemo25[i - 1], 25);
		powMemo26[i] = Mul(powMemo26[i - 1], 26);
	}

	long long len = S.length(); // len >= 1 は保証
	long long ans = 0;
	// i は S の最終文字より手前に挿入した文字数
	for (int i = 0; i <= K; i++) {
		// 並べ方
		long long a = factMemo[i + len - 1];
		a = Mul(a, modInvFactMemo[i]);
		a = Mul(a, modInvFactMemo[len - 1]);

		// 挿入文字のパターン
		a = Mul(a, powMemo25[i]);
		a = Mul(a, powMemo26[K - i]);

		ans += a;
		ans %= D;
	}

	cout << ans << endl;

	delete[] factMemo;
	delete[] modInvMemo;
	delete[] modInvFactMemo;
	delete[] powMemo25;
	delete[] powMemo26;
	return 0;
}

Measured memory_bytes: 66508
#include<stdio.h>
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	int i;
	int a[10004];
	for (i = 0; i < m; i++)
		scanf("%d", &a[i]);
	int sum = 0;
	for (i = 0; i < m; i++)
		sum += a[i];
	if (n < sum)
		printf("-1\n");
	else
		printf("%d\n", n - sum);
	return 0;
}

Measured memory_bytes: 1760
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<int> X(N), sorted(N);
    rep(i, N) {
        int tmp;
        cin >> tmp;
        X[i] = tmp;
        sorted[i] = tmp;
    }
    sort(ALL(sorted));
    int left = sorted[N/2 - 1];
    int right = sorted[N/2 + 1 - 1];
    rep(i, N) {
        if (X[i] >= right) {
            cout << left << endl;
        } else cout << right << endl;
    }
    return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if (B / A >= C) {
        cout << C << endl;
    } else {
        cout << B / A << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N = int(input())
r = [[int(i) for i in input().split()] for _ in range(N)]
b = [[int(i) for i in input().split()] for _ in range(N)]

b1 = sorted(b)
r1 = sorted(r, key=lambda x: x[1])[::-1]

cnt = 0
for ib in b1:
    for ir in r1:
        if ir[0] < ib[0] and ir[1] < ib[1]:
            cnt += 1
            r1.remove(ir)
            break
print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 810114514
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define int long long 

int UF[114514];
void UFinit(int n){
    for(int i=0;i<=n;i++){
        UF[i]=i;
    }
}
int UFroot(int k){
    if(UF[k]==k){
        return k;
    }else{
        UF[k]=UFroot(UF[k]);
        return UF[k];
    }
}
int UFsame(int P,int Q){
    if(UFroot(P)==UFroot(Q)){
        return true;
    }else{
        return false;
    }
}
void UFunite(int P,int Q){
    int p=UFroot(P);
    int q=UFroot(Q);
    if(p==q)return;
    if(p>q)swap(p,q);
    UF[q]=p;
}

signed main(){
    int N,M;
    int Ans=0;
    int p[114514];
    int x[114514],y[114514];
    cin >> N >> M;
    UFinit(N);
    REP(i,N){cin >> p[i];}
    REP(i,M){cin >> x[i] >> y[i];}
    REP(i,M){UFunite(x[i],y[i]);}
    REP(i,N){if(UFsame(i+1,p[i]))Ans++;}
    cout << Ans << endl;
	return 0;
}

Measured memory_bytes: 3584
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, x int
	fmt.Scan(&n, &x)

	m := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&m[i])
	}
	sort.Ints(m)

	fmt.Println((x-sum(m))/m[0] + len(m))
}

func sum(a []int) (x int) {
	for _, i := range a {
		x += i
	}
	return
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
using namespace std;

int main(void) {
	string S;
	cin >> S;
	int Ans = 700;
	for (int i = 0; i < 3; i++) {
		if (S[i] == 'o') {
			Ans += 100;
		}
		else if (S[i] == 'o') {
			Ans += 100;
		}
		else if (S[i] == 'o') {
			Ans += 100;
		}
	}
	cout << Ans << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
L = list(map(int, input().split()))

## Trivial = (N-1)//(K-1)

if (N-1) % (K-1) == 0:
  print( (N-1)//(K-1) )
else:
  print( (N-1)//(K-1) + 1)

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

int main()
{
	int a;
    cin>>a;
    if(a==25)
        cout<<"Christmas"<<endl;
    if(a==24)
        cout<<"Christmas Eve"<<endl;
    if(a==23)
        cout<<"Christmas Eve Eve"<<endl;
    if(a==22)
        cout<<"Christmas Eve Eve Eve"<<endl;
    

	
	return 0;
}
	

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    n=n%10;
    if(n==2 || n==4 || n==5 || n==7 || n==9)
    cout<<"hon"<<'\n';
    if(n==0 || n==1 || n==6 || n==8)
    cout<<"pon"<<'\n';
    if(n==3)
    cout<<"bon";
    return 0;
}

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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

// ------------------------------------------------------------------------------------------

const int INF = 1e18;

int N, A, B, C;
vec<int> l;

int rec(int idx, int a, int b, int c) {
  if (idx >= N) {
    if (a == 0 or b == 0 or c == 0) return INF;
    return abs(a - A) + abs(b - B) + abs(c - C);
  }

  int ret = INF;

  // A
  chmin(ret, rec(idx+1, a+l[idx], b, c) + (a > 0 ? 10 : 0));
  // B
  chmin(ret, rec(idx+1, a, b+l[idx], c) + (b > 0 ? 10 : 0));
  // C
  chmin(ret, rec(idx+1, a, b, c+l[idx]) + (c > 0 ? 10 : 0));
  // なし
  chmin(ret, rec(idx+1, a, b, c));

  return ret;
}

signed main() {
  cin >> N >> A >> B >> C;
  l.resize(N);
  rep (i, N) {
    cin >> l[i];
  }

  cout << rec(0, 0, 0, 0) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int N;
    cin >> N;
    vll A(N + 1), B(N + 1), acc(N + 1);
    ll cur = 0, ans = 1,M=0;
    for (size_t i = 0; i < N + 1; i++)
    {
        cin >> A[i];
        cur += A[i];
        M += A[i];
    }
    cur -= A[0];
    B[0] = 1 - A[0];
    for (size_t i = 1; i < N + 1; i++)
    {
        cur -= A[i];
        B[i] = min(2 * B[i - 1]-A[i], cur);
        if(B[i]<0)
        {
            cout<<-1;
            return 0;
        }
        ans += A[i]+B[i];
    }
    if(ans < M or (not(A[0] == 0 or A[0] == 1)) or (N==0 and A[0]==0))
    {
        cout<<-1;
    }
    else
    cout << ans;
    return 0;
}

Measured memory_bytes: 5568
#include<iostream>
using namespace std;
int main() {
	int tate, yoko;
	cin >> tate >> yoko;
	while (tate != 0 || yoko != 0) {
		for (int i = 0; i < tate; i++) {
			for (int j = 0; j < yoko; j++) {
				if (i % 2 == 0) {
					if (j % 2 == 0) {
						cout << "#";
					}
					else {
						cout << ".";
					}
				}
				else {
					if (j % 2 == 0) {
						cout << ".";
					}
					else {
						cout << "#";
					}
				}
			}
			cout << endl;
		}
		cout << endl;
		cin >> tate >> yoko;
	}
	return 0;
}

Measured memory_bytes: 3088
//IN THE NAME OF GOD;
//Test By Dev-C++5.11
#include<bits/stdc++.h>
#define ll  long long
#define isc ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ld long double
#define ss string
#define ww while
#define vl vector<ll>
#define pb push_back
#define in insert
#define vec vector
#define itr iterator
#define gt goto
#define rep(i,n,j) for(ll i=n;i<j;i++)
#define tep(i,n,j) for(ll i=n;i>=j;i--)
#define co(n) cout << n ;
#define pll pair<ll,ll>
#define bft bool f=true
#define bff bool f=false 
using namespace std;


ll kmm(ll a, ll b) {
	return(a*b) / __gcd(a, b);
}

const ll mod = 1e9 + 7;
const ll MAXN = 3e5+5;
ll modpower(ll x,ll n)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return modpower((x*x)%mod,n/2);
    else
        return (x*modpower((x*x)%mod,(n-1)/2))%mod;

}

ll fac(ll a){
	if(a==0)
		return 1;
	return fac(a-1)*a;
}

ll jaygasht(ll x){
	return (fac(x)/(6*fac(x-3)));
}

void solve(){
	ll n;
	cin >> n;
	bft;char b;
	set <ss> a;
	ss s;
	rep(i,0,n){
		cin >> s;
		if(i>0){
			if(b!=s[0])
				f=false;
		}
		b=s[s.size()-1];
		a.insert(s);
	}
	if(f){
		if(a.size()==n)
			cout << "Yes";
		else
			cout << "No";
	}
	else
		cout << "No";
}

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


Measured memory_bytes: 256
// --------------
// Tejas Pandey  |
// 18 - 08 - 19  |
// ABC #138      |
// --------------

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

#define mod 1000000007
#define vi vector<int>
typedef long long int ll;

vector<int> ed[200007];
bool vis[200007];
int upd[200007];

void dfs(int ver,int cur){
	vis[ver] = 1;
	upd[ver] += cur;
	cur = upd[ver];
	for(int i = 0;i < ed[ver].size();i++){
		if(!vis[ed[ver][i]]){
			dfs(ed[ver][i],cur);
		}
	}
}

int main (void)
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
	//cin >> t;
	while(t--)
	{
		//cout << "Case #" << c-t << ": ";
		int n,q;
		cin >> n >> q;
		for(int i = 0;i < n-1;i++){
			int j,k;
			cin >> j >> k;
			ed[j].push_back(k);
			ed[k].push_back(j);
		}
		for(int i =0;i < q;i++){
			int v,up;
			cin >> v >> up;
			upd[v] += up;
		}
		dfs(1,0);
		for(int i = 1;i <= n;i++){
			cout << upd[i] << " ";
		}
	}
	return 0;
}

Measured memory_bytes: 23680
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    LL A,B,C; cin >> A >>B>>C;
    LL K; cin >> K;


    if(K <= A){
        cout << K << endl;
        return 0;
    }

    LL ans = A;
    if(K-(A+B) >= 0){
        LL tmp = K - (A+B);
        ans -= tmp;
    }
    cout << ans << endl;

}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 200000000;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
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...));
}

vector<bool> prime_table(int n) {
    vector<bool> prime(n + 1, true);
    if (n >= 0)
        prime[0] = false;
    if (n >= 1)
        prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (!prime[i])
            continue;
        for (int j = i + i; j <= n; j += i) {
            prime[j] = false;
        }
    }
    return prime;
}
map<long long, int> prime_factor(long long n) {
    map<long long, int> ret;
    for (long long i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

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

    vector<int> table(n + 1, 0);
    FOR(i, 2, n + 1) {
        map<ll, int> factor = prime_factor(i);
        for (auto p : factor) {
            table[p.first] += p.second;
        }
    }

    int two, four, fourteen, twentyfour, seventyfour;
    two = four = fourteen = twentyfour = seventyfour = 0;
    REP(i, n) {
        if (table[i] >= 74) {
            seventyfour++;
        } else if (table[i] >= 24) {
            twentyfour++;
        } else if (table[i] >= 14) {
            fourteen++;
        } else if (table[i] >= 4) {
            four++;
        } else if (table[i] >= 2) {
            two++;
        }
    }

    int ans = 0;
    int over_two = two + four + fourteen + twentyfour + seventyfour;
    int over_four = four + fourteen + twentyfour + seventyfour;
    int over_fourteen = fourteen + twentyfour + seventyfour;
    int over_twenyfour = twentyfour + seventyfour;
    if (over_two >= 2 && over_four >= 1) {
        ans += over_four * (over_four - 1) / 2 * (over_two - 2);
    }
    if (over_fourteen >= 0 && over_four >= 1) {
        ans += over_fourteen * (over_four - 1);
    }
    if (over_twenyfour >= 0 && over_two >= 1) {
        ans += over_twenyfour * (over_two - 1);
    }
    ans += seventyfour;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
from collections import Counter

def main():
    n = int(input())
    c = Counter()
    for _ in range(n):
        x = int(input())
        c[x] += 1
    ans = 0
    for cc in c.values():
        if cc % 2 == 1:
            ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 15456
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
vector<vector<int>> miss;
vector<vector<int>> score;
vector<vector<pair<int,int>>> rk;

void solve(int m,int t,int p,int r){
    int in;
    v=vector<vector<int>>(r,vector<int>(4,0));
    miss=vector<vector<int>>(t,vector<int>(p,0));
    score=vector<vector<int>>(t,vector<int>(2,0));
    rk=vector<vector<pair<int,int>>>(p+1,vector<pair<int,int>>(0));
    for(int i=0;i<r;i++){
        for(int j=0;j<4;j++){
            cin>>in;
            v[i][j]=in;
        }
    }
    for(int i=0;i<r;i++){
        if(v[i][3])miss[v[i][1]-1][v[i][2]-1]++;
        else {
            score[v[i][1]-1][0]++;
            score[v[i][1]-1][1]+=v[i][0]+miss[v[i][1]-1][v[i][2]-1]*20;
        }
    }
    for(int i=t-1;i>=0;i--){
        rk[score[i][0]].push_back(make_pair(i,score[i][1]));
    }
    bool sw=false;
    for(int i=p;i>=0;i--){
        int maxx=-1;
        for(int j=0;j<rk[i].size();j++){
            maxx=max(maxx,rk[i][j].second);
        }
        for(int j=0;j<=maxx;j++){
            bool swc=false;
            for(int k=0;k<rk[i].size();k++){
                if(rk[i][k].second==j){
                    if(swc)cout<<"="<<rk[i][k].first+1;
                    else {
                        if(sw)cout<<","<<rk[i][k].first+1;
                        else{
                            cout<<rk[i][k].first+1;
                        }
                        sw=true;
                    }
                    swc=true;
                }
            }
        }
    }
    cout<<endl;
}


int main(void){
    ios::sync_with_stdio(false);
    int a,b,c,d;
    while(cin>>a>>b>>c>>d,a){
        solve(a,b,c,d);
    }
}

Measured memory_bytes: 3324
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& base) {
    for (T const& i : base) {
        out << i << ' ';
    }
    return out;
}
long maxProfit(int N, int W, vector<int>& values, vector<int>& weights) {
    long DP[N][W+1];
    memset(DP, 0, sizeof DP);
    DP[0][weights[0]] = values[0];
    for(int i = 1; i < N;++i){
        for(int w = 0; w <= W; ++w){
            if(w >= weights[i]) {
                DP[i][w] = max(DP[i-1][w], values[i] + DP[i-1][w-weights[i]]);
            }
            else DP[i][w] = DP[i-1][w];
        }
    }
    return *max_element(DP[N-1], DP[N-1] + W + 1);
}
int main() {
    int N, W;
    cin >> N >> W;
    vector<int> values(N), weights(N);
    for(int i = 0; i < N; ++i){
        cin >> weights[i] >> values[i];
    }
    cout << maxProfit(N, W, values, weights) << endl;
}

Measured memory_bytes: 81620
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long cc;

cc N, K, Ans[200000], i, j, k, A[200000], sub;
cc judge=0, judge2 = 0, judge3 = 0;

string S;


int main() {
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> A[i];
	judge = 0;
	
	for (i = 0; i < N; i++) 
		judge = A[i] - judge;
	

	sub = judge / 2;
	Ans[0] = sub * 2;
	for (i = 1; i < N; i++)
		Ans[i] = (A[i - 1] - Ans[i - 1] / 2) * 2;


	for (i = 0; i < N; i++)
		cout << Ans[i] << " ";
	cout << endl;
	return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int n, m, u, v, s;
int vis[100000];
ll g[100000], a;
bool b;
vector<pair<int,int>>vec[100000];

void dfs(int x) {
	for (auto p : vec[x]) {
		if (vis[p.first] == 0) {
			vis[p.first] = -vis[x];
			g[p.first] = p.second - g[x];
			dfs(p.first);
		}
		else {
			if (vis[x] == vis[p.first]) {
				if (vis[x] == -1) {
					a = (g[p.first] + g[x] - p.second) / 2;
				}
				else {
					a = (p.second - g[p.first] - g[x]) / 2;
				}
				b = true;
			}
		}
	}
}

bool dfs2(int x) {
	vis[x] = 1;
	for (auto p : vec[x]) {
		if (vis[p.first]) {
			if (g[x] + g[p.first] != p.second)
				return false;
		}
		else {
			g[p.first] = p.second - g[x];
			if (g[p.first] <= 0)
				return false;
			if (!dfs2(p.first))
				return false;
		}
	}
	return true;
}

int main() {
	cin >> n >> m;
	while (m--) {
		cin >> u >> v >> s;
		--u;
		--v;
		vec[u].push_back(mkp(v, s));
		vec[v].push_back(mkp(u, s));
	}
	vis[0] = 1;
	dfs(0);
	if (b) {
		if (a <= 0) {
			cout << 0 << endl;
		}
		else {
			for (int i = 0; i < n; ++i)
				vis[i] = 0;
			g[0] = a;
			cout << dfs2(0) << endl;
		}
	}
	else {
		for (int i = 0; i < n; ++i) {
			for (auto p : vec[i]) {
				if (g[i] + g[p.first] != p.second) {
					cout << 0 << endl;
					return 0;
				}
			}
		}
		ll mnev, mnod;
		mnev = mnod = llmax;
		for (int i = 0; i < n; ++i) {
			if (vis[i] == 1) {
				mnev = min(mnev, g[i]);
			}
			else {
				mnod = min(mnod, g[i]);
			}
		}
		cout << max(0ll, mnev + mnod - 1) << endl;
	}
	return 0;
}

Measured memory_bytes: 9984