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

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Scanner sc = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int n = 1;
    int[][] data;
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.solve();
//        System.out.println(main.solve());
    }
    void solve() throws IOException {
        int n0 = sc.nextInt();
        while(n<n0) n*=2;
        data = new int[26][2*n-1];
        char[] s = sc.next().toCharArray();
        for(int i=0;i<n0;i++){
            int cur = s[i]-'a';
            update(i,1,data[cur]);
        }
        int q = sc.nextInt();
        while(q-->0){
            int type = sc.nextInt();
            if(type==1){
                int i = sc.nextInt()-1;
                char c = sc.next().charAt(0);
                if(s[i] == c) continue;
                update(i,0,data[s[i]-'a']);
                update(i,1,data[c-'a']);
                s[i] = c;
            } else{
                int cnt = 0,left = sc.nextInt()-1, right = sc.nextInt()-1;
                for(int i=0;i<26;i++){
                    int cur = rangeSum(0,left,right,0,n-1,data[i]);
                    if(cur>0) cnt += 1;
                }
                out.println(cnt);

            }
        }
        out.flush();
    }
    void update(int k, int val, int[] seg){
        k += n-1;
        seg[k] = val;
        while(k>0){
            k = (k-1)/2;
            seg[k] = seg[2*k+1]+seg[2*k+2];
        }
    }
    int rangeSum(int k, int qstart, int qend, int nstart, int nend, int[] seg){
        if(nend<qstart||qend<nstart) return 0;
        if(qstart<=nstart&&nend<=qend) return seg[k];
        int mid = (nstart+nend)/2;
        int left = rangeSum(2*k+1,qstart,qend,nstart,mid,seg);
        int right = rangeSum(2*k+2,qstart,qend,mid+1,nend,seg);
        return left+right;
    }
}



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

using namespace std;
typedef long long LL;
typedef double DB;
const LL MOD = 1e9+7;
const LL NMAX = 1e6+7;
const string NAME = "test";

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen((NAME + ".inp").c_str(), "r", stdin);
    //freopen((NAME + ".out").c_str(), "w", stdout);
    int n; cin >> n;
    if((n/100) % 10 == 1) cout << 9; else cout << 1;
    if((n/10) % 10 == 1) cout << 9; else cout << 1;
    if((n/1) % 10 == 1) cout << 9; else cout << 1;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
station = [tuple(map(int, input().split())) for _ in range(n-1)]

