akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define SZ(container) ((int)container.size())

const int INF = 1<<30;
int LIS(vector<int> v){
	vector<int> dp(v.size(), INF);
	REP(i, v.size()) *lower_bound(dp.begin(), dp.end(), v[i]) = v[i]; // upper_bound にするとstrict increaseではない部分列
	return lower_bound(dp.begin(), dp.end(), INF) - dp.begin(); // ここはlower_boundのままにする
}

int n, m;

main(){
	while(cin >> n, n){
		vector<pii> x;
		REP(i, n){
			int h, r;
			cin >> h >> r;
			x.push_back(pii(h, -r));
		}
		cin >> n;
		REP(i, n){
			int h, r;
			cin >> h >> r;
			x.push_back(pii(h, -r));
		}
		sort(ALL(x));
		vector<int> lis;
		REP(i, x.size()) lis.push_back(-x[i].second);
		cout << LIS(lis) << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)

// cout<<fixed<<setprecision(15)

//点またはベクトル
class Point{
  public:
  double x,y;
  
  Point(double x=0, double y=0): x(x),y(y) {}
  
  Point operator+(Point p){return Point(x+p.x,y+p.y);}
  Point operator-(Point &p){return Point(x-p.x,y-p.y);}
  Point operator*(double a){return Point(a*x,a*y);}
  Point operator/(double a){return Point(x/a,y/a);}
  
  //絶対値とその二乗 p.norm()など使用
  double abs(){return sqrt(norm());}
  double norm(){return x*x+y*y;}
  
  bool operator<(const Point &p) const{
    return x != p.x ? x<p.x : y<p.y;
  }
  
  bool operator==(const Point &p) const{
    return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
  }
};
typedef Point Vector;

//直線
struct Segment{Point p1,p2;};
typedef Segment Line;

//円
class Circle{
public:
  Point c;
  double r;
  Circle(Point c=Point(), double r=0.0): c(c), r(r) {}
};

//多角形
typedef vector<Point> Polygon;

//内積
double dot(Vector a,Vector b){
  return a.x*b.x+a.y*b.y;
}

//外積
double cross(Vector a,Vector b){
  return a.x*b.y-a.y*b.x;
}

//直交判定
bool isOrthgonal(Vector a,Vector b){
  return equals(dot(a,b), 0.0);
}

//平行判定
bool isParallel(Vector a,Vector b){
  return equals(cross(a,b), 0.0);
}

//射影
Point project(Segment s,Point p){
  Vector base=s.p2-s.p1;
  double r=dot(p-s.p1,base)/base.norm();
  return s.p1+base*r;
}

//反射
Point reflect(Segment s,Point p){
  return p+(project(s,p)-p)*2.0;
}

int main(){
  Point p1,p2;
  cin>>p1.x>>p1.y>>p2.x>>p2.y;
  Segment s;
  s.p1=p1,s.p2=p2;
  
  int q;
  cin>>q;
  
  Point p,r;
  rep(i,q){
    cin>>p.x>>p.y;
    r=reflect(s,p);
    cout<<fixed<<setprecision(15)<<r.x<<" "<<r.y<<endl;
  } 
      
  return 0;
}


Measured memory_bytes: 3268
def int_input():
    line = input()
    return [int(x) for x in line.split()]

n, m = int_input()
cities = {}

for i in range(n):
    cities[i+1] = []

for i in range(m):
    a, b = int_input()
    cities[a].append(b)
    cities[b].append(a)

for i in sorted(cities.keys()):
    print(len(cities[i]))


Measured memory_bytes: 3060
#include <cstdio>
#define N 200005
int n, m, x, y, s, a[N], c[N], v[N];

void f(int p) {
	int t = p - c[p];
	if(t>0) {
		if(v[t]==0) s++;
		v[t]++;
	}
	c[p]++;
}

void g(int p) {
	int t = p - c[p] + 1;
	if(t>0) {
		if(v[t]==1) s--;
		v[t]--;
	}
	c[p]--;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) {
		scanf("%d", a+i);
		f(a[i]);
	}
	while(m--) {
		scanf("%d%d", &x, &y);
		g(a[x]);
		f(y);
		a[x] = y;
		printf("%d\n", n-s);
	}
	return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <stack>
#define rep(i,n) for(int i=0; i<(n); ++i)

using ll = long long;

int main() {
    ll n; std::cin >> n;
    std::stack<char> st;
    while (n > 0) {
        --n;
        ll m = n % 26;
        st.push('a'+m);
        n /= 26;
    }

    while (!st.empty()) {
        std::cout << st.top();
        st.pop();
    }
    std::cout << '\n';

    return 0;
}


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

Measured memory_bytes: 3912
using System;
namespace abc
{
    class program
    {
        static void Main()
        {
            int x, i = 0;
            x = int.Parse(Console.ReadLine());
            while(x != 0)
            {
                i++;
                Console.WriteLine("Case {0}: {1}", i, x);
                x = int.Parse(Console.ReadLine());
            }
        }
    }
}


Measured memory_bytes: 15784
//19
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int t[4]={};
  for(;;){
    int e[3];
    cin>>e[0]>>e[1]>>e[2];
    sort(e,e+3);
    if(e[2]>=e[0]+e[1])break;
    t[0]++;
    int c=e[2]*e[2]-e[1]*e[1]-e[0]*e[0];
    if(c>0){
      t[1]++;
    }else if(c==0){
      t[2]++;
    }else{
      t[3]++;
    }
  }
  cout<<t[0]<<' '<<t[2]<<' '<<t[3]<<' '<<t[1]<<endl;
  return 0;
}

