akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<deque>
#include<vector>
using namespace std;
int a[121212], indeg[121212], D[121212];
int max(int a, int b) { if (a < b)return b; return a; }
deque<int>Q;
int main() {
	int n, k, i, j, ans; scanf("%d%d", &n,&k);
	for (i = 1; i <= n; i++)scanf("%d", &a[i]);
	if (k == 1) {
		ans = 0;
		for (i = 1; i <= n; i++)if (a[i] != 1)ans++;
		printf("%d", ans);
		return 0;
	}
	ans = a[1] != 1;
	a[1] = 1;
	for (i = 1; i <= n; i++)indeg[a[i]]++;
	for (i = 1; i <= n; i++)if (indeg[i] == 0)Q.push_back(i);
	while (!Q.empty()) {
		int now = Q.front(); Q.pop_front();
		indeg[a[now]]--;
		if (D[now] == k - 1) ans+=(a[now]!=1);
		else D[a[now]] = max(D[a[now]], D[now] + 1);
		if (indeg[a[now]] == 0)Q.push_back(a[now]);
		a[now] = 0;
	}
	for (i = 2; i <= n; i++) {
		int now = i;
		vector<int>L;
		while (a[now]) {
			L.push_back(D[now]);
			int temp = now;
			now = a[now];
			a[temp] = 0;
		}
		int mx = 0, mxw = 0;
		for (j = 0; j < L.size(); j++) {
			if (L[j] > mx)L[j] = mx, mxw = j;
		}
		now = 0;
		for (j = 0,k = mxw; j < L.size(); j++, k++) {
			now++;
			if (now == k) ans++, now = 0;
			now = max(now, L[j]);
		}
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 1792
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class Main {
	static Map<Character, Integer> ROMAN_NUMERALS = new HashMap<Character, Integer>();;

	public static void main(String[] args) {

		Scanner sc = null;
		try {
			sc = new Scanner(System.in);

			if (ROMAN_NUMERALS.isEmpty()) {
				createRomanNumerals(ROMAN_NUMERALS);
			}

			while (sc.hasNextLine()) {
				char[] roman = sc.nextLine().toCharArray();
				int[] arabia = new int[roman.length];
				for (int i = 0; i < roman.length; i++) {
					arabia[i] = ROMAN_NUMERALS.get(roman[i]);
				}

				int sum = 0;
				for (int i = 1; i < arabia.length; i++) {
					if (arabia[i] > arabia[i - 1]) {
						sum -= arabia[i - 1];
					} else {
						sum += arabia[i - 1];
					}
				}
				sum += arabia[arabia.length - 1];
				System.out.println(sum);
			}

		} finally {
			sc.close();
		}
	}

	public static void createRomanNumerals(Map<Character, Integer> map) {
		map.put('I', 1);
		map.put('V', 5);
		map.put('X', 10);
		map.put('L', 50);
		map.put('C', 100);
		map.put('D', 500);
		map.put('M', 1000);
	}
}

Measured memory_bytes: 26000
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	string s;
	int n;
	cin >> n;
	cin >> s;
	int x = 0;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		if (s[i] == 'I'){
			x++;
		}
		else{
			x--;
		}
		ans = max(x,ans);
	}
	cout << ans << endl;
	return 0;
}

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

const int maxn = 1e5 + 1;
int n, h[maxn];

void Input()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
}

void Solve()
{
    h[1]--;
    for (int i = 2; i <= n; i++)
    if (h[i] > h[i - 1]) h[i]--;
    else if (h[i] < h[i - 1])
    {
        cout << "No";
        return;
    }
    cout << "Yes";
}

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

    //freopen("test.inp" , "r" , stdin);
    //freopen("test.out" , "w" , stdout);

    Input();
    Solve();
}

Measured memory_bytes: 640
//Don't give up too easy bhai
#pragma GCC optimize("O3")
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define forall(i,a,n) for(ll i=a;i<n;i++)
#define pb push_back
#define fs first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define minv(a) *min_element(all(a))
#define maxv(a) *max_element(all(a))
#define vll vector<ll>
#define vld vector<ld>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mod 1000000007
#define br cout<<"\n"
#define whatis(x) cerr << ">"<<#x << " ==> " << x << endl;
#define inputv(a) forall(i,0,a.size()) cin>>a[i]
#define outputv(a) for(auto i:a) cout<<i<<" ";br;
#define T ll __t;cin>>__t;while(__t--)

void solve()
{
    
}