for i in range(n-1):
    res = 0
    for j in range(i, n-1):
        c, s, f = station[j]
        if res == 0:
            res += s + c
        else:
            res += max(s-res, ((res+(f-1))//f)*f - res) + c
    print(res)
else:
    print(0)


Measured memory_bytes: 3188
import java.util.Scanner;

public class Main{
    static int num;
    static int[] array;
    
    private static boolean check(int i, int m){
        if(m == 0) return true;
        if(i >= num) return false;
        return check(i + 1, m) || check(i + 1, m - array[i]);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();
        array = new int[num];
        for(int i = 0; i < num; i++){
            array[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        int m = 0;
        for(int i = 0; i < q; i++){
            m = sc.nextInt();
            if(check(0, m)){
                System.out.println("yes");
            }else{
                System.out.println("no");
            }
        }
        
    }
}


Measured memory_bytes: 26676
from copy import copy
N,K = map(int, input().split())
p=list(map(int, input().split()))
expP = [(1+i)/2 for i in p]
id_H = N-K
id_T = N
minus = sum(expP[:id_H])
minimum = minus
for i in range(id_H):
    minus -= expP[id_H - i -1]
    minus += expP[id_T - i -1]
    if minus < minimum:
        minimum = copy(minus)
ans = sum(expP) - minimum
print(ans)

Measured memory_bytes: 25572
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb(x) push_back(x)
#define f(i,st,n) for(i=st;i<n;i++)
#define qu queue
#define ps(x) push(x)
#define vec vector
#define ft() front()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mst(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
#define sfl(x) scanf("%lld",&x)
#define pfl(x) printf("%lld\n",x)
#define pf(x) printf("%lld",x)
#define mpr make_pair
#define fs first
#define se second
#define inf LLONG_MAX
#define nnf INT_MIN

 
 
 
ll gcd(ll a,ll b){
    if(a==0){
        return b;
    }                     
    return gcd(b%a,a);
}
ll power(ll x,ll y){            
    ll res=1;
    while(y>0){
        if(y%2==1){
            res=((res)*(x))%mod;
        }
        x=((x)*(x))%mod;
        y=y/2;
    }
    return res;
}
    

  
int main(){

    fast
 
 /* #ifndef ONLINE_JUDGE
    
   freopen("input.txt", "r", stdin);
   
   freopen("output.txt", "w", stdout);
   #endif*/

   ll a,b,c,d;
   cin>>a>>b>>c>>d;

   ll k=1;

   while(1){
      if(k%2){
          c-=b;
          k^=1;
              if(c<=0){

                cout<<"Yes";
                break;
          }
      }
      else{

        a-=d;
        k^=1;

        if(a<=0){

            cout<<"No";
            break;
        }
      }

   }
   
    
  
    return 0;
   
 
  
 
    
 }

Measured memory_bytes: 3660
import numpy as np

m = int(input())
cur_nums = np.zeros(10, dtype = np.int64)
for _ in range(m):
	d, c = list(map(int, input().split()))
	cur_nums[d] += c

nxt_nums = np.zeros(10, dtype = np.int64)

cnt = 0
while True:
	#print(cnt, cur_nums)
	nxt_nums = np.zeros(10, dtype = np.int64)
	# 0
	cnt += cur_nums[0] // 2
	nxt_nums[0] += cur_nums[0] // 2
	nxt_nums[0] += cur_nums[0] % 2
	# 1
	cnt += cur_nums[1] // 2
	nxt_nums[2] += cur_nums[1] // 2 
	nxt_nums[1] += cur_nums[1] % 2 
	# 2
	cnt += cur_nums[2] // 2
	nxt_nums[4] += cur_nums[2] // 2 
	nxt_nums[2] += cur_nums[2] % 2 
	# 3
	cnt += cur_nums[3] // 2
	nxt_nums[6] += cur_nums[3] // 2 
	nxt_nums[3] += cur_nums[3] % 2 
	# 4
	cnt += cur_nums[4] // 2
	nxt_nums[8] += cur_nums[4] // 2 
	nxt_nums[4] += cur_nums[4] % 2 
	# 5
	cnt += cur_nums[5] // 2
	nxt_nums[0] += cur_nums[5] // 2 
	nxt_nums[1] += cur_nums[5] // 2 
	nxt_nums[5] += cur_nums[5] % 2 
	# 6
	cnt += cur_nums[6] // 2
	nxt_nums[2] += cur_nums[6] // 2 
	nxt_nums[1] += cur_nums[6] // 2 
	nxt_nums[6] += cur_nums[6] % 2 
	# 7
	cnt += cur_nums[7] // 2
	nxt_nums[4] += cur_nums[7] // 2 
	nxt_nums[1] += cur_nums[7] // 2 
	nxt_nums[7] += cur_nums[7] % 2 
	# 8
	cnt += cur_nums[8] // 2
	nxt_nums[6] += cur_nums[8] // 2 
	nxt_nums[1] += cur_nums[8] // 2 
	nxt_nums[8] += cur_nums[8] % 2
	# 9
	cnt += cur_nums[9] // 2
	nxt_nums[8] += cur_nums[9] // 2 
	nxt_nums[1] += cur_nums[9] // 2 
	nxt_nums[9] += cur_nums[9] % 2  
	if (cur_nums == nxt_nums).all():
		break
	cur_nums = nxt_nums

rest = [i for i in range(10) if cur_nums[i] == 1]

# cnt = 0
# rest = [9 for _ in range(900)]

while len(rest) >= 2:
	#print(cnt, rest)
	a = rest.pop()
	b = rest.pop()
	rest.extend(map(int, list(str(a + b))))
	cnt += 1

print(cnt)

Measured memory_bytes: 14472
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll ceil(ll a, ll b) {  // a÷b以上の最小の整数
    if(b == 0) {
        return 0;
    }
    return (a+b-1)/b;
}
 
int main() {
    ll h, a;
    cin >> h >> a;
    out(ceil(h,a));
    re0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			double v = sc.nextDouble();
			int n=0;
			while(v>=9.8*Math.sqrt(5*n/4.9))n++;
			System.out.println(n+1);
		}

	}
}

Measured memory_bytes: 18620
#include <iostream>
#include <cstdio>
#define maxn 2005
using namespace std;
const long long INF=999999999999999;
int n;
long long x;
long long a[maxn],d[maxn][maxn];
long long ans,res;
int main()
{
	scanf("%d%lld",&n,&x);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		d[i][i-1]=INF;
		for(int j=i;j<=n;j++)
		{
			d[i][j]=min(d[i][j-1],a[j]);
		}
	}
	ans=INF;
	for(int i=0;i<=n;i++)
	{
		res=i*x;
		for(int j=1;j<=i;j++)
		{
			res+=min(d[n-i+j][n],d[1][j]);
			if(res>=INF) break;
		}
		for(int j=i+1;j<=n;j++)
		{
			res+=d[j-i][j];
			if(res>=INF) break;
		}
		ans=min(ans,res);
	}
	printf("%lld",ans);
	return 0;
}

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

int main() {
  ll a;
  cin >> a;
  if(a % 2 == 1){
    cout << a * 2;
  }
  else{
    cout << a;
  }
  return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

class Main {


	public static void main(String[] args) {

		/**
		 * ??????
		 * ?????????s-1?????§????????????????????§?¶?????¨???????????????????????????????????´???????
		 * ?????????????????????????????????s-1?????§??????????????????????????????
		 * if( ??? == s) ?????¨?????? ??????????????????????????????????????????
		 * ??????????????°?¶?????¨???????????????????????±?????????????????????? ?????° ?????§??? max ?????\??????
		 * ????????¨?????? Math.max( ???, max) ??¨????????????
		 * ????????¨???????????????????????° max?????°??? ??°?¶?????¨???§????????????????????§????????\??£???????????????
		 */


		Scanner sc = new Scanner(System.in);


		int[] a = new int[1000];
		
		int[] maxArray = new int[1000];
		
		int t = 0;

		for(t = 0; ; t++) {

			int preTax = sc.nextInt();
			int nextTax = sc.nextInt();
			int s = sc.nextInt();

			if(preTax == 0 && nextTax == 0 && s == 0) break;
			
			
			for(int i=1; i<s; i++) {
				a[i] = i * (100 + preTax) / 100;
			}
			
			for(int i=1; i<s; i++) {
				for(int j=1; j<s; j++) {
					
					if(a[i] + a[j] == s) {
						
						int s1 = i * (100 + nextTax) /100;
						int s2 = j * (100 + nextTax)/ 100;
						
						maxArray[t] = Math.max(s1 + s2,  maxArray[t]);
						
						
					}
				}

			}

		}
		
		sc.close();
		
		
		for(int i = 0; i<t; i++	) {
			System.out.println(maxArray[i]);
		}


	}
}

Measured memory_bytes: 21044
#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef long long lint;

lint pattern(lint, lint, lint, lint);
lint others(lint);

lint p = 1000*1000*1000 + 7;

lint pattern(lint S, lint K, lint H, lint W) {
  if (S < 1 || S > W || abs(S-K) > H) return 0;

  lint dp[H][W];
  for (int i=0;i<W; i++) {
    dp[0][i] = 0;
  }
  if (K-2 >= 0) dp[0][K-2] = others(K-3)*others(W-K-1);
  if (K-1 >= 0) dp[0][K-1] = others(K-2)*others(W-K-1);
  if (K >= 0) dp[0][K] = others(K-2)*others(W-K-2);

  for (int i=1; i<H; i++) {
    for (int j=0; j<W; j++) {
      if (j > 0 && j < W-1) {
        dp[i][j] = (others(j-1)*others(W-j-3)*dp[i-1][j+1] % p +
          others(j-1)*others(W-j-2)*dp[i-1][j] % p +
          others(j-2)*others(W-j-2)*dp[i-1][j-1] % p) % p;
      } else if (j == 0 && j < W-1) {
        dp[i][j] = (others(j-1)*others(W-j-3)*dp[i-1][j+1] % p +
          others(j-1)*others(W-j-2)*dp[i-1][j] % p) % p;
      } else if (j > 0 && j >= W-1) {
        dp[i][j] = (others(j-1)*others(W-j-2)*dp[i-1][j] % p +
          others(j-2)*others(W-j-2)*dp[i-1][j-1] % p) % p;
      } else {
        dp[i][j] = others(j-1)*others(W-j-2)*dp[i-1][j] % p;
      }
    }
  }
  // for (int i=0; i<H; i++) {
  //   for (int j=0; j<W; j++) {
  //     cout << dp[i][j] << endl;
  //   }
  // }

  return dp[H-1][S-1];
}

lint others(lint width) {
  if (width < 0) return 1;
  switch(width) {
    case 0: return 1;
    case 1: return 2;
    case 2: return 3;
    case 3: return 5;
    case 4: return 8;
    case 5: return 13;
  }
  lint dp[width+1];
  dp[0] = 1;
  dp[1] = 2;
  for (int i=2; i<width+1; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[width];
}

int main() {
  lint H, W, K;
  cin >> H >> W >> K;
  cout << pattern(1, K, H, W) << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0004
{
    public class Program

    {
        public static void Main(string[] args)
        {

            while (true)
            {
                string line = Console.ReadLine();
                if (line == null) break;

                int[] items = Array.ConvertAll(line.Split(' '), k => int.Parse(k));
                int a = items[0];
                int b = items[1];
                int c = items[2];
                int d = items[3];
                int e = items[4];
                int f = items[5];

                decimal x = Math.Round((decimal)(c * e - b * f) / (a * e - b * d), 3, MidpointRounding.AwayFromZero);
                decimal y = Math.Round((decimal)(c * d - a * f) / (b * d - a * e), 3, MidpointRounding.AwayFromZero);
                Console.WriteLine("{0} {1}", x.ToString("F3"), y.ToString("F3"));
            }
        }

        static string ReadSt() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Console.ReadLine()); }
        static long ReadLong() { return long.Parse(Console.ReadLine()); }
        static double ReadDouble() { return double.Parse(Console.ReadLine()); }
        static string[] ReadStAr(char sep = ' ') { return Console.ReadLine().Split(sep); }
        static int[] ReadIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }
        static long[] ReadLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); }
        static double[] ReadDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); }
        static string WriteAr(int[] array, string sep = " ") { return String.Join(sep, array.Select(x => x.ToString()).ToArray()); }
        static string WriteAr(double[] array, string sep = " ") { return String.Join(sep, array.Select(x => x.ToString()).ToArray()); }
        static string WriteAr(long[] array, string sep = " ") { return String.Join(sep, array.Select(x => x.ToString()).ToArray()); }

    }

}



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

