akhauriyash/Code-Regression huggingface dataset:
function warshall(){
   for(var k=0;k<nm[1];k++){
      for(var i=0;i<nm[1];i++){
         for(var j=0;j<nm[1];j++){
            C[i][j]=Math.min(C[i][j], C[i][k]+C[k][j]);
            T[i][j]=Math.min(T[i][j], T[i][k]+T[k][j]);
         }
      }
   }
}
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var nm=(Arr.shift()).split(" ").map(Number);
   if(nm[0]==0 && nm[1]==0)break;
   var C=[];
   var T=[];
   for(var i=0;i<nm[1];i++){
      C[i]=[];
      T[i]=[];
      for(var j=0;j<nm[1];j++){
         C[i][j]=(i===j)?0:Infinity;
         T[i][j]=(i===j)?0:Infinity;
      }
   }
   for(var i=0;i<nm[0];i++){
      var A=(Arr.shift()).split(" ").map(Number);
      C[A[0]-1][A[1]-1]=C[A[1]-1][A[0]-1]=A[2];
      T[A[0]-1][A[1]-1]=T[A[1]-1][A[0]-1]=A[3];
   }
   warshall();
   var k=Arr.shift()-0;
   for(var i=0;i<k;i++){
      var B=(Arr.shift()).split(" ").map(Number);
      if(B[2]==0)console.log(C[B[0]-1][B[1]-1]);
      if(B[2]==1)console.log(T[B[0]-1][B[1]-1]);
   }
}

Measured memory_bytes: 51284
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
 ll a,b,c,d;
  cin>>a>>b>>c>>d;
  if(abs(a-b)<=d&&abs(b-c)<=d) cout<<"Yes"<<endl;
  else if(abs(a-c)<=d) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[26];
char fun(char a1){
	char tmp=NULL;
	for(int i=0; i<26; i++){
		if(a[i]==0 && i>a1-'a'){
			tmp = 'a'+i;
			return tmp;
		}
	}
	return NULL;
}
int main(void){
	string str;
	cin>>str;
	int l = str.length();
	memset(a, 0, sizeof(a));
	vector<string> mystr;
	string str1;
	for(int i=0; i<l; i++){
		char tmp = fun(str[i]);
		if(tmp != NULL){
			string tmp1 = str1;
			tmp1+=tmp;
			mystr.push_back(tmp1);
		}
		str1+=str[i];
		a[str[i]-'a'] = 1;
	}
	char tmp = fun(0);
	if(tmp != NULL){
			string tmp1 = str1;
			tmp1+=tmp;
			mystr.push_back(tmp1);
		}
	if(mystr.size()==0){
		cout<<"-1\n";
		return 0;
	}
	sort(mystr.begin(), mystr.end());
	cout<<mystr[0]<<endl;
	
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  string ST;
  cin >> ST;
  int ans = 0;
  char now = 'S';
  int count = 0,s = 0;
  rep(i,ST.size()){
    if(ST.at(i) == now) count++;
    else{
      if(now=='S'){
        s = count;
        count = 1;
        now = 'T';
      }else{
        if(count < s){
          count = s-count+1;
          now = 'S';
        }else{
          ans += count-s;
          count = 1;
          now = 'S';
        }
      }
    }
  }
  if(ST.at(ST.size()-1)=='S') ans += count;
  else ans += abs(s-count);
  cout << ans << endl;
    
  return 0;
}



Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define mp make_pair
#define IP pair<int,int>
#define enld endl

int main() {
	lint K;
	string S;
	cin >> K >> S;
	if (S.size() <= K) {
		cout << S << enld;
	}
	else {
		rep(i, K) {
			cout << S[i];
		}
		cout << "..." << endl;
	}
}

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

using namespace std;

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

struct Segtree{
	typedef int sgT;
	vector<sgT> seg;
	int nbn; sgT INF;
	void init(int n){
		for(nbn=1; nbn<n+2; nbn<<=1); INF=1<<29; // min:+inf,max:-inf
		seg.assign(nbn*2, INF);
	}
	sgT comp(sgT l, sgT r){return min(l, r);}  //min<->max
	void update(int k,sgT x){
		k+=nbn-1; seg[k]=x;
		while(k>0){ k=(k-1)/2; seg[k]=comp(seg[k*2+1],seg[k*2+2]); }
	}
	sgT query2(int a,int b,int l,int r,int k){
		if(b<=l||r<=a) return INF;
		if(a<=l&&r<=b) return seg[k];
		return comp(query2(a,b,l,(l+r)/2,k*2+1), query2(a,b,(l+r)/2,r,k*2+2));
	}
	sgT query(int a,int b){ return query2(a,b,0,nbn,0); }
	sgT get(int a){return seg[nbn+a-1];}  // =query(a,a+1)
};

struct Sts{
	int v,l,r,a,b;
	Sts(int v,int l,int r,int a,int b):v(v),l(l),r(r),a(a),b(b){}
	bool operator>(const Sts& b) const {
		return v > b.v; 
	}

};

Segtree sgg, sgk;


int gtps(int l, int r, int v,  Segtree& sgt){
	
	int lo=l-1, hi=r;
	while(hi - lo >1){
		int md = (hi + lo) >> 1;
		if( sgt.query(lo, md+1) == v ) hi = md; else lo = md; 
	}

	return hi;
}

