akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i))
#define mat(type, c, m, n) vector<vector<type>> c(m, vector<type>(n));for(auto& r:c)for(auto& i:r)cin>>i;
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define each(x,y) for(auto &(x):(y))
#define var(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { cin >> first; Scan(rest...); }
#define vec(type, c, n) vector<type> c(n);for(auto& i:c) cin>>i;
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define em emplace
#define pb pop_back
#define fi first
#define se second
#define get(a, i) get<i>(a)
#define mt make_tuple
inline string zero(int a,string s,char c='0'){return string(a-len(s),c)+s;}
inline string zero(int a,int t,char c='0'){return zero(a, to_string(t), c);}
inline string zero(int a,ll t,char c='0'){return zero(a, to_string(t), c);}
#define mini min_element
#define maxi max_element
#define sum accumulate
#define chmax(a,b) if(a<b)a=b
#define chmin(a,b) if(a>b)a=b
template <class T> inline void print(T t){cout << t << endl;}
template <class H, class... T> inline void print(H h, T... t){cout << h << " ";print(t...);}
int main() {
	var(int, k);
	print((k / 2) * ((k + 1) / 2));
	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
 
import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
S = input()
target = 'keyence'
 
for i in range(len(target)+1):
    a = target[:i]
    b = target[i:]
    if re.match('^' + a + '.*' + b + '$', S):
        print('YES')
        exit()
print('NO')

Measured memory_bytes: 5476
N = int(input())
C = list(input())
l = 0
r = N-1
ans = 0
while (r-l) > 0:
    if C[l] == "W" and C[r] == "R":
        C[l], C[r] = C[r], C[l]
        l += 1
        r -= 1
        ans += 1
        continue
    if C[l] == "R":
        l += 1
    if C[r] == "W":
        r -= 1
print(ans)

Measured memory_bytes: 10696
#include <iostream>
using namespace std;
int main(void){
    int n, m, l;
    long long t;
    cin>> n >> m >> l;
    int A[n][m], B[m][l];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>A[i][j];
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<l;j++){
            cin>>B[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<l;j++){
            t=0;
            for(int k=0;k<m;k++){
                t+=A[i][k]*B[k][j];
            }
            if(j==0) cout<<t;
            else cout<<" "<<t;
        }
        cout<<endl;
    }
    // Your code here!
     
}


Measured memory_bytes: 3164
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
int main(void){
    int h, a;
    cin >> h >> a;
    int ans = h/a;
    if(h % a != 0){
        ans++;
    }
    cout << ans << endl;
}


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

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

const double PI = 3.141592653589793238463;

using namespace std;

const int MAXN = 1000500;
// const int MAXN = 1050;
// const long long int mod = 1000003;
//const int MAXVALUE = 1000000500;
//const long double EPS = 1e-7;

i64 mod = 1000000009;

i64 n, m, r;
i64 a[MAXN];

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

	cout.precision(16);

	cin >> n >> m;
	i64 s = 0;

	for (int i = 0; i < m; ++i) {
		cin >> r;
		s += r;
	}

	if (s > n) {
		cout << -1 << endl;
	}
	else {
		cout << n - s << endl;
	}

	//a.resize(n + 1);
	//dp.assign(n + 1, -1);	

	return 0;
}

Measured memory_bytes: 3196
#include<iostream>
#include<string>
#include<cmath>
#include<iomanip>

using namespace std;

int main() {
	double n, k;
	cin >> n >> k;
	double ans = 0;
	for (double i = 1; i <= n; i++) {
		if (i >= k)ans += (1.0 / n);
		else {
			double tmp = 0;
			if (log2((k / i)) == (int)log2(k / i)) {
				tmp = log2(k / i);
			}
			else {
				tmp = (int)log2(k / i) + 1;
			}
			ans += (1.0 / n) * pow(0.5, tmp);
		}
	}
	cout << setprecision(11) << ans << endl;
	return 0;
}

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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define sint int32_t
#define int long long int
#define all(v) v.begin() , v.end()
#define vii vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int32_t main()
{   fastio;

    int t;
    cin>>t;
    if(t >= 30) cout<<"Yes\n";
    else cout<<"No\n";

}

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  bool ans = true;
  int n;
  cin >> n;
  int h[n];
  for(int i = 0;i<n;i++) cin >> h[i];
  int min = 10*10*10*10*10*10*10*10*10;
  for(int i = n-1; i >= 0; i--){
    if(h[i] < min) min = h[i];
    else if(h[i] > min+1) {ans = false; break;}
  }
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int len;
    scanf("%d",&len);
    static char s[105];
    scanf("%s",s);
    deque<char > deq;deq.clear();
    for(int i=0;i<len;i++) deq.push_back(s[i]);
    stack<char> ss;
    for(int i=0;i<len;i++)
    {
        if(s[i]==')'){
            if(!ss.empty() && ss.top()=='(') ss.pop();
            else deq.push_front('(');
        }else if(s[i]=='('){
            ss.push(s[i]);
        }
    }
    if(!ss.empty())
        while(!ss.empty()) {ss.pop();deq.push_back(')');}
    for(deque<char>::iterator ite=deq.begin();ite!=deq.end();ite++)
    {
        printf("%c",*ite);
    }
    puts("");
    return 0;
}


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

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