const ll maxs = 1e5+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e15;

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

void pre(){

}

const ll N = 2003;

ll dp[N][N];
bool vis[N][N];
pair<ll,ll> a[N];
ll n;

ll go(ll ind,ll i,ll j){
    if(ind >= n )
        return 0;
    ll& ans = dp[i][j];
    if(vis[i][j])
        return dp[i][j];
    vis[i][j] = true;
    ans = a[ind].ff*abs(i - a[ind].ss) + go(ind+1,i+1,j);
    ans = max( ans , a[ind].ff*abs(j - a[ind].ss) + go(ind+1,i,j-1) );
    return ans;
}

void solve(){ 
    cin >> n;
    for(ll i=0;i<n;i++){
        ll val;
        cin >> val;
        a[i].ff = val;
        a[i].ss = i;
    }
    sort(a,a+n);
    reverse(a,a+n);
    ll ans = go(0,0,n-1);
    cout << ans << endl;
}


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

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

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

  vector<int> A(N);
  int maxv = 0;
  for (int i = 0; i < N; i++){
    cin >> A.at(i);
    maxv = max(maxv, A.at(i));
    A.at(i)--;
  }

  vector<int> cnt(maxv, 0);
  for (int i = 0; i < N; i++) {
    cnt.at(A.at(i))++;
  }

  int tot = 0;
  for (int i = 0; i < maxv; i++){
    if(cnt.at(i) != 0 && cnt.at(i) != 1){
      tot += (cnt.at(i)-1);
    }
  }
 
  if(tot % 2 == 0)cout << N - tot << endl;
  else cout << N - tot - 1 << endl;
}