Sts f(int l, int r){
	auto& sg1 = l%2? sgk : sgg;
	auto& sg2 = l%2? sgg : sgk;
	int v,a,b;
	
	v = sg1.query(l,r);
	a = gtps(l,r,v,sg1);
	int t = sg2.query(a+1,r);
	b = gtps(a+1,r,t,sg2);
	
	return Sts(v,l,r,a,b);
}

int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	VI p(n);
	sgg.init(n+2); sgk.init(n+2);

	rep(i,n){
		int c; cin >>c;
		p[i] = c;
		if(i%2) sgk.update(i,c);
		else sgg.update(i,c);
	}
	Sts sta = f(0,n);
	priority_queue<Sts, vector<Sts>, greater<Sts> > pq;
	pq.push(sta);
	VI ans;
	int ct=0;
	while(!pq.empty()){
		auto cr = pq.top(); pq.pop();
		//printf("%d:%d:%d:%d:%d   ",cr.v,cr.l,cr.r,cr.a,cr.b);
		ans.push_back(p[cr.a]);
		ans.push_back(p[cr.b]);
		if(cr.a - cr.l > 1) pq.push(f(cr.l, cr.a));
		if(cr.b - cr.a > 1) pq.push(f(cr.a+1, cr.b));
		if(cr.r - cr.b > 1) pq.push(f(cr.b+1, cr.r));
	}
	
	for(auto x :ans) printf("%d ",x); puts("");
	return 0;
}


Measured memory_bytes: 8980
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#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 per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; 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 a, b, c, d; cin >> a >> b >> c >> d;
    cout << max(a*b, c*d) << endl;
}

Measured memory_bytes: 256
from sys import stdin
input = stdin.readline
GI = lambda: int(input())
gi = lambda: list(map(int, input().split()))

a, b, c = gi()

from decimal import getcontext, Decimal
getcontext().prec = 800

A = Decimal(a).sqrt()
B = Decimal(b).sqrt()
C = Decimal(c).sqrt()

if A + B < C:
    print "Yes"
else:
    print "No"

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

typedef long long ll;

main()
{
    int n, i, j, c = 0;
    cin >> n;
    for(i = 1; i <= 9; i++){
        if(n % i == 0){
            if(n / i <= 9){
                cout << "Yes";
                break;
            }
        }
        c++;
    }

    if(c == 9 && i != 9){
        cout << "No";
    }


}





///promy_pompom
//hello world


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

typedef unsigned long long ll;

const int MAX=1<<23;
const int MAXN=100100;

int data[MAX],datb[MAX];

void add(int a,int b,int x,int k,int l,int r)
{
	if(a<=l&&r<=b)data[k]+=x;
	else if(l<b&&a<r)
	{
		datb[k]+=(min(b,r)-max(a,l))*x;
		add(a,b,x,k*2+1,l,(l+r)/2);
		add(a,b,x,k*2+2,(l+r)/2,r);
	}
	return;
}

ll sum(int a,int b,int k,int l,int r)
{
	if(b<=l||r<=a)return 0;
	else if(a<=l&&r<=b)return data[k]*(r-l)+datb[k];
	else
	{
		ll res=(min(b,r)-max(a,l))*data[k];
		res+=sum(a,b,k*2+1,l,(l+r)/2);
		res+=sum(a,b,k*2+2,(l+r)/2,r);
		return res;
	}
}

