akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
string S;
int K;

// Nは桁数, countは0でないものの個数。これらが決まったときにあり得る数の個数(n C countで求まる)
ll combi(ll N, int count) {
  if (count == 1) return N*9ll;
  if (count == 2) return 81ll*N*(N-1)/2;
  if (count == 3) return 729ll*N*(N-1)*(N-2)/6;
  else return 0ll;
}
// i 桁目以降について、0 以外の値を残り K 個使用可能という状況を考える。
// このとき i 桁目までの部分が「等しい」か「strict に小さくなっている」かを smaller フラグによって分岐する。
ll dfs(int idx, int k, bool smaller) {
  if (k==0) return 1ll; // 以下全部0
  if (smaller) return combi((ll)S.size()-idx, k);
  if (idx==S.size()) {
    if (k==0) return 1ll;
    else return 0ll;
  }
  if (S[idx]=='0') return dfs(idx+1, k, false);

  ll zero_count = dfs(idx+1, k, true);
  ll between_count = ll(S[idx] - '1') * dfs(idx+1, k-1, true);
  ll icchi_count = dfs(idx+1, k-1, false);
  return zero_count+between_count+icchi_count;
}

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

  cin >> S;
  cin >> K;
  
  cout <<  dfs(0, K, false) << "\n";
  return 0;
}

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

using namespace std;

constexpr int MAXN = 2e5 + 5;

template <typename T>
inline void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int x, k, d, ans;
array<int, MAXN> L;

signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> x >> k >> d;
    x = abs(x), ans = x;
    int tmp = x / d;
    if (tmp >= k) {
        ans -= k * d;
    } else {
        int res = k - tmp;
        if (res & 1) {
            ans = abs(x % d - d);
        } else {
            ans = x % d;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
def main():
    from collections import deque
    k = int(input())
    ans = 0
    que = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    x = 0
    for _ in range(k):
        x = que.popleft()

        p = x % 10
        e = 10 * x
        if p != 0:
            a = e + p - 1
            que.append(a)
        b = e + p
        que.append(b)
        if p != 9:
            c = e + p + 1
            que.append(c)
    print(x)


if __name__ == '__main__':
    main()


Measured memory_bytes: 18996
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;

# define ll long long
//#define forn(i,n) for(int i = 0; i < (n); ++i)

const int N = 100001;
ll dp[N];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, tot;
	cin >> n >> tot;
	for (int i = 0; i < n; i++)
	{
		ll x, y;
		cin >> x >> y;
		for (int j = tot - x; j >= 0; j--) {
			dp[j + x] = max(dp[j + x], dp[j] + y);
		}
	}
	cout << dp[tot] << endl;
	return 0;
}

Measured memory_bytes: 4368
n = int(input())
ss = []
for _ in range(n):
    ss.append(input())
hs = dict()
keys = ['M', 'A', 'R', 'C', 'H']
for k in keys:
    hs[k] = 0
ss = sorted(ss)
for i, s in enumerate(ss, 0):
    c = s[0]
    if c in keys:
        if c in hs:
            hs[c] += 1
        else:
            hs[c] = 1
import itertools
combs = list(itertools.combinations(keys,3))
ans = 0
for comb in combs:
    ans += hs[comb[0]] * hs[comb[1]] * hs[comb[2]]
print(ans)

Measured memory_bytes: 10964
#include <stdio.h>

int main(void)
{
    int W, H, N, x[100], y[100], a[100];
    int i, x1, x2, y3, y4, ans;
    scanf("%d%d%d", &W, &H, &N);
    x1 = y3 = 0;
    x2 = W;
    y4 = H;
    for (i=0; i<N; i++)
    {
        scanf("%d%d%d", &x[i], &y[i], &a[i]);
        if (a[i] == 1 && x[i] > x1) {
            x1 = x[i];
        } else if (a[i] == 2 && x[i] < x2) {
            x2 = x[i];
        } else if (a[i] == 3 && y[i] > y3) {
            y3 = y[i];
        } else if (a[i] == 4 && y[i] < y4) {
            y4 = y[i];
        }
    }

    if (x2-x1>=0 && y4-y3>=0) {
        ans = (x2-x1) * (y4-y3);
    } else {
        ans = 0;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
//g++ -std=c++11 

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7

int main(){
	string S;
	cin >> S;
	if(S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) {
		cout << "Bad" << endl;
	} else {
		cout << "Good" << endl;
	}
}


Measured memory_bytes: 3596
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    ans = 1000
    for i in range(N - 1):
        if A[i] < A[i + 1]:
            n = ans // A[i]
            ans = ans + (A[i + 1] - A[i]) * n

    print(ans)

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 61800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(2000), b(2000), c(2000);
    for (ll i = 0; i < x; i++)
    {
        cin >> a[i];
    }
    for (ll i = 0; i < y; i++)
    {
        cin >> b[i];
    }
    for (ll i = 0; i < z; i++)
    {
        cin >> c[i];
    }
    sort(a.begin(), a.end(), greater<ll>());
    sort(b.begin(), b.end(), greater<ll>());
    sort(c.begin(), c.end(), greater<ll>());
    vector<ll> ans;
    for (ll i = 0; i < x; i++)
    {
        for (ll j = 0; j < y; j++)
        {
            for (ll l = 0; l < z; l++)
            {
                if ((i + 1) * (j + 1) * (l + 1) <= k)
                    ans.push_back(a[i] + b[j] + c[l]);
                else
                    break;
            }
        }
    }
    sort(ans.begin(), ans.end(), greater<ll>());
    for (int i = 0; i < k; i++)
    {
        cout << ans[i] << "\n";
    }
    return 0;
}


Measured memory_bytes: 1404
#include <stdio.h>

int main() {
    int a, b;
    int d, r;
    double f;
    scanf("%d %d", &a, &b);
    d = a / b;
    r = a % b;
    f = (double)a / (double)b;
    printf("%d %d %f\n", d, r, f);
    return 0;
}

Measured memory_bytes: 1852
def count_loop_halve_by(n)
  count = 0
  loop do
    break if n.odd?
    n /= 2
    count += 1
  end
  count
end

n = gets.to_i

ans = 0
max = -1
(1..n).each do |n|
  count = count_loop_halve_by(n)
  if max < count 
    ans = n
    max = count
  end
end

puts ans



Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int num[2][N],a[4][N],n,cnt[2];
void insert(int flag,int x){
	for (;x;x-=x&-x)num[flag][x]++;
}
int find(int flag,int x){
	int ans=0;
	for (;x<N;x+=x&-x)ans+=num[flag][x];
	return ans;
}
signed main(){
	scanf("%lld",&n);
	for (int i=1;i<=3;i++)
		for (int j=1;j<=n;j++)scanf("%lld",&a[i][j]),a[i][j]--;
	for (int i=1;i<=n;i++){
		if (a[2][i]%3!=1){
			puts("No");
			return 0;
		}
		if (a[1][i]/3!=a[2][i]/3||a[2][i]/3!=a[3][i]/3){
			puts("No");
			return 0;
		}
		int t=i&1;
		if (t^(!((a[2][i]/3)&1))){
			puts("No");
			return 0;
		}
		if (a[1][i]%3!=0)cnt[t^1]++;
		cnt[t]+=find(t,a[1][i]/3+1);
		insert(t,a[1][i]/3+1);
	}
	if (cnt[1]%2||cnt[0]%2){
		puts("No");
		return 0;
	}
	puts("Yes");
}

Measured memory_bytes: 7296
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;


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

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

#define f first
#define s second
#define p pair<int,int>
#define P pair<ll,ll>
#define pb push_back
#define ll long long
#define db double
#define zero(a) memset(a,0,sizeof(a))
#define inff(a,n) fill(a,a+n+1,inf)
#define all(a) a.begin(),a.end()
#define sz(a) int((a).size())
#define read(x) scanf("%lld",&x)
#define read2(x,y) scanf("%lld%lld",&x,&y)
#define write(x) printf("%lld\n",x)

const int maxn=2e5+5;
const ll inf=1e9;
const db pi=acos(-1);

ll x1,x2,Y1,y2,n,x[maxn],flag,dp[maxn],a,b,num,sum,ans;
vector<P>v;

int main()
{
    read2(x1,Y1),read2(x2,y2);
    if(x1>x2)swap(x1,x2),swap(Y1,y2);
    if(Y1>y2)Y1*=-1,y2*=-1,flag=1;
    read(n);
    for(int i=0; i<n; i++)
    {
        read2(a,b);
        if(flag)b*=-1;
        if(a>=x1&&a<=x2&&b>=Y1&&b<=y2)
        {
            v.pb({a,b});
        }
    }
    sort(all(v));
    fill(dp,dp+n+1,inf);
    for(int i=0; i<v.size(); i++)
    {
        *upper_bound(dp,dp+n,v[i].s)=v[i].s;
    }
    if(v.size()==0)num=0;
    else num=lower_bound(dp,dp+n,inf)-dp;
    db xy=(y2-Y1+x2-x1)*100;
    if(num==min(x2-x1,y2-Y1)+1)xy=xy-(20-5*pi)*(num-1)+10*pi-20;
    else xy-=(20-5*pi)*num;
    printf("%.12f",xy);
    return 0;
}

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

typedef long long int lli;
#define N_MAX 100000

lli n;
lli h[N_MAX];
lli a[N_MAX];
lli b[N_MAX];
lli c[N_MAX];

// 最後にそれぞれの行動をして得られる幸福度の最大値
lli dp_a[N_MAX];
lli dp_b[N_MAX];
lli dp_c[N_MAX];


lli max(lli a, lli b){
    if (a < b) return b;
    return a;
}

int main(void){
    // Your code here!
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        cin >> b[i];
        cin >> c[i];
    }
    dp_a[0] = a[0];
    dp_b[0] = b[0];
    dp_c[0] = c[0];
    
    for(int i = 1; i < n; i ++){
        dp_a[i] = max(dp_b[i-1], dp_c[i-1]) + a[i];
        dp_b[i] = max(dp_c[i-1], dp_a[i-1]) + b[i];
        dp_c[i] = max(dp_a[i-1], dp_b[i-1]) + c[i];
    }
    
    // dp_a[n-1], dp_b[n-1], dp_c[n-1]の最大値を調べる
    lli max_val = max(max(dp_a[n-1], dp_b[n-1]), dp_c[n-1]);
    
    cout << max_val;
}

Measured memory_bytes: 4992
#include<stdio.h>
int main(){
	int cs;
	int ang[105];
	scanf("%d", &cs);
	for(int i=0; i<cs; i++){
		scanf("%d", &ang[i]);
	}
	for(int j=cs-1; j>=0; j--){
		if(j==0) printf("%d\n", ang[j]);
		else printf("%d ", ang[j]);
	}
}


Measured memory_bytes: 2716
import sys
sys.setrecursionlimit(200000)
input_lines = [[int(i) for i in line.split()] for line in sys.stdin.read().splitlines()]
[user_num, rel_num] = input_lines[0]
rel_list = input_lines[1:rel_num+1]
ques_num = input_lines[rel_num+1][0]
ques_list = input_lines[rel_num+2:]
color_list = [-1] * user_num
adja_list = [set() for i in range(user_num)]

def dfs(id, color):
    if color_list[id] == -1:
        color_list[id] = color
        for a_id in adja_list[id]:
            dfs(a_id, color)



for rel in rel_list:
    adja_list[rel[0]].add(rel[1])
    adja_list[rel[1]].add(rel[0])

color = 0
for id in range(user_num):
    dfs(id, color)
    color += 1

for ques in ques_list:
    if color_list[ques[0]] == color_list[ques[1]]:
        print('yes')
    else:
        print('no')



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

typedef pair<ll, ll> P;//b, a
P p[100000];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	ll N, H;
	cin >> N >> H;
	ll amax = 0;
	for(int i = 0; i < N; i++){
		cin >> p[i].second >> p[i].first;
		amax = max(amax, p[i].second);
	}
	sort(p, p + N);
	reverse(p, p + N);

	ll ans = (H + amax - 1) / amax;
	ll bsum = 0;
	for(int i = 0; i < N; i++){
		bsum += p[i].first;
		ll cnt = i + 1;
		ll rem = H - bsum;
		if(rem >= 1){
			cnt += (rem + amax - 1) / amax;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

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


int main(){
    int n, m;
    cin >> n >> m;
    vector<int> G[3 * n];
    rep(i, m){
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        G[s].push_back(n + t);
        G[n + s].push_back(2 * n + t);
        G[2 * n + s].push_back(t);
    }
    int s, t;
    cin >> s >> t;
    // rep(i, 3 * n){
    //     cout << i << " :";
    //     rep(j, G[i].size()){
    //         cout << " " << G[i][j];
    //     }
    //     cout << endl;
    // }
    queue<int> q;
    int length[3 * n];
    rep(i, 3 * n) length[i] = -1;
    int e = s - 1;
    length[e] = 0;
    q.push(e);
    while(true){
        if (q.empty()) {
            cout << -1 << endl;
            return 0;
        }
        
        e = q.front();
        // cout << "::::" << e << " " << length[e] << endl;
        for(int i = 0; i < G[e].size(); i++){
            if (length[G[e][i]] != -1) {
                continue;
            }
            
            if (G[e][i] == t - 1) {
                cout << (length[e] + 1) / 3 << endl;
                return 0;
            }
            q.push(G[e][i]);
            length[G[e][i]] = length[e] + 1;
        }
        q.pop();
        if (length[e] > 3 * n) {
            cout << -1 << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 17792
import java.util.Scanner;
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
	static long lcm (int a, int b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}
	static int upper_division(int a,int b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lupper_division(long a,long b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lmax(long a,long b) {return Math.max(a, b);}
	static long lmin(long a,long b) {return Math.min(a, b);}
	static int[] setArray(int a) {
		int b[]=new int[a];
		for(int i=0;i<a;i++) {
			b[i]=scan.nextInt();
		}
		return b;
	}
	public static void main(String[] args) {
		int a=scan.nextInt();
		int rui1[]=new int[a];
		int rui2[]=new int[a+1];
		rui2[0]=0;
		int cnt=0;
		for(int i=0;i<a;i++) {
			cnt+=scan.nextInt();
			rui1[i]=cnt;
		}
		cnt=0;
		for(int i=1;i<=a;i++) {
			cnt+=scan.nextInt();
			rui2[i]=cnt;
		}
		int max=0;
		for(int i=0;i<a;i++) {
			int now=rui1[i]+rui2[a]-rui2[i];
			max=max(max,now);
		}
		System.out.println(max);
	}
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N; ll W;
  cin >> N >> W;
  ll w0 = 0;
  vector<vector<ll>> Vs(4);
  rep(i, N) {
    ll w, v; cin >> w >> v;
    if(i == 0) w0 = w;
    Vs[w-w0].push_back(v);
  }
  vector<vector<ll>> sum(4);
  rep(i, 4) {
    sort(all(Vs[i]), greater<ll>());
    sum[i] = vector<ll>(Vs[i].size()+1);
    rep(j, Vs[i].size()) sum[i][j+1] = sum[i][j] + Vs[i][j];
  }

  ll ans = 0;
  function<void(int, ll, ll)> dfs = [&](int cur, ll w, ll v) {
    if(cur == 4) {
      ans = max(v, ans);
      return;
    }
    rep(i, sum[cur].size()) {
      if(w+i*(w0+cur) > W) break;
      dfs(cur+1, w+i*(w0+cur), v+sum[cur][i]);
    }
  };
  dfs(0, 0, 0);
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3640
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int l = sc.nextInt();
		int r = sc.nextInt();
		int d = sc.nextInt();
		
		// 計算
		int result = 0;
		for(int i = l; i <= r; i++){
		    if(i%d == 0) result++;
		}
		

		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
	
}



Measured memory_bytes: 25364
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<cmath>
#include<complex>
#include<iomanip>

using namespace std;

#define REP(i,s,e) for(int i=int(s);i<=int(e);i++)
#define rep(i,n) for(int i=0;i<int(n);i++)
#define pi 3.14159265358979

int main(void){

	int k,a;
	for(;;){
	cin >> k;
	if(k==0) break;

    int c=0;
	rep(i,k*(k-1)/2){
	cin >> a;
    c+=a;
	}

	cout << c/(k-1) << endl;

	}

	return 0;
}

Measured memory_bytes: 1160
package main

import (
	"fmt"
	"sort"
)

func main() {
	// Code for B - Snake Toy
	var N, K int
	fmt.Scanf("%d %d", &N, &K)

	l := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &l[i])
	}

	sort.Sort(sort.Reverse(sort.IntSlice(l)))
	var sum int
	for i := 0; i < K; i++ {
		sum += l[i]
	}
	fmt.Println(sum)

}


Measured memory_bytes: 1840
open System

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f

[<EntryPoint>]
let main _ =
    let a = read int
    let b = read int
    let c = read int
    let x = read int
    seq {
        for i in 0..a do
            for j in 0..b do
                for k in 0..c do
                    yield i * 500 + j * 100 + k * 50
    }
    |> Seq.filter (fun y -> y = x)
    |> Seq.length
    |> printfn "%d"
    0


Measured memory_bytes: 14172
using System;

namespace ITP1_9_B
{
    class Program
    {
        static void Main(string[] args)
        {
            string str;
            while (!(str = Console.ReadLine()).Equals("-"))
            {
                int n = int.Parse(Console.ReadLine());
                int s = 0;
                for (int i = 0; i < n; i++) s+= int.Parse(Console.ReadLine());
                int h = s % str.Length;
                Console.WriteLine((str + str).Substring(h, str.Length));
            }
        }
    }
}

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

typedef long long ll;
ll mod = 1000000007;
ll INF = 1e18L+9;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    long long int n, w;
    cin >> n >> w;

    vector<pair<long long int, long long int>> weights;

    long long int x, y;
    long long int total_sum=0;
    for(long long int i=1; i<=n; i++){
        cin >> x >> y;
        total_sum+=y;
        weights.push_back({x,y});
    }

    sort(weights.begin(),weights.end());

    vector<long long int> dp(total_sum+1, INF);
    dp[0]=0;

    for(int i=0; i<n; i++){
        for(int j=total_sum; j>0; j--){
            if(j-weights[i].second>=0){
                dp[j]=min(dp[j], weights[i].first + dp[j-weights[i].second]);
            }
        }
    }

    ll ans = 0;
    for(ll i=0; i<=total_sum; i++){
        if(dp[i]<=w){
            ans=max(ans, i);
        }
    }

    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 3924
#include<iostream>
using namespace std;
int main(void){
  string N;
  cin >> N;
  
  char a = N[ (N.length()-1) ];
  if(a=='2' || a== '4' || a== '5' || a== '7' || a == '9'){
    cout << "hon" << endl;
  }
  else if( a=='0' || a=='1' || a=='6' || a == '8'){
    cout << "pon" << endl;
  }
  else {
    cout << "bon" << endl;
  }
  return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
//#define int long long  
int main(){
	int N,A,B;
	cin >> N >>A >> B;
	cout << min(A*N,B) << endl;
	
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (int)2e5 + 9;
const ll inf = (ll)1e15;

ll dp[N][4];
ll suf[N];

int main(){
  fastIO;
  int n;
  cin >> n;
  for(int i = 0; i <= n; i ++ ){
    for(int j = 0 ; j < 4; j ++ ){
      dp[i][j] = inf;
    }
  }
  dp[0][0] = 0;
  ll x;
  ll las;
  int bit;
  for(int i = 1; i <= n; i ++ ){
    cin >> x;
    for(int j = 0 ; j < 4; j ++ ){
      for(int p = 0 ; p <= j; p ++ ){
        las = dp[i-1][p];
        if(j == 0){
          las += x;
        }
        else{
          bit = (j-1)%2;
          if(bit == 0){
            if(x == 0) las += 2;
            else if(x % 2 == 1) las ++ ;
          }
          else{
            if(x % 2 == 0) las ++ ;
          }
        }
        dp[i][j] = min(dp[i][j], las);
      }
    }
    suf[i] = x;
  }
  for(int i = n; i >= 1; i -- ) suf[i] += suf[i + 1];
  ll ans = inf;
  for(int i = 0 ; i <= n; i ++ ){
    for(int j = 0 ; j < 4; j ++ ){
      ans = min(ans, dp[i][j] + suf[i + 1]);
    }
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 8192
#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    int N,TF=0;
    scanf("%d",&N);
    for(int i=1;i<=9;i++){
        if((N%i==0)&&(N/i>=1)&&(N/i<=9)){
            printf("%s\n","Yes");
            TF=1;
            break;
        }
    }
    if(TF!=1){
        printf("%s\n","No");
    }
    TF=0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define per(i,n) for(int i=n-1;i>=0;++i)
#define rep1(i,n) for(int i=1; i<=n; ++i)
#define per1(i,n) for(int i=n; i>=1; ++i)
#define debug cout << "line : " << __LINE__ << " debug" << endl
#define Dcout(N) cout << setprecision(20) << N << endl
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF 1e9
#define MOD 1000000007
typedef long long ll;
//------------------------------------------------------------------------

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

  string s; cin >> s;
  int cnt=0;
  rep(i,s.size()){
    if(s[i] == 'o') cnt++;
  }
  if(cnt+15-s.size()>=8) cout << "YES" << endl;
  else cout << "NO" << endl;


  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
char A[200000],B[200000];
ll n,k,s,g,m,ans;
string t;
bool f(ll p,ll q){
    for(int i=0;i<k;i++){
        if(A[i]==t[p]){
            if(B[i]=='L')p--;
            else p++;
        }
    }
    if(p==q)return true;
    return false;
}
int main(void){
    cin>>n>>k>>t;
    t='#'+t+'#';
    for(int i=0;i<k;i++)cin>>A[i]>>B[i];
    s=0,g=n+1;
    while(g-s>1){
        m=(g+s)/2;
        if(f(m,0))s=m;
        else g=m;
    }
    ans+=s;
    s=0,g=n+1;
    //cout<<ans<<endl;
    while(g-s>1){
        m=(g+s)/2;
        if(f(m,n+1))g=m;
        else s=m;
        //cout<<s<<g<<endl;
    }
    ans+=n-s;
    //cout<<ans<<endl;
    cout<<n-ans<<endl;
}


Measured memory_bytes: 984
#include<bits/stdc++.h>
int pr[10000001]= {0};
int main()
{
    int i,j,k,s,d,r,n,h,l,x,y,z,g;


    scanf("%d",&g);
    s=0;
   for(h=1; h<=g; h++)
   {
        scanf("%d",&n);


            d=0;
            r=sqrt(n);
            if(n%2==0) d++;
            for(i=3; i<=r; i+=2)
            {
                if(n%i==0) d++;
                if(d>0) break;
            }

            if(n==2) s++;

            else if(d==0) s++;
            



   }
     printf("%d\n",s);


    return 0;

}

Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
using ll=long long;

ll fact(int n) {
  if(n == 1)
    return 1;
  else
    return n*fact(n-1) % mod;
}

int main() {
  int N,i,l,cL=0,cR=0;
  ll r=1;
  string S,d;
  cin >> N >> S;
  l = N*2;
  
  if(S[0]=='W' || S[l-1]=='W') {
    cout << 0 << endl;
    return 0;
  }
  
  d.push_back('L');
  for(i=1; i<l; i++) {
    if(S[i] == S[i-1]) {
      if(d[i-1] == 'L')
        d.push_back('R');
      else
        d.push_back('L');
    } else
      d.push_back(d[i-1]);
  }
  
  for(i=0; i<l; i++)
    if(d[i] == 'L')
      cL++;
  	else
      cR++;
  
  if(cL != cR) {
    cout << 0 << endl;
    return 0;
  }
  cL=0; cR=0;
  
  for(i=0; i<l; i++) {
    if(d[i] == 'R') {
      r *= cL-cR;
      r %= mod;
      cR++;
    } else
      cL++;
  }
  
  cout << r * fact(N) % mod << endl;
}

Measured memory_bytes: 2312
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define sz(v) (int)v.size() 
#define all(v) v.begin(), v.end()
void dbg_out() { cerr << "\b\b]\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << H << ", "; dbg_out(T...);}
#define watch(...) cerr << "[" << #__VA_ARGS__ << "]: [", dbg_out(__VA_ARGS__)


/****************************** CODE IS HERE ***********************************/

const int inf = 1e9;

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

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

    int n, m; cin >> n >> m;
    int s1, s2, t1, t2; 
    cin >> s1 >> s2 >> t1 >> t2;
    s1--, s2--, t1--, t2--;

    vector <string> A(n);
    for (auto &i: A) cin >> i;

    vector <vector<int>> dist(n, vector<int>(m, inf));
    vector <vector<bool>> used(n, vector<bool>(m, false));
    
    auto check = [&](int r, int c) {
        if (r < 0 or c < 0 or r >= n or c >= m or A[r][c] == '#' or used[r][c]) return false;
        return true;
    };

    deque<pair<int,int>> q;
    q.push_back({s1, s2});
    dist[s1][s2] = 0;
    while (!q.empty()) {
        int r, c;
        tie(r, c) = q.front(); q.pop_front();
        used[r][c] = true;
        for (int i = 0; i < 4; ++i) {
            int x = r + dx[i];
            int y = c + dy[i];
            if (!check(x, y)) continue;
            if (dist[r][c] < dist[x][y]) {
                dist[x][y] = dist[r][c];
                q.push_front({x, y});
            }
        }
        for (int i = r-2; i <= r + 2; ++i) {
            for (int j = c-2; j <= c + 2; ++j) {
                if (!check(i, j)) continue;
                if (dist[i][j] > dist[r][c] + 1) {
                    dist[i][j] = dist[r][c] + 1;
                    q.push_back({i, j});
                }
            }
        }
    }

    cout << (dist[t1][t2] == inf ? -1 : dist[t1][t2]);
    

    return 0;
}


Measured memory_bytes: 8856
use std::io::stdin;

#[allow(unused_macros)]
macro_rules! read {
    ($($t:ty), *) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

fn main() {
    let (s,) = read!(String);

    println!("{}", solve(&s));
}

fn solve(x: &str) -> usize {
    let days = ["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"];
    7 - days.iter().position(|&d| d == x).unwrap()
}

#[cfg(test)]
mod tests {
    #[allow(unused_imports)]
    use super::*;

    #[test]
    fn it_works() {
        assert_eq!(solve("SAT"), 1);
        assert_eq!(solve("SUN"), 7);
    }
}


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

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            String[] inputNum = Console.ReadLine().Split(' ');
            int num1 = int.Parse(inputNum[0]);
            int num2 = int.Parse(inputNum[1]);
            int num3 = int.Parse(inputNum[2]);

            int result = num1 + num2 + num3;

            if(result <= 21)
            {
                Console.WriteLine("win");
            }
            else
            {
                Console.WriteLine("bust");
            }
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;

int main(){
    string S;
    ll K;
    cin >> S >> K;
    int ans = 1;
    rep(i, S.size()){
        if(K <= i + 1){
            cout << S[i] << endl;
            return 0;
        }
        if(S[i] != '1'){
            cout << S[i] << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3600
#include<iostream>
#include<string>
using namespace std;
int main(){
	int n,ta=0,ha=0;
	string t , h;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> t >> h;
		if (t>h){
			ta = ta + 3;
		}
		else if (h > t){
			ha = ha + 3;
		}
		else{
			ta++;
			ha++;
		}
	}
	cout << ta << " " << ha << endl;
	return 0;
}

Measured memory_bytes: 3140
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES	// M_PI=3.1415...
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
#include <iomanip>	// 20桁出力 cout << setprecision(20) << double;
#include <queue>
#include <bitset>	// bitset<8> bs1(131uL); // 10000011 bs1[0]は1 01stringからビット集合生成可
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMIS;
typedef pair<int, int> P;
typedef pair<int, pair<P, P> > PP;

#define MP make_pair
#define FAST_IO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FOR_REV(i,a,b) for(int i=(a);i>=(b);i--)
//for gcc (未test)
// #define FOREACH_IT(it,c) for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
#define FOR_ITR(d) for(auto itr=d.begin(),d_end=d.end();itr!=d_end;++itr)	// C++11
// for Debug.
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}
#define D_OUT(str,value) if(dbgF){cout<<str<<" : "<<value<<endl;}
// 入力をpush_back(d)やarray[d]に使う時に1行で書ける
// int INPUT_INT() {int d;cin>>d;return d;}
template<class T>T IN() { T d; cin >> d; return d; }
// 最大公約数（Greatest Common Divisor）
LL gcd(LL a, LL b) { return (b > 0) ? gcd(b, a%b) : a; }
// 最小公倍数（Least Common Multiple）
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
// Y年はうるう年か否か
bool uruu(LL Y) { return (((Y % 4 == 0 && Y % 100 != 0) || Y % 400 == 0) ? true : false); }

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

// vector注意
// vec[i][j]の形に入力を入れるとき、vecは初期化してある必要がある.

// ------------------- include, typedef, define END. -------------------

int N, M;
vector<string> A, B;

bool Check(int i, int j) {
	FOR(k, 0, M) {
		if (A[i+k].substr(j, M) != B[k])
			return false;
		else
			;
	}
	return true;
}


int main() {
	FAST_IO;
	// for D_OUT(str, value)  ... cout<< str <<" : "<< value <<endl;
	bool dbgF = true;

	//コードはここから書く.

	bool ans;
	cin >> N >> M;

	FOR(i, 0, N)
		A.push_back(IN<string>());
	FOR(i, 0, M)
		B.push_back(IN<string>());

	FOR(i, 0, N-M+1) {
		FOR(j, 0, N - M + 1) {
			// 画像Aの左上座標(i,j)
			ans = Check(i, j);
			if (ans)
				break;
		}
		if (ans)
			break;
	}
	cout << (ans?"Yes":"No") << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void) {
	int h[10000], w[10000], i = 0, j, a, b;
	while (1) {
		cin >> h[i] >> w[i];
		if (h[i] == 0 && w[i] == 0) {
			break;
		}
		i++;
	}
	for (j = 0; j < i; j++) {
		for (a = 0; a < h[j]; a++) {
			for (b = 0; b < w[j]; b++) {
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3088
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
Int mod = 1e9+7;

int main() {
    Int n;
    cin >> n;
    map<string, vector<pair<Int, Int>>> mp;
    for (Int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        Int p;
        cin >> p;
        mp[s].emplace_back(p, i);
    }
    for (auto v : mp) {
        sort((v.second).begin(), (v.second).end(), greater<pair<Int, Int>>());
        for (auto v2 : v.second) dump(v2.second);
    }
    return 0;
}

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


class A {
public:
  int p;
  int m;
  int start;
  bool operator <(const A &a) const {
    if(p != a.p) return p < a.p;
    return start < a.start;
  }
};


int main() {
  A data[300];
  int n;
  int m, a, b;
  int cnt;
  int w;
  bool flag;
  while(1) {
    cnt = 0;
    cin >> n;
    if(n == 0) break;
    for(int i = 0; i < n; i++) {
      cin >> m >> a >> b;
      data[cnt].p = a;
      data[cnt].m = m;
      data[cnt].start = 1;
      cnt++;
      data[cnt].p = b;
      data[cnt].m = m;
      data[cnt].start = -1;
      cnt++;
    }
    sort(data, data+cnt);
    w = 0;
    flag = false;
    for(int i = 0; i < cnt; i++) {
      w += data[i].m * data[i].start;
      if(w > 150) {
	flag = true;
	break;
      }
    }
    if(flag) cout << "NG" << endl;
    else     cout << "OK" << endl;
  }
  return 0;
}

Measured memory_bytes: 0
import Data.List.Split
import Data.List
import Control.Monad

data Cake = Cake Int Int Int

val :: Cake -> Int
val (Cake a b c) = a + b + c

getMultipleInt :: IO [Int]
getMultipleInt = getLine >>= \x -> (return . (map read)) $ splitOn " " x

rec :: [Int] -> Cake
rec ls = Cake (ls !! 0) (ls !! 1) (ls !! 2)

solve :: [Cake] -> Int -> Bool -> Bool -> Bool -> Int
solve dat am x y z = (sum . (take am)) (sortBy (flip compare) calc)
    where
        calc = map val cakes'
        change a x = if x then -a else a
        cakes' = (flip map) dat $ \(Cake a b c) -> Cake (change a x) (change b y) (change c z)


main = do
    first <- getMultipleInt
    dat <- forM [1..(first !! 0)] $ \_ -> getMultipleInt
    let dat' = map rec dat
    let x = [True, False]
    let y = [True, False]
    let z = [True, False]
    let cand = [solve dat' (first !! 1) x' y' z' | x' <- x, y' <- y, z' <- z]
    putStrLn . show $ maximum cand

Measured memory_bytes: 3324
n = int(input())
arr = [list(input().split()) for i in range(n)]

ans = 0

for j in range(n):
    if arr[j][1] == 'JPY':
        ans += int(arr[j][0])
    else:
        ans += float(arr[j][0]) * 380000.0
        
print(ans)


Measured memory_bytes: 2940
n=input()
if n=="SUN":
  print(7)
elif n=="MON":
  print(6)
elif n=="TUE":
  print(5)
elif n=="WED":
  print(4)
elif n=="THU":
  print(3)
elif n=="FRI":
  print(2)
elif n=="SAT":
  print(1)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();

        int count = 0;

        for(int i = 1 ; i <= N ; i++){
            double p = sc.nextInt();
            double q = sc.nextInt();

            if(Math.sqrt(p*p+q*q)<=D){
                count++;
            }
        

        }
        sc.close();
        System.out.println(count);
    }
}

Measured memory_bytes: 49140
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, m = map(int, readline().split())
  ab = [[0 for i in range(2)] for j in range(n)]
  for i in range(n):
    ab[i][0], ab[i][1] = map(int, readline().split())
  sort_ab = sorted(ab, key = itemgetter(0))

  
  ans = 0
  for i in range(n):
    kau = min(sort_ab[i][1], m)
    m -= kau
    ans += sort_ab[i][0] * kau
  print(ans)
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 25572
#include<iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	int ans = 0;
	for(int j = 1; j <= N; j+=2){
		int count = 0;
		for (int i = 1; i <= j; ++i) {
			if (j%i == 0)
				count++;
		}
		if (count == 8) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int lld;
typedef unsigned long long int llu;
#define INF (lld)(9223372036854775807)
#define IINF (int)(2147483647)

using namespace std;
int main(void) {
  string a,b;
  cin >> a >> b;
  lld l = a.length();
  for (lld i = 0; i < l; i++) {
    if (a.c_str()[i] != b.c_str()[i]) {
      cout << "No\n";
      return 0;
    }
  }
  cout << "Yes\n";
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int N;cin>>N;
  vector<int>v;
  map<int,int>mp;
  for(int t=0;t<N;t++){
    int a;cin>>a;
    v.push_back(a);
    mp[a]++;
  }
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());

  int temp=(int)v.size();
  if(v.size()%2==0){
    cout<<v.size()-1<<endl;
  }else{
    cout<<v.size()<<endl;
  }
  return 0;
}


Measured memory_bytes: 7284
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <time.h>
#define all(c) ((c).begin(),(c).end())
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n)
#define vsort(v) sort(v.begin(),v.end())
#define vvsort(v) sort(v.begin(),v.end(),greater<int>())
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
const ll MOD = 1e9 + 7;
const double PI = acos(-1.0);
//---------------------------------------------------------------------------------------------//
int n;
bool isso(int a) {
	int i = 2;
	while (i*i <= a) {
		if (a%i == 0)return 1;
		i++;
	}
	return 0;
}

int main() {
	while (cin >> n, n) {
		int ans = 0;
		for (int i = n + 1; i <= 2 * n; i++) {
			if (!isso(i)) {
				ans++;
			}
		}
		cout << ans << endl;
	}

}

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

using ll=long long;

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

int N,W;
ll w[110];
ll v[110];
ll dp[110][100100];

int main(){
  cin >> N >> W;
  for (int i=1;i<=N;i++)
    cin >> w[i] >> v[i];
  
  for (int j=1;j<=W;j++){
    for (int i=1;i<=N;i++){
      chmax(dp[i][j],dp[i-1][j]);
      if (j-w[i]>=0) chmax(dp[i][j],dp[i-1][j-w[i]]+v[i]);
    }
  }
  
  cout << dp[N][W] << endl;
  
}

Measured memory_bytes: 79360
/***********************************************************
 *This code By @1353055672(Ligen)                          *
 *[Warning]You're not excepted to understand this code!    *
 *NOIP 2019 RP++                                           *
 ***********************************************************/
//#pragma GCC optimize(3)
#define ADD_STACK int size = 512 << 20;\
	char *pp = (char*)malloc(size) + size;  \
	__asm__("movl %0, %%esp\n" :: "r"(pp))
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<fstream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<vector>
#define ll long long
#define ull unsigned long long
#define mn 200020
#define Max(x,y) (((x)>(y))?(x):(y))
#define Min(x,y) (((x)<(y))?(x):(y))
#define Abs(x) (((x)<(0))?(-(x)):(x))
#define infll (ll)(1e18)
#define infint (1<<30)
#define mod (int)(1e9+7)
#define FOR(a,b,c) for (register int a=b;a<=c;++a)
#define FORD(a,b,c) for (register int a=b;a>=c;--a)
using namespace std;
//char buf[1<<20],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll read(){
	ll x=0,f=1;char c;
	for(c=getchar();c<'0'||c>'9';f=((c=='-')?-1:f),c=getchar());
	for(;c>='0'&&c<='9';x=x*10+c-'0',c=getchar());return x*f;
}
template<typename T>
inline void write(T a){
	if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
	while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
}
inline void write_(){return;}
template<typename T,typename... Args>
inline void write_(T a,Args... b){write(a);putchar(' ');write_(b...);}
inline void writeln(){putchar('\n');return;}
template<typename T,typename... Args>
inline void writeln(T a,Args... b){write(a);putchar(' ');writeln(b...);}
//need c++11

//inline void write(ll a){
//    if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
//    while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
//}
//inline void write_(ll a){write(a);putchar(' ');}
//inline void writeln(ll a){write(a);putchar('\n');}
inline ll gcd(ll a,ll b){return a==0?b:gcd(b%a,a);}
inline ll lcm(ll a,ll b){return 1ll*a/gcd(a,b)*b;}
inline ll Pow(ll n,ll a){ll b=1;while(a){if(a&1)b=1ll*b*n%mod;n=1ll*n*n%mod;a>>=1;}return b;}
//---------------------Head Files--------------------------//
int n,an[mn];
bool v[mn];
char s[mn];
signed main(){
	#ifdef _WIN32
		// freopen("0.in","r",stdin);
		// freopen("0.out","w",stdout);
		long double be=clock();
	#endif
	scanf("%s",s+1);
	n=strlen(s+1);
	int j,ti=0;
	FOR(i,1,n-1)if(s[i]=='R'&&s[i+1]=='L'){
		v[i]=v[i+1]=1;
		j=i;ti=0;
		while(s[j]=='R'&&j>0){if(ti&1)++an[i+1];else ++an[i];--j;++ti;}
		j=i+1;ti=0;
		while(s[j]=='L'&&j<=n){if(ti&1)++an[i];else ++an[i+1];++j,++ti;}
	}
	FOR(i,1,n)write_(an[i]);puts("");
	#ifdef _WIN32
		long double en=clock();
		printf("Time: %.0Lfms\n",en-be);
		fclose(stdin);fclose(stdout);
	#endif
	return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
#include <queue>
#include <set>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

string s;
int n,result;
ll a,b;

int main () {
  cin >> n;
  rep(i,9) {
    if(n%(i+1) == 0 && n/(i+1) < 10) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int INF = 1001001001;

int main(){
    int N, H;
    cin >> N >> H;
    vector<int> a(N), b(N);
    priority_queue<P> que;      // (value, 攻撃できる回数)
    for(int i = 0; i < N; ++i){
        cin >> a[i] >> b[i];
        que.push(P(a[i], INF));
        que.push(P(b[i], 1));
    }
    
    ll cnt = 0;
    while(H > 0){
        P p = que.top();
        que.pop();
        int value = p.first;
        int times = p.second;
        
        if(times == 1){
            H -= value;
            cnt++;
        }
        else{
            if(H % value == 0){
                cnt += H / value;
                break;
            }
            else{
                cnt += H / value + 1;
                break;
            }
        }
    }
    
    cout << cnt << endl;
}

Measured memory_bytes: 3188
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end()) // ちゃんとユニークな配列にする。連続した値を除去して切り出す。
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

int main() {
  char X, Y;
  cin >> X >> Y;
  int x, y;
  x = (int)X;
  y = (int)Y;
  if (x == y) {
    cout << "=" << endl;
  } else if (x > y){
    cout << ">" << endl;
  } else {
    cout << "<" << endl;
  }
}


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

int main() {
  int n; cin >> n;
  vector<string> w(n);
  rep(i, n){cin >> w[i];}

  for(int i = 0; i<n-1; i++){
    for(int j = i+1; j < n; j++){
      if (w[i] == w[j]) {
        cout << "No" << endl;
        return 0;
      }
    }
  }

  for(int i = 0; i<n-1; i++){
    if (w[i][w[i].size()-1] != w[i+1][0]){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
}

Measured memory_bytes: 256