Measured memory_bytes: 1024
import sys
import string
n = raw_input()
n,k = n.split(' ') 

l=[1]
f=[1]
for i in range(55):
    l.append(l[len(l)-1]*2+3)
    f.append(f[len(f)-1]*2+1)

def s(k,level):
    if (level==0):
        if (k>0): return 1
        return 0
    if (k==1): return 0
    if (k>=l[level]): return f[level]
    if (k<l[level]):
        if (k<=l[level-1]+1):
            return s(k-1,level-1)
        if (k==l[level-1]+2):
            return 1+s(k-1,level-1)
        return 1+f[level-1]+s(k-1-1-l[level-1],level-1)

n = string.atoi(n)
k = string.atoi(k)
print (s(k,n))




Measured memory_bytes: 2820
function Main(arg) {
    var arg = arg.trim().split('\n');
    var n = Number(arg[0]);
    var aList = arg[1].split(' ');
    
    if(aList.includes('0')){
        console.log(0);
        return;
    }
    var ret = 0;
    for (key in aList) {
        a = BigInt(aList[key]);
        if(a > 1000000000000000000){
            console.log(-1);
            return;
        }
        if (ret == 0){
            ret = a;
        } else {
            ret = ret * a;
        }
        if(ret > 1000000000000000000){
            console.log(-1);
            return;
        }
    }
    console.log(ret.toString());
    return;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

using namespace std;


int main()
{
	int N, T, A;
	const int DT = 6;

	cin >> N >> T >> A;

	vector<int> Hs;
	int h;
	for (int hi = 0; hi < N; hi++) {
		cin >> h;
		Hs.push_back(h);
	}

	int min_dif = 999999999;
	int min_hi;
	int dif;
	for (int hi = 0; hi < N; hi++) {
		dif = abs(A*1000-(T * 1000 - Hs[hi] * DT));
		if (dif < min_dif) {
			min_hi = hi;
			min_dif = dif;
		}
	}

	int ans = min_hi + 1;

	cout << ans;

	return 0;
}



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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP0(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define RREP0(i,n) for(int i=n-1; i>=0; --i)
#define RREP1(i,n) for(int i=n; i>=1; --i)

#define SORT(c) sort((c).begin(),(c).end())
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define CLR(a) memset((a), 0 ,sizeof(a))

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

const int INTINF = 2147483647;
const LL LLINF = 9223372036854775807;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;
const int MAX = 10000;

int n;
std::vector<PII> adj[MAX];

struct init{
    init(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
} init;


void dijkstra(){
  priority_queue<PII> PQ;  // <cost, vertex> のPQ
  int color[MAX];
  int d[MAX];  // d[i] : mincost from s to i
  REP0(i,n){
    d[i] = INTINF;
    color[i] = WHITE;
  }
  d[0] = 0;
  PQ.push(MP(0,0));
  color[0] = GRAY;
  while ( !PQ.empty() ) {
    PII f = PQ.top(); PQ.pop(); //最小となる頂点と重み
    int u = f.second;
    color[u] = BLACK;

    if( d[u] < f.first * -1 ) continue;

    REP0( j, adj[u].size() ){ // uに隣接する頂点をみていく
      int v = adj[u][j].first;
      if ( color[v] == BLACK ) continue;
      if ( d[v] > d[u] + adj[u][j].second ){ // does it renew shortest path to v
        d[v] = d[u] + adj[u][j].second;
        PQ.push(MP(d[v]*-1, v));
        color[v] = GRAY;
      }
    }
  }

  REP0(i,n){
    std::cout << i << " " << (d[i] == INTINF ? -1 : d[i]) << '\n';
  }
}


void input(){
  int u,k,v,c;
  std::cin >> n;
  REP0(i,n){
    std::cin >> u >> k;
    REP0(j,k){
      std::cin >> v >> c;
      adj[u].PB(MP(v,c));
    }
  }
}


int main(int argc, char const *argv[]) {
  input();
  dijkstra();
  return 0;
}



Measured memory_bytes: 8172
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main ( )
{
	string n;
	int num;
	cin>>num;
	cin>>n;
	int s1;
	s1=n.length();
	
	if(num>=s1){
	cout<<n;
	}
	else 
	{
		for(int i=0;i<num;i++)
		{
			cout<<n[i];
		}
		cout<<"...";
	}
	return 0; 
}

Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <cassert>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
#define pi 3.141592653589793
using namespace std;
int sdkys(int a,int b){
    if(b==0) return a;
    return sdkys(b,a%b);
}
int sskbs(int a,int b){
    return a*b/sdkys(a,b);
}
int sosu(int a){
    if(a==2){
        return 1;
    }
    for(int i=2;i<sqrt(a)+1;i++){
        if(a%i==0){
            return 0;
        }
    }
    return 1;
}
vector<int> v;
int n,m,cnt=7,ans=0,aa[220000],ab[220000];
pair<int,int> pp[220000];
string s,ss[220000],sa;
char ch[110][110];
queue<int> que;
signed main(){
    cin>>n;
    cnt%=n;
    ans=cnt;
    rep(i,n+1){
        if(cnt==0){
            cout<<i+1<<endl;
            return 0;
        }
        ans*=10;
        ans%=n;
        cnt+=ans;
        cnt%=n;
    }
    cout<<-1<<endl;
}

Measured memory_bytes: 10588
import java.util.Scanner;

//Carry a Cheeze
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			if(a==0&&b==0&&c==0)break;
			double da = Math.sqrt(a*a+b*b);
			double db = Math.sqrt(b*b+c*c);
			double dc = Math.sqrt(a*a+c*c);
			double min = da;
			if(db < min)min = db;
			if(dc < min)min = dc;
			int t = sc.nextInt();
			while(t--!=0){
				int r = sc.nextInt()*2;
				System.out.println(min<r?"OK":"NA");
			}
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
#define all(v) (v).begin(),(v).end()
typedef pair<ll,ll> P;
#define fi first
#define se second
set<string> c;
map<ll,ll> mp;
const ll inf=100000000000000000;
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}

int main(){
int n;
cin>>n;
vector<int> a(n),b(n),c(n);
//multiset<int> b,c;
for(int i=0;i<n;i++)cin>>a.at(i);
for(int i=0;i<n;i++)cin>>b.at(i);
for(int i=0;i<n;i++)cin>>c.at(i);
sort(all(a));
sort(all(b));
sort(all(c));
ll ans=0;
for(int i=0;i<n;i++){
  ll itb=lower_bound(all(a),b.at(i))-a.begin();
  ll itc=c.end()-upper_bound(all(c),b.at(i));
  //cout<<itb<<" "<<itc<<endl;
  //if(itc==0)continue;
ans+=(itb*itc);
}
cout<<ans<<endl;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e17;
 
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
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;}



signed main()
{
	IOS();
	vector<int>ans;
	while(1){
		int N,M,X;
		cin>>N>>M>>X;
		if(N==0&&M==0&&X==0)break;
		int sum = 0,t = -1;
		rep(i,0,N){
			int tt;
			cin>>tt;
			if(i == M-1)t = tt;
			sum += tt;
		}
		if(t==0)ans.push_back(0);
		else ans.push_back(sum*(100-X)/t);
	}
	for(auto e:ans){
		cout<<e<<endl;
	}
}



Measured memory_bytes: 3176
#include <iostream>
#include <complex>
#include <vector>
using namespace std;

typedef complex<double> point;
double cross(const point& a, const point& b) {
	return imag(conj(a)*b);
}
double dot(const point& a, const point& b) {
	return real(conj(a)*b);
}
int ccw(point a, point b, point c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;  // counter clockwise
	if (cross(b, c) < 0)   return -1;  // clockwise
	if (dot(b, c) < 0)     return +2;  // c--a--b on line
	if (norm(b) < norm(c)) return -2;  // a--b--c on line
	return 0;  // a--c--b on line or a----bc
}

typedef vector<point> polygon;
bool is_convex(const polygon &P) {
	size_t n = P.size();
	for (int i = 0; i < n; ++i)
		if (ccw(P[(i+n-1) % n], P[i % n], P[(i+1) % n]) == -1) return false;
	return true;
}

int main() {
	int n;
	while (cin >> n) {
		polygon pol(n);
		for (auto& p : pol) {
			int x, y;
			cin >> x >> y;
			p = point(x, y);
		}
		cout << is_convex(pol) << endl;
	}
	return 0;
}

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

int a[26];
int main(void) {
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    a[s[i] - 'a']++;
  }

  for(int i=0;i<26;i++){
    if(a[i] > 1){
      cout << "no" << endl;
      return 0;
    }
  }
  cout << "yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() { cerr << "--------------" << endl; }
const int INF = 2e9;
const int MOD = 1e9 + 7;

int main() {
   int n;
   cin >> n;
   string s;
   cin >> s;
   int ans = 1;
   rep(i, 0, n - 1) {
      if (s[i] != s[i + 1]) ans++;
   }
   cout << ans << endl;
   return 0;
}

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


struct node{
    node *left, *right, *parent;
    int key;
};

node *root, *NIL;

node* find(node *x, int k){
    while(x != NIL and k != x->key){
        if(k < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    return x;
}

void insert(int a){
    node *y = NIL;
    node *x = root;
    node *z;

    z = (node *)malloc(sizeof(node));
    z->key = a;
    z->left = NIL;
    z->right = NIL;

    y = NIL;
    x = root;

    while(x != NIL){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }

    z->parent = y;

    if(y == NIL){
        root = z;
    }else if(z->key < y->key){
        y->left = z;
    }else{
        y->right = z;
    }



}

int perParse(node *a){
    if(a == NIL){
        return 0;
    }
    //ve.push_back(u);
    std::cout << " " << a->key;
    perParse(a->left);
    perParse(a->right);
}

int inOrder(node *a){
    if(a == NIL){
        return 0;
    }
    inOrder(a->left);

    std::cout << " " << a->key;
    //ve.push_back(u);
    inOrder(a->right);
}

int main(void){
    int n;
    int a;
    std::string str;
    std::cin >> n;
    for(int i = 0; i < n; i++){
        std::cin >> str;
        if(str == "insert"){
            std::cin >> a;
            insert(a);
        }else if(str == "find"){
            std::cin >> a;
            if(find(root, a) == NIL){
                std::cout << "no" << std::endl;
            }else{
                std::cout << "yes" << std::endl;
            }
        }else{
            inOrder(root);
            std::cout << std::endl;
            perParse(root);
            std::cout << std::endl;

        }
    }
    return 0;
}


Measured memory_bytes: 21872
#include <bits/stdc++.h>
using namespace std;
 
#define sws ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INFINITO 1000000000
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    int n;
    int a[3][3];

    fo(i, 3) {
        fo(j, 3) {
            cin >> a[i][j];
        }
    }
    cin >> n;

    set<int> b;

    fo(i, n) {
        int l;
        cin >> l;
        b.insert(l);
    }

    bool foi = false;
    int cont;
    fo(i, 3) {
        cont = 0;
        fo(j, 3) {
            if ( b.find(a[i][j]) != b.end() ) cont++;
        }
        if ( cont == 3 ) foi = true;
    }

    cont = 0;
    fo(i, 3) {
        if ( b.find(a[i][i]) != b.end() ) cont++;
    }
    if ( cont == 3 ) foi = true;

    fo(j, 3) {
        cont = 0;
        fo(i, 3) {
            if ( b.find(a[i][j]) != b.end() ) cont++;
        }
        if ( cont == 3 ) foi = true;
    }

    cont = 0;
    fo(i, 3) {
        if ( b.find(a[i][2 - i]) != b.end() ) cont++;
    }
    if ( cont == 3 ) foi = true;

    cout << (foi ? "Yes\n" : "No\n");

    return 0;
}

Measured memory_bytes: 256
MOD = 10**9 + 7


def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    dist = [[-1]*W for i in range(H)]

    def bfs_2d(sy=0, sx=0):
        que = deque()

        dist[sy][sx] = 1
        que.append((sy, sx))
        d = ((0, 1), (1, 0))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    dist[next_h][next_w] += dist[uh][uw]
                    dist[next_h][next_w] %= MOD
                    continue
                if c[next_h][next_w] == '#':
                    continue
                dist[next_h][next_w] = dist[uh][uw]
                dist[next_h][next_w] %= MOD
                que.append((next_h, next_w))

    bfs_2d()
    print(dist[H-1][W-1] if dist[H-1][W-1] != -1 else 0)


if __name__ == '__main__':
    main()


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

ans = [0 for _ in range(10001)]
for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      v = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if v < 10001:
        ans[v] += 1

for i in range(n):
  print(ans[i+1])

Measured memory_bytes: 9160
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

string a[10];

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

int main() {
	int h, w;
	cin >> h >> w;
	rep (i, h) cin >> a[i];

	bool ok = true;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (a[i][j] == '.') continue;
			bool le = false, ri = false, up = false, dw = false;
			rep (k, 4) {
				int x = dx[k] + j;
				int y = dy[k] + i;
				if (x < 0 || x >= w || y < 0 || y >= h) continue;
				if (a[y][x] == '.') continue;
				if (k == 0) ri = true;
				if (k == 1) le = true;
				if (k == 2) dw = true;
				if (k == 3) up = true;
			}
			if (!i && !j) {if (!ri && !dw || ri && dw) ok = false;}
			else if (i == h - 1 && j == w - 1) {if (le && up || !le && !up) ok = false;}
			else {if ((le && up) || (!le && !up) || (ri && dw) || (!ri && !dw)) ok = false;}
		}
	}

	cout << (ok ? "Possible" : "Impossible") << endl;
 	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,l,r,d) for(ll i=(l);i<(r);i+=(d))
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define abs(p) ((p)>=(0)?(p):(-(p)))
int main(void){
    ll M, D, ANS=0, d1, d10;
    scanf("%lld %lld", &M, &D);
    rep(i, 4, M+1, 1){
        rep(j, 22, D+1, 1){
            d1 = j%10;
            if(d1!=1){
                d10 = j/10;
                if(i==d1*d10)ANS++;
            }
        }
    }
    printf("%lld\n", ANS);
    return 0;
}


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

int main() {
  
  int N;
  cin >> N;
  vector<string> plus(N);
  for (int i = 0; i < N; i++) {
    cin >> plus.at(i);
  }
  int M;
  cin >> M;
  vector<string> minus(M);
  for (int i = 0; i < M; i++) {
    cin >> minus.at(i);
  }
  
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int score = 0;
    string say = plus.at(i);
    for (int j = 0; j < N; j++) {
      if(say==plus.at(j)) score++;
    }
    for (int j = 0; j < M; j++) {
      if(say==minus.at(j)) score--;
    }
    if(score>ans) ans = score;
  }
  
  cout << ans << endl;
}

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