Measured memory_bytes: 1180
N=int(input())
D1,D2=[],[]
for i in range(N):
    d1,d2=map(int,input().split())
    D1.append(d1)
    D2.append(d2)

flag=False
for i in range(2,N):
    if D1[i-2]==D2[i-2] and D1[i-1]==D2[i-1] and D1[i]==D2[i]:
        flag=True
        break

if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 62532
import math
a,b,h,m=map(int,input().split())
hkaku=(h+m/60)*30
mkaku=m/60*360
if abs(hkaku-mkaku)>180:
    kakudo=360-abs(hkaku-mkaku)
else:
    kakudo=abs(hkaku-mkaku)

kakudo=math.radians(kakudo)

print(math.sqrt(a**2+b**2-2*a*b*math.cos(kakudo)))


Measured memory_bytes: 9384
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=3.1415926535897932384626433832795;
const ll INF = 1LL<<62;
const ll MINF = -1LL<<62;

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


int main() {
	IO;
	int k,n;
	cin>>k>>n;
	vector<int>t(n);
	for(int i=0;i<n;++i){
		cin>>t[i];
	}
	int mx=0;
	for(int i=0;i+1<n;++i) {
		mx=max(mx, t[i+1]-t[i]);
	}
	mx=max(t[0]+k-t.back(), mx);
	cout<<k-mx<<"\n";
	return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        var kn = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var k = kn[0];
        var n = kn[1];
        var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var res1 = a.Skip(1).Zip(a, (x, y) => x - y).Max();
        var res2 = (a.First() + k) - a.Last();
        Console.WriteLine(k - Max(res1, res2));
    }
}


Measured memory_bytes: 34780
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <algorithm>

using namespace std;

int main()
{
	int h, w;
	while(1){
		cin >> h >> w;
		if(h == 0 && w == 0) break;
		int i, j, a, b, c, ans_w=114, ans_h=514;
		a = (h * h) + (w * w);
		b = (ans_w * ans_w) + (ans_h * ans_h);
		for(i = 1; i <= 150; i++){
			if(i * i < a){
				for(j = i+1; j <= 150; j++){
					c = (i * i) + (j * j);
					if((c == a && i > h) || c > a){
						if(c < b){
							ans_h = i;
							ans_w = j;
							b = c;
						}
					} 
				}
			}
		}
		cout << ans_h << ' ' << ans_w << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int SIZE = 100010;
int f[SIZE][20], d[SIZE], dist[SIZE];
int ver[2 * SIZE], Next[2 * SIZE], edge[2 * SIZE], head[SIZE];
int T, n, m, tot, t;
queue<int> q;

void add(int x, int y, int z) {
	ver[++tot] = y; edge[tot] = z; Next[tot] = head[x]; head[x] = tot;
}
void bfs() {
	q.push(1); d[1] = 1;
	while (q.size()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = Next[i]) {
			int y = ver[i];
			if (d[y]) continue;
			d[y] = d[x] + 1;
			dist[y] = dist[x] + edge[i];
			f[y][0] = x;
			for (int j = 1; j <= t; j++)
				f[y][j] = f[f[y][j - 1]][j - 1];
			q.push(y);
		}
	}
}
int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = t; i >= 0; i--)
		if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i = t; i >= 0; i--)
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
int main() {
	
	
		cin>>n;m=n-1;
		t = (int)(log(n) / log(2)) + 1;
		for (int i = 1; i <= n; i++) head[i] = d[i] = 0;
		tot = 0;
		for (int i = 1; i<n; i++) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			add(x, y, z), add(y, x, z);
		}
		bfs();
		/*for (int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			printf("%d\n", dist[x] + dist[y] - 2 * dist[lca(x, y)]);
		}*/
		for(int i=1;i<=n;i++) 
		{
			if(dist[i]%2==0) cout<<0<<endl;
			else cout<<1<<endl;
		}
	
}

Measured memory_bytes: 11776
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const int maxN = 1e5; int n, a, b, c;
char s[maxN][3];
int kind[maxN];
int r[3][maxN + 1];

