akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize ("O3")
//#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define FOR(i,a,n) for(register int i=a; i<=n; ++i)
#define FDR(i,a,n) for(register int i=a; i>=n; --i)
#define mem(a) memset(a, 0, sizeof(a))
#define pb(a) push_back(a)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
priority_queue <int,vector<int>,greater<int> > q1;
priority_queue<int> q2;
const int maxn = 100005;
const int MOD = 1000000009;
const ll LINF = 1e15;
ll a[maxn];

int main()
{
//    ios::sync_with_stdio(false);
//    freopen("data.txt", "r", stdin);
//    freopen("text2.txt", "w", stdout);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    cin >> a[i];
    int m = 0;
    for(int i = 1; i < n; i++)
    {
        if(a[i] < 0 && a[i+1] >= 0){
            m =i;
            break;
        }
    }
    if(a[n] < 0)m = n;
    ll ans = LINF;
    for(int i = m+1; i <= n; i++)
    {
        int o = k-(i-(m+1)+1);
//        cout << o << endl;
        if(o > m)continue;
        else if(o < 0)break;
        else
        {
            int temp = m-o+1;
            if(temp > m)temp = 0;
            ans = min(ans, a[i]-2*a[temp]);
        }
//    cout << ans << endl;
    }
    for(int i = 1; i <= m; i++)
    {
        int o = k-i;
        if(o > n-m)continue;
        else if(o < 0)break;
        else
        {
            int temp = o-1+m+1;
            if(temp <= m)temp = 0;
            ans = min(ans, -a[m-i+1]+2*a[temp]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long lng;
typedef unsigned long long ulng;

#define pb push_back
#define SZ(a) int((a).size())
#define ALL(aA) (a).begin(), (a).end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

lng power(lng b, lng e) {lng sol=1; while(e>0) {if(e&1) {sol=sol*b;} e>>=1; b*= b;} return sol;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N;
    cin >> S;

    int ans = 0;
    FOR(c, 1, N-1) {
        int tmp = 0;
        bool flag[40] = {0};
        REP(i, c) {
            flag[S[i]-'a'] = 1;
        }
        FOR(i, c, N-1) {
            if(flag[S[i]-'a']) {
                tmp++;
                flag[S[i]-'a'] = 0;
            }
        }
        ans = max(ans, tmp);
    }

    std::cout << ans << endl;
}


Measured memory_bytes: 256
/************************************************
*Author        :  xzj213
*Created Time  :  2019.10.27.20:59
*Mail          :  xzj213@qq.com
*Problem       :  E
************************************************/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int a[maxn],f[maxn],l,r,n,k;
int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch>57 || ch<48){if(ch==45)f=-1;ch=getchar();}
    while(ch<=57 && ch>=48){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
bool check(int point){
	int num=k;
	for(int i=1;i<=n;i++){
		int b=point/f[i];
		if(a[i]-b>0)
			num-=(a[i]-b);
		if(num<0)return false;
	}
	return true;
}
bool cmp(int a,int b){
	return a>b;
}
signed main() {
    n=read();k=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		f[i]=read();
	sort(a+1,a+1+n);
	sort(f+1,f+1+n,cmp);
	l=0;r=1e18;
	while(l<r){
		int Mid=(l+r)>>1;
		if(check(Mid))r=Mid;
		else l=Mid+1;
	}
	cout<<r<<endl;
    return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int A,B,K;
  int ans=0;
  int i;
  int answer[100]={0};
  cin>>A>>B>>K;
  for(i=1;i<=B;i++){
	if(A%i==0&&B%i==0){answer[ans]=i;ans++;}
  }
cout<<answer[ans-K]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int N,M,X;
  cin >> N >> M >> X;
  int C[N];
  int A[N][M];
  int ans = 99999999;
  for (int i = 0; i < N; i++) {
    cin >> C[i];
    for (int j = 0; j < M; j++) {
      cin >> A[i][j];
    }
  }
  for (int bit = 0; bit < (1 << N); bit++) {
    int now = 0;
    int n[M];
    for (int i = 0; i < M; i++) {
      n[i] = 0;
    }
    for (int i = 0; i < N; i++) {
      if (bit & (1 << i)) {
        now += C[i];
        for (int j = 0; j < M; j++) {
          n[j] += A[i][j];
        }
      }
    }
    bool can = true;
    for (int i = 0; i < M; i++) {
      if (n[i] < X) {
        can = false;
      }
    } 
    if (can) {
      ans = min(ans,now);
    }
  }
  if (ans == 99999999) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3640
n, m = [int(i) for i in input().split()]

matrix = []
for ni in range(n):
    matrix.append([int(a) for a in input().split()])

vector = []
for mi in range(m):
    vector.append(int(input()))

for ni in range(n):
    sum = 0
    for mi in range(m):
        sum += matrix[ni][mi] * vector[mi]

    print(sum)

Measured memory_bytes: 8048
#![allow(non_snake_case)]

fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn to_base3(n: i32) -> String {
    let q = n / 3;
    let r = n % 3;
    if q == 0 {
        r.to_string()
    } else {
        to_base3(q) + &r.to_string()
    }
}

fn main() {
    let N: u32 = read_line().parse().unwrap();
    let len = N.to_string().len();
    if len < 3 {
        println!("0");
        return;
    }
    let mut ans: i32 = (2..len as u32).map(|x| 3_i32.pow(x) - 3*2_i32.pow(x) + 3).sum();
    for n in 0..3_i32.pow(len as u32) {
        let mut s: Vec<char> = to_base3(n).chars().collect();
        while s.len() < len {
            s.insert(0, '0');
        }
        if N < s.iter().fold(0, |sum, &d| sum*10 +  d.to_digit(10).unwrap()*2+3) {
            break;
        }
        if s.contains(&'0') && s.contains(&'1') && s.contains(&'2') {
            ans += 1;
        }
    }
    println!("{}", ans);
}


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

int main() {
  long long N; cin >> N;
  long long res = 0;
  for (long long r = 1; r*r <= N; ++r) {
    if ((N-r) % r == 0 && (N-r)/r > r) res += (N-r)/r;
  }
  cout << res << endl;
}

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

using namespace std;

typedef long long llint;

int main() {
  int n;
  cin >> n;
  vector<llint> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a.begin() + 1, a.end());
  int t = 0;
  llint sum = 0;
  for (int i = 1; i < n; i++) {
    sum += a[i];
    if (2 * sum < a[i + 1]) {
      t = i;
    }
  }
  cout << n - t << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  
  int count = 0;
  
  for (int i = 0; i < n; i++) {
    if (a.at(i) == count + 1) {
      count++;
    }
  }
  
  if (count > 0) cout << n - count << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>

using namespace std;

int main() {
	int n;
	cin >> n;
	if (n % 2 == 0) {
		cout << setprecision(10) << 0.5 << "\n";
	} else {
		cout << setprecision(10) << (double)(n / 2 + 1) / (double)n << "\n";
	}
	return 0;
}

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

#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;

typedef long long ll;



int main(){

    int a,b,c;
    cin >> a >> b >> c;

    if((a != b && b != c && a != c)||(a == b && b == c)){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

int main(){
	int n, s;
	cin >> n >> s;

	vector<ll> x(n), p(n);
	rep(i,0,n) cin >> x[i] >> p[i];

	ll ans = 0;

	int lo = 0, hi = n-1;

	int prevdir = 0;

	while(true){
		if(x[lo] >= s){
			ans += x[hi]-s;
			cout << ans << endl;
			return 0;
		}
		if(x[hi] <= s){
			ans += s - x[lo];
			cout << ans << endl;
			return 0;
		}

		if(p[lo] >= p[hi]){
			p[lo] += p[hi];
			if(prevdir != 1){
				prevdir = 1;
				ans += x[hi] - x[lo];
			}
			--hi;
		}
		else {
			p[hi] += p[lo];
			if(prevdir != -1){
				prevdir = -1;
				ans += x[hi] - x[lo];
			}
			++lo;
		}
	}
}

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

#define ARC(i, a, b) for(int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)

template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; }
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; }
template<class T> T &anth(T &a, const T &b){ return a = ant(a, b); }
template<class T> T &onth(T &a, const T &b){ return a = ont(a, b); }

std::vector<std::pair<int, int>> e[112345];
int ans[112345];

int main(){
	int n;
	scanf("%d", &n);
	RC(i, n - 1){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		e[u].push_back(std::make_pair(v, w));
		e[v].push_back(std::make_pair(u, w));
	}
	for(int i = 2; i <= n; ++i) ans[i] = -1;
	std::queue<int> q;
	q.push(1);
	while(!q.empty()){
		for(auto i : e[q.front()]) if(ans[i.first] == -1){
			ans[i.first] = ans[q.front()] ^ (i.second % 2);
			q.push(i.first);
		}
		q.pop();
	}
	for(int i = 1; i <= n; ++i){
		std::cout << ans[i] << std::endl;
	}
}


Measured memory_bytes: 7168
n, q = map(int, input().split())

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
ald = [True]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
ald[0] = False
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    for root in tree[now]:
      if ald[root]:
        ald[root] = False
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

Measured memory_bytes: 67724
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <queue>
#include <math.h>
#include <cmath>
#include <unordered_map>

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



void solve(std::string S, std::string T){
    int ans=T.length();
    rep(i, S.length()-T.length()+1){
        //cout<<S[i]<<endl;
        int cnt=0;
        rep(j,T.length()){
            if(S[i+j]!=T[j])cnt++;
        }
        ans=min(cnt,ans);
    }
    cout<<ans<<endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
    std::cin >> S;
    std::string T;
    std::cin >> T;
    solve(S, T);
    return 0;
}


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

/**
 * Made by egor https://github.com/chermehdi/egor.
 * 
 * @author Azuz
 * 
 */
public class Main {

    void solve(Scanner in, PrintWriter out) {
      int n = in.nextInt();
      int m = in.nextInt();
      ArrayList<Integer>[] g = new ArrayList[n + 1];
      
      for (int i = 0; i <= n; ++i) {
        g[i] = new ArrayList<>(); 
      } 
      
      for (int i = 0; i < m; ++i) {
        int u = in.nextInt();
        int v = in.nextInt();
        g[u].add(v);
        g[v].add(u);
      }

      int ans = 0;
      int count = 0;
      boolean[] vis = new boolean[n + 1];
      for (int i = 1; i <= n; ++i) if (!vis[i]) {
        int size = 0;
        Stack<Integer> stk = new Stack<>();
        stk.push(i);

        while (!stk.isEmpty()) {
          int u = stk.pop();
          if (vis[u]) continue;
          vis[u] = true;
          ++size;

          for (int v : g[u]) {
            stk.push(v);
          }
        }
        ans = Math.max(ans, size);
      }

      
      out.println(ans);
    }

    public static void main(String[] args) {
        try(Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)) {
            new Main().solve(in, out);
        }
    }
}


Measured memory_bytes: 85136
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=b[a[0]-1]
for i in range(1,n):
    ans=ans+b[a[i]-1]
    if a[i-1]==a[i]-1:
        ans=ans+c[a[i]-2]
print(ans)

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

struct Dimension {
    int N;
    vector< LL >basis;
    Dimension(int N) : N(N), basis(N, 0) { }

    bool add(LL x) {
        for (int i = 0; i < N; i++) {
            if (x&(1LL<<i)) {
                if (basis[i]) x ^= basis[i];
                else {
                    basis[i] = x;
                    return true;
                }
            }
        }
        return false;
    }
};

char solve() {
    int n;
    cin >> n;

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

    string s;
    cin >> s;

    Dimension d(60);
    for (int i = n-1; i >= 0; i--) {
        if (d.add(A[i])) {
            if (s[i]=='1') return '1';
        }
    }
    return '0';
}


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

    while (t--) {
        cout << solve() << "\n";
    }


    return 0;
}


Measured memory_bytes: 3600
program main
implicit none
integer:: n,i,j,b,alice,bob,gap
integer,allocatable:: a(:)
 
read(*,*) n
allocate(a(n))
read(*,*) a
 
do j=1,n
do i=1,n-1
if(a(i)<a(i+1))then
b=a(i+1)
a(i+1)=a(i)
a(i)=b
endif
end do
end do
 
alice=0
bob=0
 
do i=1,n
if(mod(i,2)==0)then
bob=bob+a(i)
else
alice=alice+a(i)
endif
end do
 
gap=alice-bob
write(*,*) gap
 
end program main

Measured memory_bytes: 2772
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL<<60);

int main() {
    int n, m;
    cin >> n >> m;
    long long data[n][3];
    for (int i = 0; i < n; i++) {
        cin >> data[i][0] >> data[i][1] >> data[i][2];
    }
    
    long long ans = -INF;
    for (int bit = 0; bit < (1<<3); bit++) {
        vector<long long> v;
        for (int i = 0; i < n; i++) {
            long long s = 0;
            for (int j = 0; j < 3; j++) {
                if (bit&(1<<j)) s += data[i][j];
                else s -= data[i][j];
            }
            v.emplace_back(s);
        }
        sort(v.rbegin(), v.rend());
        long long res = accumulate(v.begin(), v.begin() + m, 0LL);
        if (ans < res) ans = res;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

bool func(const pair<pair<long long, long long>, long long> &a, pair<pair<long long, long long>, long long> &b)
{
	return a.second > b.second;
}

int main()
{
	int n;
	vector<pair<pair<long long,long long>,long long>> p;
	long long input1, input2;
	int i;
	long long tot = 0;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf("%lld %lld", &input1, &input2);

		p.push_back(pair<pair<long long, long long>, long long>(pair<long long, long long>(input1, input2), input1 + input2));
	}

	sort(p.begin(), p.end(), func);

	for (i = 0; i < n; i++)
	{
		if (!(i % 2))
		{
			tot += p[i].first.first;
		}

		else
		{
			tot -= p[i].first.second;
		}
	}

	printf("%lld\n", tot);

	return 0;
}

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

ll gcd(ll a,ll b){
   if(a==0)return b;
   else return gcd(b%a,a);

}
int main()


{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll hcf =(c*d)/gcd(c,d);
    ll c1 = b/c-(a-1)/c;
    ll c2 = b/d-(a-1)/d;
    ll c3 = b/hcf-(a-1)/hcf;
    
    cout<<b-a+1-(c1+c2-c3);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#define sp ' '
#define nyan "(=^・ω・^=)"
#define mkp make_pair
#define intmax 2147483647
#define llmax 9223372036854775807
#define lP pair<ll,ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;
const int mod=1000000007;

int N, res, P[100][10];
bool F[100][10];

int main() {
	cin >> N;
	for (int i = 0; i != N; ++i) {
		for (int j = 0; j != 10; ++j) {
			cin >> F[i][j];
		}
	}
	for (int i = 0; i != N; ++i) {
		for (int j = 0; j != 11; ++j)
			cin >> P[i][j];
	}
	res = -intmax;
	for (int i = 1; i != (1 << 10); ++i) {
		int sum = 0;
		vector<int>cnt(N, 0);
		for (int j = 0; j != 10; ++j) {
			if (i&(1 << j)) {
				for (int k = 0; k != N; ++k) {
					if (F[k][j])
						++cnt[k];
				}
			}
		}
		for (int j = 0; j != N; ++j) {
			sum += P[j][cnt[j]];
		}
		res = max(sum, res);
	}
	cout << res << endl;
	return 0;
}

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

long long func(long long n, long long x) {
  if (n < 0) {
    return 0;
  }
  return n / x + 1;
}

int main() {
  long long a, b, x;
  cin >> a >> b >> x;
  cout << func(b, x) - func(a - 1, x) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//:/
#define pb push_back
#define mp make_pair
#define nt _ll128
#define ld long double
long double PI =3.14159265358979323846;
using ll = long long;



const ll modo=998244353;
const ll inf=1e17;
const ll ms=(1e5)+5;

ll ar[ms]={0};
ll dp[ms][2]={0};

int go(int a,int b,int c)
{

    int r=0;
    if(a)
    {
        r+=c;
        if(b){r++; b--;}
        r+=min(a-1,b);
    }
    else if(c)
    {
        r=c-1;
        if(b)r++;
    }
    return r;
}

int main()
{
    idfc;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int x=c-a;
    int y=d-b;
    int i;

    for(i=1;i<=x;i++)
    {
        cout<<"R";
    }
    for(i=1;i<=y;i++)cout<<"U";
    for(i=1;i<=x;i++)cout<<"L";
    for(i=1;i<=y;i++)cout<<"D";
    
    cout<<"D";
    
    for(i=1;i<=x+1;i++)cout<<"R";
    
    for(i=1;i<=y+1;i++)cout<<"U";
    
    cout<<"L";
    
    cout<<"U";
    
    for(i=1;i<=x+1;i++)cout<<"L";
    
    for(i=1;i<=y+1;i++)cout<<"D";
    
    cout<<"R";
    
    return 0;
}

Measured memory_bytes: 3664
Dy = [0,1,0,-1]
Dx = [1,0,-1,0]
H, W, K = map(int, input().split())
y1,x1,y2,x2 = map(int, input().split())
C = ["@" + input() + "@" for _ in range(H)]
C = ["@"*(W+2)] + C + ["@"*(W+2)]
L = [[1]*(W+2) for _ in range(H+2)]
R = [[1]*(W+2) for _ in range(H+2)]
U = [[1]*(W+2) for _ in range(H+2)]
D = [[1]*(W+2) for _ in range(H+2)]
q = [(y1, x1)]
ans = 0
while q:
    q_new = []
    for y0, x0 in q:
        if (y0, x0) == (y2, x2):
            print(ans)
            exit()
        for dy, dx, Next in zip(Dy, Dx, [L, R, U, D]):
            y, x = y0, x0
            sum_next = 0
            Path = [(y, x)]
            while True:
                sum_next += Next[y][x]
                y = y0 + dy * sum_next
                x = x0 + dx * sum_next
                if sum_next > K:
                    break
                if C[y][x] == "@":
                    break
                Path.append((y, x))
                q_new.append((y, x))
            for path_y, path_x in Path:
                Next[path_y][path_x] = abs(path_y-y) + abs(path_x-x)
    q = q_new
    ans += 1

print(-1)


Measured memory_bytes: 181852
#include<stdio.h>
#include<math.h>
int gcd(int a,int b){
	while(a){
		b%=a;
		int c=b;
		b=a;
		a=c;
	}
	return b;
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a+b){
		double t=sqrt(a);
		double L=999999;
		int w=0;
		int x=0;
		int y=0;
		int z=0;
		double R=999999;
		for(int i=1;i<=b;i++){
			int l=(int)(t*i);
			int r=l+1;
			if(l<=b&&gcd(l,i)==1&&t-(double)l/i<L){
				L=t-(double)l/i;
				w=l;
				x=i;
			}
			if(r<=b&&gcd(r,i)==1&&(double)r/i-t<R){
				R=(double)r/i-t;
				y=r;
				z=i;
			}
		}
		printf("%d/%d %d/%d\n",y,z,w,x);
	}
}

Measured memory_bytes: 760
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	params := strings.Split(scanner.Text(), " ")
	paramA, _ := strconv.ParseInt(params[0], 10, 64)
	paramB, _ := strconv.ParseInt(params[1], 10, 64)
	paramC, _ := strconv.ParseInt(params[2], 10, 64)
	paramK, _ := strconv.ParseInt(params[3], 10, 64)
	result := math.Min(float64(paramA), float64(paramK))
	paramK -= paramA
	paramK -= paramB
	if paramK > 0 {
		result -= math.Min(float64(paramC), float64(paramK))
	}
	fmt.Println(int64(result))
}


Measured memory_bytes: 1756
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
#include<cmath>
#include<array>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)
#define show(x) cout<< #x << " = " << (x) << endl
#define show_array(arr) REP(i,int((arr).size()))cout<< #arr << "["<<i<<"]"<<"="<<arr[i]<<endl

ll douro = 0;
bool isA = true;

array<array<ll,300>,300> B;

template<typename T,size_t N>
void warshallFloyd(array<array<T,N>,N>& distance_matrix,int M){
	
	for(int k = 0; k < M; k++){
		for(int i = 0; i < M; i++){
			for(int j = 0; j < M; j++){
				if(i == j || i == k || j == k)continue;

				if(distance_matrix[i][j] > distance_matrix[i][k] + distance_matrix[k][j]){
					isA = false;
					B[i][j] = 0;
				}
				else if(distance_matrix[i][j] == distance_matrix[i][k] + distance_matrix[k][j]){
					B[i][j] = 0;
				}

			}
		}
	}

}

int main(){
	
	ios::sync_with_stdio(false);
	int N;
	
	cin>>N;
	array<array<ll,300>,300> A;
	REP(i,N){
		REP(j,N){
			cin>>A[i][j];
			B[i][j] = 1;
		}
	}
	
	warshallFloyd(A,N);
	
	REP(i,N){
		REP(j,N){
			douro += A[i][j] * B[i][j];
		}
	}

	if(!isA){
		cout<<-1<<endl;
	}
	else{
		cout<<douro / 2 <<endl;
	}

	return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int mo = 1e9+7;
constexpr int  mod = mo;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<62;
int main(){
    int n;
    cin>>n;
    vector<int> A(3),B(3);
    for(auto & a : A) cin>>a;
    for(auto &b : B) cin >> b;
    vector<pair<int,int>> ba,ab;
    for(int i=0;i<3;++i){
        if(A[i] >= B[i]){
            ba.push_back({A[i],B[i]});
        }else {
            ab.push_back({A[i],B[i]});
        }
    }
    ll ret = 1ll*n;
    if(ab.size()){
        vector<ll> one(n+1);
        iota(one.begin(),one.end(),0ll);
        for(auto cur : ab){
            for(int i=0;i<=n;++i){
                if(i+cur.first <= n){
                    one[i+cur.first] = max(one[i+cur.first],one[i] + cur.second);
                }
            }
        }
        ret = max(ret,1ll*one[n]);
    }
    if(ba.size()){
        vector<ll> sec(ret+1);
        iota(sec.begin(),sec.end(),0ll);
        for(auto cur : ba){
            for(int i=0;i<=ret;++i){
                if(i+cur.second <= ret){
                    sec[i+cur.second] = max(sec[i+cur.second],sec[i] + cur.first);
                }
            }
        }
        ret = max(ret,1ll*sec[ret]);
    }
    cout << ret << endl;
    return 0;
}



Measured memory_bytes: 195584
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
#define intt long long

int main() {
	intt A, B, C; std::cin >> A >> B >> C;
	for (intt i = 1; i < 1000000; ++i) {
		intt a = A * i;;
		if (a % B == C) {
			std::cout << "YES" << std::endl;
			return 0;
		}
	}
	std::cout << "NO" << std::endl;

	return 0;
}

Measured memory_bytes: 3588
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,vector<int> > P;
 
static const double EPS = 1e-8;

static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

class UnionFindTree {
  int* _par;
  int* _rank;
public:
  UnionFindTree(int N){
    _par = new int[N];
    _rank = new int[N];
    for(int i = 0; i < N; i++){
      _par[i] = i;
      _rank[i] = 0;
    }
  }

  ~UnionFindTree(){
    delete[] _par;
    delete[] _rank;
  }

  int find(int u){
    if(_par[u] == u) return u;
    return find(_par[u]);
  }

  bool unite(int u,int v){
    u = find(u);
    v = find(v);
    if(u == v) return false;
    
    if(_rank[u] < _rank[v]){
      _par[u] = v;
    }
    else{
      _par[v] = u;
      if(_rank[u] == _rank[v]) _rank[u]++;
    }
    return true;
  }
};

class Edge {
public:
  int from;
  int to;
  int cost;
  Edge(int from,int to,int cost) 
    : from(from), to(to), cost(cost) {}
  bool operator<(const Edge& e) const {
    return cost < e.cost;
  }
  bool operator>(const Edge& e) const {
    return cost > e.cost;
  }
};

int main(){
  int num_of_springs;
  int num_of_districts;
  while(~scanf("%d %d",&num_of_springs,&num_of_districts)){
    if(num_of_springs == 0 && num_of_districts == 0) break;
    priority_queue<Edge,vector<Edge>, greater<Edge> > que;

    int spring_district_distance[51][51];
    for(int spring_i = 0; spring_i < num_of_springs; spring_i++){
      for(int district_i = 0; district_i < num_of_districts; district_i++){
        scanf("%d",&spring_district_distance[spring_i][district_i]);
        if(spring_district_distance[spring_i][district_i] == 0) continue;
        que.push(Edge(0,num_of_springs + district_i,spring_district_distance[spring_i][district_i]));
      }
    }

    int district_distance[51][51];
    for(int i = 0; i < num_of_districts - 1; i++){
      for(int j = 0; j < num_of_districts - i - 1; j++){
        scanf("%d",&district_distance[i][i+j+1]);
        district_distance[j+i+1][i] = district_distance[i][i+j+1];
        if(district_distance[j+i+1][i] == 0) continue;
        que.push(Edge(num_of_springs + i,num_of_springs + i + j + 1,district_distance[i][i+j+1]));
      }
    }

    int res = 0;
    UnionFindTree uft(101);
    while(!que.empty()){
      Edge e = que.top();
      que.pop();
      if(e.cost == 0) continue;
      if(uft.unite(e.from,e.to)){
        res += e.cost;
      }
    }

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

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

int main() {
  string s; cin >> s; int d=0;
  for(int i=0;i<s.size();i++) if(s.at(i) == 'R') d++;
  if(s.at(1) == 'S' && d != 0) cout << 1 << endl;
  else cout << d << endl;
  return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
int main(){
    int n,a[5000],top;
    while(1){
        scanf("%d",&n);
        if(n==0)return 0;
        scanf("%d",&a[0]);
top=a[0];
        for(int i=1;i<n;i++){
            scanf("%d",&a[i]);
            if(a[i-1]>0)a[i]+=a[i-1];
if(a[i]>top)top=a[i];
        }
        
        printf("%d\n",top);
    }
}

Measured memory_bytes: 2608
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
 
int main() {
    int n,k;
    cin >> n;
    map<int,int> a;

    for(int i = 0;i < n;i++){
        cin >> k;
        a[k-1]  = i+1;
    }
        for(int i = 0;i < n;i++){
            cout << a[i]<< " ";
        }
}
   


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

int main()
{
    int n,m,c;
    std::cin >> n >> m >> c;
    std::vector<int> b(m);
    std::vector<std::vector<int>> a(n,std::vector<int>(m));
    for(int i = 0; i < m; i++)std::cin >> b[i];
    for(int i = 0; i < n; i++){
        for(int j = 0;j < m; j++){
            std::cin >> a[i][j];
        }
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            sum += a[i][j]*b[j];
        }
        sum += c;
        if(sum > 0)cnt++;
    }
    std::cout << cnt << std::endl;
}

Measured memory_bytes: 256
def main():
    N = int(input())
 
    for h in range(1, 3501):
        for n in range(1, 3501):
            x = 4 * h * n - N * n - N * h
            if x <= 0: continue
            w, mod_ = divmod(N * h * n, x)
            if not mod_:
                print(h, n, w)
                return
 
main()

Measured memory_bytes: 3060
$n=<>;@A=glob<>;
$max = -1;

for(my $i=0;$i<$n;$i++){
    $mm = gcd(L($i),R($i+1));
    $max = $mm if ($mm > $max);
}
print "$max";

sub L{
    my$j=$_[0];
    return 0 if($j==0);
    return $l{$j} if($l{$j}!=undef);
    my $ret=gcd(L($j-1),$A[$j-1]);
    $l{$j}=$ret;
    return $ret;
}
sub R{
    my$j=$_[0];
    return 0 if($j==$n);
    return $r{$j} if($r{$j}!=undef);
    my $ret=gcd(R($j+1),$A[$j]);
    $r{$j}=$ret;
    return $ret;
}
sub gcd{
    my ($a, $b) = @_;
    ($a, $b) = ($b, $a) if ($a > $b);
    until ($a == 0){
        ($a, $b) = ($b%$a, $a)
    }
    return $b;
}

Measured memory_bytes: 117896
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

typedef long long ll;

const int N = 2e5 + 9;
const int INF = 1e9 + 239;

int a[N];
int b[N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	

	int n;
	cin >> n;
	int mx = -INF;
	int mn = INF;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		mx = max(mx, max(a[i], b[i]));
		mn = min(mn, min(a[i], b[i]));
	}
	ll ans = (ll)INF * INF;
	{
		int min_f = INF;
		int min_s = INF;
		int max_f = -INF;
		int max_s = -INF;
		for (int i = 0; i < n; i++) {
			int v = (a[i] > b[i]);
			if (v) swap(a[i], b[i]);
			// swap(a[i], b[i]);
			min_f = min(min_f, a[i]);
			min_s = min(min_s, b[i]);
			max_f = max(max_f, a[i]);
			max_s = max(max_s, b[i]);
		}
		ans = min(ans, ((ll)max_f - (ll)min_f) * (max_s - min_s));
	}
	{
		vector<int> ind(n);
		iota(ind.begin(), ind.end(), 0);
		sort(ind.begin(), ind.end(), [&](int i, int j) {
			return a[i] < a[j];
		});
		multiset<int> s;
		int c = INF;
		for (int i = 0; i < n; i++) {
			s.insert(a[i]);
		}
		c = *s.rbegin() - *s.begin();
		for (auto i : ind) {
			s.erase(s.find(a[i]));
			s.insert(b[i]);
			c = min(c, *s.rbegin() - *s.begin());
		}
		ans = min(ans, (ll)c * (mx - mn));
	}
	cout << ans << endl;
}

Measured memory_bytes: 13952
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits.h>
#include <climits>
#include <map>
#include <unordered_map>
#define _USE_MATH_DEFINES
#include <cmath>
#include <set>
#include <unordered_set>
#include <iterator>
#include <deque>
#include <assert.h>
#include <cstdlib>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
ull min(ull x, ull y){ if (x<y) return x; return y;}
ull max(ull x, ull y){ if (x<y) return y; return x;}
ll min(ll x, ll y){ if (x<y) return x; return y;}
ll max(ll x, ll y){ if (x<y) return y; return x;}
double min(double x, double y){ if (x<y) return x; return y;}
double max(double x, double y){ if (x<y) return y; return x;}
ull gcd(ull x, ull y){
    if (!x) return y;
    if (!y) return x;
    if (x>y) swap(x,y);
    return gcd(x, y%x);
}
ull inv(ull a, ull c){ // a,c are coprime and a<c
    if (a==1){
        return 1;
    }
    return ((c-(c/a))*inv(c%a,c))%c;
}

int a[200005] = {0}, ina[1000005] = {0}, ans = 0;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i){
        cin>>a[i];
        ina[a[i]]++;
    }
    if (ina[1]){
        if (ina[1]>1) cout<<0<<"\n";
        else cout<<1<<"\n";
        return 0;
    }
    for (int i = 0; i < n; ++i){
        if (ina[a[i]]>1){
            continue;
        }
        int ok = 1;
        for (int j = 2; j <= sqrt(a[i]); ++j){
            if (a[i]%j==0){
                if (ina[j]){
                    ok = 0;
                    break;
                }
                int k = a[i]/j;
                if (ina[k]){
                    ok = 0;
                    break;
                }
            }
        }
        ans += ok;
    }
    cout<<ans<<"\n";
    return 0;
}






Measured memory_bytes: 7688
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;

ll mod = 1e9+7;

int main(){
	ll n,k;
	cin >> n >> k;
	vector <ll> arr(n+1);
	for (int z=1;z<=n;z++){
		cin >> arr[z];
	}
	vector<vector<ll>> dp(n+1,vector<ll>(k+1,0));
	dp[0][0] = 1;
	ll count = 0;
	for (int z=1;z<=n;z++){
		ll sum = 0;
		count += arr[z];
		for (int x=0;x<=count && x <=k;x++){
			if (x > arr[z]) sum -= dp[z-1][x-arr[z]-1];
			sum += dp[z-1][x];
			if (sum < 0) sum += mod;
			dp[z][x] += sum;
			dp[z][x] %= mod;
			sum %= mod;
		}
	}
	// for (int z=0;z<=n;z++){
	// 	for (int x=0;x<=k;x++){
	// 		cout << dp[z][x] << " ";
	// 	} cout << endl;
	// }
	cout << dp[n][k] << endl;
	cin >> n;
}

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

#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define fi first
#define se second
#define pb push_back
#define int long long

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 2e5 + 10;
const int oo = 1e18;

int n, ans = oo;
int a[N], dp[N][5];

void upd(int &x, int y) { x = min(x, y); }

void solve()    {
    FOR(i, 1, n) FOR(j, 0, 4) dp[i][j] = oo;

    FOR(i, 1, n)    {
        // j = 0
        upd(dp[i][0], dp[i - 1][0] + a[i]);
        // j = 1
        upd(dp[i][1], dp[i][0]);
        if(a[i])    {
            upd(dp[i][1], dp[i - 1][1] + a[i] % 2);
            upd(dp[i][1], dp[i - 1][0] + a[i]);
        } else {
            upd(dp[i][1], dp[i - 1][1] + 2);
            upd(dp[i][1], dp[i - 1][0] + a[i]);
        }
        // j = 2
        upd(dp[i][2], dp[i][1]);
        if(a[i])    {
            upd(dp[i][2], dp[i - 1][1] + a[i] % 2);
            upd(dp[i][2], dp[i - 1][2] + (1 - a[i] % 2));
        } else {
            upd(dp[i][2], dp[i - 1][1] + 2);
            upd(dp[i][2], dp[i - 1][2] + 1);
        }
        // j = 3
        upd(dp[i][3], dp[i][2]);
        if(a[i]) {
            upd(dp[i][3], dp[i - 1][2] + (1 - a[i] % 2));
            upd(dp[i][3], dp[i - 1][3] + a[i] % 2);
        } else {
            upd(dp[i][3], dp[i - 1][2] + 1);
            upd(dp[i][3], dp[i - 1][3] + 2);
        }
        // j = 4
        upd(dp[i][4], dp[i][3]);
        if(a[i])    upd(dp[i][4], dp[i - 1][3] + a[i] % 2);
        else upd(dp[i][4], dp[i - 1][3] + 2);
        upd(dp[i][4], dp[i - 1][4] + a[i]);
    }
    //FOR(i, 1, 4) cout << dp[1][i] << ' '; cout << '\n';
    upd(ans, dp[n][4]);
}

signed main()  {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios_base::sync_with_stdio(false); cout.tie(0);

    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    solve();
    //FOR(i, 1, n / 2) swap(a[i], a[n - i + 1]);
    //solve();

    return cout << ans, 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define PII pair<ll,ll>
#define VI  vector<ll>
#define VB  vector<bool>
#define VVI vector<vector<ll>>
#define VS  vector<string>
#define VP  vector<PII>
#define lf(i,a,b) for(ll i=a;i<=b;i++)
#define lr(i,a,b) for(ll i=a;i>=b;i--)
#define lfl(i,v) for(ll i=0;i<v.size();i++)
#define lrl(i,v) for(ll i=(ll)(v.size())-1;i>=0;i--)
#define chk2(a,b) cout<<"check :  "<<a<<" "<<b<<endl
#define chk3(a,b,c) cout<<"check :  "<<a<<" "<<b<<" "<<c<<endl
#define chk4(a,b,c,d) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define chk5(a,b,c,d,e) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl
#define lb(v,k)  lower_bound(v.begin(),v.end(),k)-v.begin()
#define ub(v,k)  upper_bound(v.begin(),v.end(),k)-v.begin()
#define mod 1000000007
#define pb push_back
#define pf push_front
#define m_p make_pair
#define fi first
#define se second
#define sz size()
#define sort(v) sort(v.begin(),v.end())
ll dp[3001][3001];
void solve()
    {   string s;
        string t;
        cin>>s>>t;
        ll n=s.length();
        ll m=t.length();
        // cout<<s<<endl;
        // cout<<t<<endl;
        lf(i,0,n)
        {   lf(j,0,m)
            {   if(i==0 || j==0)
                {   dp[i][j]=0;
                }
                else if(s[i-1]==t[j-1])
                    dp[i][j]=1+dp[i-1][j-1];
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }    
        string s1;
        ll j=m,i=n;
        // lf(i,1,n)
        // {   cout<<endl;
        //     lf(j,1,m)
        //     {   cout<<dp[i][j]<<" ";
        //     }
        // }
        while(i>=1 && j>=1)
        {   if(s[i-1]==t[j-1])
            {   s1.pb(s[i-1]);
                i--;j--;
            }
            else if(dp[i-1][j]>=dp[i][j-1])
            {   i--;
            }
            else
                j--;
        }
        reverse(s1.begin(),s1.end());
        cout<<s1<<endl;
    }
int main()
{   
    solve();
}

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

int main()
{
  int N; cin >> N;
  vector<int> h(N);
  for (int i = 0; i < N; i++) cin >> h[i];
  h.push_back(0);

  vector<int> dp(N+2, 10e9);
  dp[0] = 0;

  for (int i = 0; i < N-1; i++)
  {
    dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
    dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));
  }

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
#define lint long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define POPCNT(n) (__builtin_popcount(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
template <typename T> inline T LB(vector<T>& v, T a) { return *lower_bound(ALL(v),a); }
template <typename T> inline int LBP(vector<T>& v, T a) { return lower_bound(ALL(v),a) - v.begin(); }
template <typename T> inline T UB(vector<T>& v, T a) { return *upper_bound(ALL(v),a); }
template <typename T> inline int UBP(vector<T>& v, T a) { return upper_bound(ALL(v),a) - v.begin(); }
template <typename T1, typename T2> ostream& operator<< (ostream& os, const pair<T1,T2>& p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream& operator>> (istream& is, pair<T1,T2>& p) { is >> p.first >> p.second; return is; }
template <typename T> ostream& operator<< (ostream& os, const vector<T>& v) { REP(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template <typename T> istream& operator>> (istream& is, vector<T>& v) { for(T& in : v) is >> in; return is; }
template <typename T = int> vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template <typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e,v); }
const lint MOD = 1000000007;
const lint INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;

int N;

void _main() {
    cin >> N;
    cout << 1.0 * ((N + 1) / 2) / N << endl;
}

signed main(signed argc, char **argv) {
    if (argc > 1) {
        if (strchr(argv[1], 'i'))
            freopen("input.txt", "r", stdin);
        if (strchr(argv[1], 'o'))
            freopen("output.txt", "w", stdout);
    }
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <queue>
#include <utility>
#include <climits>
#include <bitset>
#include <cmath>
#include <map>

#define MOD 1000000007

using namespace std;

typedef long long ll;

typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<vl> vvl;
typedef vector<vi> vvi;

typedef pair<ll, ll> pll;
typedef pair<int, int> pi;

typedef vector<pll> vpl;
typedef vector<pi> vpi;

typedef queue<ll> ql;
typedef queue<int> qi;

template <class T>
void printv(vector<T> vc)
{
    for (auto e : vc)
        cout << e << " ";
    cout << endl;
}

template <class T>
void printvv(vector<T> vvc)
{
    for (auto vc : vvc)
    {
        for (auto e : vc)
            cout << e << " ";
        cout << endl;
    }
}

template <class T>
void printvp(vector<pair<T, T> > vp)
{
    for (auto pT : vp)
        cout << pT.first << " " << pT.second << endl;
}

int main() {
    int n, y;
    cin >> n >> y;
    bool flag = false;
    for (int i = 0; i <= n; ++i) {
        if (flag) break;
        for (int j = 0; j <= n-i; ++j) {
            if (flag) break;
            int k = n-(i+j);
            if (i*10000 + j*5000 + k*1000 == y) {
                cout << i << " " << j << " " << k << endl;
                flag = true;
            }
        }
    }
    if (flag) return 0;
    cout << "-1 -1 -1" << endl;
    return 0;
}


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

int main() {
  int a;
  cin >> a;
  for(int i = 999; i > 0; i -= 111){
    if(i == a){
      cout << i << endl;
      break;
    }else if(a > i){
      cout << i + 111 << endl;
      break;
    }else if(a == 100){
      cout << 111 << endl;
      break;
    }
  }

}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, ll> P;
#define MOD (1000000007ll)

P art[555555];
ll s[555555],r[555555],l[555555];

int main(void){
	int n,i;
	ll a,b,ans=0ll,mn=INFLL;
	cin >> n;
	for(i=0; i<n; i++){
		cin >> a >> b;
		ans = max(ans,b);
		art[i] = P(a,b);
	}
	sort(art,art+n);
	s[0] = 0ll;
	for(i=0; i<n; i++){
		s[i+1] = s[i] + art[i].second;
	}
	for(i=0; i<n; i++){
		r[i+1] = s[i+1] - art[i].first;
		l[i] = s[i] - art[i].first;
	}
	for(i=0; i<n; i++){
		mn = min(l[i],mn);
		ans = max(ans,r[i+1]-mn);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 23508
#include <stdio.h>

#define SIZE 1000

int sum[SIZE][SIZE], n;
char map[SIZE][SIZE];

int in(int y, int x, int size)
{
     int d=size-1, t;

     t = sum[y+d][x+d];
     
     if(x>0) t -= sum[y+d][x-1];
     if(y>0) t -= sum[y-1][x+d];
     
     if(x>0 && y>0) t += sum[y-1][x-1];

     return t;
}

int main(void)
{
     int i, j, max=0, count;

     while(1){
	  max = 0;
	  
	  // input
	  scanf("%d%*c",&n); if(n==0) return 0;
	  for(i=0; i<n; i++) scanf("%s",map[i]);

	  // init sum
	  for(i=0; i<n; i++)
	       for(j=0; j<n; j++)
		    sum[i][j] = (map[i][j]=='*'? 1 : 0);

	  // add vertically
	  for(i=1; i<n; i++)
	       for(j=0; j<n; j++)
		    sum[i][j] += sum[i-1][j];
     
	  //add horizontally
	  for(i=1; i<n; i++)
	       for(j=0; j<n; j++)
		    sum[j][i] += sum[j][i-1];

	  // check
	  for(i=0; i<n; i++)
	       for(j=0; j<n; j++)
		    if(map[i][j]!='*'){
			 count=1;

			 while(i+count<n && j+count<n && !in(i,j,count+1))
			      count++;
		    
			 if(count>max) max=count;
		    }

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

Measured memory_bytes: 4220
/*					                                
										   *                             *
		                                    *             * * * * * * * *
		                                    *             *
		                                    *             *
		                                    *             *
		                                    *             *
		                                    *             *
		                                    *             *
		                                    * * * * * * * * * * * * * * *
		                                                  *             *
		                                                  *             *
		                                                  *             *
		                                                  *             *
		                                                  *             *
		                                                  *             *
		                                    * * * * * * * *             *
		                                   *                             *                             
*/
import java.util.*;
import java.io.*;
import java.lang.*;
class Main{
	public static long dp[][]=new long[102][100002];
	public static long knapsack(int wt[],int val[],int N,int W) {
		if(N<=0 || W<=0)
			return 0;
		else if(Main.dp[N-1][W]!=0)
			return Main.dp[N-1][W];
		else if(wt[N-1]<=W) {
			Main.dp[N-1][W]=Math.max(val[N-1]+Main.knapsack(wt, val, N-1, W-wt[N-1]),Main.knapsack(wt, val, N-1, W));
			return Main.dp[N-1][W];
		}
		else {
			Main.dp[N-1][W]=Main.knapsack(wt, val, N-1, W);
			return Main.dp[N-1][W];
		}
	}
	public static void main(String []args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int W=sc.nextInt();
		int wt[]=new int[N];
		int val[]=new int[N];
		for(int i=0;i<N;i++){
			wt[i]=sc.nextInt();
			val[i]=sc.nextInt();
		}
		long ans=Main.knapsack(wt, val, N, W);
		System.out.println(ans);
		sc.close();
	}
}

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

long long int memo[101][100001];

long long int solve(vector<int>& weights, vector<int>& vals, int w, int i) {
    if(i >= weights.size() || w == 0) return 0;

    if(memo[i][w] == -1)
    {
        long long int taken = 0;
        if(w-weights[i] >= 0) taken = solve(weights, vals, w-weights[i], i+1) + vals[i];
        long long int not_taken = solve(weights, vals, w, i+1);

        memo[i][w] = max(taken, not_taken);
    }

    return memo[i][w];
}


int main() {
    int n, w;
    cin >> n >> w;
    vector<int> weights(n, 0);
    vector<int> vals(n, 0);

    for(int i=0; i<101; ++i)
    {
        for(int j=0; j<100001; ++j)
            memo[i][j] = -1;
    }
    
    for(int i=0; i<n; ++i) cin >> weights[i] >> vals[i]; 

    cout << solve(weights, vals, w, 0) << endl;
    return 0;
}

Measured memory_bytes: 82516
a=int(input())
b=set([a])
count=1
if a%2==0:
    a=a/2
    count+=1
else:
    a=3*a+1
    count+=1
while a not in b:
    b.add(a)
    if a%2==0:
        a=a/2
        count+=1
    else:
        a=3*a+1
        count+=1
print(count)

Measured memory_bytes: 3060
#include<stdio.h>
#include<string.h>
	int main(){
		int h,i,r,n,m,j,k=0;
		char a[7],b[8][5];
		while(scanf("%s",a)!=EOF){
if(k!=0)
printf("\n");

			h=strlen(a);
			n=h-5;
			for(i=0;i<5;i++){
				if(i>=5-h){
					if(a[i+n]-'0'>=5){
						b[0][i]=' ';
						b[1][i]='*';
					}
					else
					{
						b[0][i]='*';
						b[1][i]=' ';
					}
					r=a[i+n]-'0';
					m=r%5;
					b[2][i]='=';
					for(j=3;j<m+3;j++)
						b[j][i]='*';
					b[j++][i]=' ';
					for(;j<8;j++)
						b[j][i]='*';
				}
				else
				{
					b[0][i]='*';
					b[1][i]=' ';
					b[2][i]='=';
					b[3][i]=' ';
					for(j=4;j<8;j++)
						b[j][i]='*';
				}
			}
			for(i=0;i<8;i++){
				for(j=0;j<5;j++)
				printf("%c",b[i][j]);
				printf("\n");
			}
k++;			
		}
		return 0;
}

Measured memory_bytes: 0