akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define go(i, a, n) for (ll i = a; i < (ll)n; i++)
#define gor(i, a, n) for (ll i = (ll)n - 1; i >= 0; i--)
#define gos(i, a, n, step) for (ll i = a; i < (ll)n; i += step)
#define show(a) cout << a << '\n'
#define show2(a, b) cout << a << " " << b << '\n'
#define show3(a, b, c) cout << a << " " << b << " " << c << '\n'
#define show4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << '\n'
#define ull unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define mem(a, k) memset(a, k, sizeof(a))
#define answer(z, k) cout << "Case #" << z << ": " << k << endl;
#define ans(z) cout << "Case #" << z << ": "
auto t1 = chrono::high_resolution_clock::now();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // ll t;
    // cin >> t;
    // while (t--)
    // {
    // }
    ll n;
    cin >> n;
    ll count = 0;
    go(i, 1, n + 1)
    {
        go(j, 1, (n / i) + 1)
        {
            ll ans = n - (i * j);
            count += (ans > 0);
        }
    }
    show(count);
    auto t2 = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(t2 - t1).count();
    clog << "Time taken = " << duration * 1.0 / 1000 << " seconds" << endl;
    return 0;
}


Measured memory_bytes: 3812
#include<stdio.h>


int main(){

  int H, W, i, j, k, l;

  while(1){

  scanf("%d %d", &H, &W);

  if(H == 0 && W == 0)

    break;

  else{

  for(i = 0;i < W;i++){

    printf("#");

  }

  printf("\n");

    for(j = 0;j < H - 2;j++){

      printf("#");

      for(k = 0;k < W - 2;k++){

	printf(".");

      }

      printf("#\n");

    }

    for(l = 0;l < W;l++){

    printf("#");

  }

  printf("\n");

  
  }

  printf("\n");
  
  }

    
  return 0;
  
}

Measured memory_bytes: 588
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n,k;
cin>>n>>k;
long long int a[n],dp[n],i,j;
for(i=0;i<n;i++)
{
cin>>a[i];
dp[i]=999999999999;
}
dp[0]=0;
dp[1]=abs(a[0]-a[1]);
//cout<<dp[n-1]<<endl;
for(i=2;i<n;i++)
{
for(j=1;j<=min(i,k);j++)
{
dp[i]=min(dp[i],(dp[i-j]+abs(a[i-j]-a[i])));
}
}
cout<<dp[n-1]<<endl;
}


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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
        #define eprintf(...) 42
#endif

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

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

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

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

  vi a(n);
  rep(i, n) cin >> a[i];

  if(n == 1){
    cout << "YES" << endl;
    return 0;
  }

  ll s = 0;
  rep(i, n) s += a[i];

  ll b = (ll)n*(n+1)/2;

  if(s%b != 0){
    cout << "NO" << endl;
    return 0;
  }

  ll t = s/b;
  vl c(n);
  rep(i, n){
    c[i] = a[(i+1)%n]-a[i];
  }
  rep(i, n) c[i] -= t;

  ll d = t;
  rep(i, n){
    if(c[i] > 0 or c[i]%n != 0){
      cout << "NO" << endl;
      return 0;
    }
    d += c[i] / n;
  }

  cout << (d == 0 ? "YES" : "NO") << endl;

  return 0;
}


Measured memory_bytes: 1408
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
    int num[1000];
int main()
{
    int n,m;
    cin>>n>>m;
    int sum=0;
    for(int i=1;i<=m-n;i++) sum+=i;
    cout<<sum-m<<endl;
    return 0;
}


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

int main()
{

    ll n,i,j;
    cin>>n;
    double a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    double dp[n+1]={0};
    dp[0]=1;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j>0;j--)
        {
            dp[j]=(1-a[i])*dp[j]+(a[i]*dp[j-1]);
        }
        dp[0]=dp[0]*(1-a[i]);
    }
    double ans=0;
    for(i=n;i>n/2;i--)
    {
        ans+=dp[i];
    }
    printf("%.12lf\n",ans);
}

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

#define BR "\n"
#define SP " "

int main() {
  vector<int> a(3);
  cin >> a[0] >> a[1] >> a[2];
  sort(a.begin(), a.end());
  cout << a[0] << SP << a[2] << BR;

  return 0;
}


Measured memory_bytes: 3140
N,M=map(int,input().split())
AB=[[int(x) for x in input().split()] for _ in range(M)]
sa=set()
en=set()
for a,b in AB:
    if a>b:
        a,b=b,a
    if a==1:
        sa.add(b)
    if b==N:
        en.add(a)
print('POSSIBLE' if sa&en else 'IMPOSSIBLE')

Measured memory_bytes: 91608
n, m = map(int, input().split())
s, t = list(input()), list(input())


def gcd(a, b):
    if a > b:
        return gcd(b, a)
    while a > 0:
        a, b = b % a, a
    return b


def lcm(a, b):
    return a * b // gcd(a, b)


