akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    private final static Main main = new Main();

    public static void main(String[] args) {
        main.contest();
    }

    private void contest() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Point[] students = new Point[n];
        for (int i=0; i<n; ++i) {
            students[i] = new Point(sc.nextInt(), sc.nextInt());
        }
        Point[] checks = new Point[m];
        for (int i=0; i<m; ++i) {
            checks[i] = new Point(sc.nextInt(), sc.nextInt());
        }
        for (Point student : students) {
            System.out.println(solve(student, checks));
        }
    }

    private int solve(Point student, Point[] checks) {
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int i=0; i<checks.length; ++i) {
            Point check = checks[i];
            int dist = Math.abs(student.x - check.x) + Math.abs(student.y - check.y);
            if (min > dist) {
                min = dist;
                index = i;
            }
        }
        return index+1;
    }

    public static class Point {
        private final int x;
        private final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}


Measured memory_bytes: 23508
#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    // cもAにまとめて格納する
    int A[n+1][m];
    for(int i = 0; i < n+1; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> A[i][j];
        }
    }
    
    for(int i = 0; i < n; ++i) {
        int c = 0;
        for(int j = 0; j < m; ++j) {
            c += A[i][j]*A[n][j];
        }
        cout << c << endl;
    }
    return 0;
}


Measured memory_bytes: 3144
from collections import defaultdict
from itertools import product

N = int(input())

red_points = [tuple(map(int, input().split(' '))) for _ in range(N)]
blue_points = [tuple(map(int, input().split(' '))) for _ in range(N)]

edges = defaultdict(set)

for i, j in product(range(N), repeat=2):
    a, b = red_points[i]
    c, d = blue_points[j]

    if a < c and b < d:
        edges[i].add(j + N)
        edges[j + N].add(i)

pairs = [-1] * (2 * N)
ans = 0


def dfs(v, seen):
    seen[v] = True
    for u in edges[v]:
        w = pairs[u]
        if w < 0 or (not seen[w] and dfs(w, seen)):
            pairs[v] = u
            pairs[u] = v
            return True
    return False


for v in range(2 * N):
    if pairs[v] < 0:
        seen = [False] * (2 * N)
        if dfs(v, seen):
            ans += 1

print(ans)


Measured memory_bytes: 9624
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
const ll INF = (ll)1e18 + 1;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int l, r, d; cin >> l >> r >> d;
    int res=0;

    for(int i=l; i<=r; i++) if(i%d==0) res++;

    cout << res << ln;
    return 0;
}

Measured memory_bytes: 3644
import java.util.*;
import java.util.stream.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		int x = in.nextInt();
		int p = 0;
		for (int i=0; i<m; i++) {
			int a = in.nextInt();
			if (a < x) {
				p++;
			}
		}
		out.println(Math.min(p, m-p));
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 22612
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <limits>
#include <iomanip>
#include <queue>
#include <cmath>
#include <math.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;
using pll = pair<long long, long long>;
#define min(a, b) ((a) < (b) ? (a) : (b))

long long N;
long long dp[200000];
int main() {
	cin >> N;
	for (long i = 0; i < 200000; i++) dp[i] = INF;
	// 配るDP
	dp[0] = 0;
	for (long long  i = 0; i < N; i++) {
		for (long long pow6 = 1; pow6 <= N; pow6 *= 6) {
			chmin(dp[i + pow6], dp[i] + 1);
		}
		for (long long pow9 = 1; pow9 <= N; pow9 *= 9) {
			chmin(dp[i + pow9], dp[i] + 1);
		}
		chmin(dp[i + 1], dp[i] + 1);
	}

	cout << dp[N] << endl;
}

Measured memory_bytes: 1792
x,y=map(int,input().split())

A=[1,3,5,7,8,10,12]
B=[4,6,9,11]

if x==2 and y==2:
  print('Yes')
elif x in A and y in A:
  print('Yes')
elif x in B and y in B:
  print('Yes')
else:
  print('No')
  

Measured memory_bytes: 38384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <complex>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define putsp(x) cout << x << ' ';
#define putbd cout << "---------------------------------------------" << endl;
#define putln(x) cout << x << endl;
#define debug(x) cerr << #x << "=" << x << endl;
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef complex<double> comp;
typedef vector <int> vec;
typedef vector <ll> vecll;
typedef vector <double> vecd;
typedef vector <vec> mat;
typedef vector <vecll> matll;
typedef vector <vecd> matd;

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 200020;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const ll INFL = 1e18;
const int MOD = 1e9+7;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
//const int dx[]={-1,-1,-1,0,1,1,1,0},dy[]={-1,0,1,1,1,0,-1,-1};

//********************************template END****************************************//

typedef pair<intP, intP> q;

void solve(void){

	int H, W;
	cin >> H >> W;
	mat m(H, vec(W, 0));
	rep(H, i) rep(W, j)
	{
		cin >> m[i][j];
		m[i][j] = m[i][j] & 1;
	}

	int opecnt = 0;
	vector <q> ans;

	rep(H, i) rep(W, j)
	{
		if (m[i][j] & 1)
		{
			if (j == W-1)
			{
				if (i == H-1)
				{
					continue;;
				}
				opecnt++;
				ans.pb(q(intP(i+1, j+1), intP(i+2, j+1)));
				m[i+1][j] ^= 1;
				m[i][j] ^= 1;
			}
			else
			{
				opecnt++;
				ans.pb(q(intP(i+1, j+1), intP(i+1, j+2)));
				m[i][j+1] ^= 1;
				m[i][j] ^= 1;
			}
		}
	}

	cout << opecnt << endl;
	for (auto q : ans)
	{
		printf("%d %d %d %d\n", q.fst.fst, q.fst.snd, q.snd.fst, q.snd.snd);
	}

}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 5232
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;
//struct edge{lint to,num;};