int main()
{
	int n;
	cin>>n;
	int m;
	cin>>m;
	int p[MAXN];
	for(int i=0;i<m;i++)
	{
		cin>>p[i];
	}
	for(int i=1;i<m;i++)
	{
		add(min(p[i-1],p[i]),max(p[i-1],p[i]),1,0,0,n);
	}
	int a[MAXN],b[MAXN],c[MAXN];
	for(int i=1;i<n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
	}
	
	ll ans=0;
	for(int i=1;i<n;i++)
	{
		ll s=sum(i,i+1,0,0,n);
		if(a[i]*s<b[i]*s+c[i])ans+=a[i]*s;
		else ans+=b[i]*s+c[i];
	}
	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 6180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, a, b;
    cin >> n >> a >> b;

    if (a * n < b) {
        cout << a * n << endl;
    }
    else
    {
        cout << b << endl;
    }
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define pi 3.14159265358979323846
using namespace std;
typedef long long ll;

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

int main()
{

  int k; cin >> k;
  cout << (k/2) * (k-k/2) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
 
#define INF (1<<31)//INT_MAX/2
#define MOD 1000000007
 
using ll  = long long;
using ull = unsigned long long;
 
int main(int argc, char *argv[])
{
    int N;
    std::cin >> N;

    std::vector<int> a(3*N);
    for (int i = 0; i < 3*N; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end(), std::greater<int>());

    double sum = 0;
    for (int i = 0; i < 2*N; i++) {
        if (i % 2 != 0) {
            sum += a[i];
        } else {
            ;
        }
    }
    
    std::string s = std::to_string(sum);

    for (int i = 0; i < 7; i++) {
        s.pop_back();
    }
    std::cout << s << std::endl;

    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
int main(){
  long long N, K;
  std::cin >> N >> K;
  long long ans = 0;
  if(K % 2 != 0){
    long long t = N / K;
    ans = t*t*t;
  }
  else{
    long long t = N*2/K - N / K;
    long long s = N / K;
    ans = t*t*t + s*s*s;
  }
  std::cout << ans << std::endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>

#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <limits>
#include <queue>
#include <unordered_map>
#include <list>
#include <set>
#include <numeric>
using namespace std;

using ll = long long;

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

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

		x.push_back(vector<int>(A[i]));
		y.push_back(vector<int>(A[i]));
		rep(j, A[i])
		{
			cin >> x[i][j] >> y[i][j];
			--x[i][j];
		}
	}

	int iter_num = 1 << N;
	int ans = 0;
	rep(i, iter_num)
	{
		vector<int> a(N, 0);
		int m = i;
		int count = 0;
		for (int j = 0; m != 0; ++j)
		{
			if ((m & 0x1) == 1)
			{
				a[j] = 1;
				++count;
			}
			m >>= 1;
		}

		if (count <= ans) continue;

		bool isOk = true;
		rep(j, N)
		{
			if (a[j] == 1)
			{
				rep(k, A[j])
				{
					if (a[x[j][k]] != y[j][k])
					{
						isOk = false;
						break;
					}
				}

				if (!isOk)
				{
					break;
				}
			}
		}

		if (isOk) ans = count;
	}

	cout << ans << endl;
}

Measured memory_bytes: 3636
#include<stdio.h>

#define MAX_COUNT 10
#define MAX_VALUE 1000

int main() {
	int i, j, m, n;
	int heights[MAX_COUNT];

	for (i=0; i<MAX_COUNT; i++) {
		scanf("%d", &heights[i]);
	}

	for (i=0; i<3; i++) {
		n = heights[i];
		for (j=i+1; j<MAX_COUNT; j++) {
			m = heights[j];
			if (m > n) {
				heights[j] = n;
				heights[i] = m;
				n = m;
			}
		}
		printf("%d\n", heights[i]);
	}

	return 0;
}

Measured memory_bytes: 600
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		
		List <Integer> L =  new ArrayList <Integer>();
		
		int temp = A;
		int i = 1;
		
		while (L.contains(temp)!=true){
			L.add(temp);
			
			if (temp%2==0)
				temp/=2;
			else
				temp = temp*3+1;
	
			i++;
		}
		
		System.out.println(i);
		sc.close();
	}

}


Measured memory_bytes: 21332
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */
//xは回文数か
bool is_kaibun(ll x){
  if(x%10 == 0) return false;
  string s = to_string(x);
  ll l = 0; 
  ll r = s.size()-1;
  while(l<=r){
    if(s[l] != s[r]) return false;
    l++;
    r--;
  }
  return true;
}

//1,2,...,xの中で回文数がいくつあるか
ll calc(ll x){
  ll res = 0;
  FOR(i, 1, x+1){
    if(is_kaibun(i)) res++;
  }
  return res;
}

int main() {
  ll a,b; cin >> a >> b;
  cout << calc(b) - calc(a-1) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    string ans = "keyence";
    string s;cin>>s;
    int window = s.size()-7;
    for(int i=0;i<=s.size()-window;i++){
        string tmp="";
        tmp.append(s.substr(0,i));
        tmp.append(s.substr(i+window));
        if(ans==tmp){co("YES");return 0;}
    }
    co("NO");
}

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

int main() {
    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; ++i) cin >> a[i];
    int q; cin >> q;
    map<int, string> exist_map;
    int m[q]; for (int i = 0; i < q; ++i) cin >> m[i], exist_map[m[i]] = "no";
    
    for (int bit = 0; bit < (1 << n); ++bit) {
        int sum = 0;
        for (int i = 0; i < n; ++i) if (bit & (1 << i)) sum += a[i];
        
        if (exist_map[sum] == "no") exist_map[sum] = "yes";
    }
    
    for (int i = 0; i < q; ++i) cout << exist_map[m[i]] << endl;
    
    return 0;
}


Measured memory_bytes: 3236
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace 新しいフォルダー__2_
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {  
            int K = cin.ReadInt;
            int S = cin.ReadInt;

            int ans = 0;
            for(int x = 0;x<=K;x++){
                for(int y=0;y<=K;y++){
                    int z= S-(x+y);
                    if( 0<=z && z<=K) ans++;
                    
                }
            }

            Console.WriteLine(ans);

        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}