l = lcm(len(s), len(t))
x = {}  # これふつうにリストだとREになるのマジで謎なんだけど
for i in range(0, len(s)):
    x[i * (l // len(s))] = s[i]
for i in range(0, len(t)):
    if i * (l // len(t)) not in x:
        continue
    else:
        if x[i * (l // len(t))] != t[i]:
            print(-1)
            exit()
print(l)

Measured memory_bytes: 20572
# -*- coding: utf-8 -*-
# B

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

N, k = map(int, input().split())
h = list(map(int, input().split()))
# print(h)
h.sort()
a = bisect.bisect_left(h, k)
print(N-a)


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

#define dbg(x) cerr<<#x": "<<x<<"\n"
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"
#define DMAX 100001

using namespace std;

long long v[DMAX], c, k, n, s=0;
int ok[DMAX];


int main()
{
	ios_base::sync_with_stdio(0);
	cin >> n;

	for(long long i=1;i<=n;i++)
	{
		cin >> v[i];
		s += v[i];
	}
	ok[n]=1;
	long long ans = 1;
	sort(v+1, v+n+1);
	s-=v[n];
	//dbg(s);
	for(int i=n-1;i>0;i--)
	{
		if(ok[i+1]==1 && 2*s >= v[i+1])
		{
			//dbg(s);
			//dbg(i);
			ok[i]=1;
			ans++;
		}
		s-=v[i];
	}
	cout << ans << '\n';
}

Measured memory_bytes: 1408
n = int(input())
pre_ab = []
for i in range(n):
    ai, bi = map(int, input().split())
    pre_ab.append([ai, bi])
ab = sorted(pre_ab, key=lambda x: x[1])

time = 0
flag = 0
for i in range(n):
    if time + ab[i][0] > ab[i][1]:
        flag = 1
        break
    else:
        time += ab[i][0]
if flag:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 39620
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> P; typedef pair<Int,Int> Pl;
const int mod = 1e9+7;
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) v.begin(),v.end()
#define Pr(type) priority_queue<type>
#define gPr(type) priority_queue<type,vector<type>,greater<type>>
#define V(type) vector<type>
#define rep(i,n) for(int i=0; i<n; i++)
#define rer(i,st,en) for(int i=st; i<en; i++)
#define eb emplace_back
#define pri1(a) cout<<a<<'\n'
#define pri2(a,n) rep(i,n)cout<<a[i]<<'\n'
#define pri3(a,n) rep(i,n-1)cout<<a[i]<<' '; cout<<a[n-1]<<'\n'
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int n,m,_,x,y,q;
string s,sb;
bool ok;

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

  cin>>n; Int a[n],b[n]; rep(i,n)cin>>a[i]; 
  sort(a,a+n); b[0]=a[0];
  rep(i,n-1)b[i+1]=b[i]+a[i+1];
  int ans=1;
  for (int i = n-2; i >= 0; i--){
    if(b[i]*2<a[i+1])END
    else ans++;
  }
  END
}

Measured memory_bytes: 1792
n = int(input())
lis = [int(input()) for _ in range(n)]

lis = sorted(lis)
t = sum(lis)

if t % 10 != 0:
    print(t)
    exit()
else:
    tmp = [0]*n
    ans = 0
    for i in range(n):
        tmp[i] = t - lis[i]
    
    for j in range(n):
        if tmp[j] % 10 != 0:
            ans = max(ans, tmp[j])

print(ans)

Measured memory_bytes: 9040
#include<bits/stdc++.h>
#include<map>
#define ll long long int
#define ld long double
#define pb push_back
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define mod 1000000007
#define MAX 100009
#define endl '\n'
#define mp make_pair
#define INF 1000000000
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ff first
#define ss second
#define ps(x,y) fixed<<setprecision(y)<<x
#define pii pair<long long int,long int>
#define mii map<long long int,long long int>
#define w(t) 	int t; cin>>t; while(t--)

using namespace std;

//ll c[MAX];




int main() {
	int k,a,b;
	cin>>k>>a>>b;
	bool flag=0;
	for(int i=a;i<=b;i++){
		if(i%k==0){
			flag=1;
			break;
		}
	}
	if(flag)	cout<<"OK";
	else	cout<<"NG";
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    int counta=0,countb=0;
    while(t>=3600){
        counta++;
        t-=3600;
    }
    while(t>=60){
        countb++;
        t-=60;
    }
    cout<<counta<<":"<<countb<<":"<<t<<endl;
}


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

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll a,b,c;
    cin>>a>>b>>c;
    int ans=0;
    for(int i=b;i<=c;i++){
        if(i%a==0){
            cout<<"OK"<<endl;
            ans=1;
            break;
        }
    }
    if(ans==0)
        cout<<"NG"<<endl;
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  double p;
  
  if (n % 2 == 0) {p = 0.5;}
  else {p = (n/2 + 1.0)/n;}
  
  cout << fixed << setprecision(10) << p << endl;
}
  

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

double solve(vector<int> v, vector<double> r)
{
    int m = v.size();
    double sum = accumulate(r.begin(), r.end(), 0.0);

    double ret = 0.0;
    for(int i=0; i<m; ++i)
        ret += v[i] * r[i] / sum;
    return ret;
}

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

    vector<double> ret(t+1);
    for(int i=0; i<=t; ++i){
        int n, m;
        cin >> n >> m;
        vector<int> v(m);
        vector<double> r(m);
        for(int j=0; j<m; ++j)
            cin >> v[j] >> r[j];
        ret[i] = solve(v, r);
    }

    if(*max_element(ret.begin(), -- ret.end()) > ret.back() + 0.0000001)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}

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

const ll max_n = 1000000000000001;

int main() {
	string ans;
	ll n;
	cin >> n;
	while (true) {
		if (!(n % 26)) {
			ans = "z" + ans;
			n /= 26;
			--n;
		}
		else {
			ans = (char)('a' + n % 26 - 1) + ans;
			n /= 26;
		}
		if (n == 0)break;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3624
#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 cnt = 0;
  for (int i = 0, tmp = 1; i < N; i++) {
    if (A.at(i) != tmp) cnt++;
    else tmp++;
  }

  cout << ((cnt == N) ? -1 : cnt) << "\n";
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define mp make_pair
#define pb push_back
#define f first
#define se second
vector<int>adj[N];
vector<bool>vis(N,false);
int cnt=0;
bool prime[1000004];
void dfs(int v)
{   
    vis[v]=true;
    for(auto it:adj[v])
        if(!vis[it])
            dfs(it);
}
bool isPerfectSquare(long double x) 
{   
  // Find floating point value of  
  // square root of x. 
  long double sr = sqrt(x); 
  
  // If square root is an integer 
  return ((sr - floor(sr)) == 0); 
} 
void prime_check() 
{  
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=1000000; p++) 
    { 
        if (prime[p] == true) 
        {  
            for (int i=p*p; i<=1000000; i += p) 
                prime[i] = false; 
        } 
    } 
} 
int main()
{
  ll h,count=1,count1=0;
  cin>>h;
  while(h)
  {
    count1+=count;
     h>>=1;
     count*=2;
  }
  cout<<count1;
}

Measured memory_bytes: 2560
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Set<Integer> s = new HashSet<Integer>();
        for (int i = 0 ; i < N ; i++ ) {
            s.add(sc.nextInt());
        }
        System.out.println(s.size());
    }

}