map<pair<int, int>, int> memo[maxN], path[maxN];
bool solve(int i = 0, int aa = a, int bb = b, int cc = c)
{
  if (aa < 0 || bb < 0 || cc < 0) return false;
  if (i == n) return true;
  aa = min(aa, n - i), bb = min(bb, n - i), cc = min(cc, n - i);
  if (aa == n - i && bb == n - i && cc == n - i) return true;
  pair<int, int> u = kind[i] == 0 ? make_pair(aa, bb) : kind[i] == 1 ? make_pair(aa, cc) : make_pair(bb, cc);
  if (memo[i].count(u))
    return memo[i][u];

  bool ans = false;
  if (kind[i] == 0)
  {
    bool aaa = solve(i + 1, aa + 1, bb - 1, cc);
    bool bbb = !aaa ? solve(i + 1, aa - 1, bb + 1, cc) : false;
    path[i][u] = aaa >= bbb ? 0 : 1;
    ans = max(aaa, bbb);
  }
  else if (kind[i] == 1)
  {
    bool aaa = solve(i + 1, aa + 1, bb, cc - 1);
    bool ccc = !aaa ? solve(i + 1, aa - 1, bb, cc + 1) : false;
    path[i][u] = aaa >= ccc ? 0 : 2;
    ans = max(aaa, ccc);
  }
  else
  {
    bool bbb = solve(i + 1, aa, bb + 1, cc - 1);
    bool ccc = !bbb ? solve(i + 1, aa, bb - 1, cc + 1) : false;
    path[i][u] = bbb >= ccc ? 1 : 2;
    ans = max(bbb, ccc);
  }
  return memo[i][u] = ans;
}

int main()
{
  while (scanf("%d %d %d %d", &n, &a, &b, &c) != EOF)
  {
    a = min(a, maxN), b = min(b, maxN), c = min(c, maxN);
    for (int i = 0; i < n; i++)
    {
      scanf(" %s", s[i]);
      kind[i] = !strcmp(s[i], "AB") ? 0 : !strcmp(s[i], "AC") ? 1 : 2;
      memo[i].clear(), path[i].clear();
    }
    r[0][n] = r[1][n] = r[2][n] = 0;
    for (int i = n - 1; i >= 0; i--)
      for (int j = 0; j < 3; j++)
        r[j][i] = r[j][i + 1] + (kind[i] == j);

    bool ans = solve();
    if (!ans) printf("No\n");
    else
    {
      printf("Yes\n");
      for (int i = 0, aa = a, bb = b, cc = c; i < n; i++)
      {
        aa = min(aa, n - i), bb = min(bb, n - i), cc = min(cc, n - i);
        pair<int, int> u = kind[i] == 0 ? make_pair(aa, bb) : kind[i] == 1 ? make_pair(aa, cc) : make_pair(bb, cc);
        if (kind[i] == 0)
        {
          if (path[i][u] == 0)
            aa++, bb--, printf("A\n");
          else
            aa--, bb++, printf("B\n");
        }
        else if (kind[i] == 1)
        {
          if (path[i][u] == 0)
            aa++, cc--, printf("A\n");
          else
            aa--, cc++, printf("C\n");
        }
        else
        {
          if (path[i][u] == 1)
            bb++, cc--, printf("B\n");
          else
            bb--, cc++, printf("C\n");
        }
      }
    }
  }
  return 0;
}


Measured memory_bytes: 39472
c=[list(map(int,input().split())) for _ in range(3)]
a=[0]*3
b=[0]*3
for j in range(3):
    b[j]=c[0][j]
#print(b)
for i in range(1,3):
    a[i]=c[i][0]-b[0]
#print(a)
import sys
for i in range(3):
    for j in range(3):
        if a[i]+b[j]!=c[i][j]:
            print('No')
            sys.exit()
print('Yes')



Measured memory_bytes: 3064
n,x,y = list(map(int,input().split()))
ans = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        ans[min(j-i,1+abs(x-1-i)+abs(y-1-j))-1]+=1
for num in ans:
    print(num)

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

#define rep(i,x,y) for(int (i)=(x);(i)<(y);(i)++)

int main()
{
  while(true){
    int h,w;
    cin>>h>>w;
    if(h==0&&w==0){
      break;
    }

    int minh=150;
    int minw=150;
    bool flag=false;
    rep(i,1,151){
      rep(j,i+1,151){
        if(i*i+j*j==h*h+w*w){
          if(i>h){
            minh=i;
            minw=j;
            flag=true;
          }
        }else if(i*i+j*j>h*h+w*w){
          if(minh*minh+minw*minw>i*i+j*j){
            minh=i;
            minw=j;
          }
        }
      }
      if(flag==true){
        break;
      }
    }

    cout<<minh<<" "<<minw<<endl;
  }

  return 0;
}

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

int main()
{
    string S;
  int sum=700;

  cin >> S;
  for (int i=0;i<S.size();i++){
    if(S[i]=='o'){
    sum+=100;
    } 
  }
  
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main(){

    unsigned long n = 0;
    cin >> n;
    unsigned long ans = 0;

    /*
    for(float i = 1; i <= n - 1; ++i){
        ans += i;
    }
    */

    ans = (n*(1+n))/2;
    ans -= n;


    cout << ans << endl;

}

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = n; i >= 0; --i)
#define ALL(x) (x).begin(),(x).end()
const int INF = 1'010'000'000'000'000'017LL;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0 ,1 ,0,-1};
using vint = vector<int>;
using pint = pair<int, int>;