int main()
{
    fast;

    ll n;cin>>n;
    vll a(n);inputv(a);
    ll x = 0;

    forall(i,0,n) x = x^a[i];
    forall(i,0,n) a[i] = x^a[i];
    outputv(a);

    return 0;
}

Measured memory_bytes: 4764
#include<bits/stdc++.h>
using namespace std;
int wqpfs(int x)
{
    for(int i=1;i*i<=x;i++)
      if(i*i==x)return 1;
    return 0;
}
long long a,b,a1,z,m;
int main()
{
    cin>>a>>b;a1=b;
    while(a1>0)
    {
        a1/=10;
        z++;
    }
    m=a*pow(10,z)+b;
    if(wqpfs(m))cout<<"Yes";else
      cout<<"No";
    return 0;
}

Measured memory_bytes: 256
n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)


cola = [(0, -1)]
qind = 0
while qind < len(cola):
    u, pu = cola[qind]
    qind += 1
    for v in tree[u]:
        if v != pu:
            cola.append((v, u))

dp = [1] * n
for i in range(n - 1, -1, -1):
    u, pu = cola[i]
    for v in tree[u]:
        if v != pu:
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

resp = [0] * n
pval = [1] * n
for j in range(n):
    u, pu = cola[j]
    resp[u] = (dp[u] * pval[u]) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval[u]
    for i in range(len(chlds)):
        v = chlds[i]
        pval[v] = (1 + pref * cumulr[i]) % MOD
        pref *= (dp[v] + 1)
        pref %= MOD

for i in range(n):
    print(resp[i])


Measured memory_bytes: 63644
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 1LL << 61;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222






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


  cin >> n;
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  cin >> s;
  ok = true;
  s = "a" + s + "a";
  FOR(i, a, c) if (s[i] == '#' &&s[i + 1] == '#') ok = false;
  FOR(i, b, d) if (s[i] == '#' &&s[i + 1] == '#') ok = false;
  if (c > d) {
    bool x = false;
    FOR(i, b, d + 1) {
      if (s[i] == '#') continue;
      if (s[i - 1] == '.' &&s[i + 1] == '.') x = true;
    }
    if (!x) ok = false;
  }

  if (ok) cout << "Yes" << endl;
  else cout << "No" << endl;



  return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll H; cin >> H;
    ll cnt = 1;
    ll ans = 0;
    while (H > 0) {
        ans += cnt;
        cnt *= 2;
        H /= 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main {
 public static void main(String[] args){
  Scanner s = new Scanner(System.in);
  int a = s.nextInt();
  int b = s.nextInt();
  int d = a / b;
  int r = a % b;
  double f = (double)a / (double)b;
  System.out.printf("%d %d %.5f", d, r, f);
 }
}

Measured memory_bytes: 17292
n = int(input())
p = list(map(int, input().split()))
ans = 0

for i in range(n - 1):
    if p[i] == i + 1:
        p[i], p[i + 1] = p[i + 1], p[i]
        ans += 1
if p[-1] == n: ans += 1

print(ans)

Measured memory_bytes: 14008
package main

import "fmt"

func main() {
	var N int
	fmt.Scanf("%d", &N)

	A := make([]int64, N+1)
	B := make([]int64, N)

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

	var ans int64
	for i, b := range B {
		for j := 0; j < 2; j++ {
			t := min(b, A[i+j])
			ans += t
			b -= t
			A[i+j] -= t
		}
	}
	fmt.Println(ans)
}

func min(x, y int64) int64 {
	if x < y {
		return x
	}
	return y
}

Measured memory_bytes: 5504
#include<stdio.h>
int main(void){
	int a,b,c,i,count=0;
	
	scanf("%d %d %d",&a,&b,&c);
	
	for(i=a;i<=b;i++){
		if(c%i==0){
			count++;
		}
	}
	printf("%d\n",count);
	return 0;
}

Measured memory_bytes: 596
n = int(input())
pw = input()
l = [pw]
flag = 0
for i in range(1, n):
    w = input()
    if w in l:
        flag = 1
    if pw[-1] != w[0]:
        flag = 1
    l.append(w)
    pw = w
if flag == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());
        var L = new List<long>();
        var input = Console.ReadLine().Split(" ");

        for (int i = 0; i < N; i++)
        {
            L.Add(long.Parse(input[i]));
        }

        var count = 0;
        for(int i = 0; i < N; i++)
        {
            for(int j = i + 1; j < N; j++)
            {
                for(int k = j + 1; k < N; k++)
                {
                    var side = new List<long>();
                    side.Add(L[i]);
                    side.Add(L[j]);
                    side.Add(L[k]);
                    side.Sort();

                    if (side.Distinct().Count() != 3) continue;
                    if ((side[0] + side[1]) > side[2]
                        && (side[1] + side[2]) > side[0]
                        && (side[2] + side[0]) > side[1]) count++;
                }
            }
        }

        Console.WriteLine(count);

    }
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, W, K;
  cin >> H >> W >> K;
  int cnt = 1;
  vector<vector<int>> cake(H, vector<int>(W, 0));
  vector<string> S(H);
  for (int i = 0; i < H; i++) {
    cin >> S[i];
    for (int j = 0; j < W; j++) {
      if (S[i][j] == '#') {
        cake[i][j] = cnt++;
      }
    }
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (j - 1 >= 0 && cake[i][j] == 0) {
        cake[i][j] = cake[i][j - 1];
      }
    }
    for (int j = W - 1; j >= 0; j--) {
      if (j + 1 < W && cake[i][j] == 0) {
        cake[i][j] = cake[i][j + 1];
      }
    }
  }
  for (int j = 0; j < W; j++) {
    for (int i = 0; i < H; i++) {
      if (i - 1 >= 0 && cake[i][j] == 0) {
        cake[i][j] = cake[i - 1][j];
      }
    }
    for (int i = H - 1; i >= 0; i--) {
      if (i + 1 < H && cake[i][j] == 0) {
        cake[i][j] = cake[i + 1][j];
      }
    }
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cout << cake[i][j] << (j != W - 1 ? ' ' : '\n');
    }
  }
  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main() 
{
	ios::sync_with_stdio(false);
	int max = 0,sum=0;
	int n,a;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		if (a >= max)
		{
			sum++;
			max = a;
		}
	}
	cout << sum<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int a = 0;
        int z = s.length() - 1;
        while (a < z) {
            if (s.charAt(a) == 'A' && s.charAt(z) == 'Z') {
                break;
            }
            if (s.charAt(a) != 'A') a++;
            if (s.charAt(z) != 'Z') z--;
        }
        System.out.println(z - a + 1);
    }

}