Measured memory_bytes: 27748
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int main(){
  int a, b, c, k;cin>>a>>b>>c>>k;
  if(k>a+b)cout<<a-(k-a-b)<<endl;
  else cout<<min(a, k)<<endl;
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


Measured memory_bytes: 3592
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://atcoder.jp/contests/tdpc/tasks/tdpc_number
    # https://atcoder.jp/contests/tdpc/submissions/14489469
    n = input()
    d=int(input())
    # dp[ i ][ smaller ][ d ] := i 桁目までで 0 以外の数の使用数dである数の個数


    dp = [[[0] * (d+2) for _ in range(2)] for _ in range(len(n) + 1)]
    dp[0][0][0] = 1
    
    MOD = 10**9 + 7
    for i in range(len(n)):
        c = ord(n[i]) - ord('0')
        for j in range(d+1):
            # small->small
            dp[i+1][1][j+1]+=dp[i][1][j]*9
            dp[i+1][1][j]+=dp[i][1][j]

            # else->small
            if c>0: # i桁めが0以外
                dp[i + 1][1][j+1]+=dp[i][0][j]*(c-1) #i+1桁目が0以外
                dp[i + 1][1][j]+=dp[i][0][j]#0
            

            # else->else
            if c>0:
                dp[i + 1][0][j+1]+=dp[i][0][j]
            else:
                dp[i+1][0][j]+=dp[i][0][j]
                dp[i + 1][0]
    
    print(dp[len(n)][1][d] + dp[len(n)][0][d])
    
    
    
resolve()

Measured memory_bytes: 62404
#include<stdio.h>
   
#define MAXLEN 100000
    
     
int main( void ) 
{
    int n,q;
    int S[MAXLEN+1],T[MAXLEN+1];
    int i;
    int cnt;
    int lo,hi,m;
       
    scanf( "%d", &n ); 
    for( i=0; i<n; i++ ) {
        scanf( "%d", &S[i] ); 
    }
   
    scanf( "%d", &q); 
    for( i=0; i<q; i++ ) {
        scanf( "%d", &T[i] ); 
    }
    
    cnt=0;
    for( i=0; i<q; i++ ) {
		lo=0;
		hi=n;
		while( lo <= hi ) {
			m=(lo+hi)/2; 
            if( T[i] == S[m] ) {
                cnt++;
                break;
            } else if( T[i] < S[m] ) {
            	hi=m-1;
            } else {
            	lo=m+1;        	
            }
        }
    }
 
    if( cnt ) {
        printf( "%d\n", cnt );
    } else {
        printf( "0\n" );
    }
   
    return 0;
}

Measured memory_bytes: 1192
m[5]['= r'],z,d[4]={0,-2},k,i;f(i){m[k+1][i]=i[*m]+47?0:m[k+1][i]?:1+f(d[k]-~i);}main(t){for(scanf("%*d%d",d);m[0][++i-~*d]=~getchar();d[2]=-*d-2);for(;k--?:(z=z<-t?-t:z,t=k=3,--i);)t-=f(i-~*d);printf("%d",z);}

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

int main(){
	int a,b,c;
	int i,j;

	cin >> a >> b >> c;
	j=0;
	for (i=a;i<=b;i++){
		if(c%i==0){
			j++;
		}
	}
	cout << j << endl;
	return 0;
}



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

int main() {
	string s;
	cin>>s;
	
	string t="ATCG";
	int ans=0;
	
	for(int i=0;i<s.size();i++){
		int now=0;
		for(int j=i;j<s.size();j++){
			bool ok=false;
			for(int k=0;k<t.size();k++){
				if(s[j]==t[k])ok=true;
			}
			if(ok){
				now++;
				ans=max(ans,now);
			}else{
				break;
			}
		}
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a,b = LI()
print(a*b)

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

using namespace std;

typedef long long ll;
const int MAX = 100005;
const int MOD = 1000000007;


void solve()
{
	
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	ll n;
	cin>>n;
	ll ans=n/2;
	ans+=n%2;
	cout<<ans<<endl;	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int main() {
    int a, b, c, d, e;
    scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
    int min = std::min({(a+9)%10, (b+9)%10, (c+9)%10, (d+9)%10, (e+9)%10});
    a = (a + 9) / 10;
    b = (b + 9) / 10;
    c = (c + 9) / 10;
    d = (d + 9) / 10;
    e = (e + 9) / 10;
    if (min == 9) {
        printf("%d", (a+b+c+d+e)*10);
    } else {
        printf("%d", (a+b+c+d+e-1)*10+min+1);
    }
}

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

b=[0]*(N+1)
M=0

for i in range(N,0,-1):
    cnt = 0

    for j in range(i+i,N+1,i):
        if b[j] == 1:
            cnt += 1

    if a[i-1]==1 and cnt%2==0:
        b[i]=1
        M+=1
    elif a[i-1]==0 and cnt%2==1:
        b[i]=1
        M+=1
        

print(M)
for i in range(1,N+1):
    if b[i]==1:
        print(i,end=" ")


Measured memory_bytes: 7276
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<string>

using namespace std;
#define ll long long

int main(){
    ll b= 1;
    while(b > 0){
        cin >> b;
        if(b==0)break;
        ll a = 0, c = 0;
        ll kai = 0;
        ll first = 0;

        while(1){
            c++;
            a = b/c - (c-1)/2;
            if( (2*b -(c*c)+c) % (2*c) == 0 && a > 0){ 
                kai = c;
                first = a;
            }
            if(a < 0) break;
        }
        cout << first << " " << kai << endl;
    }


}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MAX 510000
#define rrep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define dcout cout<<fixed<<setprecision(15);
#define mp make_pair
#define pb push_back
 
using namespace std;
typedef long long int  ll;
typedef pair<ll, ll> P;
 
constexpr int MOD = 1e9 + 7;
constexpr ll inf = 1LL << 60;
 
template< typename S, typename T >
inline void chmax(S &a, const T &b) { if(a < b) a = b; }
 
template< typename S, typename T >
inline void chmin(S &a, const T &b) { if(a > b) a = b; }
 
 
//lcm//
ll gcd(ll x, ll y) {
	if (x == 0) return y;
	return gcd(y%x, x);
}
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }
 
//a^n mod p//
ll modpow(ll a, ll n, ll p) {
	if(n==0) return (ll)1;
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modpow(a, n - 1, p)) % p;
  ll t = modpow(a, n / 2, p);
  return (t * t) % p;
}
 
//inversemod//
ll modinv(ll a, ll m) {
	if(m==0)return (ll)1;
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
 
//Cmonp//
ll 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;
	}
}
 
// 
ll COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
//LARGE n
ll com(ll n,ll m){
    if(n<m || n<=0 ||m<0){
		return 0;
	}
	if( m==0 || n==m){
		return 1;
	}
	ll k=1;
	for(ll i=1;i<=m;i++){
       k*=(n-i+1); 
	   k%=MOD;
	   k*=modinv(i,MOD);
	   k%=MOD;
	}
	return k;
}
 
//radP
ll rad(ll u, ll p){
ll cnt=0;
	while(u%p==0){
		u/=p;
		cnt++;
	}
	return cnt;
}
 
 
////////////////////////////////////////////////////////////////////
 
int main() {

 
 
ll n;
cin>>n;
ll a[n+1];
rep(i,n){
	cin>>a[i];
}
 
int num[1000005];
rep(i,1000000){
	num[i]=0;
}
 
rep(i,n){
num[a[i]]++;
}
 
ll ans=0;
rep(j,n){
	int imp=0;
ll now=a[j];
vector<ll> vec{};
for(ll i=1;i*i<=a[j];i++){
	if(a[j]%i==0){vec.push_back(i); vec.push_back(a[j]/i);}
}
for(int i=0;i<vec.size();i++){
	
if(num[vec[i]]){
	if(vec[i]==a[j]&&num[vec[i]]==1){continue;}
	imp=1;
	break;}
}
if(imp)continue;
ans++;
 
}
 
cout<<ans<<endl;
 
 
 
return 0;
}

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

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

  int counter = 0;

  vector<int> d(n);
  for (int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;

    d.at(i) = tmp;

    bool exist = false;
    for (int j = 0; j < i; j++) {
      if (d.at(j) == tmp) {
        exist = true;
        break;
      }
    }
    if (!exist) {
      counter++;
    }
  }
  cout << counter << endl;
}


