akhauriyash/Code-Regression huggingface dataset:
mod=1000000007

s=input()
x=len(s)
dp=[[0 for i in range(4)] for j in range(100005)]
for i in range(x,-1,-1):
    for j in range(3,-1,-1):
        if i==x:
            dp[i][j]=[0,1][j==3]
        else:
            dp[i][j]=dp[i+1][j]*([1,3][s[i]=="?"])
            if (j<3 and (s[i]=="?" or s[i]=="ABC"[j])):
                dp[i][j]+=dp[i+1][j+1]
            dp[i][j]%=mod
print(dp[0][0])

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_h(const vector<T>& c, int n=INT_MAX)
{ rep(i, min(n, (int)c.size())) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
#define D1(a) cout<<#a<<":"<<a<<"\n"
#define D2(a,b) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<endl 
#define D3(a,b,c) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl 
#define MOD 1000000007

template <typename T> T gcd(T a, T b) {
	if (b == 0) return abs(a);
	T r; while ((r = a % b) != 0) a = b, b = r;
	return abs(b);
}
template <typename T> T lcm(T a, T b) {
	return a/gcd(a, b) * b;
}

int main()
{
    ll A,B; cin >>A>>B;

    ll ans = lcm(A, B);

    cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static AtCoder.Io;
 
namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var abc = ReadIntArray();
            var a = abc[0];
            var b = abc[1];
            var c = abc[2];
            var ans = b - a == c - b ? "YES" : "NO";
            Console.WriteLine($"{ans}");
        }
    }
 
    public static class Io
    {
        public static string ReadString() => Console.ReadLine();
        public static string[] ReadStringArray() => ReadString().Split(' ');
        public static int ReadInt() => int.Parse(ReadString());
        public static long ReadLong() => long.Parse(ReadString());
        public static int[] ReadIntArray() => ReadStringArray().ParseInt().ToArray();
        public static long[] ReadLongArray() => ReadStringArray().ParseLong().ToArray();
        public static IEnumerable<int> ParseInt(this IEnumerable<string> source) => source.Select(int.Parse);
        public static IEnumerable<long> ParseLong(this IEnumerable<string> source) => source.Select(long.Parse);
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int n;
    cin >> n;
    int ans = 0;
    rep(i, n) {
        ans += i + 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
 
void visit(int);
int map[101][101];
int f[101],d[101],color[101],time,n;

 
void visit(int u)
{
  int i;
  color[u]=1;
  d[u]=++time;
  for(i=0;i<n;i++){
    if(map[u][i]==1){
      if(color[i]==0)visit(i);
   
    }
  }
  color[u]=2;
  f[u]=++time;
}

int main()
{
  int i,j,v,v2,m;
 
  scanf("%d",&n);
  for(i=0;i<n;i++){
    color[i]=0;
    for(j=0;j<n;j++){
      map[i][j]=0;
    }
  }
  time=0;
  for(i=0;i<n;i++){
    scanf("%d%d",&v,&m);
    for(j=0;j<m;j++){
      scanf("%d",&v2);
      map[v-1][v2-1]=1;
    }
  }
  for(i=0;i<n;i++){
    if(color[i]==0)visit(i);
  }
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }
  return 0;
}

Measured memory_bytes: 636
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			int S = scn.nextInt();
			int W = scn.nextInt();

			if(S > W) {
				System.out.println("safe");
			} else {
				System.out.println("unsafe");
			}
		}
	}
}