Measured memory_bytes: 40248
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N,A,B;
    cin>>N>>A>>B;
    
    int a = min(A,B);
    int b = max(0,(A+B)-N);
    
    cout2(a,b)
}

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

using namespace std;

const int MAXN = (int) 2E5;
const int MAXM = (int) 1E5;
int p[MAXN + 1];
int parent[MAXN + 1];
int s[MAXN + 1];
int loc[MAXN + 1];

int getRoot(int x)
{
    if (parent[x] != x)
        parent[x] = getRoot(parent[x]);
    return parent[x];
}

void mge(int a, int b)
{
    int r1 = getRoot(a);
    int r2 = getRoot(b);
    if (r1 == r2)
        return;
    if (s[r1] > s[r2])
        swap(r1, r2);
    parent[r1] = r2;
    s[r2] += s[r1];
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        s[i] = 1;
        cin >> p[i];
        loc[p[i]] = i;
    }
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        mge(x, y);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (getRoot(loc[i]) == getRoot(i))
            ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
object Main extends App {
  import scala.io.StdIn._


  val Array(h, w) = readLine.trim.split(' ').map(_.toInt)
  val a = readLine.trim.split(' ').map(_.toInt).sorted
  val b = readLine.trim.split(' ').map(_.toInt).sorted

  println(
    b.map(n ⇒ (h - upperBound(a, n)) * n).sum + a.map(n ⇒ (w - lowerBound(b, n)) * n).sum
  )