Measured memory_bytes: 23124
N = int(input())

A = [ int (x) for x in input().split() ]
B = [ int (x) for x in input().split() ]
C = [ int (x) for x in input().split() ]

result = sum(B)

for i in range(N-1):
  if A[i] == A[i+1]-1:
    result += C[A[i]-1]
      
print(result)

Measured memory_bytes: 3064
import Control.Arrow
import Control.Monad
import Data.Bits
import qualified Data.ByteString.Char8 as BC
import Data.Char
import Data.List
import Data.Maybe

main :: IO ()
main = do
  n <- getInt
  xs <- getInts
  let ys = zipWith (-) xs [1..]
  let m = median ys
  print . sum . map (abs . subtract m) $ ys

getInt :: IO Int
getInt = readLn

getInts :: IO [Int]
getInts = unfoldr (BC.readInt . BC.dropWhile (== ' ')) <$> BC.getLine

median :: Ord a => [a] -> a -- O(n log n)
median xs = sort xs !! (length xs `div` 2)


Measured memory_bytes: 50556
def io_tmp():
    global input
    import io
    f = io.StringIO(open(0).read())
    input = f.readline

io_tmp()


from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = map(int, input().split())
graph = [[0] * N for _ in range(N)]
for _ in range(M):
    s, t, w = map(int, input().split())
    if w <= L:
        graph[s-1][t-1] = graph[t-1][s-1] = w
dist = floyd_warshall(graph, directed=False)
graph = dist <= L
#np.fill_diagonal(graph, 0)
#graph[dist > L] = 0
dist = floyd_warshall(graph, directed=False)
dist[np.isinf(dist)] = 0
dist = dist.astype(int)

Q = int(input())
ans = []
for _ in range(Q):
    s, t = map(int, input().split())
    ans.append(dist[s-1][t-1] - 1)
print(*ans, sep='\n')


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

public class Hello
{
    static void Main()
    {
        string[] s_data = Console.ReadLine().Split(' ');
        int num = int.Parse(s_data[0]);
        int lower_num = int.Parse(s_data[1]);
        int upper_num = int.Parse(s_data[2]);

        int new_num = 0;
        int add_num = 0;

        var result = new List<int>();

        for(int i = 1; i <= 9; i++)
        {
            if(i>=lower_num && i <= upper_num)
            {
                result.Add(i);
            }
        }
        for(int i = 10; i <= num; i++)
        {
            new_num = i;
            add_num = 0;
            while (true)
            {
                if (new_num <= 0)
                {
                    break;
                }
                else
                {
                    add_num += new_num % 10;
                    //Console.WriteLine(add_num);
                    new_num = new_num / 10;
                    //Console.WriteLine(new_num);
                }
            }
            if(add_num >= lower_num && add_num <= upper_num)
            {
                result.Add(i);
            }
        }

        Console.WriteLine(result.Sum());
    }
}

Measured memory_bytes: 11272
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define arr(n) array<int,n>
#define INF 1e9
typedef long long ll;
typedef pair<int,int> pii;