using namespace __gnu_pbds;
using namespace std;


typedef tree<int, null_type, less<int>, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;


#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pii pair<int,int>
#define pf push_front
#define mp make_pair
#define vi vector<int>
#define vip vector<pair<int,int> >
#define ff first
#define ss second
#define int long long
#define mod 1000000007
#define BIG 998244353
#define s(t) scanf("%lld",&t)
#define p(t) printf("%lld\n",t)
#define mii map<int,int>
#define MSET(table,i) memset(table, i, sizeof(table))
#define endl '\n'
#define tc int t;cin>>t;while(t--)
#define pi  3.1415926358
#define bits(x) __builtin_popcount(x)
#define minimum(a,n) min_element(a,a+n)-a
#define maximum(a,n) max_element(a,a+n)-a
#define pqbig priority_queue<int>
#define pqsmall priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > >
#define all(v) v.begin(),v.end()
#define sitr set<int>:: iterator
#define spitr set<pii>:: iterator
#define mitr map<string,int>:: iterator


#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl


int32_t main()
{
    fast;
    int n;cin>>n;
    map<string,int> m;
    for(int i=0;i<n;i++)
    {
        string s;cin>>s;
        m[s]++;
    }

    int maxi=-1e18;
    for(mitr it=m.begin();it!=m.end();it++)
        maxi=max(maxi,it->ss);

    for(mitr it=m.begin();it!=m.end();it++)
    {
        if(it->ss==maxi)
            cout<<it->ff<<endl;
    }
}