A.sort(reverse=True)

cnt = 0
x = [0] * 2

i = 0

while i < N-1:
  #print(i)
  if A[i] == A[i+1]:
    x[cnt] = A[i]
    i += 2
    cnt += 1
  else:
    i += 1
  
  if cnt >= 2:
    break
  
print(x[0]*x[1])

  

Measured memory_bytes: 62704
from functools import reduce
from operator import and_, or_

N = int(input())
S, T, U, V = [[int(a) for a in input().split()] for _ in range(4)]
X = [[U[i] & V[j] if S[i] and T[j] else U[i] if T[j] else V[j] if S[i] else U[i] | V[j] for j in range(N)] for i in range(N)]
m = (1 << 64) - 1

for _ in range(2):
    A1 = [[m] * N for _ in range(N)]
    A2 = [[m] * N for _ in range(N)]
    for i in range(N-1)[::-1]:
        for j in range(N):
            A2[i][j] = A2[i+1][j] & X[i+1][j]

    for i in range(N):
        a = ~U[i] | reduce(or_, X[i])
        for j in range(N):
            if i:
                A1[i][j] = A1[i-1][j] & X[i-1][j]
            if S[i] and not T[j]:
                X[i][j] |= ~(A1[i][j] & A2[i][j] | a)
            a |= X[i][j]
    
    X = [[X[j][i] for j in range(N)] for i in range(N)]
    S, T, U, V = T, S, V, U

if [reduce(or_ if S[i] else and_, x) for i, x in enumerate(X)] != U or [reduce(or_ if T[j] else and_, x) for j, x in enumerate(zip(*X))] != V:
    print(-1)
    exit()

for x in X:
    print(*x)

Measured memory_bytes: 183312
#include<cstdio>
#include<cstdlib>
using namespace std;
int field[2][5001] = {0};
int main(void){
    int current = 1;
    int n_a,n_b; scanf("%d%d",&n_a,&n_b);
    int a[5001]; for(int i = 1;i <= n_a;i++) scanf("%d",&a[i]);
    int b[5001]; for(int i = 1;i <= n_b;i++) scanf("%d",&b[i]);
    for(int i = 1;i <= n_a;i++){
        for(int j = 1;j <= n_b;j++){
            field[current][j] = field[abs(current-1)][j];
            if(a[i] == b[j] && field[current][j] <= field[abs(current-1)][j-1]+1) field[current][j] = field[abs(current-1)][j-1]+1;
        }
        current = 1-current;
    }
    int max = 0;
    for(int i = 0;i <= 1;i++){
        for(int j = 1;j <= n_b;j++){
            if(max <= field[i][j]) max = field[i][j];
        }
    }
    printf("%d\n",max);
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()


int main(){
    int N;
    cin>>N;
    vector<int> A(N);
    rep(i,N)cin>>A[i];
    ll Co=0,Bp=1;

    for(int memo=1;memo<N;memo++){
        bool t=true;
        for(int i=Bp;i<=N;i++){
            if(A[i-1]==memo){
                Co+=(i-Bp);
                Bp=i+1;
                t=false;
                break;
            }
        }
        if(t){
            if(memo==1){
                cout<<-1<<endl;
                return 0;
            }else{
                if(Bp<=N)Co+=(N-Bp+1);
                break;
            }
        }
    }

    if(Co==N)cout<<-1<<endl;
    else{
        cout<<Co<<endl;
    }

    return 0;
}

//a=97,z=122

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <limits>
#include <set>
#include <iomanip>
 
int main()
{
    std::array<long double, 1001> table = {0.0};
    for (int i = 1; i < 1001; i++) {
        table[i] = static_cast<long double>(i + 1) / 2;
    }
 
    int n{}, k{};
    std::cin >> n >> k;
    std::vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        std::cin >> nums[i];
    }
 
    long double result{};
    for (int i = 0; i < k; i++) {
        result += table[nums[i]];
    }
    auto tmp = result;
    for (int i = 1; i <= n - k; i++) {
        tmp = tmp - table[nums[i - 1]] + table[nums[i + k - 1]];
        if (tmp > result) {
            result = tmp;
        }
    }
 
    printf("%.10Lf\n", result);
    
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
  int money,a,ureshisa500=0,ureshisa5=0;
  scanf("%d",&money);
  
  ureshisa500+=money/500;
  a=money%500;
  ureshisa5+=a/5;
  
  printf("%d",ureshisa500*1000+ureshisa5*5);
  
 return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

map<int, int> mp;
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, T; cin >> N >> T;
    int A[100010];
    rep(i, N) cin >> A[i];
    int left = 0, right = 0;
    while(left < N) {
        while (right + 1 < N && A[left] < A[right + 1]) {
            right++;
            mp[A[right] - A[left]]++;
        }
        left = right + 1;
        right = left;
        //cout << left << " " << right << endl;
    }
    int ans = 0;
    int mx = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        if (mx < itr->first) {
            mx = itr->first;
            ans = itr->second;
        }
    }
    cout << ans << endl;

    return 0;
}


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