Measured memory_bytes: 27048
#include<bits/stdc++.h> 
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef long long ll;
typedef double db;
using namespace std;
inline int read(){
	int n=0;char c;
	for(c=getchar();c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) n=n*10+c-48;
	return n;
}
const int maxn=3e5+5;
int i,n,m,a[maxn],q[maxn],tail,x,y,w,last;
ll inf,cost[maxn],f[maxn],F[maxn],ans,f1[maxn],f2[maxn],g[maxn],ff[maxn];
db p[maxn];
ll V(int n){
	return (ll)n*(n+1)>>1;
}
void dp(){
	int i,j;
	q[tail=1]=0;
	fo(i,1,n){
		for(;tail>1&&i>p[tail];tail--);
		x=q[tail];
		f[i]=max(f[i-1],f[x]+V(i-x)-cost[i]+cost[x]);
		F[i]=f[i]+((ll)i*(i-1)>>1)+cost[i];
		for(;tail>1;){ 
			x=q[tail];
			if ((db)(F[i]-F[x])/(i-x)>=p[tail]) tail--;else break;
		}
		x=q[tail],q[++tail]=i;
		p[tail]=(db)(F[i]-F[x])/(i-x);
	}
}
void work(int l,int r,bool bz){
	int i,m=(l+r-bz)>>1;
	if (l==r){
		i=l;
		if (bz) g[i]=max(g[i],f1[i-1]+f2[i+1]+1-a[i]);
		else g[n-i+1]=max(g[n-i+1],f1[n-i]+f2[n-i+2]+1-a[n-i+1]);
		for(;tail>1&&i>p[tail];tail--);
		x=q[tail];
		f[i]=max(f[i-1],f[x]+V(i-x)-cost[i]+cost[x]);
		F[i]=f[i]+((ll)i*(i-1)>>1)+cost[i];
		for(;tail>1;){ 
			x=q[tail];
			if ((db)(F[i]-F[x])/(i-x)>=p[tail]) tail--;else break;
		}
		x=q[tail],q[++tail]=i;
		p[tail]=(db)(F[i]-F[x])/(i-x);
		return;
	}
	work(l,m,bz);
	int now=tail;
	fo(i,m+1,r){
		for(;tail>1&&i>p[tail];tail--);
		x=q[tail];
		if (bz)ff[i]=f[x]+V(i-x)-cost[i]+cost[x]+f2[i+1];else
		ff[i]=f[x]+V(i-x)-cost[i]+cost[x]+f1[n-i];
	}tail=now;
	ff[r+1]=inf;
	fd(i,r,m+1) {
		ff[i]=max(ff[i],ff[i+1]);
		if (bz) g[i]=max(g[i],ff[i]);else
		g[n-i+1]=max(g[n-i+1],ff[i]);
	}
	work(m+1,r,bz);
}
int main(){
	n=read();
	fo(i,1,n) a[i]=read(),cost[i]=cost[i-1]+a[i];
	dp();
	fo(i,1,n) f1[i]=f[i],cost[i]=cost[i-1]+a[n-i+1];
	dp();
	fo(i,1,n) f2[i]=f[n-i+1];
	q[tail=1]=0;
	memset(g,-127/2,sizeof(g));
	inf=g[0];
	work(1,n,0);
	fo(i,1,n) cost[i]=cost[i-1]+a[i];
	q[tail=1]=0;
	work(1,n,1);
	m=read();
	for(;m--;){
		w=read(),x=read();
		ans=max(f1[w-1]+f2[w+1],g[w]+a[w]-x);
		printf("%lld\n",ans);
	}
}

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

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define R(i,n) for(int i = 0; i < (n); i++)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}

template<class T> ostream &operator<<(ostream& os, set<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}

template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.FI << "," << P.SE << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  int n;
  cin >> n;
  int ost = -1;
  int res = 0;
  R(i,n){
    int pom;
    cin >> pom;
    if(pom == ost){
      res++;
      ost = -1;
    }else{
      ost = pom;
    }
  }
  cout << res << "\n";
}




Measured memory_bytes: 256
n = int(input())
s = input()
cnt = s.count("R") * s.count("G") * s.count("B")
for i in range(n-2):
    pl = 1
    while i + pl * 2 < n:
        if s[i] != s[i+pl] and s[i+pl] != s[i+pl*2] and s[i] != s[i+pl*2]:
            cnt -= 1
        pl += 1
print(cnt)


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

int main(){
    int n;
    cin>>n;
    bool flag=true;
    for(int i=0;i<n;i++) {
        int temp;
        cin>>temp;
        if(temp%2==0){
            if(temp%3 && temp%5){
                flag=false;
                break;
            }
        }
    }
    if(flag) cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
#define all(v) v.begin(), v.end()
const int INF = 1 << 30;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    string s;
    cin >> s;
    if(s[0] == s[1] && s[1] == s[2] && s[2] == 'R')cout << 3 << "\n";
    else if(s[0] == s[1] && s[0] == 'R')cout << 2 << "\n";
    else if(s[2] == s[1] && s[1] == 'R')cout << 2 << "\n";
    else if(s[0] == 'R' || s[1] == 'R' || s[2] == 'R')cout << 1 << "\n";
    else cout << 0 << "\n";

    return 0;
}

Measured memory_bytes: 3624
import numpy as np

W,H,N = map(int,input().split())

xl = 0
xr = W
yu = H
yd = 0

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

    if a == 1:
        xl = max(xl,x)
    elif a == 2:
        xr = min(xr,x)
    elif a == 3:
        yd = max(yd,y)
    else:
        yu = min(yu,y)

ans = max(0,xr - xl) * max(0,yu - yd)

print(ans)


Measured memory_bytes: 12504
#include<iostream>
#define ll long long
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
    ll n,w;
    cin>>n>>w;
    vector<vector<ll>> knapsack(n);
    ll temp;
    for(ll i=0; i<n; ++i)
    {
        cin>>temp;
        knapsack[i].push_back(temp);
        cin>>temp;
        knapsack[i].push_back(temp);

    }
    //sort(knapsack.begin(), knapsack.end());

    ll arr1[w+1], arr2[w+1];
    ll *ptr1;
    ll *ptr2;
    ptr1 = arr1;
    ptr2 = arr2;
    for(ll i=0; i<=w; ++i)
    {
        ptr1[i] = 0;
    }

    for(ll i=0; i<n; ++i)
    {
        ptr2[0] = 0;
        for(ll j=1; j<=w; ++j)
        {
            if(knapsack[i][0] <= j)
            {
                ptr2[j] = max(ptr1[j], knapsack[i][1] + ptr1[j-knapsack[i][0]]);
            }
            else
            {
                ptr2[j] = ptr1[j];
            }
        }
        if(i != n-1)
        {
            ll *temp = ptr1;
            ptr1 = ptr2;
            ptr2 = temp;
        }
    }
    cout<<ptr2[w];
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int n;
  while (cin >> n, n) {
    int p[1010], h[1010], w[1010];
    for (int i = 0; i < n; i++) {
      cin >> p[i] >> h[i] >> w[i];
    }
    double diff = 1e9;
    for (int i = 0; i < n; i++) {
      double bmi = 1e4 * double(w[i]) / h[i] / h[i];
      if (abs(bmi - 22) < diff) {
        diff = abs(bmi - 22);
      }
    }
    vector<int> ans;
    for (int i = 0; i < n; i++) {
      double bmi = 1e4 * w[i] / h[i] / h[i];
      if (abs(bmi - 22) == diff) {
        ans.emplace_back(p[i]);
      }
    }
    sort(ans.begin(), ans.end());
    for (int i : ans) {
      cout << i << endl;
    }
  }

  return 0;
}


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