  def upperBound(array: Array[Int], target: Int): Long = {
    var left = 0
    var right = array.length
    while(left < right){
      val mid = (left + right) / 2
      if (array(mid) <= target){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }
  def lowerBound(array: Array[Int], target: Int): Long = {
    var left = 0
    var right = array.length
    while(left < right){
      val mid = (left + right) / 2
      if (array(mid) < target){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline
    def let[A](func: T ⇒ A): A = func(value)
  }
}


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

//最大値の添字
long long maxat(vector<long long> a) {
  long long m = a.at(0);
  long long memo = 0;
  for (long long i = 1; i < a.size(); i++) {
    if (m < a.at(i)) {
      m = a.at(i);
      memo = i;
    }
  }
  return memo;
}
long long cnt = 0;
void saveL(long long i, vector<long long> &a, vector<long long> &b) {
  if (a.at(i) >= b.at(i)) {
    cnt += b.at(i);
    a.at(i) -= b.at(i);
    b.at(i) = 0;
  }
  else if (a.at(i) + a.at(i + 1) >= b.at(i)) {
    cnt += b.at(i);
    b.at(i) -= a.at(i);
    a.at(i) = 0;
    a.at(i + 1) -= b.at(i);
    b.at(i) = 0;
  }
  else {
    cnt += a.at(i) + a.at(i + 1);
    b.at(i) -= a.at(i) + a.at(i + 1);
    a.at(i) = 0;
    a.at(i + 1) = 0;
  }
}
void saveR(long long i, vector<long long> &a, vector<long long> &b) {
  if (a.at(i + 1) >= b.at(i)) {
    cnt += b.at(i);
    a.at(i + 1) -= b.at(i);
    b.at(i) = 0;
  }
  else if (a.at(i) + a.at(i + 1) >= b.at(i)) {
    cnt += b.at(i);
    b.at(i) -= a.at(i + 1);
    a.at(i + 1) = 0;
    a.at(i) -= b.at(i);
    b.at(i) = 0;
  }
  else {
    cnt += a.at(i) + a.at(i + 1);
    b.at(i) -= a.at(i) + a.at(i + 1);
    a.at(i) = 0;
    a.at(i + 1) = 0;
  }
}

int main() {
  long long n;
  cin >> n;
  vector<long long> a(n + 1), b(n);
  for (long long i = 0; i < n + 1; i++) cin >> a.at(i);
  for (long long i = 0; i < n; i++) cin >> b.at(i);
  for (long long i = 0; i < n / 2; i++) saveL(i, a, b);
  for (long long i = 0; i < n / 2; i++) saveR(n - 1 - i, a, b);
  if (b.at(n / 2) <= a.at(n / 2) + a.at(n / 2 + 1))
    cnt += b.at(n / 2);
  else cnt += a.at(n / 2) + a.at(n / 2 + 1);
  cout << cnt << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  char s;int ans = 0,now = 0;
  while(cin >> s){
    if(s=='A' || s=='C' || s=='G' || s=='T') now++;
    else now = 0;
    ans = max(now,ans);
  }
  cout << ans << endl;
}

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

int main()
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  
  int64_t D,T,S;
  std::cin>>D>>T>>S;
  
  std::string result;
  
  if(D<=T*S)
  {
    result="Yes";
  }
  else
  {
    result="No";
  }
  
  std::cout<<result<<std::endl;
  
  return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
const int INF = 1e9;
const int EPS = 1e-9; 

int main() {
  int N;
  cin >> N;
  vector<int> H(N);
  for (int i = 0; i < N; ++i) cin >> H.at(i);
  
  bool isJudge = true;
  for (int i = N-2; i >= 0; --i) {
    if (H.at(i) > H.at(i+1)) {
      H.at(i)--; 
    }
    if (H.at(i) > H.at(i+1)) {
      isJudge = false;
      break;
    }
  }
  (isJudge)? cout << "Yes" << endl : cout << "No" << endl;
}

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

int main(){

    int n,m;
    double sum=0;
    cin>>n>>m;
    vector<int> a(n);

    for(int i=0;i<n;i++){

        cin>>a.at(i);
        sum+=a.at(i);

    }

    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());

    if(a.at(m-1)>=sum/4/m) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;






    return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<60);
const ld pi=acosl((ld)1);
const ll mod = 1000000007;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endN "\n"

bool solve(){
  ll x;cin>>x;
  ll i=0;
  for(;i*(i+1)/2<x;i++);
  cout<<i<<endl;
  return false;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout<<fixed;
	cout<<setprecision(30);
  // ll Q;cin>>Q;
	// while(Q--)solve();
  solve();
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	int p[3];
	cin >> p[0] >> p[1] >> p[2];

	sort(p, p + 3);

	cout << p[0] + p[1] << endl;

	return 0;
}

Measured memory_bytes: 256
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
//過半数：N/2.0で判定
//優先度付きキュー
//priority_queue<
//ll,
//vector<ll>
//> q;
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
#define PI 3.14159265358979323846264338327950L
using namespace std;


//割るやつ
const ll MOD = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1));
}