#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=1e5+5;
int a[N],n,up[N],down[N],dp[N];

int main()
{
	//freopen("1.in","r",stdin);
	int n;cin>>n;
	rep(i,1,n)scanf("%d",a+i);
	dp[1]=up[1]=down[1]=1;
	rep(i,2,n)
	{
		up[i]=a[i]>=a[i-1]?up[i-1]:i;
		down[i]=a[i]<=a[i-1]?down[i-1]:i;
		dp[i]=dp[min(up[i],down[i])-1]+1;
	}
	cout<<dp[n];
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
const int N=17;

int n,m,G[N][N],g[1<<N],f[1<<N][N],sum=0;

int main() {
	cin>>n>>m;
	for(int i=1,a,b,c;i<=m;i++) {
		cin>>a>>b>>c;--a,--b;sum+=c;
		G[a][b]=G[b][a]=c;
		for(int j=0;j<(1<<n);j++)
			if((j>>a&1)&&(j>>b&1)) g[j]+=c;
	}
	memset(f,-1,sizeof(f));
	f[1][0]=0;
	for(int i=1;i<(1<<n);i++)
		for(int j=0;j<n;j++)
			if(~f[i][j]) {
				for(int k=0;k<n;k++)
					if(!(i>>k&1)&&G[j][k]) f[i|(1<<k)][k]=max(f[i|(1<<k)][k],f[i][j]+G[j][k]);
				for(int all=((1<<n)-1)^i,k=all;k;k=(k-1)&all)
					f[i|k][j]=max(f[i|k][j],f[i][j]+g[k|(1<<j)]);
			}
	cout<<sum-f[(1<<n)-1][n-1];
	return 0;
}


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




int main() {
 long long N,c=1;
  cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin>>a.at(i);
    if(a.at(i)==c){
      c++;
    }
  }
  if(c!=1){
    cout<<N-c+1;
  }
  else{
    cout<<-1;
  }
  
}


Measured memory_bytes: 1024
from collections import defaultdict
s = input()
s = s[::-1]

app = [0 for _ in range(13)]

for i in range(len(s)):
    tmp_dic = [0 for _ in range(13)]
    if i == 0:
        if s[i] != '?':
            tmp_dic[int(s[i])]+= 1
        else:
            for j in range(10):
                tmp_dic[j] += 1

    else:
        if s[i] != '?':
            tmp = int(s[i]) * pow(10, i, 13)
            for j in range(13):
                tmp_dic[(tmp+j)%13] += app[j] % (10**9+7)

        else:
            for j in range(10):
                tmp = int(j) * pow(10, i, 13)
                for k in range(13):
                    tmp_dic[(tmp+k)%13] += app[k] % (10**9+7)

    app = tmp_dic
    # print(app)

print(app[5] % (10**9+7))