int main(){
  int N;
  cin >> N;
  int a[N];
  int b[1000007] = {};
  rep(i,N){
    cin >> a[i];
    b[a[i]]++;
  }
  sort(a,a+N);
  int ans = N;
  
  rep(i,N){
    if(b[a[i]] > 1){
      ans--;
      continue;
    }
    bool f = false;
    int v = 100;
    for(int c=2; c<v; c++){
      if(a[i]%c==0 and (b[a[i]/c]) > 0){
        f = true;
        break;
      }
    }
    if(f){
      ans--;
      continue;
    }
    int x = *lower_bound(a,a+N,a[i]/v + 1);
    int j = 0;
    while(a[j] < x){
      if(j!=i and a[i]%a[j] == 0){
        ans--;
        break;
      }
      j++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 8276
import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()

# N = list(map(int,input().split()))
N = list(map(int,input().split()))
N.sort()
if sum(N)==17 and int(N[0]) == int(N[1]) == 5:
    print('YES')
else:
    print("NO")

Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int numS[26] = {0, }, numT[26] = {0, };

string S, T;
int main() {
	cin >> S >> T;
	
	int n = 0;
	int strSize = S.size();
	for(int i = 0; i < strSize; i++) {
		if(numS[S[i] - 'a'] == 0) numS[S[i] - 'a'] = (++n);
	}

	n = 0;
	for(int i = 0; i < strSize; i++) {
		if(numT[T[i] - 'a'] == 0) numT[T[i] - 'a'] = (++n);
	}

	string ans = "Yes";
	for(int i = 0; i < strSize; i++) {
		if(numS[S[i] - 'a'] != numT[T[i] - 'a']) {
			ans = "No";
			break;
		}
	}

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


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

int num(char c){
  int ret=c-'0';
  return ret;
}

int main() {
  string a,b;
  cin>>a>>b;
  bool flag=true;
  if (a.size()==b.size()) {
    int i=0;
    while (i<a.size() && flag){
      if(num(a.at(i))>num(b.at(i))) {
        cout <<"GREATER"<<endl;
        flag=false;
      }
      else if (num(b.at(i))>num(a.at(i))) {
        cout <<"LESS"<<endl;
        flag=false;
      }
      i++;
    }
  }
  else if (a.size()>b.size()) {
    cout <<"GREATER"<<endl;
    flag=false;
  }
  else {
    cout<<"LESS"<<endl;
    flag=false;
  }
  if (flag) cout <<  "EQUAL" <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

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

    ll M;
    cin >> M;
    vec d(M), c(M);
    ll digit = 0, cnt = 0;
    Rep (i, M) {
        cin >> d[i] >> c[i];
        digit += c[i];
        cnt += d[i] * c[i];
    }

    cout << digit - 1 + (cnt-1) / 9 << "\n";
}

Measured memory_bytes: 3328
#include <iostream>
#include<string>
#include<cstdio>
#include<string.h>
#include<vector>
#include<cmath>
using namespace std;
const int N=2*1e5+100;


int main ()
{
    int n;
    cin>>n;
    int r[N],w[N],ret=0;
    r[0]=w[0]=-1;
    int i=0;int j=0;
    for(int k=0;k<n;k++){
        char a;
        cin>>a;
        if(a=='R'){
            r[i]=k;
            i++;
        }
        else {
            w[j]=k;
            j++;
        }
    }
    if(i==0||j==0){  }
    else
    for(int k=0;;){
        if(k==j){
            break;
        }
        else if(r[i-1]<w[k]){
            break;
        }
        else{
            i--;
            k++;
            ret++;
        }
    }
    cout<<ret<<endl;
    return 0;
}

Measured memory_bytes: 4408
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <string>
#include <cmath>
#include <functional>
#include <queue>
#include <map>
using namespace std;

typedef long long ll;
const int M = 1e9 + 7;
const int N = 2e5 + 10;
const int MAX = 1e9 + 1;
//int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n;

int g(int t, int c, int d) {
    int mx = 0;
    for (int i = 0; i * c <= t; ++i) {
        mx = max(mx, (t - c * i) / d * d + c * i);
    }
    return mx;
}

int main() {
    int i, j;
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    int ans1, ans2;
    double mx = -1;
    for (i = 0; 100 * a * i <= f; ++i) {
        for (j = 0; 100 * b * j + 100 * a * i <= f; ++j) {
            if (i == 0 && j == 0)
                continue;
            int water = 100 * a * i + 100 * b * j;
            int suger = f - water;
            suger = min(suger, water / 100 * e);
            suger = g(suger, c, d);
            if ((double)suger / (double)(suger + water) > mx) {
                mx = (double)suger / (double)(suger + water);
                ans1 = suger, ans2 = water;
            }
        }
    }
    cout << ans1 + ans2 << ' ' << ans1 << endl;
    return 0;
}


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

class Program
{
    static void Main(string[] args) {
#if DEBUG
        //MyDebugger.MakeTestCase("../TextFile2.txt");
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        int a = int.Parse(input.ReadLine());
        var s = input.ReadLine();

        return (a < 3200 ? "red" : s);
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
using ll = long long;
using namespace std;
int main() {
  	ll n, d;
  	vector<vector<int> > mat;
  	cin >> n >> d;
  	ll tmp;
  	REP(i,n){ 
      	vector<int> v;
      	mat.push_back(v);
      	REP(j,d) {
          	cin >> tmp;
          	mat[i].push_back(tmp);
      	}
    }
  
  	ll ct = 0;
  	REP(i, n - 1){
      	FOR(j, i + 1, n) {
          	ll sum = 0;
          	REP(k, d){
              	sum += pow(mat[i][k] - mat[j][k], 2);
            }
          	double dist = sqrt(sum);
          	if (dist == floor(dist)){
              	ct++;
            }
        }
    }
      
    cout << ct << endl;
  
  	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

#define deg_to_rad(deg) (((deg)/360)*2*M_PI)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

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

bool dis0(long double a, long double b){
    if(abs(a-b) < 0.000001){
        return true;
    }
    else{
        return false;
    }
}
int main()
{
    cout << fixed << setprecision(15);
    long double X;
    cin >> X;

    long double x = 0;
    long double y = 0;

    ll k= 0;
    while(1){
        x += cos(deg_to_rad(k*X));
        y += sin(deg_to_rad(k*X));
        k++;
        // cout << x << " " << y << endl;
        if(dis0(x, 0.0) && dis0(y, 0.0)){
            cout << k << endl;
            return 0;
        }
        if(k>=100000) break;
    }

    return 0;
}

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

int a[101], n;

int main(){
    cin>>n;

    for(int i=1;i<n;i++)cin>>a[i];

    int sol=a[n-1]+a[1];

    while(n>1){
        sol+=min(a[n], a[n-1]);
        n--;
    }
    cout<<sol;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	long long n, a = 0, b = 0, c = 0, d = 0, e = 0, f = 0;
	cin >> n;
	string s;
	for (int h = 1; h <= n; h++) {
		cin >> s;
		if (s[0] == 'M') { a++; }
		if (s[0] == 'A') { b++; }
		if (s[0] == 'R') { c++; }
		if (s[0] == 'C') { d++; }
		if (s[0] == 'H') { e++; }
	}
	f += a * b * c; f += a * b * d; f += a * b * e;
	f += a * c * d; f += a * c * e; f += a * d * e;
	f += b * c * d; f += b * c * e; f += b * d * e; f += c * d * e;
	cout << f << endl;
	cin >> e;
}

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

int main(){
    map<long long, long long> mp;
    long long K, tmp = 1, a = 7;
    cin >> K;
    while(1){
        a %= K;
        //cout << a << endl;
        if(a == 0) break;
        else if(mp[a] == 0){
            mp[a]++;
            a = a * 10 + 7;
            tmp++;
        }
        else{
            cout << "-1" << endl;
            return 0;
        }
    }
    cout << tmp << endl;
    return 0;
}


Measured memory_bytes: 66064
#include<stdio.h>
int main(){
int k,d[1010],e[1010],f[1010],g[1010],i,a,b,c,n,x[1010];
while(1){
scanf("%d %d %d\n",&a,&b,&c);
if(a==0 && b==0 && c==0){
break;
}
scanf("%d\n",&n);
for(i=1;i<=a+b+c;i++){
x[i]=2;
}
for(i=0;i<n;i++){
scanf("%d %d %d %d\n",&d[i],&e[i],&f[i],&g[i]);
if(g[i]==1){
x[d[i]]=1,x[e[i]]=1,x[f[i]]=1;
}
}
do{
k=0;
for(i=0;i<n;i++){
if(x[d[i]]==2 && x[e[i]]==1 && x[f[i]]==1){
x[d[i]]=0;
k++;
}
else if(x[d[i]]==1 && x[e[i]]==2 && x[f[i]]==1){
x[e[i]]=0;
k++;
}
else if(x[d[i]]==1 && x[e[i]]==1 && x[f[i]]==2){
x[f[i]]=0;
k++;
}
}
}while(k==0);
for(i=1;i<=a+b+c;i++){
printf("%d\n",x[i]);
}
}
return 0;
}


Measured memory_bytes: 1988
#include<bits/stdc++.h>
using namespace std;
char ar[7][7], cpy[7][7];
int r, c, k;
void copy_matrix()
{
	for(int i = 0; i<r; i++)
		for(int j = 0; j<c; j++)
			cpy[i][j] = ar[i][j];
}
void color(int i, int j)
{
	for(int rr = 0; rr<r; rr++)
	{
		if(i & (1<<rr))
		{
			for(int cc = 0; cc<c; cc++)
				cpy[rr][cc] = '$';	
		}
	}
	for(int cc = 0; cc<c; cc++)
	{
		if(j & (1<<cc))
		{
			for(int rr = 0; rr<r; rr++)
				cpy[rr][cc] = '$';	
		}
	}
	
}
bool check()
{
	int cnt = 0;
	for(int i = 0; i<r; i++)
	{
		for(int j = 0; j<c; j++)
		{
			if(cpy[i][j] == '#')
				cnt++;
		}
	}
	if(cnt == k) return true;
	else return false;
}
void solve()
{
	cin>>r>>c>>k;
	
	for(int i = 0; i<r; i++)
		for(int j = 0; j<c; j++)
			cin>>ar[i][j];
		
	int ans  = 0;
	for(int i = 0; i<(1<<r); i++)
	{
		for(int j = 0; j<(1<<c); j++)
		{
			copy_matrix();
			color(i, j);
			if(check())
				ans++;
		}
	}
	cout<<ans<<"\n";
}
int main()
{
	solve();
	return 0;
}

Measured memory_bytes: 3596
#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);
  }
  sort(a.begin(),a.end());
  int c = 1;
  for(int i = 0;i < n-1;i++){
    if(a.at(i) != a.at(i+1)){
      c++;
    }
  }
  if( (n-c) % 2 == 0){
    cout << c << endl;
  }
  else{
    cout << c-1 << endl;
  }
}

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

template<class T> void mkmin(T& a, const T b) { a = min(a, b); }
template<class T> void mkmax(T& a, const T b) { a = max(a, b); }

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

#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ferrari ios_base::sync_with_stdio(false); cin.tie(NULL)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7; // 998244353
const ll OO = 1e18;
const int oo = 2e9;
const int N = 200100;

int n, k, a[N];

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = k + 1; i <= n; i++)
		cout << (a[i] > a[i - k] ? "Yes\n" : "No\n");
}


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

typedef unsigned long long ull;

const ull B=10007;

void RollingHash(string T, string P){
	int t=T.size();
	int p=P.size();
	
	ull x=1;
	for (int i=0;i<p;i++) x*=B;
	
	ull th=0,ph=0;
	for (int i=0;i<p;i++) th=th*B+T[i];
	for (int i=0;i<p;i++) ph=ph*B+P[i];
	
	for (int i=0;i+p<=t;i++){
		if(th==ph) printf("%d\n",i);
		if(i+p<t) th=th*B+T[i+p]-T[i]*x;
	}
}

int main(){
	string T,P;
	cin >> T >> P;
	RollingHash(T,P);
	return 0;
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define rep(i , x , n)  for(int i = x ; i <= n ; i ++) 
#define per(i , n , x)  for(int i = n ; i <= x ; i --) 
using namespace std ;
typedef long long ll ;
typedef pair<int , int> pii ;
const int inf = 0x3f3f3f3f ;
const int maxn = 2e5 + 5 ;
const int maxm = 5005 ;
int k , n , a[maxn] ;
int main()
{
	int ans = 1e9 ;
	scanf("%d%d" , &k , &n) ;
	rep(i , 1 , n)  scanf("%d" , &a[i]) ;
	a[n + 1] = a[1] + k ;
	rep(i , 1 , n)  ans = min(ans , k - (a[i + 1] - a[i])) ;
	printf("%d\n" , ans) ;
	return 0 ;
}

Measured memory_bytes: 1024
import Control.Monad
import Data.List
import Data.Ord
import Control.Applicative

main = do
  n <- readLn
  ab <- replicateM n $ words <$> getLine
  let abInt = reverse $ sortBy (comparing get1st) $ map sumh $ map (map read) ab :: [(Int,Int,Int)]
  putStrLn $ show $ (sumt abInt) - (suma abInt)
  
sumt :: [(Int,Int,Int)] -> Int
sumt (a:as) = (get2nd a) + (sumt (drop 1 as))
sumt _ = 0

suma :: [(Int,Int,Int)] -> Int
suma (_:(a:as)) = (get3rd a) + (suma as)
suma _ = 0

sumh :: [Int] -> (Int,Int,Int)
sumh [a,b] = ((a + b),a,b)

get1st (a,_,_) = a
get2nd (_,a,_) = a
get3rd (_,_,a) = a


Measured memory_bytes: 143740
import math
import itertools

N = int(input())
A =[]
path_length = 0
permm = list(range(N))

for i in range(N):
    x,y = map(int, input().split())
    A.append((x,y))

for p in itertools.permutations(permm):
  # p は、点の順列

  for i, j in zip(p, p[1:]):
      x1, y1 = A[i]
      x2, y2 = A[j]
      path_length += math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
ans = path_length / math.factorial(N)

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200005;
ll n,a[maxn],cnt[maxn];
ll ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		ans+=cnt[i]*(cnt[i]-1)/2;
	}
	for(int i=1;i<=n;i++){
		if(cnt[a[i]]>=2){
			cout<<ans-cnt[a[i]]*(cnt[a[i]]-1)/2+(cnt[a[i]]-1)*(cnt[a[i]]-2)/2<<endl;
		}else cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 4736
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
#include <iomanip>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 2;
const int MOD = 1000000007;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
	string s;
	cin >> s;
	string ans = "";
	REP(i, s.length()) {
		switch (s[i]) {
		case '0':
			ans.push_back('0');
			break;
		case '1':
			ans.push_back('1');
			break;
		case 'B':
			ans = ans.substr(0, ans.length() - 1);
			break;
		}
	}

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

Measured memory_bytes: 256
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}


int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

int n,q,k;
vector<pair<int,int> > g[N];
int d[N];

void dfs(int v, int par, int dist){
    d[v]=dist;
    for(int i=0; i<g[v].size(); i++){
        if(g[v][i].first==par) continue;
        dfs(g[v][i].first,v,dist+g[v][i].second);
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    rep(i,1,n){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    cin >> q >> k;
    dfs(k,-1,0);
    while(q--){
        int x,y;
        cin >> x >> y;
        cout << d[x]+d[y] << "\n";
    }
    return 0;
}

Measured memory_bytes: 13824
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Scanner;

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

        while (true) {
            int h = scanner.nextInt();
            int w = scanner.nextInt();
    
            if (h == 0 && w == 0) {
                scanner.close();
                return;
            }

            for (int y = 0; y < h; y++) {
                for (int x = 0; x < w; x++) {
                    System.out.print("#");
                }
                System.out.println("");
            }
            System.out.println("");
        }
    }
}



Measured memory_bytes: 35008
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>
#include <cassert>
#include <atcoder/math>

using namespace std;
using namespace atcoder;
typedef long long ll;

int main()
{
   int T;
   cin >> T;
   for (int i = 0; i < T; i++)
   {
      ll N, M, A, B;
      cin >> N >> M >> A >> B;
      cout << floor_sum(N, M, A, B) << endl;
   }

   return 0;
}


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

int main() {

    int n;
    int a[100010] = {0};
    int b[100010] = {0};

    cin >> n;
    int tmp;
    int max_a = 0, min_a = 100010;
    int max_b = 0, min_b = 100010;
    for (int i=0; i<n; i++) {
        cin >> tmp;
        if (i%2==0) {
            a[tmp-1]++;
            if (tmp > max_a) {
                max_a = tmp;
            }
            if (tmp < min_a) {
                min_a = tmp;
            }
        } else {
            b[tmp-1]++;
            if (tmp > max_b) {
                max_b = tmp;
            }
            if (tmp < min_b) {
                min_b = tmp;
            }
        }
    }

    if (n==2) {
        if (max_a == max_b) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
        return 0;
    }

    int num_a = -1;
    int max_num_a1 = 0;
    int max_num_a2 = 0;
    for (int i=min_a-1; i<max_a; i++) {
        if (a[i] > max_num_a1) {
            max_num_a1 = a[i];
            num_a = i+1;
        }
    }
    sort(a, end(a),
         [](int x, int y) -> int {
             return ( x < y );
         } );
    max_num_a2 = a[100008];

    int num_b = -1;
    int max_num_b1 = 0;
    int max_num_b2 = 0;
    for (int i=min_b-1; i<max_b; i++) {
        if (b[i] > max_num_b1) {
            max_num_b1 = b[i];
            num_b = i+1;
        }
    }
    sort(b, end(b),
         [](int x, int y) -> int {
             return ( x < y );
         } );
    // for (int i=0; i<5; i++) {
    //     cout << b[i] << " ";
    // }
    // cout << endl;
    max_num_b2 = b[100008];

    // cout << "max_num_a1: " << max_num_a1 << endl;
    // cout << "max_num_a2: " << max_num_a2 << endl;
    // cout << "num_a: " << num_a << endl;
    // cout << "max_num_b1: " << max_num_b1 << endl;
    // cout << "max_num_b2: " << max_num_b2 << endl;
    // cout << "num_b: " << num_b << endl;

    int ans;
    if (num_a == num_b) {
        if (max_num_a1 + max_num_b2 > max_num_b1 + max_num_a2) {
            ans = n - max_num_a1 - max_num_b2;
        } else {
            ans = n - max_num_b1 - max_num_a2;
        }
    } else {
        ans = n - max_num_a1 - max_num_b1;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
import heapq as hq
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(lambda x: x*(-1),A))
hq.heapify(B)
for i in range(m):
  x=hq.heappop(B)
  hq.heappush(B,(x+1)//2)

print(sum(B)*(-1))

Measured memory_bytes: 14180
import java.util.Scanner;

// Aising2020_A
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int L = sc.nextInt();
		int R = sc.nextInt();
		int d = sc.nextInt();

		int i = 0;
		int count = 0;

		while (true) {
			if (d * i > R) {
				break;
			}
			if (L <= d * i && d * i <= R) {
				count++;
			}
			i++;
		}

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

}


Measured memory_bytes: 35572
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <sstream>
#include <string>

using namespace std;
int main(){

	string s,S;
	int cnt = 0;
	getline(cin,s);
	for(int i = 0; i < s.size(); i++){
		s[i] = tolower(s[i]);
	}
	while(getline(cin,S) && S!= "END_OF_TEXT"){
		stringstream ss;
		ss<<S;
		string w;
		while(ss>>w){
			for(int i = 0; i < w.size(); i++){
				w[i] = tolower(w[i]);
			}
			if ( w == s){
				cnt++;
			}
		}
	}
	cout <<cnt <<endl;
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)

int main (void) {
    int N,A,B;
    cin>>N>>A>>B;
    cout<<min(N*A,B)<<endl;
    return 0;
}

Measured memory_bytes: 256
N,X=map(int,input().split())
L=[int(i) for i in input().split()]

ans=0

def d(i):
    if i==1:
        return 0
    else:
        return d(i-1)+L[i-2]

for i in range(1,N+2):
    if d(i)>X:
        print(i-1)
        exit()

print(N+1)

Measured memory_bytes: 3060
import java.util.*;
import java.util.function.*;
import java.io.*;

class Main {
    static Scanner scanner = new Scanner();
    static long mod = 1000000007;
    static int inf = 0x7ffffff;

    public static void main(String[]$) throws Exception {
        double a = scanner.nextInt();
        double b = scanner.nextInt();
        double x = scanner.nextInt() / a;
        if (2 * x <= a * b) {
            double y = 2 * x / b;
            System.out.println(Math.atan2(b, y) * 180 / Math.PI);
        } else {
            double y = 2 * (a * b - x) / a;
            System.out.println(Math.atan2(y, a) * 180 / Math.PI);
        }
    }

    static class System {
        static PrintWriter out = new PrintWriter(java.lang.System.out);

        static {
            Runtime.getRuntime().addShutdownHook(new Thread(System.out::flush));
        }
    }

    static class Scanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(java.lang.System.in), 0x10000);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        char[][] nextCharArray(int n, int m) {
            char[][] a = new char[n][m];
            for (int i = 0; i < n; i++) {
                a[i] = next().toCharArray();
            }
            return a;
        }
        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        int[] nextIntArray(int n, IntUnaryOperator op) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsInt(nextInt());
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }

        long[] nextLongArray(int n, LongUnaryOperator op) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsLong(nextLong());
            }
            return a;
        }
    }
}


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