Measured memory_bytes: 23808
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    pf(0)
    ta = ti = S()
    if ti == 'Vacant':
        return
    mi = 0
    ma = n
    while 1:
        mm = (mi+ma) // 2
        pf(mm)
        c = S()
        if c == 'Vacant':
            return
        if ti == c:
            if (mm - mi) % 2 == 0:
                mi = mm
                ti = c
            else:
                ma = mm
                ta = c
        else:
            if (mm - mi) % 2 == 1:
                mi = mm
                ti = c
            else:
                ma = mm
                ta = c

    return 'No'


main()




Measured memory_bytes: 7960
open System

let s = stdin.ReadLine().Split() |> Array.map(float)
let a = s.[0]
let b = s.[1]
let h = s.[2]
let m = s.[3]

let thetaH = 2.0 * Math.PI * (h + m / 60.0) / 12.0
let thetaM = 2.0 * Math.PI * m / 60.0

let result = Math.Sqrt(a*a+b*b - 2.0*a*b*Math.Cos(thetaH-thetaM))
printfn "%.10f" result


Measured memory_bytes: 30512
using System;
using System.Collections.Generic;
using System.Linq;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            for (int i = S.Length - 2; i >= 0; i -= 2)
            {
                var halfPos = i / 2;
                if (S.Substring(0, halfPos) == S.Substring(halfPos,halfPos))
                {
                    Console.WriteLine(i);
                    return;
                }
            }
        }

    }
}