signed main() {
	int n, x;
	cin >> n >> x;
	int sum = 0, cnt = 0;
	if (sum <= x) cnt++;
	rep(i, n) {
		int l;
		cin >> l;
		sum += l;
		if (sum <= x) cnt++;
	}
	cout << cnt << endl;
}


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

#define ll double
#define mod 1e9+7

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL)

ll dp[301][301][301];

ll solve(int one, int two, int three, int& n)
{
	if(one < 0 || two < 0 || three < 0) return 0;
	if(one == 0 && two == 0 && three == 0) return 0;
	if(dp[one][two][three] > 0) return dp[one][two][three];
	int rem = one + two + three;
	ll exp_val = n + one*solve(one-1, two, three, n) + two*solve(one+1, two-1, three, n) + three*solve(one, two+1, three-1, n);

	return dp[one][two][three] = exp_val/rem;

}

int main()
{
	int i, j, n, m, p, k, x;
	cin>>n;
	int one = 0, two = 0, three = 0;
	for(i = 0; i < n; i++)
	{
		cin>>x;
		if(x == 1) one++;
		else if(x == 2) two++;
		else three++;
	}
	memset(dp, -1, sizeof(dp));
	cout<<fixed<<setprecision(9)<<solve(one, two, three, n);
	return 0;
}


Measured memory_bytes: 216836
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

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

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

signed main() {
    int w, h, n; cin >> w >> h >> n;
    int dlx = 0, dly = 0, urx = w, ury = h;
    int x, y, a;
    rep(i,0,n) {
        cin >> x >> y >> a;
        if(a == 1) dlx = max(dlx, x);
        else if(a == 2) urx = min(urx, x);
        else if(a == 3) dly = max(dly, y);
        else if(a == 4) ury = min(ury, y);
    }
    int ans = max((ll)0, urx - dlx) * max((ll)0, ury - dly);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <string>
#define ll long long
#define ull unsigned long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define makevec(x,y,n) vector <x> y(n); for(ll i=0;i<n;i++) cin>>y[i]
#define M (ll)1000000007
#define MM (ll) 1e8
#define INF (ll) 1e18

# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)


using namespace std;


template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
bool sortbysec(const ll &a, const ll &b){
    return abs(a)>abs(b);
}

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};