vector<bool> prime;
void primeinit(int N){
    if(N+1>prime.size()){
        prime.resize(N+1,true);
    } 
    prime[0] = false;
    prime[1] = false;
    for(int i=2; i*i<=N;i++) if(prime[i]) for(int j=2; i*j<=N;j++) prime[i*j]=false;
}

int main(void){
    int N,A,B;
    cin >> N >> A >> B;
    if((B-A)%2) cout << "Borys" << endl;
    else cout << "Alice" << endl;
}

Measured memory_bytes: 3628
function move(d1,d2,d3,d4,d5,d6){
   var x=this.toString();
   if(x=="N")return [d2,d6,d3,d4,d1,d5];
   if(x=="E")return [d4,d2,d1,d6,d5,d3];
}
function roll(d1,d2,d3,d4,d5,d6){
   return [d1,d3,d5,d2,d4,d6];
}
function rolls(arr){
   for(var i=0;i<4;i++){
      obj[arr.join(",")]=true;
      arr=roll.apply(null,arr);
   }
}
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var n=Arr.shift()-0;
   if(n==0)break;
   var OBJ={};
   var result="Yes";
   var cnt=0;
   for(var i=0;i<n;i++){
      var obj={};
      var color="Red,Yellow,Blue,Magenta,Green,Cyan".split(",");
      var dice=(Arr.shift()).split(" ");
      dice=dice.map(function(v){return color.indexOf(v);});
      for(var j=0;j<4;j++){
         rolls(dice);
         dice=move.apply("N",dice);
      }
      dice=move.apply("E",dice);
      rolls(dice);
      dice=move.apply("E",dice);
      dice=move.apply("E",dice);
      rolls(dice);
      for(var k in obj){
         if(OBJ.hasOwnProperty(k)){cnt++;break;}
         else OBJ[k]=true;
      }
   }
   console.log(cnt);
}

Measured memory_bytes: 12880
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) ll((a).size())
#define out(a) cout<<(a)<<endl;
const int inf=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;

int main(){
  ll n;cin>>n;
  vll a(n),b(n);
  rep(i,0,n){
    cin>>a[i]>>b[i];
  }
  sort(a.begin(),a.end());sort(b.begin(),b.end());
  if(n%2){
    cout<<b[n/2]-a[n/2]+1<<endl;
  }
  else{
    double aa=a[n/2]+a[n/2-1],bb=b[n/2]+b[n/2-1];
    aa/=2;bb/=2;
    ll ans=(bb-aa)*2;
    cout<<ans+1<<endl;
    
  }
}





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

public class Main {
  static private InputReader in;
  static private PrintWriter out;

  public static void main(String[] args) {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out);
    Task solver = new Task();
    solver.solve();
    out.close();
  }

  static class Task {
    public void solve() {
      String s = in.next();
      int n = (int) s.length();
      Stack<Character> stk = new Stack<Character>();
      int zcnt = 0, ocnt = 0;
      for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '0') {
          zcnt++;
        } else {
          ocnt++;
        }
      }
      out.println(Math.min(zcnt, ocnt) * 2);
    }
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
    
    public long nextLong() {
      return Long.parseLong(next());
    }
    
    public double nextDouble() {
      return Double.parseDouble(next());
    }
  }
}

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

int N;
string S;

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

  vector<int> W(N+1, 0), E(N+1, 0);

  rep(i,N) {
    char c = S[i];
    W[i+1] = W[i] + (c == 'W');
    E[i+1] = E[i] + (c == 'E');
  }

  int ans = N;
  rep(i,N) {
    ans = min(ans, W[i] + E[N] - E[i+1]);
  }

  cout << ans << endl;

  return 0;
}


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

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

ll gcd(ll a,ll b){
  while(b!=0){
    a%=b;
    swap(a,b);
  }
  return a;
}

ll kaizyou(ll N){
  ll num=1;
  for(ll i=1;i<=N;i++){
  num*=i;
  }
  return num;
}

int dy[]={-1,0,1,0};
int dx[]={0,-1,0,1};

ll mod=1e9+7;