//Nのd桁目の数
ll dignum(ll N, ll d) {
	ll x = pow(10, d);
	N %= x;
	ll y = pow(10, d - 1);
	N /= y;
	return N;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

ll RS(ll N, ll P, ll M) {
	if (P == 0) return 1;
	if (P % 2 == 0) {
		ll t = RS(N, P / 2, M);
		return t * t % M;
	}
	return N * RS(N, P - 1, M);
}

int main() {
	string S, T;cin >> S >> T;
	ll cnt = 0;
	for(int i = 0; i < S.size();i++){
		if(S[i] != T[i]){
			cnt++;
		}
	}
	cout << cnt << endl;
}	

Measured memory_bytes: 11736
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{

   ll n,x,sum=0,mn;
   vector<int>v;
   cin>>n;
   n*=2;
   while(n--)
   {
       cin>>x;
       v.push_back(x);
   }
   sort(v.begin(),v.end());
   for(int i=0;i<v.size()-1;i++)
   {
     sum+=min(v[i],v[i++]);

   }
    cout<<sum;
}


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

using namespace std;

int N;
string A, B;

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

    for (int i = N; i; -- i)
        if (A.substr(N - i, i) == B.substr(0, i)) {
            cout << 2 * N - i << '\n';
            return 0;
        }

    cout << 2 * N << '\n';
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Stream;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] l = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    br.close();

    int ans = 0;
    Arrays.sort(l);
    int len = l.length;
    for(int i = 0; i < len; i++){
      for(int j = i + 1; j < len; j++){
        if(l[i] == l[j]) {
          continue;
        }
        for(int k = j + 1; k < len; k++){
          if(l[j] == l[k]) {
            continue;
          }
          if(l[k] < l[i] + l[j]){
            ans++;
          }
        }
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 34512
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int n;
ll a[100000];
ll dp[3001][30001];
ll used[3001][3001];
ll dfs(int l, int r){
    if(l>r)return 0;
    if(used[l][r]) return dp[l][r];
    used[l][r]=true;
    int count=n-(r-l+1);//取った回数の合計
    ll res;
    if(count%2==0){//自分のターン
        res=-10000000000000;
        res=max(res,dfs(l+1,r)+a[l]);
        res=max(res,dfs(l,r-1)+a[r]);
    }
    else{//相手のターン
        res=100000000000000;
        res=min(res,dfs(l+1,r)-a[l]);
        res=min(res,dfs(l,r-1)-a[r]);
    }
    dp[l][r]=res;
    return dp[l][r];
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    memset(dp,0,sizeof dp);
    memset(used,false,sizeof used);
    cout << dfs(0,n-1) << "\n";
}



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

using namespace std;
#define REP(i, n)  for(int i=0;i<(int)(n);++i)
#define FOR(i, b, n)  for(int i=b;i<(n);++i)
#define ALL(c) (c).begin(),(c).end()
#define PB(c) push_back(c)
#define SS size()
#define ST first
#define ND second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
template<typename T> void sout(T &w) {
  for (auto x : w) cout << x << ", ";
  cout << endl;
}

int main() {
  ios::sync_with_stdio(0);
  int a, b; cin >> a >> b;
  cout << max(a+b, max(a-b, a*b)) << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define INF (1<<21)
#define WHITE 1
#define BLACK 2
#define GRAY 3
#define neg -1
using namespace std;

int n;
int m[100][100];
vector<int> g;
vector<int> color;

void di(){
  int u, mincost;

  for(int i = 0; i < n; i++){
    g[i] = INF;
    color[i] = WHITE;
  }

  g[0] = 0;
  color[0] = GRAY;

  while(1){
    mincost = INF;
    u = -1;

    for(int i = 0; i < n; i++){
      if(mincost > g[i] && color[i] != BLACK){
	u = i;
	mincost = g[i];
      }
    }

    if(u == neg) break;

    color[u] = BLACK;

    for(int i = 0; i < n; i++){
      if(color[i] != BLACK && m[u][i] != INF){
	if(g[i] > (g[u] + m[u][i])){
	  g[i] = g[u] + m[u][i];
	  color[i] = GRAY;
	}
      }
    }
  }

  for(int i = 0; i < n; i++){
    cout << i << " " << (g[i] == INF ? neg:g[i]) << endl;

  }
}

int main()
{
  cin >> n;
  g.resize(n);
  color.resize(n);

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      m[i][j] = INF;
    }
  }

  int k, c, u, v;

  for(int i = 0; i < n; i++){
    cin >> u >> k;

    for(int j = 0; j < k; j++){
      cin >> v >> c;
      m[u][v] = c;
    }
  }

  di();

  return 0;

}



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

using namespace std;

#define USE_IOSTREAM \
{\
	ios::sync_with_stdio(false);\
	cin.tie(0);\
	cout.tie(0);\
}

#define pii pair<int, int>
#define mp make_pair

typedef long long ll;

const int N = 1e5 + 100;
const ll MOD = 1e9 + 7;

int a[N];
int cnt[N];

int main()
{
	USE_IOSTREAM;
	int n, i;
	cin >> n;
	for (i = 1; i <= n; i++)
	{
		cin >> a[i];
		cnt[a[i]]++;
	}
	
	
	bool ok = true;
	if (n % 2 && cnt[0] != 1)
	{
		ok = false;
	}
	
	int start = n % 2 ? 2: 1;
	for (i = start; i <= n - 1; i += 2)
	{
		if (cnt[i] != 2)
		{
			ok = false;
		}
	}
	
	if (!ok)
	{
		cout << 0 << endl;
		return 0;
	}
	
	ll ans = 1;
	for (i = 0; i < n / 2; i++)
	{
		ans = (ans * 2) % MOD;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
while True:
    T = list(map(int,input().split()))
    if T[0]==0 and T[1]==0:
        break

    for i in range(T[0]):
        for j in range(T[1]):
            if (i+j)%2 == 1:
                print(".",end="")
            else:
                print("#",end="")
        print()

    print()



Measured memory_bytes: 7008
/**
 * Created by hiramekun at 19:13 on 2019-10-22.
 */

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
class WarshallFloyd {
public:
    int V; // 頂点数
    vector<vector<ll> > d; // 最短頂点間距離
    WarshallFloyd() = default;

    WarshallFloyd(int v) {
        V = v;
        d.resize(v);
        rep(i, v) d[i].resize(v);
        rep(i, v)rep(j, v)d[i][j] = ll_inf;
        rep(i, v) d[i][i] = 0;
    };

    void add(int u, int v, int cost) {
        d[u][v] = cost;
    }

    // v: 頂点数, d: 頂点間距離
    void solve() {
        rep(k, V)rep(i, V)rep(j, V) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

    vvl solve2(ll l) {
        vvl d2(V, vl(V, ll_inf));
        rep(i, V)rep(j, V) if (d[i][j] <= l) d2[i][j] = 1;
        rep(k, V)rep(i, V)rep(j, V) d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);
        return d2;
    }
};

void solve() {
    ll n, m, l;
    cin >> n >> m >> l;
    WarshallFloyd warshallFloyd(n);
    rep(i, m) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        warshallFloyd.add(a, b, c);
        warshallFloyd.add(b, a, c);
    }
    warshallFloyd.solve();
    vvl ans = warshallFloyd.solve2(l);
    ll q;
    cin >> q;
    rep(i, q) {
        ll s, t;
        cin >> s >> t;
        s--, t--;
        if (ans[s][t] == ll_inf) cout << -1 << '\n';
        else cout << ans[s][t] - 1 << '\n';
    }
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 1920
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val k = sc.nextLong()

    var ans = 0L
    for(a in 1..k) {
        for(b in 1..k) {
            for(c in 1..k){
                ans+= gcd(a, gcd(b,c))

            }
        }
    }

    println(ans)

}

fun gcd(a:Long, b:Long): Long{
    if(a < b) return gcd(b, a)
    if(b == 0L) return a
    return gcd(b, a % b)
}

Measured memory_bytes: 36884
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int n;
  string s;
  cin >> n;
  cin >> s;
  vector<int> a(n + 1, 0), b(n + 1, 0);
  for (int i = 0; i < n; i++) {
    if (s[i] == '#') {
      a[i + 1] = a[i] + 1;
      b[i + 1] = b[i];
    }
    else {
      a[i + 1] = a[i];
      b[i + 1] = b[i] + 1;
    }
  }
  int ans = 999999;
  for (int i = 0; i <= n; i++) {
    ans = min(ans, a[i] - a[0] + b[n] - b[i]);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2180
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String S=sc.next();
        String T=sc.next();

        int steps=0;
        for(int i=0;i<S.length();i++){
            if(S.charAt(i)!=T.charAt(i)){
                steps++;
            }
        }
        System.out.println(steps);
    }
}


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

using namespace std;

long tri[100005]={0};
int main(){
    long n, k;
    cin >> n >> k;
    long index=0;
    long count=1;
    char c1, c2, first;
    cin >> c1;
    if( c1=='0'){
        tri[index] = 0;
        index++;
    }
    for( long i=1; i<n; i++){
        cin >> c2;
        if( c1 != c2 ){
            tri[index] = count;
            count = 1;
            index++;
            c1 = c2;
        }else{
            count++;
        }
    }
    tri[index] = count;
    index++;
    if( c1=='0'){
        tri[index] = 0;
        index++;
    }
    /*
    for(int i=0; i<index; i++){
        cerr << tri[i] << ", " ;
    }
        */
    //cerr << endl;
    long result = 0;
    long pre;
    for(long i=0; i<2*k+1; i++){
        if( i>index) break;
        result += tri[i];
    }
    pre = result;
    for(long i=2;i<index;i+=2){
        long st=i, ed=i+2*k+1;
        long tmp=pre;
        tmp -= tri[i-1]+tri[i-2];
        if( ed >  index ) break;
        else{
            tmp += tri[ed-1]+tri[ed-2];
            if( tmp > result ) result = tmp;
        }
        //cout << tmp << ", " <<endl;
        pre = tmp;
    }
    cout << result << endl;
    return 0;
}



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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<int> A(3);
  for (auto &it : A)
    cin >> it;
  int ans = 1000;
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      if (i == j)
        continue;
      for (int k = 0; k < 3; k++)
      {
        if (k == i or k == j)
          continue;
        int tmp = abs(A[j] - A[i]) + abs(A[k] - A[j]);
        ans = min(ans, tmp);
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);i++)
#define urep(i,a,n) for(ll i = (a);i>=(n);i--)
#define all(x) (x).begin(),(x).end()
#define INF 1e9
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N, M, Q, H, W, D, L, R, K, X;
ll A;
ll B;
ll ans;
string S;
bool Prime[100001];
ll anstable[100001];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
int main() {
	cin >> S;
	ans = S.size();
	char oldnum = S[0];
	rep(i, 1, S.size()) {
		if (S[i] != oldnum) {
			ll num = S.size();
			ans = min(ans, max(i, num - i));
		}
		oldnum = S[i];
	}
	
	cout << ans << endl;
	cin >> ans;
	return 0;
}

