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

int main(){
    int n;
    cin >> n;
    long long int t = 0, a = 0;
    for(int i=0;i<n;++i){
        long long int ti, ai;
        cin >> ti >> ai;
        long long int m = max(1ll, max((t+ti-1) / ti, (a+ai-1) / ai));
        t = ti * m;
        a = ai * m;
    }

    cout << t + a << endl;

    return 0;
}


Measured memory_bytes: 256
import fractions
N,K=map(int,input().split())
a=list(map(int,input().split()))
bef=a[0]
gcd=a[0]
max_=a[0]
for i in range(1,N):
    if max_<a[i]:
        max_=a[i]
    gcd=fractions.gcd(gcd,a[i])
if max_<K:
    print("IMPOSSIBLE")
else:
    if K%gcd==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Measured memory_bytes: 88172
n = int(input())
a = list(map(int,input().split()))
l = [0]
k = 0
for i in range(n-1):
  if a[i]>=a[i+1]:
    l[k] += 1   
  else:
    k += 1
    l.append(0)
print(max(l))
    

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

int main()
{
	int a;
	cin>>a;
	if(a==7||a==5||a==3)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair

using namespace std;

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.precision(10);
	string s; cin >> s;
	if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3])
		cout << "Bad";
	else 
		cout << "Good";
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    int count1 = 0;
    int count2 = 0;
    for(int i = 0;i < S.length();i++){
      if(i % 2 == 0){
        if(S.charAt(i) == '0'){
          count1++;
        }else{
          count2++;
        }
      }else{
        if(S.charAt(i) == '1'){
          count1++;
        }else{
          count2++;
        }
      }
    }
    System.out.println(Math.min(count1,count2));
  }
}

Measured memory_bytes: 25552
#include <iostream>