#define MAXN (100010)

int n;
int a[MAXN], b[MAXN];
std::vector<int> vec[MAXN];
std::map<int, int> map;
std::multiset<int> seta, setb;
bool vis[MAXN];

void dfs(int u){
	vis[u] = true;
	for(auto v : vec[u]){
		if(vis[v]) continue;
		dfs(v);
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) scanf("%d", a + i), a[0] ^= a[i], seta.insert(a[i]);
	for(int i = 1; i <= n; ++ i) scanf("%d", b + i), b[0] ^= b[i], setb.insert(b[i]);
	seta.insert(a[0]);
	setb.insert(b[0]);
	if(seta != setb) return printf("-1\n"), 0;
	
	int cnt = 0, e = 0, c = 0;
	for(int i = 1; i <= n; ++ i){
		if(a[i] == b[i]) continue;
		int u = map[a[i]] ? map[a[i]] : (map[a[i]] = ++ cnt);
		int v = map[b[i]] ? map[b[i]] : (map[b[i]] = ++ cnt);
		++ e;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	if(!map[a[0]]) map[a[0]] = ++ cnt;
	if(!map[b[0]]) map[b[0]] = ++ cnt;
	for(int i = 1; i <= cnt; ++ i){
		if(!vis[i]){
			++ c;
			dfs(i);
		}
	}
	
	printf("%d\n", e + c - 1);
	return 0;
}

Measured memory_bytes: 23808
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
const int INF = 1e18, MOD = 1e9 + 7;
signed main() {
    INCANT;
    int n, m, a, mx = -INF;
    cin>>n>>m;
    rep(i, m) {
        cin>>a;
        chmax(mx, a);
    }
    if(mx < (n + 1) / 2) cout<<0<<endl;
    else cout<<n - (n - mx) * 2 - 1<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int[] a=new int[n+2];
		for(int i=1;i<=n;i++) a[i]=sc.nextInt();
		
		long money=0;
		for(int i=1;i<=n+1;i++){
			money+=Math.abs(a[i]-a[i-1]);
		}
		
		for(int i=1;i<=n;i++){
			System.out.println(money - Math.abs(a[i]-a[i-1]) -Math.abs(a[i+1]-a[i]) +Math.abs(a[i+1]-a[i-1]));
		}
		
	}
}


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

        string S;

        cin  >> S;

        if(S[2] == S[3] && S[4] == S[5]){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }

    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%2019;
    }
    return n*rep_jijo(n,x-1)%2019;
}
ll com(ll n,ll r){
    ll x=1,y=1;
    ll tmp=n;
    while(tmp>=n-r+1){
        x=x*tmp%mod;
        tmp--;
    }
    while(r>0){
        y=y*r%mod;
        r--;
    }
    return x*rep_jijo(y,mod-2)%mod;
}
int main(){
    string s;
    cin >> s;
    reverse(all(s));
    ll n=s.size();
    vector<ll>a(n);
    rep(i,n){
        a[i]=(s[i]-'0')*rep_jijo(10,i);
        a[i]%=2019;
    }
    vector<ll>rui(n+1);
    for(int i=0;i<n+1;i++){
        if(i==0)rui[i]=0;
        else {
            rui[i]=rui[i-1]+a[i-1];
            rui[i]%=2019;
        }
    }
    map<ll,int>mp;
    rep(i,n+1) mp[rui[i]]++;
    ll ans=0;
    for(auto p:mp){
        ans+=p.second*(p.second-1)/2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6720
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;

int calc(int a, int t, int x){
  return abs(1000 * t - x * 6 - 1000* a);
}

int main(){
  int n, t, a; cin >> n >> t >> a;
  int h[n]; REP(i, n) cin >> h[i];

  int tmp = INT_MAX, ans = -1;
  REP(i, n){
    int res = calc(a, t, h[i]);
    if(tmp > res){
      tmp = res;
      ans = i+1;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
from collections import Counter
N=int(input())
X=input()

value = int(X,2)
#print(value)
TFlist =[]
for i in range(N):
  if X[i] == '0':
  	TFlist.append(False)
  else:
    TFlist.append(True)
#print(TFlist)
p = sum(TFlist)


def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count
  
def popcount(n):
 # print("popcount",n)
  return (n  % count_ones_by_bin(n))

for i in range(N):
#  print("N", N)
  cnt = 0
  tmp = 0
  if p != 1 or (not TFlist[i]):
    if TFlist[i]: tmp = (value % (p-1) - (pow(2,(N-i-1), (p-1)))) % (p-1)
    else: tmp = (value % (p+1) + (pow(2,(N-i-1) , (p+1) ) ) ) % (p+1)    
    cnt += 1
  while tmp != 0:
    cnt+= 1
    tmp = popcount(tmp)
  print(cnt)

Measured memory_bytes: 85296
import math
N =int(input())

li = list(map(int,input().split()))

count=0
flag=False
for i in range(N):
    if i != 0:
        if li[i] == li[i - 1]:
            if flag==False:
                count += 1
                flag = True
            else:
                flag = False
        else:
            flag=False
        
print(count)

Measured memory_bytes: 3188