akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;

constexpr ll MOD = (ll)1e9 + 7;
constexpr ll MOD2 = 998244353;
constexpr ll HIGHINF = (ll)1e18;
constexpr ll LOWINF = (ll)1e15;
constexpr long double PI = 3.1415926535897932384626433;

template<typename T> vector<T> make_v(size_t N,T init){return vector<T>(N,init);}
template<typename... T> auto make_v(size_t N,T... t){return vector<decltype(make_v(t...))>(N,make_v(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
template <class T> void chmin(T& a, const T b){a=min<T>(a,b);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

int main() {
    ll A,B; cin >> A >> B;
    corner((A+B)%2==1,"IMPOSSIBLE");
    cout << (A+B)/2 << endl;




	
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> pp;
void SieveOfEratosthenes(int n) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          pp[p]++;
} 
  
void solve()
{
    int n,m,k,i,j,count=0,sum=0,maxi=0,mini=1e18,flag=0;
    cin>>n;
    
    SieveOfEratosthenes(1000001);
    
    int a[n];
    map<int,int> mp1;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        mp1[a[i]]++;
    }
    
    for(i=0;i<n;i++)
    {
        if(a[i]==1 && mp1[1]>1)
        {
            continue;
        }
        else if(a[i]==1 && mp1[1]==1)
        {
            count++;
            continue;
        }
        else if(mp1[a[i]]>1 || mp1.find(1)!=mp1.end())
        {
            continue;
        }
        flag=0;
        
        if(pp.find(a[i])!=pp.end())
        {
            count++;
            continue;
        }
        for(j=2;j<=sqrt(a[i]);j++)
        {
            if(a[i]%j==0)
            {
                if(mp1.find(j)!=mp1.end())
                {
                    flag=1;
                    break;
                }
                
                if(a[i]/j!=j)
                {
                    if(mp1.find(a[i]/j)!=mp1.end())
                    {
                        flag=1;
                        break;
                    }
                }
            }
        }
        
        if(flag==0) count++;
        
    }
    cout<<count;
    
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 22592
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    
    for(int i = 0; i < N; i++){
        cin >> p[i];
    }
    
    sort(p.begin(), p.end());
    
    int ans = 0;
    for(int i = 0; i < K; i++){
        ans += p[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 3236
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define inf 10000000LL
#define fast_io	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define mod 1000000007
#define range 1005
#define lg 22
using namespace std;
queue<pair<ll,ll> > mq;
queue<pair<pair<ll,ll> ,ll> >warpq,master;
ll visited[range][range];
ll A[range][range];
ll h,w;
ll dr[4]={0,0,-1,1};
ll dc[4]={1,-1,0,0};
void print()
{
				for(ll i=1;i<=h;i++)
	{
//		cin>>s;
		for(ll j=1;j<=w;j++)
		{
			cout<<visited[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"\n\n";
}
void simple(ll c)
{
	ll x,y,rr,cc;
//	print();
	while(mq.size())
	{
		
		x=mq.front().ff;
		y=mq.front().ss;
		master.push(mp(mp(x,y),c));
		mq.pop();
//		cout<<x<<"	"<<y<<endl;
		if(visited[x][y]!=-1)
		continue;
		visited[x][y]=c;
		
		for(ll i=0;i<4;i++)
		{
			rr=dr[i]+x;
			cc=dc[i]+y;
			if(rr<1||rr>h||cc<1||cc>w)
			continue;
			if(A[rr][cc]=='#')
			continue;
//			cout<<"x"<<endl;
//			cout<<rr<<" "<<cc<<endl;
			if(visited[rr][cc]==-1)
				mq.push(mp(rr,cc));
					
			
		}
//		cout<<"\n";
	}
//	print();
}

void warp()
{
	ll x,y,rr,cc,c;
//	cout<<"warp begin:\n";
	while(master.size())
	{
		
		x=master.front().ff.ff;
		y=master.front().ff.ss;
		c=master.front().ss;
		
		master.pop();
//		cout<<x<<"	"<<y<<endl;
		for(ll i=-2;i<=2;i++)
		{
			for(ll j=-2;j<=2;j++)
			{
				
				rr=x+i;
				cc=y+j;
				if(rr<1||rr>h||cc<1||cc>w)
				continue;
				if(A[rr][cc]=='#')
				continue;
				if(visited[rr][cc]==-1)
				warpq.push(mp(mp(rr,cc),c+1));
			}
			
		}
	}
//		cout<<warpq.size()<<endl;
//		cout<<"warp end:\n";
		
}
void move(ll x,ll y)
{

	ll c,rr,cc;
	warpq.push(mp(mp(x,y),1));
	while(warpq.size())
	{
		
		x=warpq.front().ff.ff;
		y=warpq.front().ff.ss;
		c=warpq.front().ss;
//		cout<<x<<"	xx	"<<y<<endl;
		warpq.pop();

		if(visited[x][y]==-1)
		{
			mq.push(mp(x,y));
		simple(c);
		}

		if(warpq.size()==0)
		warp();		
	}
	
	
	
}
int main()
{
	ll x,y,p,q;
	memset(visited,-1,sizeof(visited));
	cin>>h>>w;
	cin>>x>>y;
	cin>>p>>q;
	string s;
	for(ll i=1;i<=h;i++)
	{
		cin>>s;
		for(ll j=1;j<=w;j++)
		{
			A[i][j]=s[j-1];
		}
	}
	move(x,y);
	if(visited[p][q]==-1)
	cout<<-1<<endl;
	else cout<<visited[p][q]-1<<endl;

}

Measured memory_bytes: 19732
import sys

N = int(sys.stdin.readline().rstrip())

F = [[] for _ in range(N)]
for i in range(N):
    F[i] = list(map(int, sys.stdin.readline().rstrip().split()))

P = []
for i in range(N):
    P.append(list(map(int, sys.stdin.readline().rstrip().split())))

ans = -float("inf")
for i in range(1, 1<<10):
    score = 0
    for j in range(N):
        count = 0
        for k in range(10):
            # print(i & (1 << k))
            if i & (1<<k) and F[j][k] == 1:
                count += 1
        # print("count", count)
        score += P[j][count]
    # print(score)
    ans = max(ans, score)

print(ans)

Measured memory_bytes: 42212
#include<vector>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	int t,t1;
	bool j=0;
	for(t=0;t<=n;t++)
	{
		for(t1=0;t1<=m;t1++)
		{
			if(t*t1+(n-t)*(m-t1) == k)
				j = 1;
		}
	}
	if(j)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void)
{
	int i, j ;
	int H, W ;
	
	while(1){
		scanf("%d %d", &H, &W);
		if(H==0 && W==0){
			break;
		}
		
		for(i=1; i<=H; i++){
			for(j=1; j<=W; j++){
				if(i==1 || i==H){
					printf("#");
				}else{
					if(j==1 || j==W){
						printf("#");
					}else{
						printf(".");
					}
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	
	
	
	return 0;
}

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

int main()
{
	string n;
	cin >> n;
	for (int i = 0; i < n.size(); ++i)
	{
		if (n[i] == '1')
		{
			cout << "9";
		}
		else if (n[i] == '9')
		{
			cout << "1";
		}
		else
		{
			cout << n[i];
		}
	}
	cout << endl;
	return 0;
}

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

int main() {
int n;
  cin>>n;
  
  vector<int> vec(n);
  for (int i=0;i<n;i++){
    cin>>vec.at(i);}
  
  sort (vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  
  int a=vec.at(0);
    int b=0;
    for(int i=1;i<n;i++){
      b+=vec.at(i);}
  
  if(a<b){
    cout<<"Yes"<<endl;}
  else{
    cout<<"No"<<endl;}

}


Measured memory_bytes: 256
from collections import Counter


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    X = Counter(sorted(A[::2]))
    Y = Counter(sorted(A)[::2])
    K = set(list(X.keys()) + list(Y.keys()))
    diff = 0
    for k in K:
        tmp = 0
        if k in X:
            tmp += X[k]
        if k in Y:
            tmp -= Y[k]
        diff += abs(tmp)
    print(diff//2)


if __name__ == "__main__":
    main()


Measured memory_bytes: 67928
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;

long long cnt(long long h) {
    if (h == 1) return 1;
    else return 1+cnt(h / 2) * 2;
}
int main() {
    long long h;
    cin >> h;
    long long ans = cnt(h);
    cout << ans << endl;
}


Measured memory_bytes: 256
(defparameter n (read))
(defparameter s (read-line))

(defun split-py (str)
  (let ((pos (position #\space str)))
    (cond ((null pos) (list str))
           (t (cons (subseq str 0 pos) (split-py (subseq str (1+ pos))))))))

; incf は1+してsetq
; 1+ は1+した値を返すだけ

(let ((L (sort (mapcar (lambda (x) (read-from-string x)) (split-py s)) #'<)))
  (princ (- (car (last L)) (first L))))

Measured memory_bytes: 5096
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int main(){

  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0;i < N;i++)cin >> A[i];

  vector<int> B(N);
  int BB = -1;

  for(int i = 0;i < N;i++){
    BB = max(BB,A[i]);
    B[i] = BB;
  }


  vector<int> C(N);
  int CC = -1;

  for(int i = N - 1;i >= 0;i--){
    CC = max(CC,A[i]);
    C[i] = CC;
  }

  for(int i = 0;i < N;i++){
    if(i == 0)cout << C[1] << endl;
    else if(i == N - 1)cout << B[N-2] << endl;
    else cout << max(B[i-1],C[i+1]) << endl;
  }

}


Measured memory_bytes: 3968
//
// Created by corol

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio();
    cin.tie(0);
    int n;
    cin >>n;
    cout << n*n;

    //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s. \n";
    return 0;
}


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

using namespace std;

int main(){
  int a, b;
  string s,t;
  cin >> s >> t;
  cin >> a >> b;
  string u;
  cin >> u;

  if(s == u){
    a--;
  }else{
    b--;
  }
  printf("%d %d\n",a, b);
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
class Main
{
    public static void main(String args[])throws IOException
    {
	BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
	String str=input.readLine();
	String str_ary[]=str.split(" ");
	int a[]=new int[5];
	for(int i=0;i<5;i++)
	    {
		a[i]=Integer.parseInt(str_ary[i]);
	    }
	for(int i=0;i<5;i++)
	    {
		int max=i;
		for(int j=i;j<5;j++)
		    {
			if(a[j]>a[max])
			    {
				max=j;

			    }
			
		    }
		
		int tmp=a[i];
		a[i]=a[max];
		a[max]=tmp;
		
	    
	
	    }
	for(int k=0;k<5;k++)System.out.print(a[k]+((k==4)?"\n":" "));
    }
}

Measured memory_bytes: 16964
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            //int N = int.Parse(line);
 
            if (line[2] == line[3] && line[4] == line[5]) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                              \
  ifstream in("atcoder-problems/arc095_b.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v)                        \
  rep(l, v.size()) { cout << v[l] << " "; } \
  cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  cin >> N;

  vector<ll> c(N);
  rep(i, N) { cin >> c[i]; }
  sort(c.begin(), c.end(), greater<int>());

  ll n = c[0];
  ll r = n / 2;
  auto comp = [&](ll x) -> bool { return x > r; };
  auto it = partition_point(c.begin(), c.end(), comp);
  // printf("%lld\n", *it);
  if (r != *it) {
    ll tmp = *it;
    ll tmp2 = *it;
    int j = it - c.begin() - 1;
    if (j > 0) {
      tmp2 = c[j];
    }
    r = abs(r - tmp) < abs(r - (n - tmp2)) ? tmp : tmp2;
  }
  printf("%lld %lld", n, r);
}

Measured memory_bytes: 1152
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int n;
int a[1010];

int main(){
  cin >> n;
  rep(i, 1, n + 1){
    int x = i;
    rep(j, 2, x + 1){
      while (x % j == 0){
        x /= j;
        a[j]++;
      }
    }
  }
  ll res = 1;
  rep(i, 1010) res = res * (a[i] + 1) % mod;
  cout << res << endl;
}


Measured memory_bytes: 256
mod = 1000000007

n,k = map(int,input().split())

memo = []

for i in range(n+1):
  memo.append(i)

min_sum = [0]

for i in range(1,n+1):
  kazu = memo[i]+min_sum[i-1]
  min_sum.append(kazu)

memo.reverse()

max_sum = [memo[0]]

for i in range(1,n+1):
  kazu = memo[i]+max_sum[i-1]
  max_sum.append(kazu)

ans = 0

for i in range(k-1,n+1):
  ans += max_sum[i]-min_sum[i]+1

print(ans%mod)

Measured memory_bytes: 96724
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pi;
typedef pair<lld,lld> pl;
typedef vector<int> vit;
typedef vector<vit> vitt;
typedef vector<lld> vlt;
typedef vector<vlt> vltt;
typedef vector<pi> vpit;
typedef vector<vpit> vpitt;
typedef long double ld;
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define mk(a,b) make_pair(a,b)
bool isrange(int y,int x,int n,int m){
	 if(0<=y&&y<n&&0<=x&&x<m) return true;
	 return false;
}
int dy[4] = {1,0,-1,0},dx[4]={0,1,0,-1},ddy[8] = {1,0,-1,0,1,1,-1,-1},ddx[8] = {0,1,0,-1,1,-1,1,-1};
lld arr[222222];
int main(void){
	int n;
	scanf("%d",&n);
	for(int e=0;e<n;e++) scanf("%lld",&arr[e]);
	lld num = 0;
	for(int e=1;e<n;e++){
		if(arr[e-1]>arr[e]){
			num += (arr[e-1] - arr[e]);
			arr[e] = arr[e-1];
		}
	}
	printf("%lld",num);
	return 0;
}


Measured memory_bytes: 5372
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	
	a := make(map[rune]bool)
	
	for _,v := range s {
		if a[v] {
			fmt.Println("no")
			return
		}
		a[v] = true
	}
	fmt.Println("yes")
}

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

int main() {
  int N, K, Q;
  int x;
   cin >> N >> K >> Q;
  vector<int> vec(N,K-Q);
vector<string> vec2(N,"No");
 
  for (int i=0; i< Q; i++) {
	cin >> x;
    vec.at(x-1)++;
    if (vec.at(x-1) > 0) {
      vec2.at(x-1) = "Yes";
    }
  }
      if (K > Q ) {
  vec2 = vector<string>(N,"Yes");}
  for (int i=0; i< N; i++) {
    cout << vec2.at(i) << endl;
  }
}

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
    ll n;
    cin>>n;
    vector<double> v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    double res = 0;
    sort(v.begin(),v.end());
    res = (v[0] + v[1] )/2;
    for(int i=2;i<n;i++){
	res = (res+ v[i])/2;
    }
    printf("%0.7lf\n",res);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<array>
#include<algorithm>
#include<deque>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<list>

int main(void) {
	using namespace std;
	/*int N, A,res;
	cin >> N >> A;
	res = N * N - A;
	cout << res << endl;*/

	/*int a, b,c;
	cin >> a >> b;
	c = a * b;
	c = c % 2;
	if (c == 0) {
		cout << "Even" << endl;
	}
	else if(c == 1){
		cout << "Odd" << endl;
	}*/

	/*int A, B, a, b, c;
	cin >> A >> B;
	a = A + B;
	b = A - B;
	c = A * B;
	if (a >= b && a >= c) {
		cout << a << endl;
	}
	else if (b >= a && b >= c) {
		cout << b << endl;
	}
	else if (c >= a && c >= b) {
		cout << c << endl;
	}*/

	/*int K, S,res = 0;
	cin >> K >> S;
	for (int X = 0; X <= K;X++) {
		for (int Y = 0; Y <= K; Y++) {
			for (int Z = 0; Z <= K; Z++) {
				if (X + Y + Z == S) {
					res += 1;
				}

			}
		}
	}
	cout << res << endl;*/

	int N,a;
	cin >> N;
	set<int>s;
	for (int i = 0; i < N;i++) {
		cin >> a;
		s.insert(a);
	}
	cout << s.size() << endl;

	/*int N, a, res;
	vector<int>vec;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a;
		vec.push_back(a);
	}
	sort(vec.begin(), vec.end());
	res = vec[vec.size() - 1] - vec[0];
	cout << res << endl;*/

	/*int Alice = 0, Bob = 0,a,N;
	deque<int>dec;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a;
		dec.push_back(a);
	}
	sort(dec.rbegin(), dec.rend());
	for (int i = 0; i < N;i++) {
		if (i % 2 == 0) {
			Alice += dec[0];
			dec.pop_front();
		}
		else if (i % 2 == 1) {
			Bob += dec[0];
			dec.pop_front();
		}
	}
	cout << Alice - Bob << endl;*/
}

Measured memory_bytes: 256
n = int(input())

if n < 10:
    res = n
elif n < 100:
    res = 9
elif n < 1000:
    res = (n - 99) + 9
elif n < 10000:
    res = (999 - 99) + 9
elif n < 100000:
    res = (n - 9999) + (999 - 99) + 9
elif n == 100000:
    res = (99999 - 9999) + (999 - 99) + 9

print(res)

Measured memory_bytes: 3060
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>

// 0 : space 1 : twall 2 : start 3 : goal 4 : wall
int board[32][32];
int W, H;

void init() {
  for(int i = 0; i < (int)32; ++i) {
    for(int j = 0; j < (int)32; ++j) {
      board[i][j] = 4;
    }
  }
}

void Load() {
  scanf("%d %d", &W, &H);
  for(int i = 0; i < (int)H; ++i) {
    for(int j = 0; j < (int)W; ++j) {
      scanf("%d", &board[i+1][j+1]);
    }
  }
}

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};

class Solve_ {
  std::pair<int, int> start, end;
  int limit;
  bool ok;
public:
  int operator() () {
    init();
    ok = false;
    int res = (1 << 29);
    for(limit = 1; limit < 11; ++limit) {
      dfs(start, 0);
      if( ok ) {
        res = limit;
        break;
      }
    }
    if( res >= 11 ) res = -1;
    return res;
  }
  void dfs(std::pair<int, int> p, int d) {
    if( d >= limit ) return;
    int r = p.first, c = p.second;
    if( board[r][c] == 3 ) return;
    for(int k = 0; k < 4; ++k) {
      int nr = r + dr[k], nc = c + dc[k];
      if( board[nr][nc] == 1 or board[nr][nc] == 4 ) continue;
      if( nr == end.first and nc == end.second ) {
        ok = true;
        return;
      }
      for(;;) {
        int nnr = nr + dr[k], nnc = nc + dc[k];
        if( board[nnr][nnc] == 1 or board[nnr][nnc] == 4 ) break;
        nr = nnr;
        nc = nnc;
        if( nr == end.first and nc == end.second ) {
          ok = true;
          return;
        }
      }
      if( board[nr+dr[k]][nc+dc[k]] == 4 ) continue;
      bool b = false;
      if( board[nr+dr[k]][nc+dc[k]] == 1 ) {
        b = true;
      }
      if( b ) {
        board[nr+dr[k]][nc+dc[k]] = 0;
      }
      dfs(std::pair<int, int>(nr, nc), d + 1);
      if( b ) {
        board[nr+dr[k]][nc+dc[k]] = 1;
      }
      if( ok ) break;
    }
  }
  void init() {
    for(int i = 1; i <= H; ++i) {
      for(int j = 1; j <= W; ++j) {
        if( board[i][j] == 2 ) {
          start = std::pair<int, int>(i, j);
        }
        if( board[i][j] == 3 ) {
          end = std::pair<int, int>(i, j);
        }
      }
    }
  }
};
Solve_ Solve;

int main() {
  for(;;) {
    init();
    Load();
    if( W == 0 and H == 0 ) break;
    int res = Solve();
    printf("%d\n", res);
  }
  
  return 0;
}

Measured memory_bytes: 3108
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[4002][4002];

int main() {
  string s,t;
  while(cin >> s >>t){
    for(int i=0;i<s.size();i++)
      for(int j=0;j<t.size();j++) dp[i][j] = 0;

    int ans=0;
    for(int i=0;i<s.size();i++)
      for(int j=0;j<t.size();j++)
	if(s[i]==t[j]) dp[i+1][j+1] = dp[i][j]+1,ans=max(ans,dp[i][j]+1);
    cout << ans <<endl;
  }
  return 0;
}

Measured memory_bytes: 63756
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;
using int32 = __uint32_t;

void solve() {
    int a, b;
    cin >> a >> b;

    int tp = __gcd(a, b);
    vector<int> div;
    for(int i = 1; i * i <= tp; i++){
        if(tp % i == 0){
            div.push_back(i);
            if(tp/i != i)div.push_back(tp/i);
        }
    }
    int ans = 1;
    for(int i = 2; i * i <= tp; i++){
        int ct =0 ;
        while(tp %  i == 0)tp/=i,ct++;
        ans += (ct?1:0);
    }
    if(tp > 1)ans++;
    cout <<ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}


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

int32_t main()
{
    long long int n;
    cin>>n;
    long long int ar[n];
    for(long long int i=0 ; i<n ; ++i)
    cin>>ar[i];
    long long int currentmoney=1000;
    for(long long int i=0 ; i<n-1 ; ++i)
    {
         long long int stocks=0;
        if(ar[i]<ar[i+1])
        {
        stocks=currentmoney/ar[i];
        currentmoney+=(ar[i+1]-ar[i])*stocks;
        }
    }
      cout<<currentmoney;

    return 0;
}



Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include<complex>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i > 0; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> pr;
typedef complex<double> com;


int main(){
	int a, b;
	string s;
	cin >> a >> s >> b;
	if (s == "+") {
		cout << a + b << endl;
	}
	else {
		cout << a - b << endl;
	}
	return 0;
}
//Ctrl+Aを使わない

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1e9+7;

int main()
{
    string s;
    cin >> s;
    bool ok=false;
    rep(i,3){
        if(s[i]=='7'){
            ok=true;
            break;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
} 


Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int a,d,e=1;
  cin>>a;
  vector<int> b(a);
  fo(i,a)
    cin>>b[i];
  d=b[0];
  fo(i,a){
    if(d-b[i]>=2){
      e=0;
      break;
    }
    d=max(d,b[i]);
  }
  if(e)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

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







int main(){
  
  string s,t;
  cin>>s>>t;
  
  int ssize=int(s.size());
  
  string answer="Yes";
  
  for (int i=0;i<ssize;i++){
    if (s.at(i)!=t.at(i)){
      answer="No";
      break;
    }
  }
  
  cout<<answer<<endl;
  
    
  
  
  
  
  
  
    
  
  
  
}

Measured memory_bytes: 3628
N, K = [int(x) for x in input().split()]
d = [0] * K
A = [None for _ in range(K)]
for i in range(K):
    d[i] = int(input())
    A[i] = [int(x) for x in input().split()]

trick = [False] + [True] * (N)

for i in range(K):
    for a in A[i]:
        trick[a] = False

print(trick.count(True))

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

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

int N, X, M;
int nxt[100010][60];
int cost[100010][60];

signed main()
{
    cin >> N >> X >> M;

    rep(i, M)nxt[i][0] = i * i % M;
    for(int i = 1; i < 60; i++)
    {
        rep(j, M)nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
    }

    rep(i, M)cost[i][0] = i;
    for(int i = 1; i < 60; i++)
    {
        rep(j, M)cost[j][i] = cost[j][i - 1] + cost[nxt[j][i - 1]][i - 1];
    }

    int ans = 0;
    int now = X;
    rep(i, 60)
    {
        if(N & (1LL << i))
        {
            ans += cost[now][i];
            now = nxt[now][i];
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 97356
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
ll A,B,a[N];
int n;
bool check(ll x){
	ll s=0;
	for(int i=1;i<=n;i++){
		if(a[i]-B*x<=0) continue;
		s+=(a[i]-B*x+A-B-1)/(A-B);
	}
	return s<=x;
}
int main(){
	scanf("%d%lld%lld",&n,&A,&B);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	ll l=0,r=1e9,ans=0;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 4620
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
#include <array>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define INF I64_MAX
#define MOD 1000000007
#define MEM_SIZE = 1e5+5;

template<typename T> void DEBUG(T e){std::cout <<"DEBUG>>"<< e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ DEBUG(v); } }


 
 
void solve(void)
{
  int N,W;
  cin>>N>>W;
  vector<int> weight(N);
  vector<int> value(N);

  for (int i = 0; i < N; i++)
  {
    cin>>weight[i]>>value[i];
  }
  
  vector<vector<int> > DP (N+1,vector<int>(W+1,0));
  for (int i = 1; i <= N; i++)
  {
    for (int w = 0; w <= W; w++)
    {
      if(w >= weight[i-1])
      {
        DP[i][w] = max(DP[i-1][w],DP[i-1][w - weight[i-1]] + value[i-1]);
      }
      else
      {
        DP[i][w] = DP[i-1][w];
      }
      
    }
  }
  // DEBUG(DP);
  cout<<DP[N][W]<<endl;
  
  return;
}



int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(8);
  solve();

 
  return 0;
}

Measured memory_bytes: 80256
S = list(str(input()))
S.reverse()
mod = 2019
rem = [0]*mod
num = 0
rem[num] += 1
d = 1
ans = 0
for s in S:
  num += int(s) * d
  num %= mod
  d *= 10
  d %= mod
  rem[num] += 1
for r in rem:
  ans += r*(r-1)//2
print(ans)

Measured memory_bytes: 77760
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793

/*ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    ll r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}*/
int main (){
    int n,m;
    int ans=0;
    cin >> n >> m;
    vector<int>x(m);
    vector<int>y(m-1);
    rep(i,m) cin >> x[i];
    sort(x.begin(),x.end());
    rep(i,m-1) y[i]=x[i+1]-x[i];
    rep(i,m-1) ans+=y[i];
    sort(y.begin(),y.end());
    reverse(y.begin(),y.end());
    if(n>=m) cout << 0 << endl;
    else{
        rep(i,n-1) ans-=y[i];
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 1024
<?php

fscanf(STDIN, "%d %d", $n, $m);
$k_arr = [];
for ($i = 0; $i < $m; ++$i) {
    $input = explode(' ', trim(fgets(STDIN)));
    $k = $input[0];
    $k_arr[] = $k;
    for ($j = 0; $j < $k; ++$j) {
        $s_arr[$i][] = $input[$j + 1];
    }
}
$p_arr = explode(' ', trim(fgets(STDIN)));

$count = 0;
for ($switch = 0; $switch < (1 << $n); ++$switch) {

    $flg = true;
    // 電球
    for ($i = 0; $i < $m; ++$i) {

        $on_count = 0;
        // 電球にくっつくスイッチ
        foreach ($s_arr[$i] as $s) {
            if ($switch & (1 << ($s - 1))) {
                ++$on_count;
            }
        }

        if ($on_count % 2 != $p_arr[$i]) {
            $flg = false;
            break;
        }
    }

    if ($flg) {
        ++$count;
    }
}

echo $count;


Measured memory_bytes: 4856
import math

h,n=map(int,input().split())
arr=[]
brr=[]
for i in range(n):
	a,b=map(int,input().split())
	arr.append(a)
	brr.append(b)
dp=[1000000000000000]*(h+1)
dp[0]=0
for i in range(1,h+1):
	for j in range(n):
		if ((i-arr[j])>=0):
			dp[i]=min(dp[i],dp[i-arr[j]]+brr[j])
		else:
			dp[i]=min(dp[i],brr[j])
print(dp[h])

Measured memory_bytes: 42348
import java.util.*;
import java.lang.*;

public class Main {
	static int n;
	static long[] x;
	static long[] y;
	static boolean[] visited;
	static long p;
	static long q;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		x = new long[n];
		y = new long[n];
		for (int i = 0; i < n; i++) {
			x[i] = sc.nextLong();
			y[i] = sc.nextLong();
		}
		long cost = n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					p = x[j] - x[i];
					q = y[j] - y[i];
					int tmp = 0;
					visited = new boolean[n];
					for (int k = 0; k < n; k++) {
						if (!visited[k]) {
							visited[k] = true;
							dfs(k);
							tmp++;
						}
					}
					cost = Math.min(cost, tmp);
				}
			}
		}
		System.out.println(cost);
	}
	static void dfs(int in) {
		long xt = x[in];
		long yt = y[in];
		for (int i = 0; i < n; i++) {
			if (!visited[i] && ((x[i] == xt + p && y[i] == yt + q) || (x[i] == xt - p && y[i] == yt - q))) {
				visited[i] = true;
				dfs(i);
			}
		}
	}
}



Measured memory_bytes: 22868
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return int(i)
}

func main() {
	n := nextInt()

	ss := make([]int, 0, n)
	for i := 0; i < n; i++ {
		ss = append(ss, nextInt())
	}

	var c int
	dd := make([]int, n)
	copy(dd, ss)
	sort.Sort(sort.IntSlice(dd))

	for i := 0; i < n; i++ {
		if dd[i] != ss[i] {
			c++
		}
	}

	if c == 0 || c == 2 {
		fmt.Println("YES")
		return
	}

	fmt.Println("NO")
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e18;

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

int main(){
  int N;
  cin >> N;
  ll ans=1;
  map<ll,int> m;
  FOR(i,2,N+1){
    map<ll,int> mm = prime_factor(i);
    for(auto itr = mm.begin(); itr != mm.end(); ++itr){
      m[itr->first] += itr->second;
    }
  }

  for(auto itr = m.begin(); itr != m.end(); ++itr){
    ans *= (itr->second + 1);
    ans %= MOD;
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
import math
a,b,h,m = map(int,input().split())
x = 30*h + 0.5*m
y = 6*m
if x > y:
  s = x-y
else:
  s = y-x
t = math.cos(math.radians(s))
c = ((a**2) + (b**2) - 2 * a * b * t) ** 0.5
print(c)

Measured memory_bytes: 9504
N = int(input())
A = list(map(int, input().split()))
sum=0
sa=0
for i in range(N-1):
  if A[i] <= A[i+1]:
    continue
  else:
    sa = A[i]-A[i+1]
    A[i+1]=A[i]
    sum += sa
print(sum)

Measured memory_bytes: 94372
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	string ans = string(ty - sy, 'U');
	ans += string(tx - sx, 'R');
	ans += string(ty - sy, 'D');
	ans += string(tx - sx + 1, 'L');
	ans += string(ty - sy + 1, 'U');
	ans += string(tx - sx + 1, 'R');
	ans += "DR";
	ans += string(ty - sy + 1, 'D');
	ans += string(tx - sx + 1, 'L');
	ans += "U";
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long LL;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define dumpMap(m) { for (auto it: m) cout << it.first << "=>" << it.second << ' '; }

const int MOD = 1000000007;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
    
    int L, R, d;
    cin >> L >> R >> d;

    int ans = (R/d) - (L-1)/d;
    cout << ans << endl;

    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;

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

  int m,mi,ma;
  while(true){
    cin >> m >> mi >> ma;
    if(m==0) break;
    std::vector<int> v;
    for(int i=0;i<m;i++){
      int p;cin >> p;
      v.push_back(p);
    }
    sort(v.begin(),v.end(),greater<int>());
    int gap=-1,n=mi;
    for(int i=mi-1;i<ma;i++){
      int temp=v[i]-v[i+1];
      if(temp>=gap){
        gap=temp;
        n=i+1;
      }
    }
    cout << n << endl;
  }
}

Measured memory_bytes: 3116
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_set>
# include <unordered_map>
using namespace std;



int n, m;
vector<pair<int, int> > v[100005];
map<int, int> d[100005];
set<pair<int, pair<int, int> > > s;
int cnt[100005];

inline bool cmp(pair<int, int> x, pair<int, int> y) {
    return x.second < y.second;
}

int main(int argc, const char * argv[]) {
#ifdef __APPLE__
    freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
        if (x > y) swap(x, y);
        d[x][z] = 1e9;
        d[y][z] = 1e9;
    }
    for (int i = 0; i < (int)v[1].size(); ++i) {
        int to = v[1][i].first;
        int x = v[1][i].second;
        if (d[to][x] == 1e9) {
            s.insert({1, {to, x}});
            d[to][x] = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        sort(v[i].begin(), v[i].end(), cmp);
    }
    while (!s.empty()) {
        pair<int, int> cur = s.begin() -> second;
        s.erase(s.begin());
        int x = cur.first;
        int y = cur.second;
        int len = d[x][y];
        if (cnt[x] == 2) {
            int l = 0;
            int r = (int)v[x].size() - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (v[x][mid].second >= y) r = mid;
                else l = mid + 1;
            }
            while (l < (int)v[x].size() && v[x][l].second == y) {
                int to = v[x][l].first;
                int r = len;
                if (r < d[to][y]) {
                    s.erase({d[to][y], {to, y}});
                    d[to][y] = r;
                    s.insert({d[to][y], {to, y}});
                }
                ++l;
            }
            continue;
        }
        ++cnt[x];
        for (int i = 0; i < (int)v[x].size(); ++i) {
            int to = v[x][i].first;
            int l = v[x][i].second;
            int r = len + (l == y ? 0 : 1);
            if (r < d[to][l]) {
                s.erase({d[to][l], {to, l}});
                d[to][l] = r;
                s.insert({d[to][l], {to, l}});
            }
        }
    }
    int res = 1e9;
    for (auto t: d[n]) {
        res = min(res, t.second);
    }
    cout << (res == 1e9 ? -1 : res) << '\n';
}



Measured memory_bytes: 44020
require 'matrix'


n, m= gets.split.map(&:to_i)

a = n.times.map do
      gets.split.map(&:to_i)
    end

b = m.times.map do
      gets.split.map(&:to_i)
    end

ma = Matrix.rows(a)
mb = Matrix.rows(b)
mc = ma * mb


mc.row_vectors.each {|row| puts row.to_a.join("\s")}


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

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

  std::array<int, 15> p;
  p[0] = n / 2 + n / 4 + n / 8 + n / 16 + n /32 + n / 64;
  p[1] = n / 3 + n / 9 + n / 27 + n / 81;
  p[2] = n / 5 + n / 25;
  p[3] = n / 7 + n / 49;
  p[4] = n / 11;
  p[5] = n / 13;
  p[6] = n / 17;
  p[7] = n / 19;
  p[8] = n / 23;
  p[9] = n / 29;
  p[10] = n / 31;
  p[11] = n / 37;
  p[12] = n / 41;
  p[13] = n / 43;
  p[14] = n / 47;

  int count = 0;
  if (74 <= p[0]) {
    count++;
  }

  for (int i = 0; i < 15; i++) {
    for (int j = 0; j < 15; j++) {
      if (24 <= p[i] && 2 <= p[j] && i != j) {
        count++;
      }
      if (14 <= p[i] && 4 <= p[j] && i != j) {
        count++;
      }
    }
  }

  int d_count = 0;
  for (int i = 0; i < 15; i++) {
    for (int j = 0; j < 15; j++) {
      for (int k = 0; k < 15; k++) {
        if (4 <= p[i] && 4 <= p[j] && 2 <= p[k] && i != j && i != k && k != j) {
          d_count++;
        }
      }
    }
  }

  std::cout << count + d_count / 2 << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1'000'000'007;
template <class T> bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0; }
template <class T> bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0; }

template <typename T = ll> struct TreeBFS {
    vector<T> dist;
    vector<vector<pair<int, T>>> edges;
    TreeBFS(int n) : dist(n, -1), edges(n) {}
    void addEdge(int f, int t, T w) {
        edges[f].emplace_back(t, w);
        edges[t].emplace_back(f, w);
    }
    void bfs(int start) {
        dist[start] = 0;
        deque<int> node;
        node.push_back(start);
        while (node.size() != 0) {
            int n = node.front();
            node.pop_front();
            for (auto e : edges[n]) {
                if (dist[e.first] == -1) {
                    dist[e.first] = dist[n] + e.second;
                    node.push_back(e.first);
                }
            }
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vi x(m), y(m), z(m);
    for (int i = 0; i < m; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }
    TreeBFS<ll> tr(n);
    for (int i = 0; i < m; ++i) {
        tr.addEdge(x[i] - 1, y[i] - 1, 1);
    }
    int ret = 0;
    for (int i = 0; i < n; ++i) {
        if (tr.dist[i] == -1) {
            tr.bfs(i);
            ret++;
        }
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 9984
#include <iostream>

using namespace std;

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

int main() {
  int n, m;
  cin >> n >> m;
  int l = (m+1)/2, r = m/2;
  rep(i,l) cout << i+1 << " " << 2*l - i << endl;
  rep(i,r) cout << 2*l + i+1 << " " << 2*(l+r) - i + 1 << endl;
  return 0;
}

Measured memory_bytes: 3184
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};



int main(){
    string s;cin >> s;
    if(s[2] == s[3] && s[4] == s[5]) puts("Yes");
    else puts("No");
    return 0;
}






Measured memory_bytes: 256
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(100000)  # RecursionError対策

"""解説
(1) まず、赤いボールをN-K個一列に並べる

(2) 赤いボールと赤いボールの隙間をi箇所選んで、そこに青いボールをK個置くことを考える

 R R R R R
0 1 2 3 4 5

    この選び方は、(N-K+1)C(i)通り

(3) それぞれの選び方について、青いボールをそれぞれの隙間に何個割り当てるかを考える。
    それぞれ1個以上割り当てる必要があるので、決め方は(K-1)C(i-1)通り。


[入力例1]
B B B R R

・i=1
Bの塊を挿入する位置は、
 R R  |  R R  |  R R
^     |   ^   |     ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において1通り

よって、3*1 = 3通り


・i=2
 R R  |  R R   |  R R
^ ^   | ^   ^  |   ^ ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において、

- 少なくとも1個ずつ分配すると、自由におけるBの数は1個
- 2箇所に玉1つを分配する場合の数は
(2)C(1) = 2通り

よって3*2 = 6通り

・i=3
 R R
^ ^ ^
の1通り


[重複組み合わせの考え方]
http://www7b.biglobe.ne.jp/~math-tota/suA/tamahako.htm

B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
B-i個の玉と、i-1個の区切りの重複組み合わせ。

・6個の玉を、区別のできる3つの箱に分ける場合の数
6個の玉と、2個のしきりの重複組み合わせ

○○○○|○○| (4,2,0)の場合
|○○|○○○○ (0,2,4)の場合

「8個のオブジェクトのうち、2個を選んでしきりにする」と同じなので、(8)C(2) = 28

"""
from math import factorial

def combination_formula(n, r):
    return factorial(n) // (factorial(r)*factorial(n-r))

def solve():
    N, K = list(map(int, input().split()))
    B, R = K, N-K
    MOD = 10**9+7

    for i in range(1, K+1):
        if R+1-i < 0:
            print(0)
            continue
        
        # R+1から、i個選ぶ
        ans = combination_formula(R+1, i)
        if B-i == 0:
            print(ans%MOD)
            continue
        # B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
        # B-i個の玉と、i-1個の区切りの重複組み合わせ。
        if B-i+i-1-(i-1) >= 0:
            ans *= combination_formula(B-i+i-1, i-1)%MOD
        print(ans%MOD)



if __name__ == "__main__":
    solve()


Measured memory_bytes: 3316
#include<stdio.h>

int main(){

   int i = 0,j = 0;

   /*do{
   scanf("%d",&i);

   printf("Case i:%d\n",i);
   }
   while(i != 0 );*/


    while(1){
    for(j = 1;j <=10000;j++){
        scanf("%d", &i);
        if (i == 0) goto saigo;
        printf("Case %d: %d\n",j,i);
        }
    }
    saigo:

    return 0;
}



Measured memory_bytes: 2064
#include <bits/stdc++.h>
using namespace std;
const int inf{int(1e9)};

int main() {
  int N, T;
  cin >> N >> T;
  vector<int> c(N), t(N);
  for (int i = 0; i < N; i++) {
    cin >> c[i] >> t[i];
  }

  vector<int> filtered_c;
  for (int i = 0; i < N; i++) {
    if (t[i] <= T) {
      filtered_c.push_back(c[i]);
    }
  }

  if (filtered_c.size() == 0) {
    cout << "TLE" << endl;
  } else {
    cout << *min_element(filtered_c.begin(), filtered_c.end()) << endl;
  }
}

Measured memory_bytes: 256
# -*- coding:utf-8 -*-
if __name__ == '__main__':
    A = input() + "d"
    B = input() + "d"
    C = input() + "d"

    Al = len(A)
    Bl = len(B)
    Cl = len(C)
    na = 1
    nb = 0
    nc = 0

    now = A[0]
    while(now != "d"):
        if now == "a":
            now = A[na]
            na += 1
        elif now == "b":
            now = B[nb]
            nb += 1
        else:
            now = C[nc]
            nc += 1
    if na == Al: print("A")
    if nb == Bl: print("B")
    if nc == Cl: print("C")


Measured memory_bytes: 3064