Measured memory_bytes: 256
//quming
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
int read(char *s){
    R int len=0;R char ch;while(((ch=getc())>'9'||ch<'0'));
    for(s[++len]=ch;(ch=getc())>='0'&&ch<='9';s[++len]=ch);
    return s[len+1]='\0',len;
}
double readdb()
{
    R double x=0,y=0.1,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(x=ch-'0';(ch=getc())>='0'&&ch<='9';x=x*10+ch-'0');
    for(ch=='.'&&(ch=getc());ch>='0'&&ch<='9';x+=(ch-'0')*y,y*=0.1,ch=getc());
    return x*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
int P;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int inc(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
const int N=2e5+5;
typedef long long ll;
map<int,int>mp,mmp;int a[N],n;ll res;
int main(){
	scanf("%d%d",&n,&P);
	if(P==1)return puts("0"),0;
	fp(i,1,n)scanf("%d",&a[i]),a[i]%=P,upd(a[i],a[i-1]);
	fp(i,1,n)a[i]-=i;
	mp[0]=1;
	fp(i,1,n){
		res+=mp[a[i]];
		res+=mp[a[i]+P]-mmp[a[i]+P];
		++mp[a[i]];
		if(i-P+1>=0)++mmp[a[i-P+1]];
	}
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 29184
#include<bits/stdc++.h>
#define M 1000000007
#define N 100005
#define int long long
using namespace std;

int A[N], dp[N];
int n, t;

int bynary_search(int idx){

  int l=0, r=idx;

  while(l<r){
    
    int Mid=(l+r)/2;

    if(A[idx]-A[Mid]<=t) r=Mid;
    else l=Mid+1;
      
  }

  return l;
}

main(){


  
  cin>>n>>t;

  for(int i=0;i<n;i++) scanf("%d", &A[i]);

  sort(A, A+n);
  
  dp[0]=1;

  for(int i=1;i<n;i++){
    
    int r=bynary_search(i);
    
    dp[i]=(dp[i-1]+(dp[i-1]*(i-r))%M)%M;
  }
  
  cout<<dp[n-1]<<endl;  
  
}

Measured memory_bytes: 4764
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int INF=1e10;
int MOD=1e9+7;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
}
int kurai(int a,int b){
  int m=pow(10,b),n=pow(10,b-1);
  return (a%m)/n;
}
int ketawa(int a){
  int k=0;
  rep(i,keta(a)){
  k+=kurai(a,i+1);
  }
  return k;
}
int gcd(int a,int b){
  if(a%b==0)
    return b;
  return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int mid(int a,int b,int c){
  vector<int> k(3);
  k[0]=a;k[1]=b;k[2]=c;
  sort(all(k));
  return k[1];
}
bool sosuu(int a){
  bool b=1;
  if(a<=1)
    return 0;
  else{
  rep1(i,sqrt(a)-1){
  if(a%(i+1)==0)
  b=0;
  }
  return b;
  }
}
int modpow(int a,int b,int m=MOD){
 if(!b)return 1; if(b&1)return modpow(a,b-1,m)*a%m;
 int memo = modpow(a,b>>1,m);
 return memo*memo%m;
}
int fact_mod(int n) {
    int f=1; 
for(int i=2;i<n+1;i++) f=f*(i%MOD)% MOD;
    return f;
}
int mod_pow(int x,int n) {
    int res=1;
    while(n>0){
        if(n&1) res=(res*x)%MOD; 
        x=(x*x)%MOD;        
n>>=1; 
    }
    return res;
}
int c_mod(int n, int r) {
    if(r>n-r) r=n-r;
    if(r==0) return 1;
    int a=1;
    rep(i,r) 
a=a*((n-i)%MOD)%MOD;
    int b=mod_pow(fact_mod(r), MOD-2);
    return (a%MOD)*(b%MOD)%MOD;
}
signed main(){
  int a,b;
  cin>>a>>b;
  vector<int> c(b);
  rep(i,b)
    cin>>c[i];
  vector<bool> d(102,0);
  int f=INF,k=0;
  rep(i,b)
    d[c[i]]=1;
  rep(i,102){
  if(!d[i]){
  if(f>abs(a-i)){
  f=abs(a-i);
    k=i;
  }
  }
  }
  out(k);
}


Measured memory_bytes: 3780
#include <bits/stdc++.h>
using namespace std;
typedef tuple<long long, long long, long long> T;
int main() {
    int N;
    cin >> N;
    vector<T> v(N);
    for (int i = 0; i < N; i++) {
        long long A, B;
        cin >> A >> B;
        v[i] = T(A + B, A, B);
    }
    sort(v.begin(), v.end(), greater<T>());
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            sum += get<1>(v[i]);
        } else {
            sum -= get<2>(v[i]);
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 2688
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;

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

ll rui[n+1];
rui[0]=0;
rui[1]=0;
rep(i,n+1){rui[i]=0;}
for(int long long i=1;i<n;i++){
    if(s[i]=='C'&&s[i-1]=='A'){
        rui[i+1]+=rui[i]+1;
    }else{
        rui[i+1]=rui[i];
    }

}
rep(i,q){
    ll a,b;
    cin>>a>>b;
    cout<<rui[b]-rui[a]<<endl;





}

    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
int main(){
  int a,b,c,tmp;
  scanf("%d%d%d",&a,&b,&c);
  if(b < a){
    tmp = a;
    a = b;
    b = tmp;
  }
  if(c < b){
    tmp = b;
    b = c;
    c = tmp;
    if(b < a){
      tmp = a;
      a = b;
      b = tmp;
    }
  }
  printf("%d %d %d\n",a,b,c);
  return 0;
}

Measured memory_bytes: 2700
n = int(input())
a = list(map(int, input().split()))
b=0
x=0
for i in range(n):
  if a[i]%2==0:
    x+=1
    if a[i]%3==0 or a[i]%5==0:
      b+=1
print('APPROVED' if b==x else 'DENIED')

Measured memory_bytes: 9140
#include<iostream>
#include<cstring>
using namespace std;
int dp[100][4][4];
int plan[100],N,K;
int solve(int,int,int);
int main(){
  cin >> N >> K;
  for(int i=0,a,b;i<K;i++){
    cin >> a >> b;
    plan[a-1] = b;
  }
  memset(dp,-1,sizeof(dp));
  cout << solve(0,0,0) << endl;
}
int solve(int day,int b1,int b2){ //今日の日付,前日のPasta,前々日のPasta
  if(day == N) return 1;
  if(dp[day][b1][b2] != -1) return dp[day][b1][b2];
  if(plan[day] != 0){
   return (b1 == b2 && b1 == plan[day] ? 0 : solve(day+1,plan[day],b1)%10000);
  }
  int sum=0;
  for(int i=1;i<=3;i++){
    if(i==b1&&b1==b2)continue;
    sum += solve(day+1,i,b1) % 10000;
  }
  return dp[day][b1][b2] = sum % 10000;
}

Measured memory_bytes: 1172
#include <cstdio>
int main() {
    int n, f = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        if(x & 1)f = 1;
    }
    if(f)puts("first");
    else puts("second");
    return 0;
}


Measured memory_bytes: 128
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;


#define MAX 100000
#define INF 2140000000
#define MOD 1000000007

bool badnumber(int num, vector<int> v) {
	bool bad = 0;

	while (num) {
		if (v[num % 10]) {
			bad = 1;
		}
		num /= 10;
	}

	return  bad;
}

int main() {
	int n, k, temp;
	vector<int> d(10);

	cin >> n >> k;

	for (int i = 0; i < n; ++i) {
		cin >> temp;
		d[temp] = 1;
	}
	
	while(badnumber(n,d)) {
		n++;
	}

	cout << n;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {

  int N, T; std::cin >> N >> T;

  int cmin = std::numeric_limits<int>::max();
  for(int i=0; i<N; i++) {
    int c, t; std::cin >> c >> t;
    if ( t <= T && cmin > c ) cmin = c;
  }
  if ( cmin == std::numeric_limits<int>::max() ) std::cout << "TLE" << std::endl;
  else std::cout << cmin << std::endl;
  return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
p = list(map(int, input().split()))

p_mean = [(i+1)/2 for i in p]

p_ruikei = [0] * n
p_ruikei[0] =  p_mean[0]

for i in range(1, n):
    p_ruikei[i] = p_ruikei[i-1] + p_mean[i]

maxx = p_ruikei[k-1]
for i in range(1, n-k+1):
    mean = p_ruikei[i+k-1] - p_ruikei[i-1]

    if mean > maxx:
        maxx = mean

print(maxx)

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

int a[16][16];
int c[16];
int points[16];

static int solve(const int pos, const int n, const int m, const int x, const int so_far) {
    if (pos == n) {
        return -1;
    }

    int notuse = solve(pos + 1, n, m, x, so_far);

    int use = -1;
    int pass_cnt = 0;
    for (int j = 0; j < m; j++) {
        points[j] += a[pos][j];
        if (points[j] >= x)
            pass_cnt++;
    }
    if (pass_cnt < m) {
        auto tmp = solve(pos + 1, n, m, x, so_far + c[pos]);
        if (tmp >= 0)
            use = tmp;
    } else {
        use = so_far + c[pos];
    }
    for (int j = 0; j < m; j++) {
        points[j] -= a[pos][j];
    }

    if (use < 0)
        return notuse;
    if (notuse < 0)
        return use;
    return min(use, notuse);
}

int main() {
    int n, m, x;
    cin >> n >> m >> x;

    for (int i = 0; i < n; i++) {
        cin >> c[i];
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    }

    cout << solve(0, n, m, x, 0) << "\n";
    return 0;
}


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

int main() {
    int64_t X;
    cin >> X;
    for (int64_t i = X; ; i++) {
        bool ok = true;
        for (int64_t j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int euler_phi(int n) {
  int r=n;
  for(int i=2;i*i<=n;i++) {
    if(!(n%i)){
      r-=r/i;
      while(!(n%i))n/=i;
    }
  }
  if(n>1)r-=r/n;
  return r;
}
int main() {
  int n;cin>>n;
  cout<<euler_phi(n)<<endl;
  return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
 
// Type alias
using ll=long long;
using ld=double;
 
using pi=pair<int,int>;
using pll=pair<ll,ll>;
using pld=pair<ld,ld>;
using ti3=tuple<int, int, int>;
 
using vi=vector<int>;
using vll=vector<ll>;
using vld=vector<ld>;
using vpi=vector<pi>;
using vpll=vector<ll>;
using vpld=vector<ld>;
using vti3=vector<ti3>;
 
// Constants
const double EPS = 1e-9;
const int inf = numeric_limits<int>::max();
 
// Macro
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rrep(i,n) for(int i=int(n-1);i>=0;--i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,a,b) for(int i=int(b-1);i>=int(a);--i)
#define SHOW(a) cout << #a << " = " << a << endl
#define ARR(a,n) for(int i=0;i<int(n);++i) cout << #a << "[" << i << "]" << " = " << a[i] << endl
 
#define ALL(a) a.begin(),a.end()
 
// Funtcions
ll pow(ll base, ll i, ll mod){
  ll a = 1;
  while(i){
    if (i & 1) {
      a *= base;
      a %= mod;
    }
    base *= base;
    base %= mod;
    i >>= 1;
  }
  return a;
}
ll gcd(ll a, ll b){
  while(b){
    ll c = a % b;
    a = b;
    b = c;
  }
  return a;
}
ll lcm(ll a, ll b){
  return a / gcd(a, b) * b;
}
 
 
void solve(){
  int K, N;
  cin >> K >> N;
  int A[2 * 100000 + 5];
  rep(i,N) cin >> A[i];
  int D[2 * 100000 + 5];
  rep(i, N) D[i] = A[i + 1] - A[i];
  D[N] = A[0] + K - A[N-1];
  sort(D, D + N + 1);
  cout << K - D[N] << endl;
}
 
int main(){
  // FastIO
  //ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}





















Measured memory_bytes: 1792
s = list(input())
t = list(input())

min = len(t)

for i in range(len(s) - len(t) + 1):
    
    diff = 0
    
    for j in range(len(t)):
        if t[j] != s[i + j]:
            diff += 1
    
    if diff < min:
        min = diff
    
    
print(min)

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

using namespace std;

int main(){
    int n;
    cin >> n;
    if (n%2){
        cout << fixed << setprecision(8) << (float)(n/2 + 1)/n;
    }
    else{
        cout << fixed << setprecision(8) << (float)(n/2)/n;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    char arr[12];
    cin>>a>>b>>arr;
    bool p=true;
    c=a+b+1;
    if(arr[a]!='-') p=false;
    for(int i=0;i<c;i++){
        if(i!=a){
            if(arr[i]>'9' || arr[i]<'0') p=false;
        }
    }
    if(p) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

int main()
{
  int h, w;
  cin >> h >> w;
  char a[h][w];
  bool hflag[h];
  for (int i = 0; i < h; i++) hflag[i] = false;
  bool wflag[w];
  for (int i = 0; i < w; i++) wflag[i] = false;

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> a[i][j];
      if (a[i][j] == '#') {
        hflag[i] = true;
        wflag[j] = true;
      }
    }
  }

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (hflag[i] && wflag[j]) cout << a[i][j];
    }
    if (hflag[i])cout << endl;
  }
}


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

int main() {
  int m,n;cin>>m>>n;
  int ans=0,cnt=0;
  map<int,int> ac,wa;
  rep(i,n){
    int p;string s;cin>>p>>s;
    if(s=="WA")wa[p]++;
    else {
      if(ac[p]==0){
        cnt+=wa[p];
        ans++;
        ac[p]++;
      }
    }
  }
  cout<<ans<<" "<<cnt<<endl;
}

Measured memory_bytes: 12952
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    print(N*(N-1)//2+M*(M-1)//2)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n,i,a[1000],x=0;
   cin>>n;

   for(i=0;i<n;i++)
   {
       cin>>a[i];
   }
   for(i=1;i<n-1;i++)
   {
       if((a[i]>a[i-1] && a[i]<a[i+1]) || (a[i]>a[i+1] && a[i]<a[i-1]))
        x++;
   }

   cout<<x<<endl;

    return 0;
}


Measured memory_bytes: 256
#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, K, A, C[30], res;

int main() {
	cin >> N >> M;
	for (int i = 0; i != N; ++i) {
		cin >> K;
		for (int j = 0; j != K; ++j) {
			cin >> A;
			++C[A - 1];
		}
	}
	for (int i = 0; i != M; ++i) {
		if (C[i] == N)++res;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <list>
#include <cmath>
using namespace std;
#define rep(i,m,n) for (int i = (int) (m); i < (int) (n); i++)
#define rep1(i,m,n) for (int i = (int) (m); i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
int main(){
    vector<vector<int> > bin(3,vector<int>(3));
    int N,i,j,k;
    rep(i,0,3){
        rep(j,0,3)cin>>bin.at(i).at(j);
    }
    cin>>N;
    vector<int> data(N);
    rep(i,0,N)cin>>data.at(i);
    rep(i,0,N){
        rep(j,0,3){
            rep(k,0,3){
                if(bin.at(j).at(k)==data.at(i))bin.at(j).at(k)=0;
            }
        }
    }
    if((bin.at(0).at(0)==0 && bin.at(0).at(1)==0 && bin.at(0).at(2)==0) || (bin.at(1).at(0)==0 && bin.at(1).at(1)==0 && bin.at(1).at(2)==0) ||
        (bin.at(2).at(0)==0 && bin.at(2).at(1)==0 && bin.at(2).at(2)==0) || (bin.at(0).at(0)==0 && bin.at(1).at(0)==0 && bin.at(2).at(0)==0) ||
        (bin.at(0).at(1)==0 && bin.at(1).at(1)==0 && bin.at(2).at(1)==0) || (bin.at(0).at(2)==0 && bin.at(1).at(2)==0 && bin.at(2).at(2)==0) ||
        (bin.at(0).at(0)==0 && bin.at(1).at(1)==0 && bin.at(2).at(2)==0) || (bin.at(0).at(2)==0 && bin.at(1).at(1)==0 && bin.at(2).at(0)==0)){
            cout<<"Yes"<<endl;
        }else cout<<"No"<<endl;
}

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

int main()
{
	int N_ac = 0;
	int N_wa = 0;
	int N_tle = 0;
	int N_re = 0;

	int N;
	cin >> N;

	string text;

	for (int i = 0; i < N; i++) {
		cin >> text;
		if (text == "AC")	N_ac++;
		if (text == "WA")	N_wa++;
		if (text == "TLE")	N_tle++;
		if (text == "RE")	N_re++;
	}
	cout << "AC x " << N_ac << endl;
	cout << "WA x " << N_wa << endl;
	cout << "TLE x " << N_tle << endl;
	cout << "RE x " << N_re << endl;

	return 0;
}

Measured memory_bytes: 3628
import java.util.*;
 
public class Main {
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = Integer.parseInt(sc.next());
    	int k = Integer.parseInt(sc.next());
    	long s = Long.parseLong(sc.next());
    	if(s < 1000000000) {
        	for(int i=0; i<k; i++) {
        	    System.out.print(s+" ");
        	}
        	for(int i=k; i<n; i++) {
        	    if(i < n-1) System.out.print(s+1+" ");
        	    else System.out.println(s+1);
        	}
    	}else {
    	    for(int i=0; i<k; i++) {
        	    System.out.print(s+" ");
        	}
        	for(int i=k; i<n; i++) {
        	    if(i < n-1) System.out.print(1+" ");
        	    else System.out.println(1);
        	}
    	}
    }
}

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

#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int

const int maxr = 1e5 + 5;


int32_t main()
{
	GO;
	int n;
	cin >> n;
	int i;
	for (i = 0; i < n; i += 1000);
	cout << i - n << endl;
	return 0;
}

//!

Measured memory_bytes: 3644
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 200005;

int n;
int a[MAXN];

ll ans;
ll sum[MAXN];

int main()
{
	scanf("%d",&n);
	for (int i = 1;i <= n;i++)
	{
		scanf("%d",&a[i]);
		sum[i] = sum[i - 1] + a[i];
	}
	sort(sum,sum + n + 1);
	int cnt = 0;
	for (int i = 0;i <= n;i++)
		if (i > 0 && sum[i] != sum[i - 1])
			ans += (ll)cnt * (cnt - 1) / 2,cnt = 1;
		else
			cnt++;
	ans += (ll)cnt * (cnt - 1) / 2;
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;
using ll = long long;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
const int MOD = 1e9+7;
const int MAX = 2e5+1;
long long fac[MAX], finv[MAX], inv[MAX];

void comb_init() {
  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 comb(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;
}


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

  vector<ll> A(N);
  rep(i, N) cin >> A[i];
  sort(A.begin(), A.end());

  ll sum[N+1];
  sum[0] = 0;
  rep(i, N)
    sum[i+1] = (sum[i] + A[i]) % MOD;

  ll ans = 0;
  if (K == 1) {
    cout << 0 << endl;
    return 0;
  }
  rep(l, K, N+1) {
    ans += ((sum[N] - sum[l-1]) - sum[N - l + 1]) * comb(l-2, K-2);
    ans %= MOD;
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 6528