Measured memory_bytes: 74716
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int N, H[100], h_max = 0;
    cin >> N;
    REP(i, N) {
        cin >> H[i];
        h_max = max(h_max, H[i]);
    }

    bool under;
    int ans = 0;
    FOR(i, 1, h_max + 1) {
        under = true;
        REP(j, N) {
            if (H[j] < i) {
                under = true;
            }
            else if (under) {
                under = false;
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100000000
#define MAX 101

int n,M[MAX][MAX];
 
void dijkstra(){
  int minv,i,v,u;
  int d[MAX],color[MAX];
 
  for(i=0;i<n;i++){
    d[i] = N;
    color[i] = 0;
  }
   
  d[0] = 0;
  color[0] = 1;
  while(1){
    minv = N;
    u = -1;
    for(i=0;i<n;i++){
      if(minv>d[i] && color[i]!=2){
    u = i;
    minv = d[i];
      }
    }
    if(u == -1) break;
    color[u] = 2;
    for(v = 0; v < n; v++){
      if(color[v] != 2 && M[u][v] != N){
    if(d[v] > d[u] + M[u][v]){
      d[v] = d[u] + M[u][v];
      color[v] = 1;
    }
      }
    }
  }
  for(i = 0; i < n; i++){
    printf("%d ",i);
    if(d[i] == N){
      printf("1\n");
    }
      else printf("%d\n",d[i]);
     
  }
}
 
int main(){

  int i,j,u,k,v,c;
 
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    for(j = 0;j < n; j++){
      M[i][j] = N;
    }
  }
  for(i = 0; i < n; i++){
    scanf("%d %d",&u,&k);
    for(j = 0; j < k; j++){
      scanf("%d %d",&v,&c);
      M[u][v] = c;
    }
  }
   
  dijkstra();
  return 0;
}

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

int main() {
  string s;
  cin >> s;
  if (s.back() == '2' || s.back() == '4' || s.back() == '5' ||
      s.back() == '7' || s.back() == '9') {
    cout << "hon" << endl;
  } else if (s.back() == '0' || s.back() == '1' || s.back() == '6' ||
             s.back() == '8') {
    cout << "pon" << endl;
  } else {
    cout << "bon" << endl;
  }
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,n,m,pas1,pas2,g[100009];
bool bo[100009];
string s;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(b=1; b<=m; b++){
		cin>>c>>s;
		if(s=="AC"){
		if(bo[c]==0){
			bo[c]=1;
			pas1++;
			pas2+=g[c];
		}
		}else{
			g[c]++;
		}
	}
	cout<<pas1<<" "<<pas2;
	return 0;
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int3(n, a, b);
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }

    if (n != 1) {
        cout << max(abs(data[n-1] - b), abs(data[n-2] - data[n-1])) << endl;
    } else {
        cout << abs(data[n-1]-b) << endl;
    }

    return 0;
}



Measured memory_bytes: 256
#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 <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T> inline T &chmin(T &x, const T &y){ return x = min(x, y); }
template <class T> inline T &chmax(T &x, const T &y){ return x = max(x, y); }
template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8


void mainmain(){
	int n;
	LL k;
	scanf("%d%lld", &n, &k);
	vector<pii> v(n);
	for(int i = 0; i < n; ++i){
		scanf("%d%d", &v[i].first, &v[i].second);
	}
	sort(ALL(v));
	
	for(int i = 0; i < n; ++i){
		k -= v[i].second;
		if(k <= 0){
			printf("%d\n", v[i].first);
			break;
		}
	}
}



}
int main() try{
//	ios::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){}


Measured memory_bytes: 4088
A,B,K=list(map(int,input().split()))
c=[A,B]
for i in range(K):
    if c[i%2]%2==1:
        c[i%2]-=1
    c[i%2]//=2
    c[(i+1)%2]+=c[i%2]
print('{0[0]} {0[1]}'.format(c))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define SORT(c) sort((c).begin(),(c).end())
#define dbug(x) cout<<#x<<"="<<x<<endl
#define m0(x) memset(x,0,sizeof(x))
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define reprs(i, m, n) for(int i = n; i >= m; i--)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pl;
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) is >> x;
  return is;
}


const int MAXN = 100001;
typedef pair<ll,ll> Edge; //辺の先ノード,cost
#define to first
#define cost second
vector<Edge> G[MAXN]; //始点ノード
#define A top().first
#define B top().second
int N;
ll color[MAXN];

void dijkstra(ll s) {
    fill(color,color+MAXN,-1);
    color[s] = 0;
    queue<int> pq; // greater: pair.first が小さい順
    pq.push(s); // cost, vertex
    while(!pq.empty()) {
        ll v = pq.front();
        ll cost = color[v];
        pq.pop();
        for(int i = 0; i < (int)G[v].size(); ++i) {
            Edge e = G[v][i];
            if(color[e.to]!=-1) continue;
            if(e.cost%2==0) color[e.to]=color[v];
            else color[e.to]=1-color[v];
            pq.push(e.to);
            }
        }
    }


int main() {
    cin>>N;
    for (int i = 0; i < N-1; ++i) {
        ll a,b,cost; cin>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
        G[b].push_back(Edge(a,cost));
    }
    dijkstra(1); // 始点 0 からの dist を計算

    reps(i,1,N+1){
      std::cout << color[i] << '\n';
    }
}


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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007;