Measured memory_bytes: 13140
/*#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
#include<bits/stdc++.h>
#define fr first
#define sc second
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
const int inf = 1e9+7;
const ll linf = 1e18+5;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); //uid<int> u1(5, 10); u1(rnd);
ll n;
string ch;
int main() {
    fast;
    ll rez = 0;
    cin >> ch;
    n = ch.size();
    ll inc = 0 , dec = 0, prev = 1;
    for(int i = 0; i < n ; i++){
    	if(ch[i] == '<'){
    		if(prev == 1){
    			inc ++;
    		}else{
    			rez += dec*(dec-1)/2;
    			rez += inc*(inc-1)/2;
    			rez += max(dec,inc);
    			inc = 1;
    			prev = 1;
    			dec = 0;
    		}
    	}
    	if(ch[i] == '>'){
    		dec ++;
    		prev = -1;
    	}
    }
    rez += dec*(dec-1)/2;
    rez += inc*(inc-1)/2;
    rez += max(dec,inc);
    cout << rez << '\n';
}

Measured memory_bytes: 1172
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stack>
#include<queue>
#define ll long long
using namespace std;
ll  a[50005];
ll  b[50005];
int huiwen(int x);
int main()
{
	int l,r;
	int ans=0;
	scanf("%d %d",&l,&r);
	for(int i=l;i<=r;i++){
		if(huiwen(i)==i)
		ans++;
	}
	printf("%d\n",ans);
	
	return 0;
	
	
}
int huiwen(int x) 
{
	int sum=0;
while(x)
{
	sum=sum*10+x%10;
	x/=10;
 } 
 return sum;
}

Measured memory_bytes: 256
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int a[200100];
bool aru[1001001];
int main()
{
	int n,out=0;cin>>n;rep(i,n) cin>>a[i];sort(a,a+n);
	memset(aru,false,sizeof(aru));
	rep(i,n){
		int f=1;
		for(int j=1;j*j<=a[i];j++){
			if(a[i]%j>0) continue;
			if(aru[j] || aru[a[i]/j]) f=0;
		}
		if(i<n-1 && a[i]==a[i+1]) f=0;
		//cout<<a[i]<<' '<<f<<endl;
		out+=f;
		aru[a[i]]=true;
	}
	cout<<out<<endl;
}


Measured memory_bytes: 5288
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define all(a) (a).begin(),(a).end()
#define X first
#define Y second
#define inf 2e9+5
using namespace std;
void solve()
{
  string s,t,ans=""; cin>>s>>t;
  int n1=s.size(),n2=t.size();
  string dp[n1];
  for(int i=0;i<n1;i++)dp[i]="";
  for(int i=0;i<n2;i++)
  {
      for(int j=n1-1;j>=0;j--)
      {
          if(s[j]!=t[i])continue;
          string st;
          if(!j)st=s[j];
          else st=dp[j-1]+s[j];
          if(st.size()>dp[j].size())dp[j]=st;
          if(dp[j].size()>ans.size())ans=dp[j];
      }
      for(int j=1;j<n1;j++)if(dp[j-1].size()>dp[j].size())dp[j]=dp[j-1];
  }
  cout<<ans;
  return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; t=1;
    while(t--)solve();
    return 0;
}


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

using namespace std;

int n;

vector<int> lis[100100];
vector<int> cdp[100100];
int dp[100100];

bool dfs(int here, int p, int t) {
    cdp[here].clear(); int i, j;
    for (auto &there : lis[here]) {
        if (there==p) continue;
        if (!dfs(there,here,t)) return false;
        cdp[here].push_back(dp[there]+1);
    }
    sort(cdp[here].begin(),cdp[here].end());
    if (cdp[here].empty()) {
        dp[here] = 0;
        return true;
    }
    if (p<0) {
        for (i=0,j=(int)cdp[here].size()/2*2-1;i<j;i++,j--) {
            if (cdp[here][i]+cdp[here][j]>t) return false;
        }
        if (cdp[here].back()>t) return false;
        return true;
    }
    if (cdp[here].size()%2==0) {
        for (i=0,j=(int)cdp[here].size()-1;i<j;i++,j--) {
            if (cdp[here][i]+cdp[here][j]>t) break;
        }
        if (i>=j) {
            dp[here] = 0;
            return true;
        }
        if (cdp[here].back()>t) return false;
    }
    int cur = 0;
    for (i=1,j=((int)cdp[here].size()-1)/2*2;i<j;i++,j--) {
        if (cdp[here][i]+cdp[here][j]>t) {
            cur = i;
            if (cdp[here][i-1]+cdp[here][j]>t) break;
        }
    }
    if (i>=j) {
        dp[here] = cdp[here][cur];
        return true;
    }
    cur = ((int)cdp[here].size()-1)/2*2; int fl = 0;
    for (i=0,j=((int)cdp[here].size()-1)/2*2-1;i<j;i++,j--) {
        if (cdp[here][i]+cdp[here][j]>t) return false;
        if (cdp[here][i]+cdp[here][j+1]<=t&&!fl) cur = j;
        else fl = 1;
    }
    dp[here] = cdp[here][cur];
    return true;
}

bool ok(int t) {
    return dfs(0,-1,t);
}

int main() {
    int i;

    scanf("%d",&n);
    for (i=0;i<n-1;i++){
        int a, b;
        scanf("%d%d",&a,&b);--a;--b;
        lis[a].push_back(b);
        lis[b].push_back(a);
    }
    int r1 = 1;
    for (i=0;i<n;i++) r1 += ((int)lis[i].size()-1)/2;
    printf("%d ",r1);
    int s = 0, e = n;
    while(s<=e) {
        int m = (s+e)>>1;
        if (ok(m)) e = m-1;
        else s = m+1;
    }
    printf("%d\n",s);

    return 0;
}


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

#define rep(i, n) REP(i, 0, n)
#define REP(i, k, n) for(auto i = k; i != n; i++)
#define rrep(i, n) RREP(i, n, 0)
#define RREP(i, n, k) for(auto i = n; i != k; i--)
#define all(x, r) (x), (x)+(r)
#define ALL(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " " << x << endl
#define exst(x, data) (data).find(x) != (data).end()
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define np next_permutation
#define b32 bitset<32>

using ll = long long;
using Pii = pair<int,int>;
using Tiii = tuple<int, int, int>;
template<class T>using V = vector<T>;

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

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

    ll H, W, N; cin >> H >> W >> N;

    map<Pii, int> m;
    V<ll> ans = V<ll>(10, 0); ans[0] = (H-2) * (W-2);
    REP(i,1,N+1) {
        int a, b; cin >> a >> b;
        rep(j,9) {
            int nx = b+dx[j], ny = a+dy[j];
            if(1<nx && nx<W && 1<ny && ny<H) {
                Pii n_xy = mp(nx,ny);
                if(m[n_xy] < 10) ans[m[n_xy]]--;
                m[n_xy]++;
                if(m[n_xy] < 10) ans[m[n_xy]]++;
            }
        }
    }

    rep(i,10) cout << ans[i] << endl;
    // REP(itr,m.begin(),m.end()) cout << itr->second << " "; cout << endl;
    return 0;
}


Measured memory_bytes: 56576
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/9
Solved on 2019/3/9
@author: shinjisu
"""


# ABC 121
# import math


def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_C():
    N, M = getIntList()
    dmp((N, M))
    BA = zeros(N)
    for i in range(N):
        BA[i] = getIntList()
    dmp(BA, 'BA')
    BA.sort()
    dmp(BA, 'BA')
    count = 0
    yen = 0
    for i in range(N):
        buyCount = min(BA[i][1], M-count)
        yen += buyCount * BA[i][0]
        count += buyCount
        dmp((buyCount, count, yen), 'buyCount, count, yen')
        if buyCount >= M:
            break
    dmp(yen, 'yen')
    return yen


debug = False  # True False
ans = prob_C()
print(ans)
#for row in ans:
#    print(row)




Measured memory_bytes: 21580
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

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

//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<<"}"<<endl;
  return o;
}

//逆元　a/b の modをとるとき -> a*modinv(b)%mod
long long modinv(long long a, long long m = 1e9+7) {
  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 const mod = 1e9+7;

// combination
const int MAX = 510000;
const ll MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  int X;
  cin >> X;
  cout << 10-X/200 << endl;
}


Measured memory_bytes: 3592