int main()
{
	int n; cin>>n;
	while(n--)
	{
		double x1,y1,x2,y2,x3,y3;
		cin>>x1>>y1>>x2>>y2>>x3>>y3;

		double a1=2*(x2-x1);
		double b1=2*(y2-y1);
		double c1=x1*x1-x2*x2+y1*y1-y2*y2;
		double a2=2*(x3-x1);
		double b2=2*(y3-y1);
		double c2=x1*x1-x3*x3+y1*y1-y3*y3;

		double x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
		double y=(c1*a2-c2*a1)/(a1*b2-a2*b1);
		double r=sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));

		x=floor(x*1000+0.5)/1000;
		y=floor(y*1000+0.5)/1000;
		r=floor(r*1000+0.5)/1000;

		printf("%.3lf %.3lf %.3lf\n",x,y,r);
	}
	return 0;
}

Measured memory_bytes: 1244
-- Structured Program II - How many ways?

import Control.Applicative

main :: IO ()
main = do
  xs <- map (map read . words) . lines <$> getContents
  mapM_ (print . count) $ takeWhile (/= [0, 0]) xs

count :: [Int] -> Int
count [n, x] = length $ filter (== x) xs
  where xs = [a + b + c | a <- [1 .. n], b <- [a + 1 .. n], c <- [b + 1 .. n]]



Measured memory_bytes: 4528
#include<iostream>
#include<sstream>
#include<fstream>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<string.h>
#include<math.h>
#include<cassert>
#include<iomanip>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<functional>
#include<algorithm>
#include<assert.h>
#include<numeric>
#include<limits.h>
using namespace std;
int n,m;
int a[10],g[10][10];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x-1][y-1]=1;
		g[y-1][x-1]=1;
	}
	for(int i=0;i<n;i++)a[i]=i;
	int ans=0;
	do
	{
		if(a[0]!=0)continue;
		int f=1;
		for(int i=1;i<n;i++)if(g[a[i-1]][a[i]]==0)f=0;
		if(f)ans++;
	}while(next_permutation(a,a+n));
	printf("%d\n",ans);
	return 0;
}

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

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

  unordered_set<char> a;
  char c;
  for (int i = 0; i < 3; i++) {
    cin >> c;
    a.insert(c);
  }

  string ans = (a.size() == 1) ? "No" : "Yes";
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

from math import atan2, pi
def solve(N, A):
    A.sort(key = lambda (x, y): atan2(y, x))
    A = A + A
    P = [0]
    for x, y in A:
        P.append(P[-1] + (x + y * 1j))

    ans = 0
    for i in xrange(N):
        for j in xrange(i, i+N):
            ans = max(ans, abs(P[j+1] - P[i]))
    return ans

                
N=rri()
A=[rrm() for _ in xrange(N)]
print solve(N, A)


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