int main(){
    
    int X,A;cin>>X>>A;
    if(X<A) cout<<0<<endl;
    else cout<<10<<endl;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double pi=acos(-1.0);

LL read(){
	LL x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}
struct node{
    LL x,y;
    double k;
}a[maxn];

int cmp(node a,node b){
	return a.k<b.k;
}

int main(){
    int m,n,now;
    LL nowx=0,nowy=0,ans=0;
    n=read();
    for(register int i=1;i<=n;i++){
		a[i].x=read();a[i].y=read();
		a[i].k=atan2(a[i].y,a[i].x);
		//cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].k<<endl;
	}
	sort(a+1,a+n+1,cmp);
	for(register int i=1;i<=n;i++){
		a[i+n].x=a[i].x;
		a[i+n].y=a[i].y;
		a[i+n].k=a[i].k+pi*2;
	}
	now=1;
    for(register int i=1;i<=n;i++){
        while(now<i+n && a[now].k-a[i].k<pi){
			nowx+=a[now].x;
			nowy+=a[now].y;
			now++;
			ans=max(ans,nowx*nowx+nowy*nowy);
        }
		nowx-=a[i].x;nowy-=a[i].y;ans=max(ans,nowx*nowx+nowy*nowy);
    }
    printf("%.11lf\n" ,sqrt(ans));
    return 0;
}

Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
x = int(input())

ans = 0
for i in range(min((x//500), a) +1):
  for j in range(min((x-500*i)//100, b) +1):
    tmp = x - (500 * i)  - (100 * j)
    if tmp % 50 == 0 and tmp // 50 <= c:
      ans += 1
    
print(ans)

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

void solve(long long N, long long K, std::vector<long long> A){
    //ll cnt = 0;
    vector<ll> cnt_list;
    sort(A.begin(), A.end());
    ll cnt = 1;
    for(ll i = 1; i <= N; ++i){
        if(A[i] == A[i-1]) cnt++;
        else{
            cnt_list.push_back(cnt);
            cnt = 1;
        }
    }
    sort(cnt_list.begin(), cnt_list.end());
    for(ll i = 1; i <= cnt_list.size(); ++i) cnt_list[i] = cnt_list[i-1] + cnt_list[i];
    if(cnt_list.size() <= K) cout << 0 << endl;
    else cout << cnt_list[cnt_list.size() - K - 1] << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, K, std::move(A));
    return 0;
}


Measured memory_bytes: 3956
#include <stdio.h>

int main(void)
{
    int n, i, flg = 0, num, sum = 0;
    scanf("%d", &n);
    int l[n];

    for (i = 0; i < n; i++) {
        scanf("%d", &l[i]);
        if (l[i] > flg) {
            flg = l[i];
            num = i;
        }
    }

    for (i = 0; i < n; i++) {
        if (i != num)
            sum += l[i];
    }

    if (l[num] < sum)
        printf("Yes");
    else
        printf("No");

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>

using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int N, M;

void dfs(int from, map<int, vector<int> >&edges, vector<int>& group, int group_idx) {
    if(group[from] > 0) return;
    group[from] = group_idx;
    for(auto to = edges[from].begin(); to!=edges[from].end(); ++to) {
        dfs(*to, edges, group, group_idx);
    }
}

int main() {
    cin >> N >> M;
    map<int, vector<int> > edges;

    REP(i, M) {
        int n1, n2, n3;
        cin >> n1 >> n2 >> n3;
        edges[n1-1].push_back(n2-1);
        edges[n2-1].push_back(n1-1);
    }

    vector<int> group(N, 0);
    int group_idx = 1;
    REP(i, N) {
        if((edges[i].size() > 0) && group[i] == 0) {
            dfs(i, edges, group, group_idx);
            group_idx++;
        }
    }

    int ans = 0;
    // cerr << "print group" << endl;
    REP(i, N) {
        if(group[i] == 0) ans++;
        // cerr << group[i] << endl;
    }

    ans += group_idx-1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 22528
#include <iostream>
#include <cstdio>
#include <iomanip>

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    double a[101];
    int i;
    double count=0.0;
    
    cin >> n;
    
    for(i=0; i<n; i++){
        cin >> a[i];
        count += (1/a[i]);
    }
    
    //cout << 1/count;
    cout << fixed << setprecision(7) << 1/count;
    
    return 0;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int           long long
#define pb            push_back
#define mp            make_pair
#define PI            3.14159265
#define M             1000000007
#define MM            998244353
#define fr            first
#define sc            second
#define all(v)        (v).begin(),(v).end()
#define rall(v)       (v).rbegin(),v.rend()
#define vc            vector
#define vi            vector<int>
#define pii           pair<int,int>
#define psi           pair<string,int>
#define pis           pair<int,string>
#define mii           map<int,int>
#define msi           map<string,int>

int solve(){
    int n,s=0; cin>>n;
    int h[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>h[i];
    }
    for (int i = 0; i < n; ++i)
    {
        int flag=1;
        for (int j = 0; j < i; ++j)
        {
            if(h[i]<h[j]){
                flag=0;
            }
        }
        if(flag) s++;
    }
    cout<<s;
}

signed main() {
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long power = 1;
		double pow = Math.pow(10, 9);
		for(int i = 1; i <= N; i++){
			power = power * i;
			power = power % ((int)pow + 7);
		}
		System.out.println(power);

	}

}

Measured memory_bytes: 21844
int main() {
  for(;;) {
    int x, y;
    scanf("%d %d\n", &x, &y);

    if (x == 0 && y == 0) {
      break;
    }

    if (x < y) {
      printf("%d %d\n", x, y);
    } else {
      printf("%d %d\n", y, x);
    }
  }
}


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

#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<
#define pb push_back
#define ar array

typedef long long ll;
typedef long double ld;
//using ll = long long;

typedef vector<int> vi;

const ld EPS = 1e-9, PI = acos(-1.);
const int INF = 0x3f3f3f3f, MOD = 1e9+7;

ll summ[200007];


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, k;
	cin >> n >> k;
	summ[0] = 0;
	for(int i=1; i<=200001; ++i){
		summ[i] = summ[i-1] + i; 
	}
		
	ll ans = 0;
	for(int i=k; i<=(n+1); ++i){
		ll minsum = summ[i-1];
		ll maxsum = summ[n] - summ[n-i];
		ans += (maxsum - minsum + 1);
		ans %= MOD;
	}
	cout << ans%MOD << endl;
}


Measured memory_bytes: 5212
#include<iostream>
#include<algorithm>
using namespace std;
int n,a;
int main(){
	cin>>n;
	long long ans=0;
	int bef=0;
	for(int i=0;i<n;i++){
		cin>>a;
		if(bef==1&&a>0)a--,ans++;
		bef=a%2;
		ans+=a/2;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int A,B,c;
  scanf("%d %d",&A,&B);
  if(A%2==0&&B%2==0)
   {

    c = (A+B)/2;
  printf("%d\n",c);
   }
   else if(A%2!=0&&B%2!=0)
   {
       c = (A+B)/2;
       printf("%d\n",c);
   }
  else printf("IMPOSSIBLE\n");






}


Measured memory_bytes: 128
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    string sb = to_string(b);
    int c = a * pow(10, sb.size()) + b;
    for (int i = 4; i <= (int)sqrt(c) + 1; i++) {
        if (c == i * i) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


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

#define int long long

using namespace std;

class Solver {
};

signed main() {
	int q;
	cin >> q;

	vector<string> qs(q);
	for (int i = 0; i < q; i++) {
		cin >> qs[i];
	}

	vector<int> smalls({ 5000000,2500000,1250000,625000,312500,156250,78125 });
	for (int i = 0; i < q; i++) {
		bool minus = false;
		int checker = 1 << 24;
		int m = 0;
		int small = 0;
		int smallCnt = 0;
		for (int j = 0; j < qs[i].size(); j++) {
			int val;
			if ('a' <= qs[i][j] && qs[i][j] <= 'f') {
				val = 10 + (int)(qs[i][j] - 'a');
			}
			else val = qs[i][j] - '0';

			int div = 1 << 3;
			for (int k = 0; k < 4; k++) {
				if ((val & div) > 0) {
					if (j == 0 && k == 0) {
						minus = true;
					}
					else {
						if (checker > 0) {
							m += checker;
						}
						else {
							small += smalls[smallCnt];
						}
					}
				}
				if (checker == 0)smallCnt++;
				checker /= 2;
				div = div / 2;
			}
		}
		if (minus)cout << '-';
		string small_str = "";
		for (int j = 0; j < 7; j++) {
			int num = small % 10;
			if (num > 0 || small_str.size() > 0)small_str += (char)(num + '0');
			small /= 10;
		}
		if (small_str.size() == 0)small_str += '0';
		reverse(small_str.begin(), small_str.end());
		cout << m << '.' << small_str << endl;
	}
}


Measured memory_bytes: 3296
#include <iostream>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <math.h>
#include <map>
#include <queue>
#include <string>
using namespace std;

int w,h,V[30][31],H[31][30],field[30][31];
int sx,sy,gx,gy,d[30][30],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const int INF=9999999;
typedef pair<int,int> P;

int bfs(){
    queue<P> que;
    for(int i=0;i<h;i++){
	for(int j=0;j<w;j++)d[i][j]=INF;
    }
    que.push(P(sy,sx));
    d[sx][sy]=0;
    while(que.size()){
	P p=que.front(); que.pop();
	if(p.first==gx&&p.second==gy)break;
	for(int i=0;i<4;i++){
	    int nx=p.first+dx[i],ny=p.second+dy[i];
	    if(0<=nx&&nx<h&&0<=ny&&ny<w&&d[nx][ny]==INF&&(i==0&&H[nx][ny+1]==0||i==1&&V[nx+1][ny]==0||i==2&&H[nx+1][ny+1]==0||i==3&&V[nx+1][ny+1]==0)){
		que.push(P(nx,ny));
		d[nx][ny]=d[p.first][p.second]+1;
	    }
	}
    }
    return d[gx][gy];
}

int main() {
    while(cin>>w>>h){
    	if(w+h==0)return 0;
    	for(int i=0;i<h;i++){
    		for(int j=0;j<w-1;j++)cin>>V[i+1][j+1];
    		if(i!=h-1)for(int j=0;j<w;j++)cin>>H[i+1][j+1];
    	}
    	sx=0;sy=0;gx=h-1;gy=w-1;
    	if(bfs()==INF)cout<<0<<endl;
    	else cout<<bfs()+1<<endl;
    }
}  

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>

using namespace std;

int main(){
  
  int N, W; cin >> N >> W;

  vector <long long> w(N), v(N); 
  for (int i = 0; i < N; i++){
    cin >> w[i] >> v[i];
  }
  
  long long DP[N][W + 1];

  for (int i = 0; i < W + 1; i++){
    if (i < w[0]) DP[0][i] = 0;
    else DP[0][i] = v[0];
  }

  

  for (int i = 1; i < N; i++){
    for (int j = 0; j < W + 1; j++){
      if (j < w[i]){
        DP[i][j] = DP[i - 1][j];
      }else{
        DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - w[i]] + v[i]);
      }
    }
  }
  cout << DP[N - 1][W] << endl;
  



  return 0;
}


Measured memory_bytes: 78336
N = int(input()) #N = 3
D, X = map(int, input().split()) #D = 7, X = 1
A = [int(input()) for i in range(N)] #A = [2,5,10]

choco = 0
for days in range(N):
    Ai = A[days]
    eatDay = 1
    while eatDay <= D:
        choco += 1
        eatDay += Ai

print(choco + X)



Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define log(x) cout<<x<<endl
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
using Graph=vector<vector<int>>;

int gcd(lint x, lint y){
  return y==0 ? x:gcd(y,x % y);
}

int digsum(int n) {
  int res = 0;
  while(n > 0) {
    res += n%10;
    n /= 10;
  }
  return res;
}

int dignum(int n) {
  int res = 0;
  while(n > 0) {
    res++;
    n /= 10;
  }
  return res;
}

int stringcount(string s, char c) {
  return count(s.cbegin(), s.cend(), c);
}

int lcm(lint x, lint y){
  return x/ gcd(x, y) * y;
}

int combi(int n, int r){
  int num = 1;
  for(int i = 1; i <= r; i++){
    num = num * (n - i + 1) / i;
  }
  return num;
}

int main(){
  string s,t;
  cin>>s>>t;
  int n;
  int co=0;
  n=s.size();
  rep(i,n){
    if(s[i]!=t[i]) co++;
  }
  cout<<co<<endl;
}

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

int main() {
  int n;
  cin >> n;
  vector<long> a(3 * n), former(n + 1), latter(n + 1);
  for (int i = 0; i < 3 * n; i++) cin >> a.at(i);
  priority_queue<long> q, q2;
  for (int i = 0; i < n; i++) {
    former.at(0) += a.at(i);
    q.push(-a.at(i));
  }
  for (int i = 0; i < n; i++) {
    long t = -q.top();
    q.pop();
    former.at(i + 1) = former.at(i) + a.at(n + i) - t;
    q.push(-a.at(n + i));
  }
  for (int i = 3 * n - 1; i >= 2 * n; i--) {
    latter.at(0) += a.at(i);
    q2.push(a.at(i));
  }
  for (int i = 2 * n - 1; i >= n; i--) {
    long t = q2.top();
    q2.pop();
    latter.at(2 * n - i) = latter.at(2 * n - i - 1) + a.at(i) - t;
    q2.push(a.at(i));
  }
  long ans = -1l << 60, index = 0;
  for (int i = n; i >= 0; i--) {
    if (latter.at(n - i) < latter.at(index)) index = n - i;
    ans = max(ans, former.at(i) - latter.at(index));
  }
  cout << ans << endl;
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll H, W, M;
    cin >> H >> W >> M;
    vec S(H, 0), T(W, 0);
    set<pll> U;
    set<pll> B;
    REP(i,0,M) {
        ll p, q;
        cin >> p >> q;
        --p; --q;
        ++S[p];
        ++T[q];
        U.insert({p, q});
    }

    ll ms = 0, mt = 0;
    REP(i,0,H) ms = MAX(ms,S[i]);
    REP(i,0,W) {
        mt = MAX(mt,T[i]);
        B.insert({T[i],i});
    }
    
    ll m = ms + mt;
    ll ans = 0;
    bool f = false;
    REP(i,0,H) {
        ll a = m - S[i];
        auto from = B.lower_bound({a, 0});
        auto to = B.lower_bound({a, INF});
        if(from != to) {
            
            for(auto it = from; it != to; ++it) {
                ll c = it->second;
                if(U.count({i, c})) ans = MAX(ans,m-1);
                else {
                    ans = MAX(ans,m);
                    f = true;
                    break;
                } 
            }
            
        }
        if(f) break;
    }
    PR(ans);


    return 0;
}

/*



*/

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 300005;

/* ...o(^-^)o... */

const lint mod = MOD;
class mint{
    public:
        long long x;

    constexpr mint(long long _x = 0) : x((_x%mod+mod)%mod) {}
    constexpr mint operator-() const{
        return mint(-x);
    }
    constexpr mint& operator+=(const mint& a){
        if((x += a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator-=(const mint& a){
        if((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator*=(const mint& a){
        (x *= a.x) %= mod;
        return *this;
    }
    constexpr mint operator+(const mint& a) const{
        mint res(*this);
        return res+=a;
    }
    constexpr mint operator-(const mint& a) const{
        mint res(*this);
        return res-=a;
    }
    constexpr mint operator*(const mint& a) const{
        mint res(*this);
        return res*=a;
    }
    constexpr mint pow(long long x) const{
        if(!x) return 1;
        mint a = pow(x>>1);
        a *= a;
        if(x&1) a *= *this;
        return a; 
    }
    constexpr mint inv() const{
        return pow(mod-2);
    }
    constexpr mint& operator/=(const mint& a){
        return (*this) *= a.inv();
    }
    constexpr mint operator/(const mint& a) const{
        mint res(*this);
        return res/=a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x; return os;
    }
};

int main(){
    lint n, k; cin >> n >> k;

    vector<mint> g(k+1);
    for(lint m = k; m >= 1; m--){
        if(m*2 > k){
            mint c = k / m;
            g[m] = c.pow(n);
        }
        else{
            mint c = k / m;
            g[m] = c.pow(n);
            for(lint p = m*2; p <= k; p += m){
                g[m] -= g[p];
            }
        }
    }

    mint ans = 0;
    for(lint m = 1; m <= k; m++){
        ans += mint(m) * g[m];
    }

    out(ans);
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
#define Fr(i,a,b) for(int i=(a);i<=(int)(b);++i)
#define Dr(i,a,b) for(int i=(a);i>=(int)(b);--i)
using namespace std;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
#define debug(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define bug(x) cout<<#x<<"="<<x<<" "
int main() {
	int a,b,c;
	cin>>a>>b>>c;
	if(a*b<c)cout<<1ll*a*b<<endl;
	else cout<<c<<endl;
}

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

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())

#define ll long long
#define ALL(a)  (a).begin(),(a).end()

#define pb(a) push_back(a)

int a,b;
string s;

int main(){
  cin>>a;
  int ans=(a-2)*180;
  
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let abs = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun a b -> a, b in
  Array.sort (fun (a, _) (a', _) -> compare a a') abs;
  Printf.printf "%d\n" @@ fst @@ Array.fold_left (fun (acc, n) (a, b) ->
    (acc + a * min n b, n - min n b)) (0, m) abs


Measured memory_bytes: 6784
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    s = S()
    t = S()
    if s+t == t[::-1]+s[::-1]:
        print("YES")
    else:
        print("NO")

#B
def B():
    n = I()
    for i in range(int(n**0.5)+2)[::-1]:
        if i*i <= n:
            print(i*i)
            quit()
#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()


Measured memory_bytes: 38556
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for(int i = 0; i < s.size(); i++){
    if(s[i] != t[i]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3856
#include<stdio.h>
#define rep(i,a,b) for(int i = a;i <= b;i++)
int main(void){
  int a,b; scanf("%d%d",&a,&b);
  int cnt = 0;
  rep(i,0,1000){
    if((i>=12.5*a)&&(i>=10*b)&&(i<12.5*(a+1))&&(i<10*(b+1))){
      printf("%d",i);
      cnt += 1;
      break;
    }
  }
  if(cnt == 0){
    printf("-1");
  }
  return 0;
}


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

#define pb push_back
#define mp make_pair
#define fs first
#define se second

typedef long long LL;

int n;
int a[223456];

int main() {
  //  freopen("test.txt","r",stdin);
    cin >> n ;
    for (int i=1 ; i <= n; i++) cin >> a[i] ;
    if ( n == 1) {
        cout << a[1];
        return 0;
    }
    if ( n % 2 == 0) {
        for (int i = n; i >= 2 ; i--) {
            if ( i % 2 == 0 ) cout << a[i] << " ";
        }
        cout << a[1] << " ";
        for (int i = 3 ; i<= n ; i++) {
            if ( i % 2 == 1) cout << a[i] << " ";
        }
    } else {
        for (int i = n ; i >= 3 ; i--) {
            if ( i % 2 == 1) cout << a[i] << " ";
        }
        cout << a[1] << " ";
        for (int i = 2 ; i <= n ; i++) {
            if ( i % 2 == 0) cout << a[i] << " ";
        }
    }
}


Measured memory_bytes: 2944
while 1:
    n = int(raw_input())
    if n == 0:
        break
    A = [0] * n
    for i in xrange(n):
        A[i] = int(raw_input())
    for i in xrange(1, len(A)):
        A[i] = max(A[i - 1] + A[i], A[i])
    print max(A)

Measured memory_bytes: 4288
#include<stdio.h>
#include<string.h>
int main(){
	double w,h,y,x;
	while(~scanf("%lf%lf%lf%lf",&w,&h,&x,&y)){
		int vis=0;
		if((x*2==w)&&(y*2==h))
		vis=1;
		double sum=(w*h)/2.0;
		printf("%.12lf %d\n",sum,vis);
	}
}

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

int main(){
	
	string a; cin>>a;
	sort(a.begin(), a.end());
	if (a[0]==a[1] && a[2]==a[3]&&a[0]!=a[2]) cout<<"Yes";
	else cout<<"No";
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public void main(Scanner sc) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.close();

        int ans = 1;
        for (int i = 1; i * i <= m; i++) {
            if (m % i != 0) {
                continue;
            }

            if (i >= n) {
                ans = Math.max(ans, m / i);
            } else if (m / i >= n) {
                ans = Math.max(ans, i);
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
    }
}


Measured memory_bytes: 22612
import math


def resolve():
    a, b, x = map(float, input().split())
    h = x / (a ** 2)
    if h >= b / 2:
        degree = math.degrees(math.atan(2 * (b - h) / a))
    else:
        degree = math.degrees(math.atan(b ** 2 / (2 * a * h)))
    print(degree)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3060