int main(){
  string S;
  cin >> S;
  bool ans=false;
  rep(i,S.size()-1){
    if(S.at(i)!=S.at(i+1)){
      ans=true;
    }
  }
  if(ans){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}
      
  
  
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5+5;

int n;
void ngk(){
    cin >> n;
    
    if (n < 3 || __builtin_popcount(n) == 1) {
        cout << "No";
        return;
    }
    else {
        cout << "Yes" << '\n';
        cout << 2 << ' ' << 3 << '\n';
        cout << 3 << ' ' << 1 << '\n';
        cout << 1 << ' ' << n+2 << '\n';
        cout << n+2 << ' ' << n+3 << '\n';
        cout << n+3 << ' ' << n+1 << '\n';
        for(int i=4;i<n;i+=2){
            cout << i << ' ' << i+1 << '\n';
            cout << i+1 << ' ' << 1 << '\n';
            cout << 1 << ' ' << i+n << '\n';
            cout << i+n << ' ' << i+n+1 << '\n';
        }
        if (n % 2 == 0){
            int large_bit = (1<<(31 - __builtin_clz(n)));
            cout << n << ' ' << large_bit+n << '\n';
            cout << n+n << ' ' << (n^1^large_bit) << '\n';
        }
    }
    
} 

int main(){
    #ifdef NGKCP
        freopen("input.txt","r",stdin);
    #endif
    iostream::sync_with_stdio(0);
    ngk();
}
/*
    Array limits;
    Corner cases;
*/

Measured memory_bytes: 2304
import sys
input = sys.stdin.readline

def main():
    s = input().strip()
    N = int(input())
    for i in range(N):
        t = input().strip().split()
        a = int(t[1])
        b = int(t[2])
        if t[0][0] == "p":
            print(s[int(t[1]):int(t[2])+1])
        elif t[0][2] == "p":
            s = s[:a] + t[3] + s[b+1:]
        else:
            s = s[:a] + s[a:b+1][::-1] + s[b+1:]

if __name__ == "__main__":
    main()


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j

int lbidx(vector<int> x, int y) {
  auto itr = lower_bound(x.begin(), x.end(), y);
  int idx = itr - x.begin();
  return idx;
};

int upidx(vector<int> x, int y) {
  auto itr = upper_bound(x.begin(), x.end(), y);
  int idx = itr - x.begin();
  return idx;
}

int main() {
  int x, y, z;
  cin >> x >> y >> z;
  cout << (x * y) / 2 << endl;
};


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

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int n; cin >> n;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		if (a % 2)
			cnt++;
	}
	if (cnt) cout << "first" << '\n';
	else cout << "second" << '\n';
	return 0;
}

Measured memory_bytes: 3656
x=range(int(input()))
f=lambda a,b,c,d : a*d - b*c 
P=[]
for _ in x:P+=[[int(i) for i in input().split()]]
_=0
P+=[P[0]]
for j in x:_+=f(P[j][0],P[j][1],P[j+1][0],P[j+1][1])
print(_*0.5)

Measured memory_bytes: 7724
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <iterator>
#include <algorithm>
#include <cfenv>
#include <random>
#include <numeric>
#include <cmath>
#include <iosfwd>
#include <iostream>
#include <ios>
#include <streambuf>
#include <istream>
#include <ostream>
#include <iomanip>
#include <sstream>
#include <fstream>
using namespace std;

int compare_int(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}


int main(){
    int N,M;
    int A[1000];
    int flg = 1;
    double sum=0;
    cin >> N >> M;
    for (int i = 0 ; i < N ; i++){
        cin >> A[i];
        sum += A[i];
    }
    sum /= (double)(4*M);
    qsort(A,N,sizeof(int),compare_int);
    for (int i = 0 ; i < M ; i++){
        if(sum > A[i]){
            flg--;
            break;
        }
    }
    if(flg){
        cout << "Yes";
    }else{
        cout << "No";
    }
    return 0;
}

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

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

typedef pair<int, int> pint;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front

class UnionFind {
public:
    vector <int> par;
    vector <int> siz;

    UnionFind(int sz_): par(sz_), siz(sz_, 1) {
        for (int i = 0; i < sz_; ++i) par[i] = i;
    }

    void init(int sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1);
        for (int i = 0; i < sz_; ++i) par[i] = i;
    }

    int root(int x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;

        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];

        par[y] = x;
        return true;
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    int size(int x) {
        return siz[root(x)];
    }
};