int main() {
  int N;
  cin >> N;
  
  vector<int> a(3 * N);
  priority_queue<int> q, q2;
  ll sum = 0;
  ll sum2 = 0;
  vector<ll> x(N + 1, 0), y(N + 1, 0);
  
  for (int i = 0; i < 3 * N; i++) {
    cin >> a.at(i);
  }
  
  for (int i = 0; i < 2 * N; i++) {    
    q.push(-a.at(i)); // 負の値にして入れる
    sum += a.at(i);
    
    if (q.size() > N) {
      sum += q.top();
      q.pop();
    }
    
    if (q.size() == N) {
      x.at(i - (N - 1)) = sum;
    }
  }
  
  for (int i = 3 * N - 1; i >= N; i--) {    
    q2.push(a.at(i));
    sum2 += a.at(i);
    
    if (q2.size() > N) {
      sum2 -= q2.top();
      q2.pop();
    }
    
    if (q2.size() == N) {
      y.at(i - N) = sum2;
    }
  }
  
  ll ans = -LLONG_MAX;
  for (int i = 0; i <= N; i++) {    
    ll score = x.at(i) - y.at(i);
    if (score > ans) ans = score;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 4088
n,m = map(int,input().split())
if(n%2==1):
    for i in range(1,m+1):
        print(' '.join(map(str,[i,n+1-i])))
    exit()

m1,m2 = (m+1)//2 ,m//2
sum1 = 1 + n//2
sum2 = (n//2+1) + (n-1)
for i in range(m1):
    print(' '.join(map(str,[1+i,n//2 -i])))
for i in range(m2):
    print(' '.join(map(str,[n//2+1+i,n-1-i])))

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

int main(){

    int n;
    cin >> n;
    vector<int> w(n);
    int weight = 0;
    for(int i = 0; i < n; i++){
        cin >> w[i];
        weight += w[i];
    }
    int s1, s2;
    s1 = 0;
    int min = INF;
    for(int i = 0; i < n; i++){
        s1 += w[i];
        s2 = weight - s1;
        if(min > abs(s1 - s2)) min = abs(s1 - s2);
    }
    cout << min << endl;
    
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)

using namespace std;
using ll = long long;
typedef pair<int, int> Pair;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<pair<ll, int>> factorize(ll n) {
  vector<pair<ll, int>> res;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i) continue;
    res.emplace_back(i, 0);
    while (n % i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n, 1);
  return res;
}

int main() {
  ll A, B;
  cin >> A >> B;

  ll g = gcd(A, B);
  auto f = factorize(g);
  int ans = f.size() + 1;
  cout << ans << endl;
  return 0;
}

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int all = 1;
        int odd = 1;
        for (int i = 0; i < N; i++) {
             int A =  sc.nextInt();
             all *= 3;
             if (A%2 == 0) {
                 odd *= 2;
             } else {
                 odd *= 1;
             }
        }
        System.out.println(all-odd);
    }
}


Measured memory_bytes: 23124
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);





int main() {
    ll n,k;
    cin>>n>>k;
    vector<ll> v(n);

    ll sum=0;
    rep(i,n){
        cin>>v[i];
        sum+=v[i];
    }


    sort(v.begin(),v.end());

    ll maxv = v[n-1];

    ll dmax = sqrt(v[n-1]*n);


    vector<ll> yaku;
    for(int i=1;i<=sqrt(sum);i++){
        if(sum%i==0){yaku.push_back(i);
        if(i!=sum/i){yaku.push_back(sum/i);}
        }
    }

    sort(yaku.rbegin(),yaku.rend());

    for(ll i=0;i<yaku.size();i++){
        ll h=yaku[i];


        vector<ll> r;
        rep(j,n){
            r.push_back(v[j]%h);
        }

        sort(r.begin(),r.end());

        vector<ll> left(n);
        vector<ll> right(n);

        left[0]=r[0];
        right[n-1]=h-r[n-1];
        for(int j=1;j<n;j++){
            left[j]+=r[j]+left[j-1];
        }


        for(int j=n-2;j>=0;j--){
            right[j]+=(h-r[j])+right[j+1];
        }
        //cout<<i<<endl;
        
        for(int j=0;j<=n-2;j++){
           // cout<<j<<endl;
            ll a=left[j];
            ll b=right[j+1];
           // cout<<a<<" "<<b<<endl;

            if(a==b){
                //if((k%a==0||a<=k)){
                if(a<=k){
                    cout<<h<<endl;
                    return 0;

                }
            }
        }

    }
cout<<1<<endl;





    return 0;
}


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

namespace A
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var XY = Console.ReadLine().Replace(" ", "");
            var X = XY[0] - 'A';
            var Y = XY[1] - 'A';
            var answer = "=";
            if (X > Y) answer = ">";
            if (X < Y) answer = "<";
            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 25680
n = gets.to_i
a = []
b = []
n.times do
  x,y = gets.split.map(&:to_i)
  a << x
  b << y
end
a.sort!
b.sort!
min = 0
max = 0
if n.even?
  min = (a[n/2]+a[n/2-1])
  max = (b[n/2]+b[n/2-1])
  puts max-min+1
else
  min = a[(n-1)/2]
  max = b[(n-1)/2]
  puts max-min+1
end


Measured memory_bytes: 20412
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();

        boolean isOk = true;
        if (s.charAt(0) != 'A') {
            isOk = false;
        }
        String islowerString = s.substring(1);

        int cCount = 0;
//        for (int i = 2; i < s.length() - 1; i++) {
        for (int i = 1; i < islowerString.length() - 1; i++) {
            if (islowerString.charAt(i) == 'C') {
                cCount++;
                islowerString = islowerString.substring(0, i) + islowerString.substring(i + 1);
            }
        }
        if (cCount != 1) {
            isOk = false;
        }

        for (int i = 0; i < islowerString.length(); i++) {
            if (islowerString.charAt(i) < 'a' || islowerString.charAt(i) > 'z') {
                isOk = false;
                break;
            }
        }

        if (isOk) {
            System.out.println("AC");
        } else {
            System.out.println("WA");
        }
    }

}


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

int main(void)
{
  int N;
  int T[105];
  cin >> N;
  int sum = 0; // 合計タイムをあらかじめ計算
  for (int i = 1; i <= N; ++i)
  {
    cin >> T[i];
    sum += T[i];
  }

  int M;
  cin >> M;
  int P, X;
  for (int i = 0; i < M; ++i)
  {
    cin >> P >> X;
    cout << sum - T[P] + X << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<pii, lint> ppl;
typedef pair<lint, lint> pll;
typedef complex<double> xy_t;
typedef vector<lint> poly;

const lint mod = 1e9 + 7;

int main(){
    int n;
    scanf("%d", &n);
    ppl p[n];
    rep(i, n){
        int w, s;
        lint v;
        scanf("%d%d%lld", &w, &s, &v);
        p[i] = make_pair(make_pair(w, s), v);
    }
    sort(p, p+n, [](const ppl &a, const ppl &b){return a.fi.fi+a.fi.se < b.fi.fi+b.fi.se;});

    lint dp[2][20010];
    rep(i, 2)rep(j, 20010) dp[i][j] = -1;
    dp[0][0] = 0;
    rep(i, n){
        rep(j, 20010)if(dp[0][j] >= 0){
            dp[1][j] = max(dp[1][j], dp[0][j]);
            if(p[i].fi.se >= j && j+p[i].fi.fi < 20010){
                dp[1][j+p[i].fi.fi] = max(dp[1][j+p[i].fi.fi], dp[0][j] + p[i].se);
            }
        }
        rep(j, 20010){
            swap(dp[0][j], dp[1][j]);
            dp[1][j] = -1;
        }
    }

    lint ans = 0;
    rep(j, 20010) ans = max(ans, dp[0][j]);
    printf("%lld\n", ans);
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cmath>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

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

Measured memory_bytes: 256
function Main(input) {
    // 1行目がinput[0], 2行目がinput[1], …に入る
    tmp = input.split(" ");
    tmp =tmp.map(Number);
    D = tmp[0];
    N = tmp[1];

    if(N !== 100){
        switch(D){
            case 0:
            answer = N;
            break;

            case 1:
            answer = 100*N;
            break;

            case 2:
            answer = 10000*N;
            break;
        }
    }else{
        switch(D){
            case 0:
            answer = 101;
            break;

            case 1:
            answer = 10100;
            break;

            case 2:
            answer =1010000;
            break;
        }
    }

    console.log(answer);
    
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main() {

  string s;
  cin >> s;
  
  for(int i=0;i<3;i++){
    if(s.at(i)=='1'){
      s.at(i)='9';
    }else{
      s.at(i)='1';
    }
  }
  cout << s << endl;
  }



Measured memory_bytes: 256
import java.util.*;

// CODEFES_B 2017-C
// http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c	

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

		int H = in.nextInt();
		int W = in.nextInt();
		
		char[][] map = new char[H][W];
		for (int i = 0; i < H; i++) {
			char[] c = in.next().toCharArray();
			for (int j = 0; j < W; j++) {
				map[i][j] = c[j];
			}
		}

		
		int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
		int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
		
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				int count = 0;
				for (int k = 0; k < dx.length; k++) {
					int ii = i + dx[k];
					int jj = j + dy[k];
					
					if (0 <= ii && ii < H && 0 <= jj && jj < W && map[ii][jj] == '#') {
						count++;
					}
				}
				
				if (map[i][j] == '.') {
					System.out.printf("%d", count);
				} else {
					System.out.printf("#");
				}
			}
			System.out.println();
		}
	}
}


Measured memory_bytes: 22740
s=str(input())
if s[0]=="A":
    if s[2:-1].count("C")==1:
        a=s.lstrip("A").replace("C","")
        if a==a.lower():
            print("AC")
        else:
            print("WA")
    else:
        print("WA")
else:
    print("WA")

Measured memory_bytes: 3060
import sys

[Width, Height, x, y, r] = [int(x) for x in sys.stdin.readline().split()]

lower_x = r
lower_y = r
upper_x = Width - r
upper_y = Height -r 

if lower_x <= x <= upper_x and lower_y <= y <= upper_y:
   print("Yes")
else:
   print("No")

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << "\n";
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define endl "\n"
// gcj print用
#define Case(x) printf("Case #%d: ", x);

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

template<class T>
inline bool chmax(T &a, T b) {
  if(a < b) {
    a = b;
    return true;
  }
  return false;
};

template<class T>
inline bool chmin(T &a, T b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
};

int solve(int N, int x) {
  // 商
  int quotient = x;
  int counter = 0;
  while (quotient > 0) {
    // 余り
    int remainder = quotient % N;
    quotient /= N;
    counter++;
  }

  return counter;
};

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

  int N, K;
  cin >> N >> K;

  cout << solve(K, N) << endl;

  return 0;
};


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}
template<typename T,typename U>
ll FindErase(T &v,U tar){
  ll cnt = 0;
  for(auto it = v.begin(); it != v.end();){
    if(*it == tar){
      it = v.erase(it);
      ++cnt;
    }
    else{
      ++it;
    }
  }
  return cnt;
}

template<typename T>
bool SuffixErase(T &v,size_t suf){
  if(suf > v.size()) return false;
  for(auto it = v.begin(); it != v.end();){
    if(distance(v.begin(),it) == suf){
      v.erase(it);
      return true;
    }
    else{
      ++it;
    }
  }
  return false;
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}
const int MAX_N =10001;
int par[MAX_N];
int ranks[MAX_N];
int find(int x){
  if(par[x] == x){
    return x;
  }
  else{
    return par[x] = find(par[x]);
  }
}

void Unite(int a, int b){
  a = find(a);
  b = find(b);
  if(a == b) return ;
  if(ranks[a] < ranks[b]){
    par[a] = b;
  }
  else{
    par[b] = a;
    if(ranks[a] == ranks[b]) ranks[b]++;
  }
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,q;
  cin >> n >> q;
  int s,x,y;
  rep(i,n){
    ranks[i] = 0;
    par[i] = i;
  }
  rep(i,q){
    cin >> s >> x >> y;
    if(s){
      cout << (find(x) == find(y)) << endl;
    }
    else{
      Unite(x,y);
    }
  }
  return 0;
}

Measured memory_bytes: 3272
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	while (1) {

		int L; cin >> L;
		if (!L)break;
		int ans = 22;
		for (int i = 0; i < 12; ++i) {
			int M, N; cin >> M >> N;
			L -= (M - N);
			if (L <= 0) {
				ans = min(ans,i + 1);
			}

		}
		if (ans != 22) {
			cout << ans << endl;
		}
		else {
			cout << "NA" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3080
#include <stdio.h>

int main(void)
{

int a,b,c;

scanf("%d %d %d", &a,&b,&c);

if(a>b) {
if (b<c && c<a)
puts("Yes");
else
puts("No");
}
else {
if (a<c && c<b) 
puts("Yes");
else
puts("No");
}

return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a,b,c,f=0;
    scanf("%d %d %d",&a,&b,&c);
    if(a==b && a!=c) f = 1;
    else if(a==c && a!=b) f = 1;
    else if(b==c && a!=c) f = 1;
    if(f)
        printf("Yes");
    else
        printf("No");
    return 0;
}

Measured memory_bytes: 128
// ABC177C - 

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

typedef unsigned long long int ull;
typedef long long int ll;

#define MOD 1000000007

int main() {
	int N;
	cin >> N;
	ull A[N];
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	ull sum = 0;
	ull psum[N];

	for (int i = 0; i < N; i++) {
		sum += A[i];
		sum %= MOD;
		psum[i] = sum;
	}

	sum %= MOD;

	ull ans = 0;
	for (int i = 0; i < N - 1; i++) {
		ull temp = 0;
		if (sum > psum[i]) {
			temp = (sum - psum[i])% MOD;
		} else {
			temp = (sum - psum[i] + MOD)% MOD;
		}
		ans += (A[i] * temp)% MOD;
	}

	ans %= MOD;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 6744
#include <iostream>

using namespace std;

int main(int argc, char const* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    char S[3];
    cin >> S;
    int m = 700;
    for (int i=0; i<3; ++i) {
        if (S[i] == 'o') {
            m += 100;
        }
    }
    cout << m << '\n';
    return 0;
}


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

a = []
for i in range(N):
    a.append(list(map(str,input().split())))

ans = 0
for i in range(N):
    if a[i][1] == 'JPY':
        ans += int(a[i][0])
    else:
        ans += (float(a[i][0]) * 380000)
        
print(ans)

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    char s[200022];
    Scs(s);
    N = strlen(s);

    vi su(N+1);
    Rep(i,N){
        su[i+1] = (su[i]*10 + s[i]-'0')%2019;
    }

    int t = 1;
    Rep(i,N){
        su[N-i] *= t;
        su[N-i] %= 2019;
        t *= 10;
        t %= 2019;
    }

    vi cnt(2019);
    ll ans = 0;
    Rep(i,N+1){
        ans += cnt[su[i]];
        cnt[su[i]]++;
    }

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

    return 0;
}



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

// int/long:		-2147483648 - 2147483648 (-2^31 <= int < 2^31)
// long/long long:	-9223372036854775808 - 9223372036854775807 (-2^63 <= long < 2^63)
#define	INF (1<<29)
//536870912

#define	MOD 1000000007

int	main() {
	int N;
	cin >>N;
	vector<long> A(N, 0);
	for (int i=0; i<N; i++)
		cin >>A.at(i);
	sort(A.begin(), A.end());
	reverse(A.begin(), A.end());
	int F=0;
	long H, W;
	for (int i=1; i<N; i++) {
		if (A.at(i)==A.at(i-1)) {
			if (0==F) {
				H=A.at(i);
				i++;
				F++;
			} else {
				W=A.at(i);
				cout <<H*W <<endl;
				return 0;
			}
		}
	}
	cout <<0 <<endl;
	return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+100;
int haI[maxn],haII[maxn],firI,firII,secI,secII,n,x;
int read() {
	int tot=0,fh=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') fh=-1;c=getchar();}
	while (c>='0'&&c<='9') {tot=tot*10+c-'0';c=getchar();}
	return tot*fh;
}
void getstr(char *a) {
	char ch=getchar();int len=0;
	while (ch<'a'||ch>'z') ch=getchar();
	while (ch>='a'&&ch<='z') {a[++len]=ch;ch=getchar();}
}
int main() {
	n=read();
	for (int i=1;i<=n;i++) {
		x=read();
		if (i%2==1) haI[x]++;
		else haII[x]++;
	}
	for (int i=1;i<=100000;i++) {
		if (haI[i]>haI[firI]) {
			secI=firI;
			firI=i;
		} else {
			if (haI[i]>haI[secI]) secI=i;
		}
	}
	for (int i=1;i<=100000;i++) {
		if (haII[i]>haII[firII]) {
			secII=firII;
			firII=i;
		} else {
			if (haII[i]>haII[secII]) secII=i;
		}
	}
	if (firI!=firII) cout<<n-haI[firI]-haII[firII]<<"\n";
	else {
		cout<<min(n-haI[firI]-haII[secII],n-haI[secI]-haII[firII])<<"\n";
	}
	return 0;
}


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

int main()
{
	int N,sum=0;
	while(cin>>N)
	{
		int B[N-1],A[N];
		memset(A,0,sizeof(A));
		for(int i=0;i<N-1;i++)
			cin>>B[i];
		A[0]=B[0];
		A[N-1]=B[N-2];
		for(int i=0;i<N-2;i++)
		{
			if(B[i]<=B[i+1])
				A[i+1]=B[i];
			else
				A[i+1]=B[i+1];
		}
		for(int i=0;i<N;i++)
			sum+=A[i];
		cout<<sum<<"\n";
	}
	return 0;
}


Measured memory_bytes: 256
#!usr/bin/env python3

import sys


def generate_buidlings_with_residents(building, floor, room):
    buildings = {
        key: [[0 for col in range(room)] for row in range(floor)]
        for key in range(1, building+1)
    }

    n = int(sys.stdin.readline())
    for i in range(n):
        lst = [int(num) for num in sys.stdin.readline().split()]
        buildings[lst[0]][lst[1]-1][lst[2]-1] += lst[3]

    return buildings


def print_buildings():
    separator = '####################'
    buildings_with_residents = generate_buidlings_with_residents(4, 3, 10)

    for idx, (key, value) in enumerate(buildings_with_residents.items()):
        for floor in value:
            print(' %s %s %s %s %s %s %s %s %s %s' % tuple(floor))
        if key < len(buildings_with_residents):
            print(separator)


def main():
    print_buildings()


if __name__ == '__main__':
    main()

Measured memory_bytes: 7728
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
int INF=1e9;
int MOD=1e9+7;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
double EPS = 1e-10;
const int mod=1e9+7;
const double pai=3.14159265358979;
int main(){
	ll n,m;
	cin>>n>>m;
	if(n*2>=m){
		cout<<m/2<<endl;
	}else{
		ll ans=n;
		m-=n*2;
		ans+=m/4;
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
  public static void main(String args[]){
  Scanner scanner = new Scanner(System.in);
  String esu = scanner.next();
  int raincnt = 0;
  int rainrec = 0;
  for(int i=0;i<3;i++){
    if(esu.charAt(i)=='R'){    
      raincnt++;
    }else{
      if(raincnt>rainrec){
      rainrec = raincnt;
      }else{
      }
      raincnt = 0;
 
    }
  }

    if(raincnt>rainrec){
      System.out.println(raincnt);
      }else{
      System.out.println(rainrec);
      }
  }
}



Measured memory_bytes: 26896
N = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(N - 1):
  if p[i] == i + 1:
    p[i], p[i + 1] = p[i + 1], p[i]
    ans += 1
if p[N - 1] == N:
  ans += 1
print(ans)

Measured memory_bytes: 52908
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define n_p(v) next_permutation(v.begin(),v.end())
#define to_ll(b) stoll(b)
#define MOD 1000000007
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp

signed main(){
	int n,m; cin>>n>>m;
	if(n!=0) n--;
	if(m!=0) m--;
	cout<<m*n;
	
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Solution sol = new Solution();
		sol.solve(in, out);
		out.close();
	}

	private static class Solution {
		private void solve(InputReader in, PrintWriter out) {
			out.println(in.ni() >= 30 ? "Yes" : "No");
		}
	}

	private static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		private InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		private String n() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		private int ni() {
			return Integer.parseInt(n());
		}
	}
}

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

int main(void) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }

    sort(a.begin(), a.end());
    std::set<int> st;
    for (int i = 0; i < n; i++) {
        st.insert(a.at(i));
    }
    if (st.size() <= k) {
        cout << 0 << endl;
    } else {
        // 整数ごとのボールの個数を調べる
        vector<int> ball(st.size());
        for (int i = 0; i < st.size(); i++) {
            ball.at(i) = 0;
        }
        int tmp = a.at(0), count = 0;
        for (int i = 0; i < n; i++) {
            if (a.at(i) != tmp) {
                count++;
                tmp = a.at(i);
            }
            ball.at(count)++;
        }

        sort (ball.begin(), ball.end());
        int ans = 0;
        for (int i = 0; i < st.size() - k; i++) {
            ans += ball.at(i);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 11136
#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<list>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII > VP;

#define AIN(A, B, C) assert(IN(A, B, C))

//typedef int LL;
typedef long long int LL;
//typedef __int64 LL;

VI V[100005];
int g[100005];
int n;

int G(int at, int par) {
	g[at] = 0;
	for (int v : V[at]) {
		if (par == v) continue;
		int x = G(v, at);
		x++;
		g[at] ^= x;
	}
	return g[at];
}

int main()
{
	MEM(g, -1);
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		V[u].push_back(v);
		V[v].push_back(u);
	}

	int ans = G(1, 0);
	if (ans == 0) printf("Bob\n");
	else printf("Alice\n");


	return 0;
}


Measured memory_bytes: 10752
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	alpha = input()
	if ord(alpha) <= 90:
		print("A")
	else:
		print("a")


if __name__ == '__main__':
	main()

Measured memory_bytes: 64680
n = int(input())
d = dict()
for i in range(n):
  S = ''.join(sorted(list(input())))
  if S in d.keys():
    d[S] +=1
  else:
    d[S] = 1
 
ans = 0
for i in d.values():
  ans += i*(i-1)//2
print(ans)

Measured memory_bytes: 22176
#include <iostream>
#include <string>
#include <algorithm>


int main() {
  
  std::string inputString;
  std::cin >> inputString;
  
  if (inputString.length() == 2) {
    std::cout << inputString << std::endl;
  } else {
    std::reverse(begin(inputString), end(inputString));
    std::cout << inputString << std::endl;
  }
  
}

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

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

	int ans;

	if (n <= 111) ans = 111;
	else if (112 <= n && n <= 222) ans = 222;
	else if (223 <= n && n <= 333) ans = 333;
	else if (334 <= n && n <= 444) ans = 444;
	else if (445 <= n && n <= 555) ans = 555;
	else if (556 <= n && n <= 666) ans = 666;
	else if (667 <= n && n <= 777) ans = 777;
	else if (778 <= n && n <= 888) ans = 888;
	else if (889 <= n && n <= 999) ans = 999;
		
	cout << ans << endl;
		
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
using namespace std;
#define ll long long

int main () {
  int a, b;
  cin >> a >> b;
  if (a != 1 && b != 1) {
    cout << 1 << endl;
  }
  else {
    if (a != 2 && b != 2) {
      cout << 2 << endl;
    }
    else {
      cout << 3 << endl;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int main(){

	int a[5];
	int min = 9, min_i = 0;
	for(int i=0; i<5; i++){
		cin >> a[i];	
		if( a[i] % 10 <= min && a[i] % 10 != 0 ){
				min = a[i] % 10;
				min_i = i;
		}		
	}

	int time=0;
	for(int i=0; i<5; i++){
		if( i == min_i )
			time += a[i];
		else{
			if(a[i] % 10 != 0)
				time += (a[i]/10 + 1) * 10;
			else
				time += a[i];
		}

	}

	cout << time << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    Main(){
	Scanner sc = new Scanner(System.in);

	while(sc.hasNext()){
	    int n = sc.nextInt(), m = sc.nextInt(), p = 1, tn;
	    if(n+m == 0) break;
	    int[] map = new int[n+1];
	    int[] dice = new int[m];

	    for(int i = 1; i <= n; i++) map[i] = sc.nextInt();
	    for(int i = 0; i < m; i++) dice[i] = sc.nextInt();

	    for(tn = 0; tn < m && p < n; tn++){
		p += dice[tn];
		if(p <= n){
		    p += map[p];
		    if(p < 1) p = 1;
		}
	    }

	    System.out.println(Integer.toString(tn));
	}
    }

    public static void main(String[] args){
	new Main();
    }
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[200005];
int l[200005], r[200005];

int pos[200005];
set<int> s;
set<int>::iterator its;
int main(){
	LL ans = 0;
	int n;
	scanf("%d", &n);
	s.insert(0);
	s.insert(n+1);
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}	
	for(int i=1;i<=n;i++){
		int p = pos[i];
		its = s.lower_bound(p);
		r[p] = *its;
		its--;
		l[p] = *its;

		s.insert(p);
	}
	for(int i=1;i<=n;i++){
		int le = i-l[i];
		int ri = r[i]-i;
		ans += (LL)le*ri*a[i];
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 12800
//ABC 051-C
#define _USE_MATH_DEFINES

#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#include <numeric>
#include <string>
#include <map>
#include <sstream>
using namespace std;

int main() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;

	for (int i = 0; i < ty - sy; i++) cout << "U";
	for (int i = 0; i < tx - sx; i++) cout << "R";
	for (int i = 0; i < ty - sy; i++) cout << "D";
	for (int i = 0; i < tx - sx; i++) cout << "L";

	cout << "L";
	for (int i = 0; i < ty - sy + 1; i++) cout << "U";
	for (int i = 0; i < tx - sx + 1; i++) cout << "R";
	cout << "D";
	cout << "R";
	for (int i = 0; i < ty - sy + 1; i++) cout << "D";
	for (int i = 0; i < tx - sx + 1; i++) cout << "L";
	cout << "U" << endl;
}

Measured memory_bytes: 256