struct c_h {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

ll calcpow(ll x, ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = calcpow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
    {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);

}
ll egcd(ll a, ll b, ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1;
    ll y1;
    ll g=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}


bool isprime(ll a){
bool flag=1;
for(ll i=2;i*i<=a;i++){
    if(a%i==0) {flag=0; break;}
}
return flag;
}

ll dx8[8]={1,0,-1,0,1,-1,1,-1};
ll dy8[8]={0,1,0,-1,1,-1,-1,1};
ll dx4[4]={0,0,1,-1};
ll dy4[4]={1,-1,0,0};


int main(){
    IOS;
    make(ll,n);
    vector <array <ll,4> >dp(n+1);
    dp[1][0]=8; dp[1][1]=1; dp[1][2]=1; dp[1][3]=0;
    for(ll i=2;i<=n;i++){
        dp[i][0]=(8*dp[i-1][0])%M;
        dp[i][1]=(dp[i-1][0]+(9*dp[i-1][1]))%M;
        dp[i][2]=(dp[i-1][0]+(9*dp[i-1][2]))%M;
        dp[i][3]=(dp[i-1][1]+dp[i-1][2]+(10*dp[i-1][3]))%M;
    }




    cout<<dp[n][3]<<endl;



    return 0;
}


Measured memory_bytes: 34184
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <math.h>

#define P 1000000007

int comp(const void *a, const void *b){return *(int*)a-*(int*)b;}
int compw(const void *a, const void *b){return (*(int*)a>*(int*)b)-(*(int*)a<*(int*)b);}
int compr(const void *a, const void *b){return *(int*)b-*(int*)a;}

int b[100000];
int main(void){
	int n, h, i;
	scanf("%d%d", &n, &h);
	int a=0;
	for(i=0; i<n; i++){
		int A, B;
		scanf("%d%d", &A, &B);
		if(A>a) a=A;
		b[i]=B;
	}
	qsort(b, n, sizeof(int), compr);
	for(i=0; i<n; i++){
		if(h<=0 || b[i]<=a) break;
		h-=b[i];
	}
	printf("%d\n", h>0?i+(h+a-1)/a:i);
}


Measured memory_bytes: 892
#include <iostream>
#include <tuple>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;
void init();
#define REP(var, num) for(sll var = 0; var < num; var++)
typedef signed long long sll;
typedef unsigned long long ull;
/*
numeric_limits<sll>::max()
*/

int main() {
    init();
    sll a,b;
    cin >> a>>b;

    cout  << ((b % a == 0) ? a+b:b-a) << endl;
    return 0;
}

void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

Measured memory_bytes: 256
#include <cstdio>
int N;
int main ()
{
scanf("%d",&N);
int res=N;
for(int i=0;i<=N;i++) {
int cc =0;
int t=i; while(t>0)cc+=t%6,t/=6; t=N-i; while(t>0)cc+=t%9,t/=9; if(res>cc)res=cc;
} printf("%d\n",res);
}

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

int main() {
  int N,i,X=0;
  cin>>N;
  vector<int> A(N);
  for (i=0;i<N;i++) {
    cin>>A[i];
    X ^= A[i];
  }
  cout<<(X^A[0]);
  for (i=1;i<N;i++) {
  cout<<" "<<(X^A[i]);
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 3540
#include<cstdio>
int main(){
	int a,b,c,d,e,f;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	e=a*b;
	f=c*d;
	if(e>f) printf("%d\n",e);
	else printf("%d\n",f);
	return 0;
}

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

int main() {
    string S;
    cin >> S;
    
    int maxacgt = 0;
    int tmpacgt = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S.at(i) == 'A' || S.at(i) == 'C' || S.at(i) == 'G' || S.at(i) == 'T') {
            tmpacgt++;
            if (tmpacgt > maxacgt){
                maxacgt = tmpacgt;
            }
        } else {
            tmpacgt = 0;
        }
    }
    cout << maxacgt << endl;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
signed main(void)
{
    long long n, i, ans = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        ans += (i + n - n % i) * ((n - n % i - i) / i + 1) / 2;
    cout << ans;
    return 0;
}

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

#define __STDC_FORMAT_MACROS
#define p64 PRId64

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define ALL(f, x, ...)                                                         \
    ([&] (decltype ((x)) ALL) {                                                \
        return (f) (begin (ALL), end (ALL), ##__VA_ARGS__);                    \
    }) (x)

using namespace std;
using ll = int64_t;

int main() {
    int N = 5;
    vector<int> x (N, 0);
    REP (i, N) cin >> x[i];
    cout << ALL (find, x, 0) - begin (x) + 1 << endl;
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    
  int a,amax=0;
  for(int i=0; i<n; i++){
    cin >> a;
    if(amax-a>1){
      cout << "No" << endl;
      return 0;
    }
    amax = max( a, amax );
  }
  cout << "Yes" << endl;
  return 0;
}


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

int main(){
	
	int n; cin>>n;
	n = n%10;
	if(n==2||n==4||n==5||n==7||n==9){
		cout << "hon" << endl;
	}
	else if(n==0|n==1||n==6||n==8){
		cout << "pon" << endl;
	}
	else cout << "bon" << endl;
	
}



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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin>>s;
    sort(all(s));
    if (s=="abc"){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int main() {
	string s;
	cin >> s;

	int num = 0;

	for (int i = 0; i < 4; i++) {
		if (s[i] == '+') {
			num++;
		}
		else {
			num--;
		}
	}

	cout << num << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<numeric>
using namespace std;
#define ll long long
#define Graph vector<vector<long long>>
#define all(v) v.begin(),v.end()
#define PI acos(-1)
#define inf 1000000321

int main(){
    int x;
    cin >> x;
    if(x)cout << 0 << endl;
    else cout << 1 << endl;
}

Measured memory_bytes: 3588
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <string>

#define rep(x,to) for(int x=0;x<to;x++)
#define rep2(x,from,to) for(x=from;x<to;x++)

using namespace std;


int main(void){

int N;
double x[4], y[4];

	cin >> N;
	while( N--){
		rep(i,4) cin >> x[i] >> y[i];
		
		if((y[1]-y[0])*(x[3]-x[2]) == (y[3]-y[2])*(x[1]-x[0])) 
  	    	cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

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

int main()
{
  int h, w;
  cin >> h >> w;
  
  for (int i = 0; i < h + 2; i ++)
  {
    string s;
    if (i == 0 || i == h + 1)
    {
      for (int j = 0; j < w + 2; j ++)
      {
        cout << "#";
      }
    }
    else 
    {
      cin >> s;
      cout << "#" << s << "#";
    }
    cout << endl;
  }
  
  return 0;
}


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

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            //ここから
            string[] str = Console.ReadLine().Split(' ');
            char c = char.Parse(str[0]);
            int d = c + 1;

            Console.WriteLine((char)d);



            //ここまで
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}

struct misaka{
	int x,y;
	int cnt;
}e;

int n,m;
int sx,sy;
int ex,ey;
char g[2000][2000];
bool st[2000][2000];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int ans=INF;

void bfs(){

	deque<misaka> q;
	q.pb({sx,sy,0});


	while(!q.empty()){
		auto tmp=q.front();
		q.pop_front();

		int x=tmp.x;
		int y=tmp.y;
		int cnt=tmp.cnt;

		if(x==ex && y==ey){
			ans=cnt;
			return;
		}

		if(st[x][y]) continue;
		st[x][y]=true;

		for(int i=0;i<4;++i){
			int tx=x+dx[i];
			int ty=y+dy[i];

			if(tx<1 || tx>n || ty<1 || ty>m  || g[tx][ty]=='#') continue;
			q.pf({tx,ty,cnt});
		}
		for(int i=x-2;i<=x+2;++i){
			for(int j=y-2;j<=y+2;++j){
				if(i<1 || i>n || j<1 || j>m  || g[i][j]=='#') continue;
				q.pb({i,j,cnt+1});
			}
		}
	}
}

int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	n=read();
	m=read();
	sx=read();
	sy=read();
	ex=read();
	ey=read();

	for(int i=1;i<=n;++i){
		scanf("%s",g[i]+1);
	}

	bfs();

	if(ans==INF) puts("-1");
	else printf("%d\n",ans);


    return 0;
}

Measured memory_bytes: 9296
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;

int main() {
    int N, ans = 0;
    string S;
    cin >> N >> S;
    vector<vector<int>> dp(N + 1, vector<int>(N + 1));
    for(int i = N - 1; i >= 0; --i) {
        for(int j = N - 1; j >= i; --j) {
            if(S[i] == S[j])
                dp[i][j] = dp[i + 1][j + 1] + 1;
            ans = max(ans, min(dp[i][j], j - i));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 98304
program problemB
  implicit none


integer(8) :: n,k,l
integer(8) :: BNUM, RNUM, NMAX, count,MMAX, sum, B, multi,countA,countC,KMAX
integer(8) :: money, yr
integer(8), allocatable :: d(:), a(:,:), c(:)
character(len=4) :: color



read(*,*) NMAX,KMAX

allocate(d(KMAX),a(KMAX,NMAX),c(NMAX))
a(:,:)=0

do k=1, KMAX
  read(*,*) d(k)
  read(*,*) a(k,1:d(k))
end do

c(:)=1

do n=1, NMAX
  do k=1, KMAX
    do l=1,d(k)
      if (n==a(k,l)) then
        c(n)=0
      end if
    end do
  end do
end do

  write(*,*) sum(c)




deallocate(d,a,c)

stop
end program


Measured memory_bytes: 2888
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define p pair<int,int>
int N;
vector<int> b, ans;
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        int tmp;
        cin >> tmp;
        b.push_back(tmp);
    }
    for(int i = 0; i < N; i++){
        vector<int> copy;
        bool flag = false;
        for(int j = b.size() - 1; j >= 0; j--){
            if(b[j] == j + 1 && !flag)  {
                flag = true;
                ans.push_back(b[j]);
            }else copy.push_back(b[j]);
        }
        if(!flag){
            cout << -1 << endl;
            return 0;
        }
        reverse(copy.begin(), copy.end());
        b = copy;
    }
    for(int i = 0; i < N; i++){
        cout << ans[N - i - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import sys

s = input()
t = input()

tl = len(t) ; sl = len(s)

c = 1
for i in range(sl,tl-1,-1) :
  st = s[i-tl:i]
  c = 0
  for j in range(tl) :
    if st[j] == '?' :
      continue
    elif st[j] != '?' and st[j] == t[j] :
      continue
    c = 1
    break
  if c == 0 :
    s = s[:i-tl] + t + s[i:]
    break

if c == 1 :
  print('UNRESTORABLE')
else : 
  print(s.replace('?', 'a'))

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>
 
 
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;
 
using namespace std;


int main()   {
    cout.precision(17);
    ll modd = 1000 * 1000 * 1000 + 7;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no
    ll infinit = 10000000000000000;

//    auto start = chrono::steady_clock::now();

//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
            readint(x); readint(y);
            int cran = 2*x-y/2;
            int turt = y/2-x;

            if ((cran>=0) && (turt>=0) && (cran+turt==x) && (2*cran+4*turt==y)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }

    }

//    auto end = chrono::steady_clock::now();
//    cout << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;

    return 0;
}

Measured memory_bytes: 3620
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
     String[] nyu=sc.nextLine().split(" ");

//     String nyu=sc.nextLine();
int A=Integer.parseInt(nyu[0]);
int B=Integer.parseInt(nyu[1]);
int C=Integer.parseInt(nyu[2]);
//int D=Integer.parseInt(nyu);

//StringBuffer sb = new StringBuffer(nyu);
//		String dst = sb.reverse().toString();

//     String nyu2=sc.nextLine();
//int E=Integer.parseInt(nyu2);



//double A=Double.parseDouble(nyu[0]);
//double B=Double.parseDouble(nyu[1]);
/*
switch(C){
case 7:
case 5:
case 3:
System.out.println("YES") ;
break;
default:
System.out.println("NO") ;

break;
}
*/

//int res=Math.min((A*B),C);

//for(String tem:nyu){
//if(tem.equals("1"))res++;
//}
//int res=0;
//for(int i=0;i<300;i++){
//if(num[i]==1)res=i;
//}

//char[] c = nyu.toCharArray();


//System.out.println(nyu+"-"+line_r_2+"-"+nyu2+"-"+line_r_1);


if((C-B)<=0){
//double res=Math.ceil((AB)/2);

System.out.println("delicious");
}else if((C-B)<=A){
System.out.println("safe");

}else{
System.out.println("dangerous");

}




	}
}

Measured memory_bytes: 21076
n=int(input())
a=[int(i) for i in input().split()]

def merge(A,l,m,r):
    global c
    L=A[l:m]+[1e10]
    R=A[m:r]+[1e10]
    i,j = 0,0
    for k in range(l,r):
        if L[i]<R[j]:A[k]=L[i];i+=1 ;c+=j
        else:A[k]=R[j];j+=1;

def mergesort(A,l,r):
    if l+1<r:
        m=(r+l)//2
        mergesort(A,l,m)
        mergesort(A,m,r)
        merge(A,l,m,r)
c=0
mergesort(a,0,n)
print(c)


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

int main(){
  int a,b;
  int c[3];
  int k[3] = {100,500,1000};

  while( cin>>b>>a, a|b ){

    c[0]=c[1]=c[2]=0;

    for( int i=2;i>=0;i-- ){
      while( b+k[i]<=a ){
	b+=k[i];
	c[i]++;
      }
    }
    cout << c[0] << " " << c[1] << " " << c[2] << endl;

  }
  return 0;
}

Measured memory_bytes: 868
package main

import (
	"fmt"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)
	x := min(a+b, c-1)
	if c-x > 0 {
		x++
	}
	ans := b + x
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>

#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define mod 1000000007
#define show(n) cerr<<#n<<" = "<<n<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl

//ここからAtCoder向けdefine
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using pint = pair<int,int>;

const int INF = (1 << 30);

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a, b, c, d;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;
    cout << ((a > b) ? b : a) + ((c > d) ? d : c) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007
#define Vi vector<int>
#define Vl vector<long long>
#define pb(a) push_back(a)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<int,ll>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000001;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct edge{int to,cost;};
struct pos{
	int x,y,cost;
};


int main() {

	ll n,k;
	cin>>n>>k;
	ll a=0,b=0;
	for(int i=1; i<n+1; i++){
		if(i%k==0)a++;
		if(i%k==k/2)b++;
	}
	if(k%2==0)cout<<a*a*a+b*b*b<<endl;
	else cout<<a*a*a<<endl;

	return 0;
}


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

int main(){
  int N;
  cin >> N;
  int max_count = -1;
  int n;
  for(int i=1;i<=N;i=i+1){
    int count = 0;
    int x = i;
    while(x%2 == 0){
      x = x/2;
      count = count + 1;
    }
    if(max_count < count){
      max_count = count;
      n = i;
    }
  }
  cout << n << endl;
}


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

int main(){
	long long x; cin >> x;
	ll i = 0;
	while(true){
		ll a = x + i;
		bool cek = true;
		for(int j = 2; j*j <= a; j++){
			if(a%j == 0){
				cek = false;
				break;
			}
		}
		if(cek){
			cout << a << endl;
			return 0;
		}
		i++;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 +7;
const double EPS = 1e-10;

typedef vector<lli> vec;
typedef vector<vec> matrix;

matrix mul(const matrix &a, const matrix &b){
	int h = a.size();
	int w = b[0].size();
	int r = b.size();
	matrix c(h, vec(w, 0));
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			for(int k=0; k<r; k++){
				c[i][j] += a[i][k] *b[k][j];
				c[i][j] %= mod;
			}
		}
	}
	return c;
}

lli fibonacci(lli n){
	matrix a(2, vec(2, 1)), ret(2, vec(2, 0));
	a[1][1] = 0;
	ret[0][0] = ret[1][1] = 1;
	for(int i=63; i>=0; i--){
		ret = mul(ret, ret);
		if((1LL<<i & n) != 0){
			ret = mul(ret, a);
		}
	}
	return ret[0][1];
}

int main(){
	lli k;
	cin >> k;
	lli row, col; // 0-idx
	lli q = sqrt(k) + EPS;
	if(q*(q+1) < k) q++;
	if(q*q >= k){
		row = (q-1)*2;
		col = k -q*(q-1) -1;
	}else{
		row = (q-1)*2 +1;
		col = k -q*q -1;
	}
	
	lli fhalf = row/4 +1;
	lli ans;
	if(col < fhalf){
		ans = fibonacci((col+1)*2) * fibonacci(row+2 -col*2);
	}else{
		lli w = row/2 +1;
		ans = fibonacci((w-col)*2 +1) * fibonacci(row+3 -(w-col)*2);
	}
	ans %= mod;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3080
def main():
    n = int(input())
    a = list(map(int, input().split()))

    ans = 0
    for i in range(n-1):
        if (a[i] <= a[i+1]):
            ans += 0
        else:
            ans += a[i] - a[i+1]
            a[i+1] = a[i]

    print(ans)

main()


Measured memory_bytes: 32368
function main(input){
    let lines = input.split("\n");
    let i=0;
    while(lines[i]!=="-1 -1 -1"){
        let nums = api(lines[i].split(" "));
        let sum = nums[0]+nums[1];
        if(nums[0]===-1 || nums[1]===-1){
            console.log("F");
        }else if(sum>=80){
            console.log("A");
            
        }else if(sum>=65){
            console.log("B");
        }else if(sum>=50){
            console.log("C");
        }else if(sum>=30){
            if(nums[2]>=50){
                console.log("C");
            }else{
                console.log("D");
            }
        }else{
            console.log("F");
        }
        i++;
    }
    
}
function api(arr){
    return arr.map(item=>parseInt(item));
}


main(require("fs").readFileSync("/dev/stdin","utf-8"));


Measured memory_bytes: 15348
#include <bits/stdc++.h>
#define INF 1000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  string n;
  cin >> n;
  for (ll i = 0; i < n.size(); ++i)
  {
    if (n[i] == '1')
    {
      cout << '9';
    }
    else if (n[i] == '9')
    {
      cout << '1';
    }
    else
    {
      cout << n[i];
    }
  }
  cout << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline
import numpy as np

D = int(input())
c = np.array(input().split(), dtype=np.int32)
s = np.array([input().split() for _ in range(D)], dtype=np.int32)
last = np.zeros(26, dtype=np.int32)


ans = []
point = 0
for i in range(D):
    down = (i+1-last)*c
    loss = down * 3 + s[i,:]
    idx = np.argmax(loss)
    ans.append(idx+1)
    point += s[i, idx] - down.sum()
    last[idx] = i+1


for i in range(D):
    print(ans[i])

Measured memory_bytes: 27532
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N=in();
	vector<int> P(N);
	REP(i,N){
		P[i] = in();
	}
	int sum = 0;
	for(int i=1;i<N-1;i++){
		if((P[i-1]<P[i] && P[i]<P[i+1]) || (P[i-1]>P[i] && P[i]>P[i+1])){
			sum++;
		}
	}
	
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i,n) for(int i=(int)(n);i>=0;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------
 
signed main() {
    int A,B,T;
    cin >> A >> B >> T;
    cout << B*(T/A) << endl;
    return 0;
}


Measured memory_bytes: 256
from fractions import Fraction
from collections import defaultdict
from itertools import combinations
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

N = int(input())
XY = [list(map(int, input().split())) for i in range(N)]

D = defaultdict(int)
for (x1, y1), (x2, y2) in combinations(XY, 2):
    if x1 != x2:
        a = Fraction(y2-y1, x2-x1)
        b = Fraction(y1) - a * Fraction(x1)
        D[(a, b)] += 1
    else:
        D[(None, x1)] += 1

mod = 998244353
comb = Combination(N+1, mod)
A = [0] * (N+1)
coA = [0] * (N+1)
ans = 0
for i in range(3, N+1):
    ans += comb(N, i)
    ans %= mod
for i in range(3, N+1):
    for j in range(i-2):
        A[i] += (i-2-j)*(1<<j)
    coA[i] = coA[i-1]+A[i]
for (a, b), n in D.items():
    if n==1:
        continue
    n = int((n<<1)**0.5)+1
    ans -= coA[n]
    ans %= mod
print(ans)

Measured memory_bytes: 94296
# coding: utf-8
# Your code here!

A,B,C,D = map(int, input().split())
result = 0
if D-A>0:
    result +=A
    b = D-A
    if b-B > 0:
        result -=(b-B)
        print(result)
    else:
        print(result)
else:
    print(D)
    

Measured memory_bytes: 9032
(stdin => {

  const I     = v => v
  const K     = v => _ => v
  const join  = sep => array => array.join(sep)
  const split = sep => str => str.split(sep)
  const print = fun => (f, v) => fun(f(v))
  // Define Function
  const div = (a, b) => a / b
  const mod = (a, b) => a % b

  // Declare Variable
  const inputs = stdin.toString().trim().split('\n')
  const [a, b] = Array.from(split(' ')(inputs[0]), Number)
  // Main
  const result = [
    Math.floor(div(a, b)),
    mod(a, b),
    div(a, b).toFixed(6)
  ]

  // Display
  const display = print(console.log)
  display(join(' '), result)

})(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 15404
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < n; i++) 
using namespace std;
typedef long long ll;

int main() {
  
  int n;
  cin >> n;
  
  int ans;
  
  if (n < 10) ans = n;
  else if(n < 100) ans = 9;
  else if(n < 1000) ans = (n / 100 - 1) * 100 + n % 100 + 1 + 9;
  else if(n < 10000) ans = 909;
  else if(n < 100000) ans = (n / 10000 - 1) * 10000 + n % 10000 + 1 + 909;
  else ans = 90909;
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256