signed main() {
    int N, M;
    cin >> N >> M;

    vector<pint> e;
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        e.pb(mp(a, b));
    }

    int inconv = N * (N-1) / 2;
    vector<int> ans;
    ans.pb(inconv);

    UnionFind uf(N);
    RREP(i, M) {
        pint p = e[i];
        if (uf.issame(p.first, p.second) == false) {
            inconv -= uf.size(p.first) * uf.size(p.second);
        }
        uf.merge(p.first, p.second);
        ans.pb(inconv);
    }

    RREP(i, M) {
        cout << ans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 6256
<?php

// 標準入力を一行ずつ配列に代入します
fscanf(STDIN, '%d', $a);
fscanf(STDIN, '%d', $b);
fscanf(STDIN, '%d', $c);
fscanf(STDIN, '%d', $x);


define('A_RATE', 500);
define('B_RATE', 100);
define('C_RATE', 50);

$cnt = 0;
for ($ia = 0; $ia <= $a; $ia++) {

	for ($ib = 0; $ib <= $b; $ib++) {

		for ($ic = 0; $ic <= $c; $ic++) {

			$checking_money = A_RATE * $ia + B_RATE * $ib + C_RATE * $ic;
//			var_dump('money:'.$checking_money);
//			var_dump($ia, $ib, $ic, '---');

			if ($checking_money === $x) {
				$cnt++;
			}
		}
	}
}

echo $cnt;

Measured memory_bytes: 4728
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int A, B, K;
    int result;
    int count = 0;
	scanf("%d %d %d", &A, &B, &K);
    for (int i=max(A, B); i > 0; i--) {
        if (A%i == 0 && B%i == 0) {
            result = i;
            count++;
        }
        if (count == K) {
            break;
        }
    }
    printf("%d\n", result);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;
int n;


int main(){
    int x,y;
    cin>>x>>y;
    if(y%2==0 && y<=4*x && 4*x<=2*y) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

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

int main() {
  int N,X,Y;
  cin >> N ;
  Y =0;
  vector <int> vecV(N);
  vector <int> vecC(N);
  
  for(int i=0;i<N;i++)
    cin >> vecV.at(i);
  for(int i=0;i<N;i++)
    cin >> vecC.at(i);
  for(int i=0;i<N;i++){
    X = vecV.at(i)-vecC.at(i);
    if(X>0)
      Y+=X;
   }
  cout << Y << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
  int n;
  int[] arr;
  public static void main(String[] args) throws IOException {

    new Main().run();
  }

  public void run() {

    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      n = Integer.parseInt(in.readLine());
      arr = LineToIntArr(in.readLine(), n, ' ');
      int q = Integer.parseInt(in.readLine());
      int[] seqM = LineToIntArr(in.readLine(), q, ' ');

      StringBuilder buf = new StringBuilder();
      for (int m : seqM) {
        if(solve(0, m))
          buf.append("yes\n");
        else
          buf.append("no\n");
      }

      System.out.print(buf);
    } 
    catch(IOException e) {
      System.err.println(e);
    }
  }

  private boolean solve(int i, int m) {
    if(m == 0) return true;

    if(i >= n) return false;

    return solve(i + 1, m) || solve(i + 1, m - arr[i]);
  } 

  private int[] LineToIntArr(String line, int n, char regex) {
    int offset=0,next=0;
    int[] arr = new int[n];
    boolean isContinue = true;
    for(int i=0; isContinue; i++) {
      if((next = line.indexOf(regex,offset)) == -1) {
        next = line.length();
        isContinue = false;
      }
      arr[i] = Integer.parseInt(line.substring(offset, next));
      offset = ++next;
    }

    return arr;
  }
 
}


Measured memory_bytes: 24736
A, B = map(int, input().split(' '))
def f(x):
  # xor 0 to x
  if x%4 == 0:
    return x
  if x%4 == 1:
    return 1
  if x%4 == 2:
    return 1^x
  if x%4 == 3:
    return 0
  
print (f(A-1) ^ f(B))

Measured memory_bytes: 3060
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

typedef long long ll;

int main() {
   ll A, B, C, K;
   cin >> A >> B >> C >> K;
   ll ans = 0;
   if (K % 2 == 0) ans = A - B;
   else ans = B - A;

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


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

int main(){
    string s;
    cin >> s;
    int q;
    cin >> q;
    string front = "", back = "";
    bool reverseflag = false;
    rep(i, q){
        int query;
        cin >> query;
        if (query == 1){
            if (!reverseflag) reverseflag = true;
            else reverseflag = false;
        }
        else {
            int f;
            string c;
            cin >> f >> c;
            if (!reverseflag){
                if (f == 1) front = c + front;
                else back += c;
            }
            else {
                if (f == 1) back += c;
                else front = c + front;
            }
        }
    }
    string ans = front + s + back;
    if (!reverseflag) cout << ans << endl;
    else {
        int n = ans.size();
        rrep(i, n) cout << ans[i];
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 1360
import sys
input = sys.stdin.readline

n = int(input())
sn = [input().strip('\n') for _ in range(n)]

mod = 10**6 + 7
hs = [[0, ''] for _ in range(mod)]

def hypo(s, Mod):
    h_num = 1
    for i in s:
        h_num = h_num * ord(i) % Mod
    return h_num

for s in sn:
    s = ''.join(sorted(s))
    h = hypo(s, mod)
    while True:
        if h >= mod :
            h = 0
        if hs[h][0] == 0:
            hs[h][0] += 1
            hs[h][1] += s
            break
        if hs[h][1] == s:
            hs[h][0] += 1
            break
        h += 1

ans = 0
for j, t in hs:
    if j >= 2:
        ans += j * (j-1) / 2

print(int(ans))


Measured memory_bytes: 109500
#include <bits/stdc++.h>
#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 FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=3.14159265358979323846;
using namespace std;
vector<int> dy={1,0,-1,0};
vector<int> dx={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int n;
vector<ll> data;
void add(int a,ll w) {
    for(int i=a; i<=n; i+=i&-i) data[i] += w;
}
ll sum(int a) {
    ll ret=0;
    for(int i=a; i>0;  i-=i&-i) ret+=data[i];
    return ret;
}

int main() {
    ll k;
    cin>>n>>k;
    vector<ll> vec(n+1,0);
    rep(i,n) {
        ll a;
        cin>>a;
        a-=k;
        vec[i+1]=vec[i]+a;
    }
    
    vector<ll> vals;
    rep(i,n+1) vals.push_back(vec[i]);
    sort(all(vals));
    vals.erase(unique(all(vals)),vals.end());
    
    rep(i,n+1) {
        int x=lower_bound(all(vals),vec[i])-vals.begin()+1;
        vec[i]=x;
    }
    
    data.resize(n+2);
    ll ans=0;
    rrep(i,n+1) {
        if(i!=n) ans+=(ll)((n-i)-sum(vec[i]-1));
        add(vec[i],1);
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 5104
#include <stdio.h>

int main(){
  
  int a,b=0,c=0,sum;
  a=10;
while(1){
    scanf("%d %d %d\n",&a,&b,&c);
    sum = a+b;
    if(a==-1 && b ==-1 && c==-1) break;
    else if(a ==-1 || b == -1 ) printf("F\n");
    else if(sum >= 80) printf("A\n");
    else if(sum <80 && sum >= 65 ) printf("B\n");
    else if(sum <65 && sum >= 50 ) printf("C\n");
    else if(sum <50 && sum >= 30 && c<50 ) printf("D\n");
    else if(sum <50 && sum >= 30 && c>=50 ) printf("C\n");
    else if(sum <30) printf("F\n");
    
  }
  return 0;
  
}


Measured memory_bytes: 2112
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(in);
    int x = Integer.parseInt(sc.next());
    int y = Integer.parseInt(sc.next());
int[] a={1,3,5,7,8,10,12};
int[] b={4,6,9,11};
int c1=0,c2=0;
    for (int i = 0; i < 7; i++) {
        if(a[i]==x)c1++;
        if(a[i]==y)c1++;
        if(i<4){
            if(b[i]==x)c2++;
            if(b[i]==y)c2++;
        }
        
    }
    if(c1==2||c2==2){out.println("Yes");
    }else{out.println("No");}
}
}

Measured memory_bytes: 23124
#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 <fstream>
#include <time.h>
#include <iterator>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;



int L[101];
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, X; cin >> N >> X;
	REP(i, N) {
		cin >> L[i];
	}
	int pos = 0;
	int ans = 1;
	REP(i, N) {
		pos += L[i];
		if (pos <= X)ans++;
	}
	print(ans);
}


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

int main(){
  vector<vector<pair<int,int>>> S(100000,vector<pair<int,int>>(0));
  int N,M; cin>>N>>M;
  vector<pair<int,int>> ans(M);
  int a,b;
  for(int i=0;i<M;i++){
    cin>>a>>b;
    S[a-1].push_back({b,i});
  }
  for(int i=0;i<N;i++){
    sort(S[i].begin(),S[i].end());
    for(int j=0;j<S[i].size();j++){
      ans[S[i][j].second]={i+1,j+1};
    }
  }
  vector<int> Pi(6,0);
  vector<int> x(6,0);
  for(int i=0;i<M;i++){
    a=ans[i].first;
    b=ans[i].second;
    for(int j=0;j<6;j++){
      Pi[5-j]=a%10; a/=10;
      x[5-j]=b%10; b/=10;
    }
    for(int j=0;j<6;j++){
      cout<<Pi[j];
    }
    for(int j=0;j<6;j++){
      cout<<x[j];
    }
    cout<<endl;
  }
}

Measured memory_bytes: 7808
#include<complex>
#include<iostream>
#include<vector>
#include<cfloat>
#include<utility>
#include<queue>

using namespace std;

static const long double EPS = 1e-10;
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2; // p2→p0→p1
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

class Point{
    public: 
    long double x,y;
    Point(long double x = 0.0, long double y = 0.0): x(x), y(y) {}
    Point operator + (Point p) const { return Point(x+p.x, y+p.y); }
    Point operator - (Point p) const { return Point(x-p.x, y-p.y); }
    Point operator * (long double a) const { return Point(x*a, y*a); }
    Point operator / (long double a) const { return Point(x/a, y/a); }
    bool operator < (const Point &p) const { return (x != p.x ? x < p.x : y < p.y); }
    bool operator == (const Point &p) const { return fabsl(x - p.x) < EPS && fabsl(y - p.y) < EPS; }
    long double abs() const { return sqrt(norm()); }
    long double norm() const { return x*x + y*y; }
    long double dot(Point p) const { return x*p.x + y*p.y; }
    long double cross(Point p) const { return x*p.y - y*p.x; }
};


int ccw(Point p0, Point p1, Point p2){
    Point a = p1 - p0;
    Point b = p2 - p0;
    if(a.cross(b) > EPS) return COUNTER_CLOCKWISE;
    if(a.cross(b) < -EPS) return CLOCKWISE;
    if(a.dot(b) < -EPS) return ONLINE_BACK;
    if(a.norm() < b.norm()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool intersect(Point p0, Point p1, Point p2, Point p3){
    return ccw(p0, p1, p2) * ccw(p0, p1, p3) <= 0 && ccw(p2, p3, p0) * ccw(p2, p3, p1) <= 0;
}

int main(){
    int n;
    cin >> n;
    long double x[8];
    for(int i=0;i<n;i++){
        for(int j=0;j<8;j++) cin >> x[j];
        Point p[4];
        for(int j=0;j<4;j++) p[j] = Point(x[2*j], x[2*j+1]);
        cout << intersect(p[0], p[1], p[2], p[3]) << endl; 
    }
}


Measured memory_bytes: 3228
N,K=map(int,input().split())
list_pn=list(map(int,input().split()))
# Pnの期待値を計算
pn_ave=[]
for i in range(N):
    pn_ave.append((list_pn[i]+1)/2)
# Sj+k-Sjの累積和を用いて考える
Sj = []
Sj.append(0)
S=0
for i in range(N):
    S += pn_ave[i]
    Sj.append(S)
# print(Sj)
Sk = []
for i in range(N-K+1):
    Sk.append(Sj[i+K]-Sj[i])
# print(Sk)
Sk.sort()
print(Sk[-1])

Measured memory_bytes: 29000
c_ = [list(map(int,input().split())) for i in range(3)]

a1 = 0
b1 = c_[0][0] - a1
a2 = c_[1][0] - b1
b2 = c_[0][1] - a1
a3 = c_[2][0] - b1
b3 = c_[0][2] - a1

a_ = [a1,a2,a3]
b_ = [b1,b2,b3]

flag = True
for i in range(3):
    for j in range(3):
        if c_[i][j] != a_[i] + b_[j]:
            flag = False

print('Yes' if flag else 'No')


Measured memory_bytes: 3064
from sys import stdin

n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
s = [str(i) for i in s]

ma = 0
for i in range(len(s)):
    point = 0
    fi = list(set(s[:i]))
    la = list(set(s[i:]))
    for j in fi:
        if j in la:
            point += 1
    ma =  max(ma,point)

print(ma)

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

int main()
{
    long long n,i,arr[87];
    arr[0]=2;
    arr[1]=1;
    for(i=2;i<87;i++)
        arr[i]=arr[i-1]+arr[i-2];
    cin>>n;
    cout<<arr[n]<<endl;

    return 0;
}


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

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 total = 0;

    for(int i = 0;i < k;i++){
        total += p[i];
    }

    cout << total << endl;

    return 0;
}

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

int main(){
  int n;
  cin>>n;
  int *array = new int[n];
  for(int i=0;i<n;i++){
    cin>>array[i];
  }
  int count=0;
  for(int i=0;i<n;i++){
    int minj=i;
    for(int j=i;j<n;j++){
      if(array[j] < array[minj])
	minj=j;
    }
    if(i!=minj){
      swap(array[i],array[minj]);
      count++;
    }
  }

  cout<<array[0];
  for(int i=1;i<n;i++)
    cout<<" "<<array[i];
  cout<<'\n'<<count<<endl;
  delete []array;
  return 0;
}

Measured memory_bytes: 1196
// Last Change:   12/08/2018 21:13:17.
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <list>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
ll N;
ll a[205000];
ll b[205000];
ll c[605000];
ll A[605000];

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < N; i++) {
        cin >> b[i];
    }
    for(int i = 0; i < N; i++) {
        c[i] = a[i] ^ a[(i+1)%N];
    }
    for(int i = N; i < 2 * N; i++) {
        c[i] = b[i-N] ^ b[(i + 1)%N];
    }
    for(int i = 2 * N; i < 3 * N; i++) {
        c[i] = c[i-N];
    }
    for(int i = 0; i < 3 * N; i++) {
        //cerr << c[i] << " ";
    }
    //cerr << endl;
    A[0] = 3 * N;
    int i = 1, j = 0;
    while (i < 3 * N) {
      while (i+j < 3 * N && c[j] == c[i+j]) ++j;
        A[i] = j;
        if (j == 0) { ++i; continue;}
        int k = 1;
        while (i+k < 3 * N && k+A[k] < j) A[i+k] = A[k], ++k;
      i += k; j -= k;
    }
    for(int i = N; i < 2 * N; i++) {
        //cerr << i - N << " " << A[i] << endl;
    }
    vector<int> ans;
    for(int i = N - 1; i >= 0; i--) {
        int j = N - i - 1;
        if(A[i+N] >= N) {
            ans.push_back((2 * N - i) % N);
        }
    }
    sort(ans.begin(), ans.end());
    for(auto idx : ans) {
        cout << idx << " " << (a[idx] ^ b[0]) << endl;
    }
    return 0;
}

Measured memory_bytes: 17012
A,B,M = list(map(int,input().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range (M)]
k = min(a) + min(b)
for i in range (M):
    k = min(a[s[i][0] - 1] + b[s[i][1] - 1] - s[i][2],k)
print(k)

Measured memory_bytes: 38560
#include <stdio.h>
#include <stdlib.h>
long min_l(long n, long m);

int main(void)
{
	long n, m, p1, p2, q1, q2, l;
	int err;
	char *s, *t;
	err=scanf("%ld%ld", &n, &m);
	if (err!=2) exit(1);
	s = (char *)malloc(sizeof(char)*(int)n);
	t = (char *)malloc(sizeof(char)*(int)m);
	err=scanf("%s\n%s", s, t);
	if (err!=2) exit(1);

	l=min_l(n, m);
	p1=l/n;
	q1=l/m;
	p2=0;
	q2=0;
	while((q2<n)&&(p2<m))
	{
		if (s[q2]!=t[p2])
		{
			printf("%d\n", -1);
			return 0;
		}
		p2+=p1;
		q2+=q1;
	}
	printf("%ld\n", l);
	free(s);
	free(t);
	return 0;
}

long min_l(long n, long m){
	long answer, a, b, r = 1;
	if (n >= m)
	{
		a = n;
		b = m;
	}else
	{
		a = m;
		b = n;
	}
	while (r != 0)
	{
		r = a%b;
		a = b;
		b = r;
	}
	answer = n * m / a;
	return answer;
}

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

int main() {
	
	string S;
	cin >>S;
	
	if(S=="Sunny"){
		
		cout <<"Cloudy" <<endl;
		
	}
	if(S=="Cloudy"){
		
		cout <<"Rainy" <<endl;
		
	}
	if(S=="Rainy"){
		
		cout <<"Sunny" <<endl;
		
	}
	
}

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

using namespace std;

long long int GCD(long long int a, long long int b) {
    if(a<b) {
        long long int tmp=a;
        a = b;
        b = tmp;
    }
    
    if(b==0) {
        return a;
    }
    
    return GCD(b, a%b);
}

int main() {
    long long int N, M;
    cin >> N >> M;
    
    string S, T;
    cin >> S >> T;
    
    long long int sn=0, tn=0;
    bool flag=true;
    while(sn<N && tn<M) {
        if(S[sn]!=T[tn]) {
            flag = false;
            break;
        }
        
        sn += N/GCD(N, M);
        tn += M/GCD(N, M);
    }
    
    if(flag) {
        cout << N/GCD(N, M)*M << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
    
}

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

int main()
{
  int N,ans=0;cin>>N;
  int s[N];vector<int> noten;
  for(int i=0;i<N;i++){cin>>s[i];ans+=s[i];if(s[i]%10!=0)noten.push_back(s[i]);}
  sort(noten.begin(),noten.end());
  int i=0;
  while(ans%10==0&&i<noten.size()){ans-=noten[i];i++;}
  if(ans%10!=0)cout<<ans<<endl;
  else cout<<"0"<<endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
using namespace std;

const long long mod = 1e9 + 7;
int h, w, a, b;
long long fac[200001][2];

long long modpow(long long x, long long n){
	if(n == 0) return 1;
	long long res = modpow(x, n / 2);
	res = (res * res) % mod;
	if(n % 2) res = (res * x) % mod;
	return res;
}

int main(){
	//IO("input.txt", "output.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> h >> w >> a >> b;
	fac[0][0] = fac[0][1] = 1;
	for(int i = 1; i <= h + w; i++){
		fac[i][0] = (fac[i - 1][0] * i) % mod;
		fac[i][1] = modpow(fac[i][0], mod - 2);
	}
	long long sum = ((fac[h + w - 2][0] * fac[h - 1][1]) % mod * fac[w - 1][1]) % mod;
	for(int i = 0; i < b; i++){
		long long mult = ((fac[h - a + i - 1][0] * fac[h - a - 1][1]) % mod * fac[i][1]) % mod;
		//mult = (mult * ((fac[w - i + a - 2][0] * fac[w - i - 1][1]) % mod * fac[a - 1][1]) % mod) % mod;
		mult = (((mult * fac[a - 1][1]) % mod * fac[w - i - 1][1]) % mod * fac[w - i + a - 2][0]) % mod;
		while(sum < mult) sum += mod;
		sum = (sum - mult) % mod;
	}
	cout << sum << "\n";
	return 0;
}

Measured memory_bytes: 3328
from collections import deque


def solve(k):
    que = deque([(1, 1)])
    checked = set()
    while True:
        cost, num = que.popleft()
        if num == 0 or num == k:
            return cost
        if num in checked:
            continue
        checked.add(num)
        que.appendleft((cost, num * 10 % k))
        que.append((cost + 1, num + 1))


print(solve(int(input())))


Measured memory_bytes: 21228
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int h,w;
string c[maxn],s[maxn];
int visw[maxn],vish[maxn];
void dfsw(int x,int op)
{
	if(x==w)
	{
//		for(int i=0;i<=h-1;i++)
//			cout<<vish[i]<<" ";
//		cout<<endl;
//		for(int i=0;i<=w-1;i++)
//			cout<<visw[i]<<" ";
//		cout<<endl;
		cout<<"YES"<<endl;
		exit(0);
	}
	else if(visw[x]!=-1)
		dfsw(x+1,op);
	else
	{
		for(int i=x+1;i<=w-1;i++)
		{
			if(visw[i]!=-1)
				continue;
			int flag=0;
			for(int j=0;j<=h-1;j++)
			{
				if(s[vish[j]][i]!=s[j][x])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				visw[x]=i;
				visw[i]=x;
				dfsw(x+1,op);
				visw[x]=-1;
				visw[i]=-1;
			}
		}
		if(op==1)
		{
			int flag=0;
			for(int j=0;j<=h-1;j++)
			{
				if(s[vish[j]][x]!=s[j][x])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				//cout<<"1111111111111111111111111111111111111111"<<endl;
				visw[x]=x;
				dfsw(x+1,0);
				visw[x]=-1;
			}
		}
	}
}
void dfsh(int x,int op)
{
	if(x==h)
	{
		int opp=w%2;
		dfsw(0,opp);
	}
	else if(vish[x]!=-1)
		dfsh(x+1,op);
	else
	{
		for(int i=x+1;i<=h-1;i++)
		{
			if(vish[i]!=-1)
				continue;
			if(c[i]!=c[x])
				continue;
			vish[x]=i;
			vish[i]=x;
			dfsh(x+1,op);
			vish[x]=-1;
			vish[i]=-1;
		}
		if(op==1)
		{
			//cout<<"1111111111111111111111111111111111111111"<<endl;
			vish[x]=x;
			dfsh(x+1,0);
			vish[x]=-1;
		}
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>h>>w;
    for(int i=0;i<=h-1;i++)
	{
    	cin>>s[i];
    	c[i]=s[i];
    	sort(c[i].begin(),c[i].end());
    }
//    for(int i=0;i<=h-1;i++)
//    	cout<<c[i]<<endl;
    memset(vish,-1,sizeof(vish));
    memset(visw,-1,sizeof(visw));
    int op=h%2;
    dfsh(0,op);
    cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 10648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define IN inline
#define RE register
#define F first
#define S second 
#define FF fflush(stdout)
#define random(x) (rand()%x)
#define maxn 100005 
#define LOG(m,n) 1.0*log(n)/log(m)
using namespace std;
struct Seg
{
	int l,r,i;
}ls[maxn],rs[maxn];
inline bool cmp1(Seg &a,Seg &b)
{
	return a.l>b.l;
}
inline bool cmp2(Seg &a,Seg &b)
{
	return a.r<b.r;
}
inline int dst(int l,int r,int p)
{
	if(p<=l) return l;
	if(p>=r) return r;
	return p;
}
int b[maxn];
int main()
{
	int n,j,p=0,t1;
	ll ans1=0,ans2=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&ls[i].l,&ls[i].r);
		ls[i].i=i;
	}
	sort(ls,ls+n,cmp1);
	for(int i=0;i<n;i++)
	{
		rs[i].l=ls[i].l;
		rs[i].r=ls[i].r;
		rs[i].i=ls[i].i;
	}
	sort(ls,ls+n,cmp2);
	j=0;p=0;
	for(int i=0;i<n;i++)
	{
		if(b[ls[i].i]) continue;
		b[ls[i].i]=1;
		t1=dst(ls[i].l,ls[i].r,p);
		ans1+=abs(p-t1);
		p=t1;
		while(b[rs[j].i]&&j<n) j++;
		if(j>=n) continue;
		b[rs[j].i]=1;
		t1=dst(rs[j].l,rs[j].r,p);
		ans1+=abs(p-t1);
		p=t1;
	}
	ans1+=abs(p);
	memset(b,0,sizeof(b));
	j=0;p=0;
	for(int i=0;i<n;i++)
	{
		if(b[rs[i].i]) continue;
		b[rs[i].i]=1;
		t1=dst(rs[i].l,rs[i].r,p);
		ans2+=abs(p-t1);
		p=t1;
		while(b[ls[j].i]&&j<n) j++;
		if(j>=n) continue;
		b[ls[j].i]=1;
		t1=dst(ls[j].l,ls[j].r,p);
		ans2+=abs(p-t1);
		p=t1;
	}
	ans2+=abs(p);
	printf("%lld\n",max(ans1,ans2));
	return 0;
}

Measured memory_bytes: 2944
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    string S; cin >> S;
    vector<int> v;
    while(N > 0) {
        int prev = N;
        rep(i, M) {
            if (N - M + i >= 0 && S[N - M + i] == '0') {
                v.push_back(M - i);
                N = N - M + i;
                break;
            }
        }
        if (prev == N) {cout << -1 << endl; return 0;}
    }
    rep(i, v.size()) {
        if (i != 0) cout << " ";
        cout << v[(int)v.size() - i - 1];
    }
    cout << endl;

    return 0;
}


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

int main() {
    int H, W;
    cin >> H >> W;
    
    string S, S_all;
    for (int i = 0; i < H; i++) {
        cin >> S;
        for(int j = 0; j < W; j++) {
            if(S.at(j) == '.') {
                S_all += '0';
            } else {
                S_all += '#';
            }
        }
    }
    
    
    for (int i = 0; i < S_all.size(); i++) {
            if(S_all.at(i) == '#') {
                if(i % W != 0) {
                    if(i - W - 1 >= 0 && S_all.at(i - W - 1) != '#')
                        S_all.at(i - W - 1) += 1;
                    if(i - 1 >= 0 && S_all.at(i - 1) != '#')
                        S_all.at(i - 1) += 1;
                    if(i + W - 1 < S_all.size() && S_all.at(i + W - 1) != '#')
                        S_all.at(i + W - 1) += 1;
                }
                
                if(i - W >= 0 && S_all.at(i - W) != '#')
                    S_all.at(i - W) += 1;
                if (i + W < S_all.size() && S_all.at(i + W) != '#')
                    S_all.at(i + W) += 1;

                
                if(i % W != (W - 1)) {
                    if (i - W + 1 >= 0 && S_all.at(i - W + 1) != '#')
                        S_all.at(i - W + 1) += 1;
                    if (i + 1 < S_all.size() && S_all.at(i + 1) != '#')
                        S_all.at(i + 1) += 1;
                    if (i + W + 1 < S_all.size() && S_all.at(i + W + 1) != '#')
                        S_all.at(i + W + 1) += 1;
                }
            }
        
    }
    
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cout << S_all.at(i*W +j);
        }
        cout << endl;
    }
}


Measured memory_bytes: 256
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
cands = set(b if a == 1 else a for a, b in AB if a == 1 or b == 1)
if any(a in cands and b == n or b in cands and a == n for a, b in AB):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 54792
M=10**9+7
import sys
f=sys.stdin.readline
n,m=map(int,f().split())
s,t=0,1
u=0 if m<1 else int(f())
for i in range(n):
  if i==u-1:
    s,t=t,0
    try: u=int(f())
    except: pass
  else: s,t=t,(s+t)%M
print(t)

Measured memory_bytes: 3064