Measured memory_bytes: 512
import sys
input = sys.stdin.readline
from collections import *
from heapq import *

N, M = map(int, input().split())
d = defaultdict(list)

for _ in range(N):
    A, B = map(int, input().split())
    d[A].append(B)

pq = []
ans = 0

for i in range(M, -1, -1):
    for v in d[M-i]:
        heappush(pq, -v)
    
    if len(pq)>0:
        ans += -heappop(pq)

print(ans)

Measured memory_bytes: 76764
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  float N; cin >> N;
  int odd = 0;
  for(int i=1; i<=N; ++i) {
    if(i%2) ++odd;
  }
  cout << odd/N << endl;
}

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

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
  string n;
	cin >> n;
	vector<char> r(3),l(3);
	r = {'R','U','D'};
	l = {'L','U','D'};
	int c = 0;
	REP(i,n.length()) if(i%2==0){
		REP(j,3) if(n[i]==r[j]) c+=1;
		}else REP(j,3) if(n[i]==l[j]) c+=1;
	
	if(c == n.length()) cout<< "Yes" << endl;
	else cout << "No" << endl;

}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main(){
  long K,A,B;
  long ans = 0;
  long anskari = 0;
  cin >>K>>A>>B;
  if(B<A+2){
    ans = 1+K;
  }
  else{
    if((K-A+1)%2 == 0){
      anskari = (((K-(A-1))/2)*(B-A))+A;
    }
    else{
      anskari = ((((K-(A-1))/2))*(B-A))+1+A;
    }
    ans = max(1+K,anskari);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

int main(int argc, char const *argv[])
{
  using namespace std;
  int n;
  cin >> n;
  int * a = new int[n];
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
  }
  int count = 0;
  for (int i = 0; i < n; i++)
  {
    int minj = i;
    for (int j = i; j < n; j++)
    {
      if (a[j] < a[minj])
        minj = j;
    }
    if (a[i] > a[minj])
    {
      swap(a[i], a[minj]);
      count++;
    }
  }
  for (int i = 0; i < n - 1; i++)
  {
    cout << a[i] << ' ';
  }
  cout << a[n - 1] << endl;
  cout << count << endl;
  return 0;
}



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

int main(){
	int curr = 0, ans = 0;
	string s;
	cin >> s;
	curr = 0;
	for(auto i:s){
		if(i == 'A' || i == 'T' || i == 'C' || i =='G')
			curr ++;
		else
			curr = 0;
		ans = max(ans, curr);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
int main() {
  long long q,h,s,d,n;
  cin >> q >> h >> s >> d >> n;
  h=min(h,2*q);
  s=min(s,2*h);
  d=min(d,2*s);
  cout << n/2*d+n%2*s << endl;
}

Measured memory_bytes: 256
//g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g PROGRAM -o OUTPUT -DLOCAL -lasan -lubsan
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define alli(a, n, k) (a + k), (a + n + k)
#define FP(i, a, b, k) for (__typeof(a) i = a; i < b; i += k)
#define FS(i, a, b, k) for (__typeof(a) i = a; i > b; i -= k)
#define IT(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template <class T>
inline T gcd(T x, T y)
{
    if (!y)
        return x;
    return gcd(y, x % y);
}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector<pair<int, int>> VPII;
typedef vector<pair<int, PII>> VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;


inline ll modulo(ll a, ll m)
{
    return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
    assert(__gcd(a, m) == 1);
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
    if (y == 0)
        return 1LL;
    else if (y == 1)
        return x;
    else
    {
        ll ans = modPow(x, y / 2, m) % m;
        if (y & 1)
        {
            return (((ans * ans) % m) * x) % m;
        }
        else
        {
            return (ans * ans) % m;
        }
    }
}

vector<string> split(char d,string s)
{
    stringstream ss(s);
    string t;
    vector<string> words;
    while(getline(ss,t,d))
    {
        words.pb(t);
    }

    return words;
}

int main(int argc, char *argv[])
{
#ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
#endif
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    if(s[2]==s[3] && s[4]==s[5])
        cout << "Yes";
    else
        cout << "No";

#ifdef LOCAL
    auto end = chrono::high_resolution_clock::now();
    double time_taken =
        chrono::duration_cast<chrono::nanoseconds>(end - start).count();

    time_taken *= 1e-9;

    cerr << "\nTime taken by program is : " << fixed
         << time_taken << setprecision(9);
    cerr << " sec" << endl;
#endif
    return 0;
}


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

int main(void){
	int n;
	int p,max=0,total=0;
	
	cin>>n;
	while(n--){
		cin>>p;
		if(max<p)max=p;
		total+=p;
	}
	cout<<total-max/2<<endl;
	
	return 0;
}


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

using namespace std;

const int H = 10000 + 10;
const int N = 1000 + 10;
const int inf = 1000000000;

int f[H];
int a[N], b[N];

int main()
{
	int h, n, i, j;
	cin>>h>>n;
	for (i=1; i<=n; i++) cin>>a[i]>>b[i];
	for (i=1; i<=h; i++)
	{
		f[i] = inf;
		for (j=1; j<=n; j++)
			if (i >= a[j]) f[i] = min(f[i], f[i-a[j]] + b[j]);
			else f[i] = min(f[i], b[j]);
	}
	cout<<f[h]<<endl;
	return 0;
}

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

int main(void){
    int N ,A ,B;
    cin >> N >> A >> B;
    int ans;
    ans = min(A, B);
    cout << ans << " ";
    if (A + B > N) cout << A + B - N << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define space " "
typedef long long LL;

const int maxn = 1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const double pi = acos(-1.0);

int B[maxn];

int main()
{
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N - 1; i++) scanf("%d", B+i);
	int res = 0;
	for (int i = 0; i < N; i++) {
		if (i == 0) res += B[i];
		else if (i == N-1) res += B[N-2];
		else res += min(B[i], B[i-1]);
	}
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 256
import sys
def input():
	return sys.stdin.readline()[:-1]

w, h = map(int, input().split())
r = []
for _ in range(w):
	r.append([int(input()), 0])
for _ in range(h):
	r.append([int(input()), 1])
r.sort(key=lambda x: x[0], reverse=True)
p, q = h+1, w+1
ans, num = 0, 0
while num < (w+1)*(h+1)-1:
	x = r.pop()
	if x[1] == 0:
		num += p
		q -= 1
		ans += x[0]*p
	else:
		num += q
		p -= 1
		ans += x[0]*q

	if num > (w+1)*(h+1)-1:
		ans -= x[0] * (num-(w+1)*(h+1)+1)
print(ans)

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

int main() {
  int n, x;
  while (cin >> n >> x) {
    if (n == 0 && x == 0)
      break;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++) {
        int k = x - i - j;
        if (k > j && k <= n) {
          ++cnt;
        }
      }
    cout << cnt << endl;
  }
  return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

string s;
int n;
ll ans;

int main() {
	cin >> s;
	n = (int)s.length()-1;
	
	rep(i,1<<n) {
		ll sum = 0;
		int fr = 0;
		rep(j,n) {
			if (i>>j & 1) {
				sum += stol(s.substr(fr,j-fr+1));
				fr = j+1;
			}
		}
		sum += stol(s.substr(fr, n-fr+1));
		ans += sum;
	}
	cout << ans << ln;
}

Measured memory_bytes: 256