int main(void)
{
	int a, b, result;
	char op;
	while (true)
	{
		std::cin >> a >> op >> b;
		if (op == '?') break;
		switch (op)
		{
		case '+':
			result = a + b;
			break;
		case '-':
			result = a - b;
			break;
		case '*':
			result = a * b;
			break;
		case '/':
			result = a / b;
			break;
		}
		std::cout << result << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int main(){
	boost;
	int n;
	cin>>n;
	v vec(n);
	for(auto& it:vec)cin>>it;
	vec[0]-=1;
	for (int i = 1; i < n; ++i)
	{
		if((vec[i]-1)>=vec[i-1])vec[i]--;
		if(vec[i]<vec[i-1]){cout<<"No";return 0;}
	}
	cout<<"Yes";
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Measured memory_bytes: 640
import bisect
n = int(input())
edges = sorted(list(map(int, input().split(' '))))
ans = 0
for i in range(n-1, -1, -1):
  for j in range(i-1, -1, -1):
    limit = edges[i] - edges[j]
    if limit < edges[j]:
      index = bisect.bisect_right(edges, limit)
      ans += max(0, j - index)  # maxいらんかも
print(ans)


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

int calc_sum(int n);
int check_all(int n);
int a, b;

int main() {
	int n;
	cin >> n >> a >> b;
	cout << check_all(n) << endl;
	return 0;
}

int calc_sum(int n){
	if(n < 1) return 0;
	return calc_sum(n / 10) + (n % 10);
}

int check_all(int n){
	if(n < 1) return 0;
	int s = calc_sum(n);
	if(a <= s && s <= b) return n + check_all(n - 1);
	return check_all(n - 1);
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
	int A,B;
	cin >> A >> B;
	if (A % 3 == 0 || B % 3 == 0)
		cout << "Possible" << endl;
	else if ((A + B) % 3 == 0)
		cout << "Possible" << endl;
	else
		cout << "Impossible" << endl;
}

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

int main(){
  int n;
  cin>>n;
  double xa,ya,ra,xb,yb,rb;
  while(cin>>xa>>ya>>ra>>xb>>yb>>rb){
    double r;
    r = sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
    if(r+rb<ra) cout<<"2"<<endl;
    else if(r+ra<rb) cout<<"-2"<<endl;
    else if(r>ra+rb) cout<<"0"<<endl;
    else cout<<"1"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1224
///created: 14/Jun/2019 16:07:17

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
#define db(x) cerr << "debug: " << #x << " = " << x << '\n';
template<class __Ty> bool minimize(__Ty& a, __Ty b) {
	if (a > b) { a = b; return true; }
	return false;
}
template<class __Ty> bool maximize(__Ty& a, __Ty b) {
	if (a < b) { a = b; return true; }
	return false;
}

const int hor[] = { 0, +1, -1, 0 };
const int ver[] = { -1, 0, 0, +1 };
const int w[] = { 'D', 'R', 'L', 'U' };
const int N = 1e3 + 5;
ll a[N], b[N], d[35];
int n, m;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
		cnt += int(abs(a[i] + b[i])) % 2;
	}
	if ((cnt != 0) && (cnt != n)) {
		cout << -1;
		return 0;
	}
	if (cnt == 0) {
		m = 32;
		d[1] = d[2] = 1;
		for (int i = 3; i <= m; ++i)
			d[i] = d[i - 1] * 2;
	}
	else {
		m = 31;
		d[1] = 1;
		for (int i = 2; i <= m; ++i)
			d[i] = d[i - 1] * 2;
	}
	printf("%d\n", m);
	reverse(d + 1, d + 1 + m);
	for (int i = 1; i <= m; ++i)
		printf("%lld ", d[i]);
	printf("\n");
	for (int i = 1; i <= n; ++i) {
		ll x = 0, y = 0;
		for (int j = 1; j <= m; ++j) {
			ll res = ll(1e18), t = 0;
			for (int k = 0; k < 4; ++k)
				if (minimize(res, abs(x + hor[k] * d[j] - a[i]) + abs(y + ver[k] * d[j] - b[i]))) {
					t = k;
				}
			x += 1LL * hor[t] * d[j];
			y += 1LL * ver[t] * d[j];
			printf("%c", w[t]);
		}
		printf("\n");
		fprintf(stderr, "[%lld, %lld] -> [%lld, %lld]\n", a[i], b[i], x, y);
	}
	return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent;
    vector<int> rank;

public:
    int root(int x) {
        return parent[x] >= 0 ? parent[x] = root(parent[x]) : x;
    }

    void unite(int x, int y) {
        int rootX = root(x);
        int rootY = root(y);
        if (rootX == rootY)
            return;

        if (rank[rootX] > rank[rootY]) {
            parent[rootX] += parent[rootY];
            parent[rootY] = rootX;
        } else {
            if (rank[rootX] == rank[rootY])
                ++rank[rootY];

            parent[rootY] += parent[rootX];
            parent[rootX] = rootY;
        }
    }

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

    int groupSize(int x) {
        return -parent[root(x)];
    }

    int numGroup() {
        int num = 0;
        for (int k : parent) {
            num += k < 0;
        }
        return num;
    }

    UnionFind(int size) : parent(size + 1, -1), rank(size + 1, 1) {
        parent[0] = rank[0] = 0;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edge(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
    }

    int ans = 0;
    for (int i = 0; i < m; ++i) {
        UnionFind uf(n);
        for (int j = 0; j < m; ++j) {
            if (j == i)
                continue;
            uf.unite(edge[j].first, edge[j].second);
        }
        ans += uf.numGroup() >= 2;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main(){
    int n,k,count = 0;
    cin >> n >> k;

    vector<int>v(n);

    for(int i = 0;i < n;i++)
        cin >> v[i];

    for(int i = 0;i < n;i++){
        if(v[i] >= k)count++;
    }

    cout << count << endl;

    return 0;

}

Measured memory_bytes: 640
<?php

// $s = trim(fgets(STDIN));
// fscanf(STDIN, "%d %d", $a, $b);
// $n = array_map('intval', explode(' ', trim(fgets(STDIN))));


fscanf(STDIN, "%d", $N);
$A = array_map('intval', explode(' ', trim(fgets(STDIN))));

sort($A);

$answer = 1;
foreach ($A as $A_i) {
    $answer *= $A_i;
    if ($answer == 0) {
        echo 0, PHP_EOL;
        exit;
    }
    if ($answer > 1000000000000000000) {
        echo -1, PHP_EOL;
        exit;
    }
}

echo $answer, PHP_EOL;



Measured memory_bytes: 28796
#include <bits/stdc++.h>
using namespace std;
//#define int long long
long long inf = 1e18;

signed main() {
  int a, b, q;
  cin >> a >> b >> q;
  vector<long long> s(a + 2), t(b + 2), x(q);

  for (int i = 1; i <= a; i++) {
    cin >> s[i];
  }

  for (int i = 1; i <= b; i++) {
    cin >> t[i];
  }
  s[0] = t[0] = -1 * inf;
  s[a + 1] = t[b + 1] = inf;
  for (auto &&w : x) {
    cin >> w;
  }
  //   sort(s.begin(), s.end());
  //   sort(t.begin(), t.end());

  for (auto &&w : x) {
    long long res = inf;
    int ls = lower_bound(s.begin(), s.end(), w) - s.begin();
    int lt = lower_bound(t.begin(), t.end(), w) - t.begin();
    for (int is : {ls - 1, ls})
      for (int it : {lt - 1, lt}) {
        res = min(res, abs(w - s[is]) + abs(s[is] - t[it]));
        res = min(res, abs(w - t[it]) + abs(s[is] - t[it]));
      }
    cout << res << endl;
  }
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

vector<pii> adj[30];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;
    int vv;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    for(int i=0;i<n;i++){
        cin>>x;
        for(int j=0;j<x;j++){
            cin>>a>>b;
            a--;
            adj[i].push_back(pii(a,b));
        }
    }

    bool judge = false;


    for(int i=0;i<(1<<n);i++){
        judge = true;
        cnt = 0;
        for(int j=0;j<n;j++){
            if((i&(1<<j))){
                ++cnt;
                for(int t=0;t<adj[j].size();t++){
                    cur = adj[j][t].f;
                    b = adj[j][t].s;
                    vv = i&(1<<cur);
                    if(vv&&(!b))judge = false;
                    if((!vv)&&(b))judge = false;
                }
            }
        }
        if(judge){
            mx = max(mx,cnt);
        }
    }

    cout<<mx<<"\n";

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int answer[4]={0};

int main()
{
	int n;
	char c[4];
	while(scanf("%d,%s",&n,c)!=EOF)
	{
		if(c[0]=='A'&&c[1]!='B') answer[0]++;
		else if(c[0]=='B')answer[1]++;
		else if(c[0]=='O')answer[3]++;
		else answer[2]++;
	}
	for(int i=0;i<4;i++)
	{
		printf("%d\n",answer[i]);
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
using namespace std;
const int V_MAX = 100000;

struct LowLink
{
	const vector<vector<int>> &g;
	int V;
	vector<vector<int>> dfs_tree;
	vector<int> dfs_roots;
	int pre_order[V_MAX];
	int p_ord = 0;
	int lowlink[V_MAX];
	bool articulation[V_MAX] = {};
	vector<pair<int, int>> bridge;

	LowLink(const vector<vector<int>> &g) : g(g), V(g.size()), dfs_tree(g.size()) {}

	void dfs(int v, int parent) {
		lowlink[v] = pre_order[v] = p_ord;
		p_ord++;
		for (int nv : g[v]) {
			if (nv == parent) continue;
			if (pre_order[nv] == -1) {
				dfs_tree[v].push_back(nv);
				dfs(nv, v);
				lowlink[v] = min(lowlink[v], lowlink[nv]);
			}
			lowlink[v] = min(lowlink[v], pre_order[nv]);
		}
	}

	void calc() {
		p_ord = 0;
		fill(pre_order, pre_order+V_MAX, -1);
		for (int i = 0; i < V; i++) {
			if (pre_order[i] != -1) continue;
			dfs_roots.push_back(i);
			dfs(i, -1);
		}
		for (int i = 0; i < V; i++) {
			for (int j : dfs_tree[i]) {
				if (pre_order[i] < lowlink[j]) bridge.push_back({i, j});
			}
		}
		for (int i = 0, x = 0; i < V; i++) {
			bool ok = false;
			if (x < dfs_roots.size() && dfs_roots[x] == i) {
				if (dfs_tree[i].size() > 1) ok = true;
				x++;
			} else {
				for (int j : dfs_tree[i]) {
					if (pre_order[i] <= lowlink[j]) ok = true;
				}
			}
			articulation[i] = ok;
		}
	}
};

int main() {
	int V, E;
	cin >> V >> E;
	vector<vector<int>> g(V);
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	LowLink L(g);
	L.calc();
	for (int i = 0; i < V; i++) {
		if (L.articulation[i]) cout << i << endl;
	}
	return 0;
}


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

using namespace std;

int near(string s, int i, char c) {
	int result = 1000;
	for (int j=i; j<s.size(); j++) {
		if (s[j] == c) {
			result = min(j-i, result);
		}
	}
	return result;
}

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

	int ans = 1<<30;
	for (int c=0; c<26; c++) {
		int result = 0;
		for (int i=0; i<S.size(); i++) {
			result = max(result, min(near(S, i, 'a' + c), (int)S.size()-i));
		}
		ans = min(ans, result);
	}

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


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n,m) = readLine()!!.split(" ").map { it.toInt() }
    val a = (1..n).map { readLine()!!.split(" ").map { it.toInt() }.drop(1) }
    (1..m).count{ food ->
        a.all { food in it }
    }.let { println(it) }
}

Measured memory_bytes: 36028
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int a,b,c;
			a=cin.nextInt();
			b=cin.nextInt();
			c=a+b;
			String d=Integer.toString(c);
			System.out.println(d.length());
		}
	}
}

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

int main(){
    int n,t,mx=INT_MIN,mn=INT_MAX,cnt=0;
    int A[100001],bst=0;

    cin >> n >> t;
    for(int i=1;i<=n;i++){
        cin >> A[i];
        if(A[i]<mn) mn=A[i];
        if(A[i]>mx) mx=A[i];

        if(A[i]-mn>=bst){
            if(A[i]-mn>bst) cnt=0;
            ++cnt;
            bst=A[i]-mn;
        }
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 640
n=int(input())
ans=[]
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans.append((i,j))

if n%2:
    for i in range(1,n//2+1):
        ans.remove((i,n-i))
else:
    for i in range(1,n//2+1):
        ans.remove((i,n-i+1))

print(len(ans))
for x,y in ans:
    print(x,y)


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

using namespace std;

#define int long long 
#define INF 21000000000

signed main(){
		int n;
		cin >> n;
		vector<int> b;
		for(int i=0;i<n-1;i++){
				int tmp;
				cin >> tmp;
				b.push_back(tmp);
		}
		int ans = 0;
		ans += b[0];
		ans += b[b.size()-1];
		for(int i=0;i<n-2;i++){
				ans += min(b[i],b[i+1]);
		}
		cout << ans << endl;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int K, A, B; cin >> K >> A >> B;
    for (int i = A; i <= B; ++i)
    {
        if (i % K == 0)
        {
            cout << "OK\n";
            return 0;
        }
    }
    cout << "NG\n" << endl;
}

Measured memory_bytes: 3624
import collections as c
import math as m
n=int(input())
a=[input()for i in range(n)]
a=list(map(sorted,a))
a=list(map(lambda x:"".join(x),a))
r=list(c.Counter(a).values())
r=[ m.factorial(n) // (m.factorial(n - 2) * 2) for n in r if n>1]
print(sum(r))

Measured memory_bytes: 31604
import java.awt.*;
import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
import java.time.*;
import java.util.List;


//给出两个数a,b 求出[a,b]中各位数字之和能整除原数的数的个数。
public class Main {
    int[][] dirs = new int[][]{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    int find_max(int[] arr) {
        int max = Integer.MIN_VALUE;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    int sum(int[] arr, int md) {
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            res += arr[i];
            res %= mod;
        }
        return res;
    }

    long db(long sx, long mx, long xs) {//等比数列
        return (sx + mx) * xs / 2;
    }

    int mod = (int) 1e9 + 7;
    int mx = 0;
    long[] dp;

    ///int v = (int) 1e5;
    ///
    void solve(int n,int[] arr) {
        int cnt = 0;
        for(int i=0;i<n;i+=2){
            if(arr[i]%2==1) cnt++;

        }
        System.out.println(cnt);
    }




    public static void main(String[] args)  throws IOException {
        // Use the Scanner class
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main test = new Main();
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int[] arr = new int[n];
        s = br.readLine().split(" ");
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(s[i]);
        }
        test.solve(n,arr);
    }
}


Measured memory_bytes: 32548
x0, y0, x1, y1 = map(int, raw_input().split())
dx = x1 - x0
dy = y1 - y0
r = dx**2 + dy**2
for t in xrange(input()):
    x, y = map(int, raw_input().split())
    ex = x - x0
    ey = y - y0
    ov = dx*ey - dy*ex
    if ov > 0:
        print "COUNTER_CLOCKWISE"
    elif ov < 0:
        print "CLOCKWISE"
    else:
        iv = dx*ex + dy*ey
        if iv < 0:
            print "ONLINE_BACK"
        elif 0 <= iv <= r:
            print "ON_SEGMENT"
        else:
            print "ONLINE_FRONT"

Measured memory_bytes: 6436
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#include <limits>
#include <iomanip>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
const long long INF = 1LL << 60;
typedef long long ll;
int main() {
    ll N;
    cin >> N;
    ll ans =0;
    ans = ((N-1)+1)*(N-1)/2;
    cout << ans << endl;
}

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

int main() {
  int N, A;
  cin >> N >> A;
  
  if (N % 500 == 0) {
    cout << "Yes" << endl;
  }
  else if (N % 500 <= A) {
    cout << "Yes" << endl;
  }
  else if (N % 500 >= A) {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
/*                        ______
 _______   /\     |``\   |        |  /
    |     /  \    |__/   |____    |/
    |    / _ _\   |  \   |        |\
    |   /      \  |   \  |______  |  \

            Dept. of CSE
        Comilla  University

*/
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Node struct node
#define spc " "
#define  E  2.71828182845904523536
#define pb push_back
#define pp pop_back
#define valid(nx,ny) nx>=0 && nx<n && ny>=0 && ny<m
#define ee endl
#define pii pair<int,int>
#define infinity 10000000000000000
#define mod 1000000007
int fx[]={0,0,+1,-1};
int fy[]={+1,-1,0,0};

using namespace std;
///check n=1;
///check corner case;
const int maX=1e5+1;
vector<ll>Graph[maX],cost[maX];
ll visit[maX];
ll x[10];
ll y[10];

int main()
{
    ll n,i,j,cc=0;
    cin>>n;
    ll ara[n];for(i=0;i<n;i++)cin>>ara[i];
    for(i=0;i<n;i++)if(ara[i] != i+1)cc++;
    if(cc<=2)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
return 0;
}


Measured memory_bytes: 4992
#include <iostream>

using namespace std;

int main() {
  bool A = false, B = false, C = false;
  
  for (size_t i = 0; i < 2; ++i) {
    int a;
    cin >> a;
    switch(a) {
      case 1:
        A = true;
        break;
      case 2:
        B = true;
        break;
      case 3:
        C = true;
        break;
    }
  }
  if (!A) {
    cout << 1 << endl;
  } else if (!B) {
    cout << 2 << endl;
  } else {
    cout << 3 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()
P = 10**9+7
X = [1] * N
for i in range(N-1):
    Y = [0] * (N-1-i)
    if S[i] == "<":
        Y[0] = X[0]
        for i in range(1, N-1-i):
            Y[i] = (Y[i-1] + X[i]) % P
    else:
        Y[N-2-i] = X[N-1-i]
        for i in range(N-2-i)[::-1]:
            Y[i] = (Y[i+1] + X[i+1]) % P
    X = Y

print(X[0])

Measured memory_bytes: 42204
N = int(input())
num = 0
for i in range(6):
  if N >= 10**i and N < 10**(i+1):
    keta = i+1
if keta == 1:
  num = N
elif keta == 2:
  num = 9
elif keta == 3:
  num = 9 + N - 99
elif keta == 4:
  num = 909
elif keta == 5:
  num = 909 + N -9999
else:
  num = 90909
print(num)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main()
{
  long a,b,ans=1,num=1;
  cin>>a;
  b=a;
  if(a==1) cout<<1<<endl;
  else{
    while(1){
      a/=2;
      num*=2;
      ans += num;
      if(a==1){
        break;
      }
    }
  cout<<ans<<endl;
  }
}
 

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



namespace Test1 {





    class ClassMain {

        

        public static void Main(String[] args) {
            string line;
            while ((line = Console.ReadLine()) != null) {
                int n = int.Parse(line);
                if (n == 0) { break; }
                int[] ints = new int[n];
                ints = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                int pile = 31;
                Console.WriteLine(31);
                int turn=0;
                while (true) {
                    int te = ints[turn%n];
                    if(pile<=te){pile=0;Console.WriteLine(0);break;}
                    pile-=te;
                    Console.WriteLine(pile);

                    int ani_no_te = (pile - 1) % 5;
                    pile -= ani_no_te;
                    Console.WriteLine(pile);
                    turn++;
                }
        


            }
        }
    
    }



    
}

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

int main()
{
    int h, w;
    cin >> h >> w;
    int count = 0;
    char b[h][w];
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> b[i][j];
            if (b[i][j] == '.')
                count++;
        }
    }
    int dh[4] = {-1, 1, 0, 0};
    int dw[4] = {0, 0, 1, -1};
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    vector<vector<bool>> visited(h, vector<bool>(w, 0));
    int ans[h][w];
    ans[0][0] = 1;
    ans[h - 1][w - 1] = -1;
    while (!q.empty())
    {
        pair<int, int> cr = q.front();
        q.pop();
        if (visited[cr.first][cr.second]) continue;
        visited[cr.first][cr.second] = 1;
        if (cr.first == h - 1 && cr.second == w - 1)
            break;
        for (int i = 0; i < 4; i++)
        {
            int nh = cr.first + dh[i];
            int nw = cr.second + dw[i];
            if (nh > h - 1 || nh < 0 || nw > w - 1 || nw < 0 ||
                b[nh][nw] == '#' || visited[nh][nw] == 1)
                continue;
            else
            {
                q.push(make_pair(nh, nw));
                ans[nh][nw] = ans[cr.first][cr.second] + 1;
            }
        }
    }
    if (ans[h - 1][w - 1] == -1)
        cout << -1 << endl;
    else
        cout << count - ans[h - 1][w - 1] << endl;
}

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

int main()
{
  int N;
  cin >> N;
  long long int ans = 0;
  vector<string> S(N);
  for (auto &v : S)
  {
    cin >> v;
  }
  vector<long long int> MARCH(5);
  for (auto &v : S)
  {
    if (v.at(0) == 'M')
      MARCH.at(0)++;
    else if (v.at(0) == 'A')
      MARCH.at(1)++;
    else if (v.at(0) == 'R')
      MARCH.at(2)++;
    else if (v.at(0) == 'C')
      MARCH.at(3)++;
    else if (v.at(0) == 'H')
      MARCH.at(4)++;
  }
  vector<int> P = {0, 0, 0, 0, 0, 0, 1, 1, 1, 2};
  vector<int> Q = {1, 1, 1, 2, 2, 3, 2, 2, 3, 3};
  vector<int> R = {2, 3, 4, 3, 4, 4, 3, 4, 4, 4};
  for (int i = 0; i < 10; i++)
  {
    ans += MARCH.at(P.at(i)) * MARCH.at(Q.at(i)) * MARCH.at(R.at(i));
  }
  cout << ans << endl;
}


Measured memory_bytes: 6144
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>

using namespace std;

int main()
{
	int rec = 0;
	int loz = 0;

	string s;
	for (; getline(cin, s);)
	{
		stringstream ss;
		ss << s;

		vector<int> a(3);
		for (int i = 0; i < 3; i++)
		{
			ss >> a.at(i);
			ss.ignore();
		}



		if (a.at(0) * a.at(0) + a.at(1) * a.at(1) == a.at(2) * a.at(2))
		{
			rec++;
		}
		else if (a.at(0) == a.at(1))
		{
			loz++;
		}
	}

	cout << rec << endl;
	cout << loz << endl;
}


Measured memory_bytes: 3116
/*

????????? ???????????? ????????????
?§???????????????¢????????¢???????????£??????(AiZu AnalyticS)???????\??§?????????????????§??????????
???????????????????????£?????????????????? N ????????????1 ?????? N ????????\????????????????????????
?????????AZAS ?????±?????\?????????????????§?????????????????????????????????????????????????????\??????
?????¶????°?????????¨?????????????????????????????°????????????????????¨????????????

??? ?????????????±???????????????????????????£???????????????????????????
??? ????????¢????±????????????????????????£???????????????????????????

??????
?????????????±???????????????????????????¢????±???????????????????????????£??????????????????????????????
??\???????????\?????¨???????????????????????¨???????????¶???????????????????????°???????????????????????°
?????????????????????????????????????????????????????¶???????????????????????????????????°???????????????
?????¨????????????

????£??¶????????¨?????????¶???????????????
	?????????????????§????????¶??°?????????????????????????????????????´??????????????????????????????¢???
	??£??¨??????????????¶???????????????????????°??????(A? ??? C) ??? (B ??? C??????????????????
	?????¨??? ) )????????????????´?????????°??§?????????????????????A?????????????????£?????????¨?????????

??\???
??\????????\????????¢?????§??????????????????

N
X a1 a2 ??? aX
Y b1 b2 ??? bY
Z c1 c2 ??? cZ

??\??????????????§?????????
	??????????????????????±?????????°N(1???N???100)?????????????????????
	????????????????????????????±?????????????????????°X(0???X???N)??¨???
		??????????¶????????????????????±????????????????????????\??????ai(1???ai???N)?????????????????????
	???????????????????????¢????±?????????????????????°Y(0???Y???N)??¨???
		??????????¶???????????????¢????±????????????????????????\??????bi(1???bi???N)?????????????????????
	???????????????????????£?????????????????????????????°Z(0???Z???N)??¨???
		??????????¶???????????????£????????????????????????????????\??????ci(1???ci???N)?????????????????????

??????
?????¶???????????????????????°???????????????????????????

*/

#include <stdio.h>

#define NUM 10000
#define A 0
#define B 1
#define C 2

int main( void )
{
	int n;						// ??????????±?????????°N(1???N???100)
	int d[ NUM ][ 3 ];			// 2???4??????????????????
	int t = 0;					// ?????¶????????´???????????°
	int i, j;
	int w, m;

	scanf( "%d ", &n );

	for ( i = 0 ; i < n ; i++ ) {
		d[ i ][ A ] = 0;
		d[ i ][ B ] = 0;
		d[ i ][ C ] = 0;
	}

	for ( j = 0 ; j < 3 ; j++) {
		scanf("%d ", &m );
		for ( i = 0 ; i < m ; i++) {
			scanf("%d ", &w );
			d[ w - 1 ][ j ] = 1;
		}
	}

	t = 0;
	for ( i = 0 ; i < n ; i++ ) {
		if      ( ( d[ i ][ C ] == 1 ) && ( d[ i ][ A ] == 0 ) && ( d[ i ][ B ] == 0 ) ) {
			t++;
		}
		else if ( ( d[ i ][ C ] == 1 ) && ( d[ i ][ A ] == 1 ) && ( d[ i ][ B ] == 1 ) ) {
			t++;
		}
		else if ( ( d[ i ][ C ] == 1 ) && ( d[ i ][ A ] == 0 ) && ( d[ i ][ B ] == 1 ) ) {
			t++;
		}
	}

	printf( "%d\n", t );

	return 0;
}

Measured memory_bytes: 612
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define PDD pair<double, double>
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define ctoi(x) (x - 'a') 
#define CTOI(x) (x - 'A')
#define BIT(x) (1 << (x))
using namespace std;

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

}

LL exp(LL a, LL b){
    LL res = 1;
    LL sum = a;
    while(b){
        if(b&1)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

double exp(double a, LL b){
    double res = 1;
    double sum = a;
    while(b){
        if(b&1)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

signed  main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(b, c) << " " << max(0, b + c - a) << endl;
    return 0;
}


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


using namespace std;


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

	
	
	
	
	
	
	return 0;
}

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

long long Q, H, S, D, N;

int main(){
	cin >> Q >> H >> S >> D >> N;
	N = 4 * N;
	long long ans = LONG_MAX;
	ans = min(ans, N * Q);
	ans = min(ans, N/2 * H);
	ans = min(ans, N/4 * S);
	if(N%8 == 0){
		ans = min(ans, N/8 * D);
	}else{
		ans = min(ans, (N/8*D) + 4 * Q);
		ans = min(ans, (N/8*D) + 2 * H);
		ans = min(ans, (N/8*D) + 1 * S);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define ll long long
using namespace std;

const int N = 1e5 + 7;
const long long oo = 1e18L + 5;

int n, k;

int main() {
    cin >> n >> k;
    vector<int> h(n + 1);
    vector<ll> dp(n + 2, oo);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (i + j >= n) {
                break;
            }
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }
    cout << dp[n - 1] << endl;
    return 0;
}

Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		double[] x = new double[N];
		double[] y = new double[N];
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextDouble();
			y[i] = sc.nextDouble();
		}
		double ans = 0;
		double count = 0;
		for (int i = 0; i < N - 1; i++) {
			for (int j = i + 1; j < N; j++) {
				ans += distance(x[i], y[i], x[j], y[j]);
				count++;
			}
		}
		System.out.println(ans * (N - 1) / count);
	}

	public static double distance(double x1, double y1, double x2, double y2) {
		return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
	}

}

Measured memory_bytes: 37384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    static class ACurtain
    {
        static void Main(string[] args)
        {
            var ab = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
            int a = ab[0];
            int b = ab[1];

            int answer = a - b * 2 > 0 ? a - b * 2 : 0;

            Console.WriteLine(answer);
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 13268
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[5001][10011];
int main(){
    int n,m,a[9],f[8]={},keta=0,b[10]={0,2,5,5,4,5,6,3,7,6};
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d",&a[i]);
        if(a[i]==1){
            f[2]=1;
        }
        else if(a[i]==7){
            f[3]=7;
        }
        else if(a[i]==4){
            f[4]=4;
        }
        else if(a[i]==2||a[i]==3||a[i]==5){
            f[5]=max(f[5],a[i]);
        }
        else if(a[i]==9||a[i]==6){
            f[6]=max(a[i],f[6]);
        }
        else{
            f[7]=8;
        }
    }
    dp[0][0]=1;
    for(int i=0;i<5000;i++){
        for(int j=0;j<n;j++){
            if(dp[i][j]){
                for(int k=2;k<8;k++){
                    if(f[k]){
                        dp[i+1][j+k]=max(dp[i+1][j+k],f[k]);
                    }
                }
            }
        }
    }
    for(int i=1;i<=5000;i++){
        if(dp[i][n]){
            keta=i;
        }
    }
    for(int i=keta;i>0;i--){
        printf("%d",dp[i][n]);
        n-=b[dp[i][n]];
    }
    printf("\n");
}

Measured memory_bytes: 193024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define si(x) int(x.size())
const int mod=1000000007,MAX=200005,INF=1<<29;

ll ans=0;
int N,M,Q;
vector<int> a,b,c,d;

void DFS(vector<int> now){
    if(si(now)==N){
        ll sum=0;
        for(int i=0;i<Q;i++){
            if(now[b[i]]-now[a[i]]==c[i]) sum+=d[i];
        }
        chmax(ans,sum);
        return;
    }
    
    if(si(now)==0){
        for(int i=1;i<=M;i++){
            now.push_back(i);
            DFS(now);
            now.pop_back();
        }
    }else{
        for(int i=now.back();i<=M;i++){
            now.push_back(i);
            DFS(now);
            now.pop_back();
        }
    }
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>N>>M>>Q;
    a.resize(Q);
    b.resize(Q);
    c.resize(Q);
    d.resize(Q);
    for(int i=0;i<Q;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        a[i]--;
        b[i]--;
    }
    
    vector<int> S;
    
    DFS(S);
    
    cout<<ans<<endl;
    
}


Measured memory_bytes: 3660
#include<iostream>

int power[101];
int motor[101];
int cable[101];
int a, b, c, N;
int la[1024], lb[1024], lc[1024], lr[1024];

void print(){
	int i;
	for( i = 1; i <= a; i++ ){
		std::cout << power[i] << std::endl;
	}
	for( i = 1; i <= b; i++ ){
		std::cout << motor[i] << std::endl;
	}
	for( i = 1; i <= c; i++ ){
		std::cout << cable[i] << std::endl;
	}
	return;
}

int input(){
	int i;
	std::cin >> a >> b >> c;
	std::cin >> N;
	for( i = 1; i <= a; i++ ){
		power[i] = 2;
	}
	for( i = 1; i <= b; i++ ){
		motor[i] = 2;
	}
	for( i = 1; i <= c; i++ ){
		cable[i] = 2;
	}
	for( i = 0; i < N; i++ ){
		std::cin >> la[i] >> lb[i] >> lc[i] >> lr[i];
	}
	return (a+b+c);
}

void check(){
	int x, y, z, i;
	for( i = 0; i < N; i++ ){
		if( lr[i] == 0 ){ continue; }
		x = la[i];
		y = lb[i] - a;
		z = lc[i] - a - b;
		power[x] = 1;
		motor[y] = 1;
		cable[z] = 1;
	}
	for( i = 0; i < N; i++ ){
		if( lr[i] == 1 ){ continue; }
		x = la[i];
		y = lb[i] - a;
		z = lc[i] - a - b;
		if( motor[y] == 1 && cable[z] == 1 ){
			power[x] = 0;
		}else if( power[x] == 1 && cable[z] == 1 ){
			motor[y] = 0;
		}else if( power[x] == 1 && motor[y] == 1 ){
			cable[z] = 0;
		}
	}
	return;
}

int main(){
	while( input() != 0 ){
		check();
		print();
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

#define INF 1<<30
#define LINF 1ll<<60ll
#define MOD 1000000007
#define pb(a) push_back(a)

#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload3(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)

#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)

#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))

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

#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl



int main(){
    int a,b,c;
    cin>>a>>b>>c;
    REP(i,b){
        if((a*i)%b==c){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int a,b;
    cin>>a>>b;
    if(a<9&&b<9){
        cout<<"Yay!"<<endl;
    }
    else{
        cout<<":("<<endl;
    }
  return 0;  
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    if(str.equals("ABC")) {
      System.out.println("ARC");
    }
    if(str.equals("ARC")) {
      System.out.println("ABC");
    }
  }
}

Measured memory_bytes: 35604
#include<bits/stdc++.h>
using namespace std;
int main(){
  double n;
  cin >> n;
  int num=n;
  double ans;
  if(num==1){
    ans=1;
  }
  else if(num%2==1){
    ans=(n+1)/2/n;
  }
  else{
    ans=0.5;
  }
  cout << fixed << setprecision(15) << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int maxn = 110;
int arr[maxn];
int main(){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    for(int i = 0; i < n; i++) if (i == 0) printf("%d", arr[i]); else printf(" %d", arr[i]);
    puts("");
    for(int i = 1; i <= n-1; i++){
        int key = arr[i];
        int j = i-1;
        while(j >= 0 && arr[j] > key){
            arr[j+1] = arr[j], j--;
        }
    arr[j+1] = key;
    for(int i = 0; i <= n-1; i++){
        if (i == 0) printf("%d", arr[i]); else printf(" %d", arr[i]);
    }
    puts("");
    }
}


Measured memory_bytes: 3216
#include <iostream>
#include <vector>
using namespace std;;
#define ll long long
#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 INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

ll dp[103][100300];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,W;cin >> n >> W;
  vector<ll> w(n),v(n);
  rep(i,n){
      cin >> w[i] >> v[i];
  }
  rep(i,103){
      rep(j,100300){
          dp[i][j] = LINF;
      }
  }
  dp[0][0] = 0;
  rep(i,n){
      rep(j,100001){
          dp[i+1][j]= min(dp[i][j],dp[i+1][j]);
          dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j]+w[i]);
      }
  }
  FORR(i,100000,0){
      if(dp[n][i]<=W){
          cout << i << endl;
          return 0;
      }
  }

  
}


Measured memory_bytes: 81024
// ------- PBDS ------ //
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// ------- PBDS ------ //

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define testcase ll tt; cin>>tt; while(tt--)
#define pb push_back
#define nn cout<<"\n"
#define MOD 1000000007
#define pi 3.1415926535
#define endl "\n"
#define vll vector<ll>
#define MULTI int T; cin >> T; while(T--)
#define all(a)      (a).begin(),(a).end()
#define here cout<<"I'm here\n";
void vout(vector<ll> ans){
    for(auto ele:ans) cout<<ele<<" "; cout<<endl;
}
vector<ll> adj[200001];
bool vis[200001];

// ------- PBDS ------ //
typedef tree<
// change this for any data-type
string,
null_type,
// change this for any data-type
less<string>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

/*
    to get the position of an element in set , do
    s.order_of_key(ele);
    this returns the number of elements strictly lesser than ele in set s
    Let us assume we have a set s : {1, 5, 6, 17, 88}, then :
    s.order_of_key(6) : Count of elements strictly smaller than 6 is 2.
    s.order_of_key(25) : Count of elements strictly smaller than 25 is 4.

    to get the element at position k
    s.find_by_order(k);
    returns an iterator to the ele counting from 0
    Let us assume we have a set s : {1, 5, 6, 17, 88}, then :
    *(s.find_by_order(2)) : 3rd element in the set i.e. 6
    *(s.find_by_order(4)) : 5th element in the set i.e. 88
*/

// ------- PBDS ------ //

clock_t time_p=clock();
void purvansh11()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

//BINARY EXPONENTIATION  -- O(log2(b))
ll power(ll a, ll b) {
    /*
        for 3^11 :
        as 11 -> 1011, we mean 3^8 * 3^2 * 3^1
        so multiply for all ones in binary rep of b
    */

    ll ans = 1;
    ll num = a;
    while (b > 0) {
        if (b & 1) ans = ((ans % MOD) * (num % MOD)) % MOD;
        num = ((num % MOD) * (num % MOD)) % MOD;
        b /= 2;
    }
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    SPEED;
    cout.precision(8);
    cout << fixed;
    ll n; cin>>n;
    ll pow10 = power(10,n);
    ll pow9 = power(9,n);
    ll pow8 = power(8,n);
    pow9 = (pow9*2)%MOD;
    ll ans = (pow10 - pow9 + MOD)%MOD;
    ans = (ans + pow8%MOD)%MOD;
    cout<<ans;   
    
    purvansh11();
    return 0;
}

Measured memory_bytes: 8416
N, M = map(int, input().split())
S = [tuple(map(int, input().split())) for _ in range(N)]
C = [tuple(map(int, input().split())) for _ in range(M)]

for a, b in S:
    ans = 0
    dmin = float('inf')
    for i, (c, d) in enumerate(C):
        d = abs(a - c) + abs(b - d)
        if d < dmin:
            ans = i + 1
            dmin = d
    print(ans)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
ll pic[305][305]={0};
ll sum[305][305]={0};
ll rsum(int x1,int y1,int x2,int y2){
  if(x1>=x2||y1>=y2) return 0;
  ll ret=sum[x2][y2]+sum[x1][y1];
  return ret-sum[x2][y1]-sum[x1][y2];
}
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++) cin>>pic[i][j];
  }

  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++) sum[i][j]=sum[i][j-1]+pic[i][j];
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++) sum[i][j]+=sum[i-1][j];
  }

  ll ans=-17441744;
  for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
      //l=i r=j

      vector<ll> vec;
      vec.push_back(0);
      vec.push_back(rsum(i-1,0,j,1));
      for(int k=2;k<=n;k++){
        vec.push_back(vec[k-1]+rsum(i-1,k-1,j,k)-rsum(i,k-2,j-1,k-1));
      }

      priority_queue<int> pque;
      pque.push(vec[n]);
      ll kans=pque.top();
      for(int k=n-1;k>=1;k--){
        kans=max(kans,pque.top()-vec[k]+rsum(i,k-1,j-1,k)+rsum(i-1,k-1,j,k));
        //if(i==1&&j==5) cout<<pque.top()-vec[k]+rsum(i,k-1,j-1,k)+rsum(i-1,k-1,j,k)<<endl;
        pque.push(vec[k]);
      }
      /*if(i==1&&j==5){
        for(int k=1;k<=n;k++) cout<<vec[k]<<" ";
        cout<<endl;
      }*/

      ans=max(ans,kans);
      //if(i==4&&j==4) cout<<i<<" "<<j<<" "<<kans<<endl;

      //if(kans==14) cout<<i<<"!"<<j<<endl;
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 4608
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
	long n = Long.parseLong(scan.next());
	long s = Long.parseLong(scan.next());

	long ans = 0;
	int rootN = (int)(Math.sqrt(n));
	if(n == s) {
	    ans = n+1;
	} else {
	    for (int b = 2; b <= rootN; b++) {
		if(f(b, n) == s) {
		    ans = b;
		    break;
		}
	    }
	    if(ans == 0) {
		for (int p = rootN; p > 0; p--) {
		    if((n-s) % p == 0) {
			long b = (n-s)/p+1;
			if(b > 1 && f(b, n) == s) {
			    ans = b;
			    break;
			}
		    }
		}
	    }
	}
	
	System.out.println(ans > 0 ? ans : -1);
	scan.close();
    }

    private static long f(long b, long n) {
	long result = 0;
	while(n / b > 0) {
	    result += n % b;
	    n = n/b;
	}
	result += n;
	return result;
    }
}


Measured memory_bytes: 23124
#include<stdio.h>

int main(void){

char str[1010];

int i,sum;

scanf("%s",str);

while(str[0]!='0'){

i=0; sum=0;

while(str[i]){

sum+=str[i]-'0';i++;

}

printf("%d\n",sum);

scanf("%s",str);

}

return 0;

}

Measured memory_bytes: 536