akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdio.h>
#include<vector>
using namespace std;

char b;


int main() {
	cin >> b;
	
	if (b == 'A') {
		cout << 'T' << endl;
	}
	else if (b == 'T') {
		cout << 'A' << endl;
	}
	else if (b == 'G') {
		cout << 'C' << endl;
	}
	else if (b == 'C') {
		cout << 'G' << endl;
	}

	return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n, p, c = 0;
        string s;
        cin >> n >> p >> s;
        ll sol = 0;
        if (p == 2 || p == 5) {
                for (int i = 0; i < n; i++) {
                        int x = s[i] - '0';
                        if (x % p == 0)
                                sol += i + 1;
                }
                cout << sol << "\n";
                return 0;
        }
        vector<int> put(n);
        put[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--)
                put[i] = 10 * put[i + 1] % p;
        vector<int> f(p, 0);
        f[0]++;
        for (int i = 0; i < n; i++) {
                int x = s[i] - '0';
                c = (c + put[i] * x) % p;
                sol += f[c]++;
        }
        cout << sol << "\n";
        return 0;
}


Measured memory_bytes: 1428
#include <bits/stdc++.h>
using namespace std;
#define Rep(i, N) for(int i = 0; i < N; i++)
#define INF 1 << 28
typedef pair<int,int> Pi;
#define pb push_back
#define fi first
#define se second

int main()
{
  int D, N, M;
  int A, B;
  while(cin >> D, D) {
    cin >> N >> M;
    vector<int> d;
    d.pb(-114514); d.pb(0);
    Rep(i, N - 1) {
      cin >> A; d.pb(A);
    }
    d.pb(D);
    
    sort(d.begin(), d.end());
    int sum = 0;
    while(M--) {
      cin >> A;
      int pl = lower_bound(d.begin(), d.end(), A) - d.begin();
      sum += min(d[pl] - A, A - d[pl - 1]);
    }
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 3452
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, s, n) for(int i = s; i < n; i++)
#define rRep(i, n) for(int i = n - 1; i >= 0; i--)
#define pii pair<int, int>
#define vii vector<pair<int, int>>
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define endl "\n"


int32_t main() {
    FAST
    int n, k;
    cin >> n >> k;
    vi vec(n), dp(n, 1e9);
    REP(i, 0, n)
        cin >> vec[i];
    dp[0] = 0;
    REP(i, 1, min(k + 1, n)) 
        dp[i] = abs(vec[i] - vec[0]);
    //dp[1] = abs(vec[1] - vec[0]);
    
    REP(i, 1, n) {
        REP(j, i + 1, min(n, i + k + 1)) {
            dp[j] = min(dp[j], dp[i] + abs(vec[j] - vec[i]));
        }
    }
    cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

long long f(const vector<long long>& v, const long long mod)
{
	int size = v.size();

	long long l = 0;
	for(int i=1; i<=size; i++)
	{
		l += ((i-1)*v[i-1] - (size-i)*v[i-1]) % mod;
		l %= mod;
	}

	return l;
}

int main(void)
{
	int n, m;
	cin >> n >> m;

	vector<long long> x(n);
	for(int i=0; i<n; i++)
		cin >> x[i];

	vector<long long> y(m);
	for(int i=0; i<m; i++)
		cin >> y[i];

	const long long mod = 1E9 + 7;
	long long dx = f(x, mod);
	long long dy = f(y, mod);

	cout << dx*dy%mod << endl;

	return 0;
}


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

using namespace std;

long long n, a, b;

int main()  {
    cin >> n >> a >> b;
    if((n <= 2LL && a != b) || b < a)  {
        cout << "0\n";
        return 0;
    }
    long long ans;
    ans = (n - 2LL) * (b - a) + 1LL;
    cout << ans << "\n";
    return 0;
}


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

int main()
{
    ll n;cin>>n;
    vector<ll>dp(3);//dp[i] is last day end with i
    for(ll day=0;day<n;day++){
      vector<ll>new_dp(3,0);
      vector<ll>a(3);
      for(ll i=0;i<3;i++){
          cin>>a[i];
      }
      for(ll i=0;i<3;i++){
          for(ll j=0;j<3;j++){
              if(i!=j){
                  new_dp[j]=max(new_dp[j],dp[i]+a[j]);
              }
          }
      }
      dp=new_dp;
    }
    cout<<max({dp[0],dp[1],dp[2]});
    return 0;
}


Measured memory_bytes: 3608
#include <cstdio>
#include <iostream>

struct Process {
    char name[10];
    int  time;
};
Process process_queue[100000];
int first_idx = 0;
int last_idx  = 0;

void Push(Process process)
{
    process_queue[last_idx] = process;
    if (last_idx >= 100000) {
        last_idx = 0;
    } else {
        last_idx += 1;
    }
}

void Pop(Process &process)
{
    process = process_queue[first_idx];
    if (first_idx >= 100000) {
        first_idx = 0;
    } else {
        first_idx += 1;
    }
}

bool IsNull()
{
    if (first_idx == last_idx) {
        return true;
    } else {
        return false;
    }
}

int main(int argc, char* argv[])
{
    int queue_size, quantum;
    scanf("%d", &queue_size);
    scanf("%d", &quantum);
    for (int i = 0; i < queue_size; i++) {
        Process process_i;
        scanf("%s", &process_i.name);
        scanf("%d", &process_i.time);
        Push(process_i);
    }

    int consume_time = 0;
    while(!IsNull()) {
        Process target_process;
        Pop(target_process);
        int left_time = target_process.time - quantum;
        if (left_time > 0) {
            target_process.time = left_time;
            Push(target_process);
            consume_time += quantum;
        } else {
            printf(
                "%s %d\n",
                target_process.name,
                consume_time + target_process.time
            );
            consume_time += target_process.time;
        }
    }

    return 0;
}


Measured memory_bytes: 4672
import sys
input = sys.stdin.readline

N, M, P = map(int, input().split())
edges = [None] * M
for i in range(M):
    A, B, C = map(int, input().split())
    edges[i] = (A, B, P-C)

dist = [float('inf')] * (N+1)
dist[1] = 0
for i in range(N-1):
    for u, v, weight in edges:
        if dist[v] > dist[u] + weight:
            dist[v] = dist[u] + weight
negative = [False] * (N+1)
for i in range(N):
    for u, v, weight in edges:
        if negative[u]:
            negative[v] = True
        if dist[v] > dist[u] + weight:
            dist[v] = dist[u] + weight
            negative[v] = True
print(max(-dist[N], 0) if not negative[N] else -1)


Measured memory_bytes: 44688
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int Q,limit,N;
int current_pos;
int BIT[500000],number[500000];

map<int,int> MAP;

void add(int loc,int value){

	BIT[loc] += value;

	loc += loc & -loc;

	while(loc <= N){
		BIT[loc] += value;
		loc += loc & -loc;
	}
}

int getSum(int loc){

	int sum = BIT[loc];

	loc -= loc & -loc;

	while(loc > 0){
		sum += BIT[loc];
		loc -= loc & -loc;
	}
	return sum;
}

int getLoc(int sum){

	int left = 1,right = current_pos-1,m = (left+right)/2;
	int ret;

	while(left <= right){
		if(getSum(m) >= sum){
			ret = m;
			right = m-1;
		}else{
			left = m+1;
		}
		m = (left+right)/2;
	}
	return ret;
}

void func(){

	N = Q;

	for(int i = 0; i <= N; i++)BIT[i] = 0;
	MAP.clear();

	int command,num = 0,del_pos,print_pos;
	current_pos = 1;
	int x;

	for(int loop = 0; loop < Q; loop++){
		scanf("%d %d",&command,&x);

		switch(command){
		case 0:
			add(current_pos,1);
			number[current_pos] = x;
			MAP[x] = current_pos;
			num++;
			current_pos++;
			if(num > limit){
				del_pos = getLoc(1);
				add(del_pos,-1);
				num--;
			}
			break;
		case 1:
			del_pos = getLoc(x);
			add(del_pos,-1);
			num--;
			break;
		case 2:
			print_pos = getLoc(x);
			printf("%d\n",number[print_pos]);
			break;
		case 3:
			del_pos = MAP[x];
			add(del_pos,-1);
			num--;
			break;
		}
	}
	printf("end\n");
}

int main(){

	while(true){
		scanf("%d %d",&Q,&limit);
		if(Q == 0 && limit == 0)break;

		func();
	}
	return 0;
}

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

int main()
{
  int N; cin >> N;
  string s; cin >> s;
  
  int count=0;
  for(int i=0;i<N;i++){
  	if(s.at(i) == 'R') count++;
  }
  
  if(count > s.size()-count) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;

    int main() {
        long long A,B;
         char op;
         cin>>A>>op>>B;
         if(op=='-'){
             cout<<A-B;
         }else{
             cout<<A+B;
         }

            }



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

bool isPrime(long long x){
    if(x == 2) return true;
    if(x%2 == 0 || x <= 2) return false;
    double r = sqrt(x);
    for(long long i=3; i<=r; i+=2) if(x%i == 0) return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    ll n; cin >> n;
    vi a(n), left(n), right(n);
    rep(i, n) cin >> a[i];

    // 累積gcdの計算（左右）
    for(ll i=0; i<n; i++){
        if(i == 0) left[i] = a[i];
        else left[i] = __gcd(a[i], left[i-1]);
    }
    for(ll i=n-1; i>=0; i--){
        if(i == n-1) right[i] = a[i];
        else right[i] = __gcd(a[i], right[i+1]);
    }

    // a[i]を書き換える＝a[i]を除くn-1個のgcdと等価
    ll ans = 0;
    rep(i, n){
        // a[i]を除いて最大公約数を計算
        if(i == 0) chmax(ans, right[1]);
        else if(i == n-1) chmax(ans, left[n-2]);
        else chmax(ans, __gcd(left[i-1], right[i+1]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] ab = scanner.nextLine().split(" ", 2);
        int a = Integer.parseInt(ab[0]);
        int b = Integer.parseInt(ab[1]);

        int plus = a + b;
        int minus = a - b;
        int mult = a * b;
        System.out.println(Math.max(plus, Math.max(minus, mult)));
    }
}


Measured memory_bytes: 22356
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  
  if(a+b==c||b+c==a||c+a==b){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

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

    long long money = 1000;
    for (int i = 0; i + 1 < N; i++) {
        if (A[i] < A[i + 1]) {
            long long stock = money / A[i];
            money %= A[i];
            money += A[i + 1] * stock;
        }
    }

    cout << money << endl;
}

Measured memory_bytes: 3580
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int main()
{
    int n; cin>>n;
    ll a[100010];
    for(int i=1; i<=n; i++) cin>>a[i];
    ll dp[2][100010];
    fill(dp[0], dp[0]+n+1, -1e18);
    fill(dp[1], dp[1]+n+1, -1e18);
    dp[0][1]=a[1], dp[1][1]=-a[1];
    for(int i=1; i<n-1; i++){
        for(int j=0; j<2; j++){
            if(j==0) dp[0][i+1]=max(dp[0][i+1], dp[j][i]+a[i+1]);
            else dp[0][i+1]=max(dp[0][i+1], dp[j][i]-a[i+1]);
            if(j==0) dp[1][i+1]=max(dp[1][i+1], dp[j][i]-a[i+1]);
            else dp[1][i+1]=max(dp[1][i+1], dp[j][i]+a[i+1]);
        }
    }
    cout<<max(dp[0][n-1]+a[n], dp[1][n-1]-a[n])<<endl;
    return 0;
}

Measured memory_bytes: 2560
#include <stdio.h>
#define MAX_N 100005

int a[MAX_N];
int dist[MAX_N];
int skip[MAX_N];

int abs(int x)
{
    return x >= 0? x: -x;
}

int main(void)
{
    int n;
    int sum = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n + 1; i++)
        dist[i] = abs(a[i] - a[i - 1]);
    for (int i = 1; i <= n + 1; i++)
        sum += dist[i];
    for (int i = 1; i <= n; i++)
        skip[i] = abs(a[i + 1] - a[i - 1]);
    for (int i = 1; i <= n; i++) {
        int cur = sum - dist[i] - dist[i + 1] + skip[i];
        printf("%d\n", cur);
    }
}


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

int main()
{
    char ch;
    cin >> ch;
    if (ch >= 'A' && ch <= 'Z')
    {
        cout << "A" << endl;
    }
    else
    {
        cout << "a" << endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int m, d;
  cin >> m >> d;

  int d1, d10;
  int cnt = 0;
  for (int i = 2; i <= m; i++) {
    for (int j = 22; j <= d; j++) {
      d1 = j % 10;
      if (d1 < 2) {
        continue;
      }
      
      d10 = j / 10;
      if (d1 * d10 == i) {
        cnt++;
        if (d <= i) {
          cnt++;
        }
      }
    }
  }

  cout << cnt << endl;
}

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

list = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9,'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
list2 = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I','J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

for s in S:
    index = list[s] + N-1
    if index > 25:
        index -= 26
    print(list2[index], end='')


Measured memory_bytes: 43880
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
signed main(){
	int a[4];
	cin>>a[0]>>a[1]>>a[2]>>a[3];
	sort(a,a+4);
	if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9)puts("YES");
	else puts("NO");
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007 
#define N 100005
#define M 1000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

int r,c,n;
vector<ii> cc[4];

void add(int x,int y,int lab) {

	if(x==0) cc[0].pb({y,lab});
	else if(y==c) cc[1].pb({x,lab});
	else if(x==r) cc[2].pb({-y,lab});
	else cc[3].pb({-x,lab});

}

bool in(int x,int y) {

	return x>0 && x<r && y>0 && y<c;

} 

int main() {

	int cnt=0;

	scanf("%d %d %d",&r,&c,&n);

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

		int a,b,c,d;

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

		if(in(a,b) || in(c,d)) continue ;

		add(a,b,cnt);
		add(c,d,cnt);

		cnt++;

	}

	stack<int> s;

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

		sort(all(cc[i]));

		for(auto x:cc[i]) {

			if(sz(s) && x.nd==s.top()) s.pop();
			else s.push(x.nd);

		}

	}

	if(sz(s)) printf("NO");
	else printf("YES");

}	

Measured memory_bytes: 2520
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000];

double f(int A,int B,int C,int D){
  return (double)(a[A]+a[B])/(double)(a[C]-a[D]);
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  reverse(a,a+n);
  double ans=max(f(2,3,0,1),f(0,3,1,2));
  for(int i=2;i+1<n;i++){
    ans=max(ans,f(0,1,i,i+1));
  }
  printf("%.10f\n",ans);
  return 0;
}

Measured memory_bytes: 3272
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A, B;
  int plan_A, plan_B;
  cin >> N >> A >> B;
  
  plan_A = N * A;
  plan_B = B;
  
  if (plan_A < plan_B) {
    cout << plan_A << endl;
  } else {
    cout << plan_B << endl;
  }
  
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
typedef long long int ll;
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i=0; i<n; i++){
		int num;
		cin>>num;
		a.at(i)=num-1;
	}
	vector<int> visited(n,0);
	int tmp=0;
	int cnt=0;
	while(true){
		if(visited.at(tmp)==1){
			cout << "-1" << endl;
			return 0;
		}
		if(tmp==1){
			cout << cnt << endl;
			return 0;
		}
		visited.at(tmp)=1;
		tmp=a.at(tmp);
		cnt++;
	}

	return 0;
}

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

int main(){
  int N;
  cin >> N;
  map<int,int> cnt;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    cnt[a] ++;
  }

  int ans=0, del=0;
  for(auto& it : cnt){
    ans += it.second;
    del += it.second - 1;
  }
  ans = ans - (del + del%2);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4992
n = int(input())
l = [input()]

ans = 'Yes'

for i in range(1, n):
    s = input()
    if s in l:
        ans = 'No'
        break
    else:
        if l[-1][-1].endswith(s[0]):
            l.append(s)
        else:
            ans = 'No'
            break

print(ans)

Measured memory_bytes: 3060
n=int(input())
if n%2!=0:
    print(0)
else:
    a=0
    b=0
    n=n//2
    import math
    for i in range(1,100):
        a+=n//(5**i)
    n=n*2
    for j in range(1,100):
        b+=n//(2**j)
    print(min(a,b))

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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

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

///**************************DONE****************************///

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

    if(a > 9 || b > 9)
        cout << -1 << '\n';
    else
        cout << a * b << '\n';
    return 0;
}


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

ans=0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i*500+j*100+k*50 == x:
                ans+=1
print(ans)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
string s;
int n,k;
long long memo[101][4][3];
long long dp(int index,int num,bool ssf){
    if (num<0) return 0;
    if (num==0) return 1;
    if (index==n) return 0;
    if (memo[index][num][ssf]!=-1) return memo[index][num][ssf];
    long long largest=9,ans=0;
    if (ssf) largest=s[index]-'0';
    for (int i=0;i<=largest;i++){
        int cur=num;
        if (i!=0) cur--;
        ans+=dp(index+1,cur,ssf && i==largest);
    }
    return memo[index][num][ssf]=ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(memo,-1,sizeof(memo));
    cin>>s>>k;
    n=s.size();
    cout<<dp(0,k,true);
}

Measured memory_bytes: 256
s = input()
a = [0]*len(s)
r, l = 0, 0

for i in range(len(s)):
    r += 1
    if s[i] == 'L':
        a[i-1] += r//2
        a[i] += (r+1)//2
        r = 0
        
for j in range(len(s)-1, -1, -1):
    l += 1
    if s[j] == 'R':
        a[j+1] += l//2
        a[j] += (l+1)//2
        l = 0
    a[j] -= 1

print(*a)



Measured memory_bytes: 10776
# frozen_string_literal: true

def read
  [gets.to_i, gets.chomp]
end

def solve(_, s)
  min = Float::INFINITY
  cnt = { e: 0, w: 0 }
  table = [cnt.dup]
  s.chars.each_with_index do |c, i|
    k = if c == 'W' then :w
        else :e
        end
    cnt[k] += 1
    table[i + 1] = cnt.dup
  end
  table.each do |el|
    c = el[:w] + table.last[:e] - el[:e]
    min = c if c < min
  end
  min
end

puts solve(*read)
# puts [
#   solve(5, 'WEEWW') == 1,
#   solve(12, 'WEWEWEEEWWWE') == 4,
#   solve(8, 'WWWWWEEE') == 3
# ].all?


Measured memory_bytes: 103260
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

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

int main() {
	string s;
	cin >> s;
	bool f = false;
	for(int i = 1; i < s.size(); i++) {
		if(string(s.begin()+i-1, s.begin()+i+1) == "AC") f = true;
	}
	if(f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}


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

#define gcd(a,b)     __gcd(a,b)
#define lcm(a,b)     (a*(b/gcd(a,b)))

#define pb   push_back
#define endl "\n"

#define ll  long long
#define ull unsigned long long

#define W(t)            while(t--)
#define rep(i,n)        for(int i = 0; i < n; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

int main()
{
     IOS
     string s;
     ll n =0,i;

     cin>>s;

     for(i = 0; i < s.size(); i++)
          n += (s[i]-48);
     if(n%9==0)
          cout<<"Yes\n";
     else
          cout<<"No\n";


     return 0;
}


Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d;
  
  cin >> a >> b >> c >> d;
  if(a + b == c + d){
    cout << "Balanced";
  }
  else if(a + b > c + d){
    cout << "Left";
  }
  else{
    cout << "Right";
  }
  
  	/*
  int pay, a, answer;
  string op;
  
  cin >> pay >> a;
  answer = pay % 500 - 1*a;
  
  if(answer <= 0){
  	cout << "Yes";
  }
  else{
    cout << "No";
  }
  */
}

Measured memory_bytes: 3636
def bubble_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})
            
    for i in range(N):
        for j in range(N-1, i, -1):
            if card[j]['value'] < card[j-1]['value']:
                card[j], card[j-1] = card[j-1], card[j]

    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


def selection_sort(C, N):
    card = []
    for c in C:
        card.append({'suit': c[0], 'value': int(c[1])})

    for i in range(N):
        min_j = i
        for j in range(i, N):
            if card[j]['value'] < card[min_j]['value']:
                min_j = j
        card[i], card[min_j] = card[min_j], card[i]
        
    new_C = []
    for i in range(N):
        new_C.append(card[i]['suit'] + str(card[i]['value']))
        
    return new_C


N = int(input().rstrip())
C = input().rstrip().split()

C_b = bubble_sort(C, N)
C_s = selection_sort(C, N)

print(' '.join(C_b))
print('Stable')

print(' '.join(C_s))
if C_s == C_b:
    print('Stable')
else:
    print('Not stable')


Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
int main() {
  int r, g, b;
  cin >> r >> g >> b;
  if ((g * 10 + b) % 4 == 0) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

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


int main(){
    long long A, B, K;
    std::cin >> A >> B >> K;

    if(K >= (A + B)){
        A = 0;
        B = 0;
    }else if(K >= A){
        B = B - (K - A);
        A = 0;
    }else{
        A = A - K;
    }

    std::cout << A << " " << B;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <climits>
using namespace std;

#define MOD1097 1000000007

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mpair make_pair
#define pm(first, second) pb(mpair(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(X) (X).begin(), (X).end()
#define reall(X) (X).rbegin(), (X).rend()
#define divcel(a, b) (((a) + ((b) - 1)) / (b))

int main(){

	int a, b;
	cin >> a >> b;
	cout << a*b << endl;

	return 0;
}


Measured memory_bytes: 3576
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 2e3 + 10;
const int Mod = 924844033;

int f[2][maxn], g[2][maxn];
int fac[maxn];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	fac[0] = 1;
	for (int i = 1; i <= n; ++ i)
		fac[i] = 1ll * fac[i - 1] * i % Mod;
	g[0][0] = 1;
	int cur = 0, lst = 1;
	for (int T = 2; T; -- T)
	{
		for (int i = 1; i <= k; ++ i)
		{
			int t = (n - i + k) / k - 1;
			if (!t) continue;
			swap(cur, lst);
			for (int j = 1; j <= n; ++ j)
				f[cur][j] = (f[lst][j - 1] + g[lst][j - 1]) % Mod;
			for (int j = 0; j < n; ++ j)
				g[cur][j] = (f[lst][j] + g[lst][j]) % Mod;
			while (-- t)
			{
				swap(cur, lst);
				for (int j = 1; j <= n; ++ j)
					f[cur][j] = g[lst][j - 1];
				for (int j = 0; j < n; ++ j)
				
					g[cur][j] = (f[lst][j] + g[lst][j]) % Mod;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; ++ i)
		(ans += (long long) (i & 1 ? -1 : 1) * (f[cur][i] + g[cur][i]) * fac[n - i] % Mod) %= Mod;
	printf("%d\n", (ans + Mod) % Mod);
	return 0;
}


Measured memory_bytes: 256
n = int(input())
V = list(map(int,input().split()))
Ce = {}
Co = {}
for i in range(n):
    v = V[i]
    if i%2==0:
        if v not in Ce:
            Ce[v] = 0
        Ce[v] += 1
    else:
        if v not in Co:
            Co[v] = 0
        Co[v] += 1
Ce = sorted(list(Ce.items()),key=lambda x:x[1],reverse=True)
Co = sorted(list(Co.items()),key=lambda x:x[1],reverse=True)
if len(Ce)==1 and len(Co)==1 and Ce[0][0]==Co[0][0]:
    m = n//2
else:
    if Ce[0][0]!=Co[0][0]:
        m = n-Ce[0][1]-Co[0][1]
    else:
        m1 = n-Ce[1][1]-Co[0][1]
        m2 = n-Ce[0][1]-Co[1][1]
        m = min(m1,m2)
print(m)

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

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

    int ans = 0;
    rep(i,10)rep(j,10)rep(k,10) {
        auto isOK = [&](int i, int j, int k) {
            int tmp = 0;
            for(auto ch : s) {
                if (tmp == 0 && ch - '0' == i) tmp++;
                else if (tmp == 1 && ch - '0' == j) tmp++;
                else if (tmp == 2 && ch - '0' == k) {
                    tmp++;
                    break;
                }
            }
            return (tmp == 3);
        };
        if(isOK(i,j,k)) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define int long long
using P = pair<int,int>;

int n;
void dfs(string s,char mx){
  if(s.size() == n){
    cout << s << endl;
    return;
  }
  for(char c = 'a'; c <= mx;c++){
    string t = s;
    t += c;
    dfs(t,max((int)c+1,(int)mx));
  }
}
signed main(){
  cin >> n;
  dfs("",'a');
}

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

int main(){
    int H, W;

    while(1){

        cin >> H >> W;

        if (H == 0 && W ==0) break;
        else{
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if ( (i + j) % 2 == 0 ) cout << "#";
                    else cout << ".";
                }
                cout << endl;
            }
            cout << endl;
        }
    }

}



Measured memory_bytes: 3088
import sys
from fractions import gcd
import bisect

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
s = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]



a, p = na()

keppen = 3 * a + p

print(keppen // 2)


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

typedef long long ll;
ll a[205];

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll sum=1000;
	for(int i=2;i<=n;i++){
		if(a[i]>a[i-1]){
			sum=sum/a[i-1]*a[i]+sum%a[i-1];
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,i;
	cin>>a;
	for(i=1;i<=9;i++)
	{
		if(a%i==0 && a/i<=9)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}()

func getInt() (n int) {
	sc.Scan()
	n, _ = strconv.Atoi(sc.Text())
	return n
}
func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	N := getInt()
	S := getString()

	if n := N / 2; N%2 == 0 {
		for i := 0; i < n; i++ {
			if S[i] != S[i+n] {
				goto OUT
			}
		}
		fmt.Println("Yes")
		return
	}
OUT:
	fmt.Println("No")
}


Measured memory_bytes: 640
def solve():
    H, W = map(int, input().split())

    if H == 1 or W == 1:
        print("1")
        exit(0)
    
    if H % 2 == 0:
        print(H // 2 * W)
    else:
        ans = H * (W // 2)
        if W % 2 == 1:
            ans += H // 2 + 1
        print(ans)
if __name__ == '__main__':
    solve()

Measured memory_bytes: 3060
module Main where

import Data.List.Split
import Debug.Trace

algorithm :: Int -> Int ->  Int
algorithm n m = case m of
  0 -> n*100
  _ -> 2^m*((n-m)*100 + m*1900)

process :: [String] -> String
process ls = case splitOn " " (head ls) of
  [x, y] -> show $ algorithm (read x) (read y)
  _ -> "Wrong input"

main :: IO ()
main = do
  input <- getContents
  putStrLn $ process (lines input)

Measured memory_bytes: 508
#include<stdio.h>
int main()
{
int n,x[3],i,t;
scanf("%d",&n);
while(n--){
scanf("%d %d %d",&x[0],&x[1],&x[2]);

for(i=1;i<3;i++){
if(x[0]<x[i]){
t=x[0];
x[0]=x[i];
x[i]=t;
}
}
if((x[0]*x[0])==(x[1]*x[1]+x[2]*x[2]))
printf("YES\n");
else
printf("NO\n");


}
return 0;
}

Measured memory_bytes: 1008
#ifdef LOCAL
 #include <P.hpp>
 #include <debugger.hpp>
 #define __int64 __int64_t
#else 
 #include <bits/stdc++.h>
 #define debug(a...) //
 // #define __int64 long long int
#endif
using namespace std;

int main()
{
 ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
 int a;
 cin >> a;
 cout << a + a * a + a * a * a << '\n';
 return 0;
}


Measured memory_bytes: 3636
# abc124_b.py
# https://atcoder.jp/contests/abc124/tasks/abc124_b

# B - Great Ocean View /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# 東西に N個の山が連なっており、西の果てには広大な海が広がっています。
# 各山頂には旅館があり、あなたは海を眺められる旅館を選ぶことにしました。
# 西から i番目の山の高さは Hiです。
# 西から 1番目の山頂にある旅館からは必ず海を眺めることができます。
# 西から i(i=2,3,...,N) 番目の山頂にある旅館については、H1≤Hi, H2≤Hi, ..., 
# かつ Hi−1≤Hiのとき、その旅館から海を眺めることができます。
# これら N個の旅館のうち、海を眺められる旅館はいくつあるでしょうか。

# 制約
#     入力は全て整数である。
#     1≤N≤20
#     1≤Hi≤100

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N
# H1 H2 ... HN

# 出力
# 海を眺められる旅館の数を出力せよ。

# 入力例 1
# 4
# 6 5 6 8

# 出力例 1
# 3

# 西から 1,3,4番目の旅館から海を眺めることができます。

# 入力例 2
# 5
# 4 5 3 5 4

# 出力例 2
# 3

# 入力例 3
# 5
# 9 5 6 8 4

# 出力例 3
# 1


def log(line):
    if False:
        print(line)


def calculation(lines):
    # line = lines[0]
    N = int(lines[0])
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[1].split()))
    # values = list()
    # for i in range(6):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(Q):
    #     valueses.append(list(map(int, lines[i+1].split())))

    result = 0

    for i in range(N):
        if values[i] >= max(values[:i+1]):
            result += 1

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['4', '6 5 6 8']
        lines_export = [3]
    if pattern == 2:
        lines_input = ['5', ' 4 5 3 5 4']
        lines_export = [3]
    if pattern == 3:
        lines_input = ['5', '9 5 6 8 4']
        lines_export = [1]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9268
import numpy as np


if __name__ == '__main__':
    n,d  = list(map(int, input().split(" ")))

    coord_list = []
    count = 0
    for i in range(n):
        new_coord = list(map(int, input().split(" ")))
        if coord_list != None:
            for coord in coord_list:
                norm = np.linalg.norm(np.array(coord) - np.array(new_coord))
                if float.is_integer(norm) == True:
                    count += 1
            coord_list.append(new_coord)
        else:
            coord_list = [new_coord]
    print(count)

Measured memory_bytes: 12504
import java.util.Scanner;



import java.lang.*; 
import java.io.*; 
import java.util.*; 


public class Main
{
   
    public static void main(String[] args)
    {
        Scanner keyboard = new Scanner(System.in);
        String s = keyboard.nextLine();
        
        boolean flag = false;
        StringBuilder test = new StringBuilder();
        
        test.append(s);
        

        test = test.reverse();
        String reverse = test.toString();
        if(s.equals(reverse))
            flag = true;
        
        if(flag == true)
        {
            String s1 = s.substring(0,((s.length()-1)/2));
            
            
            String s2 =s.substring((s.length()+1)/2,s.length());
            
            if(s1.equals(s2))
            {
                System.out.println("Yes");
            }
            else
                System.out.println("No");
               
        }
        else   
            System.out.println("No");
    }
}



Measured memory_bytes: 23124
import math
def modpow(a, n, p):
  if n == 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
MOD = 1000000007
n = int(input())
#初期値が0の辞書
from collections import defaultdict
pp = defaultdict(lambda: 0) 
pm = defaultdict(lambda: 0) 
def seiki(x,y):
    tmp=math.gcd(x,y)
    return (x//tmp,y//tmp)

a0b0 = 0

for i in range(n):
  a, b = map(int, input().split())

  if a == 0 and b == 0:
    a0b0 += 1
  elif a == 0:
    pp[(0,1)] += 1

  elif b == 0:
    pm[(0,1)] += 1

  elif a*b>0:
    tmp = seiki(abs(a),abs(b))
    pp[tmp] += 1

  else:
    tmp = seiki(abs(b),abs(a))
    pm[tmp] += 1

ans = 1
for key in set(pp.keys()) | set(pm.keys()):
    pp_v=pp[key]
    pm_v=pm[key]
    ans*=(modpow(2,pm_v,MOD)+modpow(2,pp_v,MOD)-1)
    ans%=MOD

ans = (ans+a0b0-1) % MOD
print(ans)
    
  


Measured memory_bytes: 71096
#include<stdio.h>
int main(void){
  char s[100];
  char h[100];
  int a;
  scanf("%d\n",&a);
  scanf("%s%s",s,h);
  for(int i = 0; i < a; i++){
    	printf("%c%c",s[i],h[i]);
  }
  return 0;
}


Measured memory_bytes: 128
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()


n, m, s = map(int, input().split())

graph = [[] for _ in range(n+1)]

maxcoin = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))
    maxcoin += a

ryougae = [0, 0]*(n+1)

for i in range(1, n+1):
    c, d = map(int, input().split())
    ryougae[i] = [c, d]


mindist = [[10**20]*(maxcoin+1) for _ in range(n+1)]
hq = []
heapq.heappush(hq, (0, 1, min(maxcoin, s)))
while hq:
    minute, city, coin = heapq.heappop(hq)
    if mindist[city][coin] != 10**20:
        continue
    mindist[city][coin] = minute
    for i, pay, length in graph[city]:
        if coin >= pay:
            if mindist[i][coin-pay] != 10**20:
                continue
            heapq.heappush(hq, (minute+length, i, coin-pay))
    if coin < maxcoin:
        kankin = min(maxcoin, ryougae[city][0]+coin)
        if mindist[city][kankin] != 10**20:
            continue
        heapq.heappush(hq, (minute+ryougae[city][1], city, kankin))

for i in range(2, n+1):
    print(min(mindist[i]))


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

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

  if (N % 500 <= A)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3560
n=int(input())
a=list(map(int, input().split()))
b=[0]*n
for i in range(n):
    #print(sum(b[n-i::n-i]), a[-i-1], b)
    b[n-i-1]=(sum(b[n-i-1::n-i])+a[n-i-1])%2
#print(b)
print(sum(b))
for i in range(n):
    if b[i]==1:
        print(i+1, end=' ')
print()

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

int main(void){
    int n;
    cin >> n;
    vector<int> h(n);
    int count = 0,H=0;
    for (int i = 0; i < n; i++){
        cin >> h.at(i);
        if(H <= h.at(i)){
             H = h.at(i);
             count++;
        }
        }
        cout << count << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>

using namespace std;

int N;
int a[100100];

bool solve(){
	sort(a, a + N);
	if(a[0] <= a[N - 1] - 2) return false;
	if(a[0] == a[N - 1]){
		int x = a[0];
		if(N >= x * 2) return true;
		if(x == N - 1) return true;
		return false;
	}
	int x = a[N - 1];
	int k = 0;
	for(int i = 0; i < N; ++i){
		if(a[i] == x - 1) k++;
	}
//	printf("%d %d %d\n", x, k, N);
	if(x - k <= 0) return false;
	if(N - k >= (x - k) * 2) return true;
	return false;
}

void input(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		scanf("%d", a + i);
	}
}

int main(){
	input();
	bool flg = solve();
	if(flg) printf("Yes\n");
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    dsu A(n);
    rep(i,q){
        int t,u,v;
        cin>>t>>u>>v;
        if(t==0) A.merge(u,v);
        else cout<<A.same(u,v)<<"\n";
    }
}

Measured memory_bytes: 4004
#include <iostream>
#include <cmath>
#include <climits>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <set>

using namespace std;
using ll = long long;

template<typename T> void print(T t) { cout << t << endl; }
ll MOD = 1000000007;

int main() {
	ll N, D, ans = 0;
	cin >> N >> D;
	for (int i = 0; i < N; i++) {
		ll x, y;
		cin >> x >> y;
		if (x * x + y * y <= D * D) ans++;
	}
	print(ans);
}


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

int main() {
	stack<int> st;
	char s[10];
	int a=0,b=0;
	while(cin>>s){
		if(s[0]=='+'){
			a = st.top(); st.pop();
			b = st.top(); st.pop();
			st.push(a+b);
		}
		else if(s[0]=='-'){
			a = st.top(); st.pop();
			b = st.top(); st.pop();
			st.push(b-a);
		}
		else if(s[0]=='*'){
			a = st.top(); st.pop();
			b = st.top(); st.pop();
			st.push(a*b);
		}
		else{
			st.push(atoi(s));
		} 
	}
	cout << st.top() << endl;
	return 0;
}


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

using namespace std;

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

int h, w;
int a[15][15];

int check(int sx, int sy, int tx, int ty) {
  int bd = 1e9;
  for (int y = sy; y <= ty; y++) {
    bd = min({bd, a[y][sx], a[y][tx]});
  }
  for (int x = sx; x <= tx; x++) {
    bd = min({bd, a[sy][x], a[ty][x]});
  }
  return bd;
}

int calc(int sx, int sy, int tx, int ty, int bd) {
  int ans = 0;
  for (int y = sy; y <= ty; y++) {
    for (int x = sx; x <= tx; x++) {
      if (bd <= a[y][x]) return 0;
      ans += bd - a[y][x];
    }
  }
  return ans;
}

int main() {
  while (true) {
    cin >> h >> w;
    if (h == 0 && w == 0) break;
    rep(y, h) rep(x, w) cin >> a[y][x];

    int ans = 0, bd;
    for (int sy = 0; sy < h - 2; sy++) {
      for (int sx = 0; sx < w - 2; sx++) {
        for (int ty = sy + 2; ty < h; ty++) {
          for (int tx = sx + 2; tx < w; tx++) {
            //池の境界の高さの最小値を求める
            bd = check(sx, sy, tx, ty);

            //容量を求める
            ans = max(ans, calc(sx + 1, sy + 1, tx - 1, ty - 1, bd));
          }
        }
      }
    }
    cout << ans << "\n";
  }
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char ch[N];int n;
int main()
{
	scanf("%d",&n);
	scanf("%s",ch);
	int ans=1;
	for(int i=1;i<n;i++)
		if(ch[i]!=ch[i-1])ans++;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384
def f(n):
	if n & 1:
		return 3 * n +1
	else:
		return n // 2

cur = int(input())

ans = 1
ss = set([cur])

while True:
	ans += 1
	cur = f(cur)
	ss.add(cur)
	
	if ans > len(ss):
		break

print(ans)


Measured memory_bytes: 2940
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanInit()
	n := scanInt()
	a := make([]int,n+1) // 0はつかわないようにする
	// numbers := map[int]int{}
	for i:=1; i<=n; i++ {
		number := scanInt()
		a[i] = number
		//if _,ok := numbers[number]; !ok {
		//	numbers[number] = 0
		//}
		// numbers[number] += 1
	}
	// fmt.Println(numbers)
	sum := 0
	// j-Aj = Ai+i
	a_i := make(map[int]map[int]int)
	for i:= 1; i<=n; i++ {
		if _,ok := a_i[a[i]+i]; !ok{
			a_i[a[i]+i] = map[int]int{}
		}
		a_i[a[i]+i][i] = 1
	}
	for j:=1; j<=n; j++{
		if _,ok := a_i[j-a[j]]; ok{
			// まずその配列があるかどうか
			sum += len(a_i[j-a[j]])
		}
	}
	fmt.Println(sum)

}
var sc = bufio.NewScanner(os.Stdin)
func scanInit () {
	sc.Split(bufio.ScanWords)
}
func scanInt () int{
sc.Scan()
	i,_ := strconv.Atoi(sc.Text())
	return i
}
//func scan () string{
//  sc.Scan()
//	return sc.Text()
//}

Measured memory_bytes: 52028
#include<stdio.h>
#define N 1000000

int a[N],n;
int binarysearch(int key){
    int left = 0;
    int right = n;
    int mid;
    while(left<right){
        mid = (left + right)/2;
        if( key == a[mid] )return 1;
        if( key > a[mid] )left = mid+1;
        else if( key < a[mid] )right = mid;
    }
    return 0;
}

int main(){
    int i,q,k,sum = 0;
    
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&k);
        if(binarysearch(k))sum++;
    }
    printf("%d\n",sum);
    return 0;
    }



Measured memory_bytes: 2104
# 先頭と末尾が同じ場合はそれを省き、単体で完結するもの*K + 先頭と末尾が同じ場合の連結部分 * (K-1)
# ただし全部同じ場合は別で計算
# 3WA出した後にtestcase: aaaeiiiaiaa でやって気づいた
# -> なーにが気づきじゃ なんも変わっとらんやんけ
# *(k-1) 忘れてたっぽい？
from math import floor

s = input()
k = int(input())
if len(set(list(s))) == 1:
    print(floor((len(s) * k) / 2))
    exit()

if s[0] == s[-1]:
    # このへんの算数は手書きでいくつか書いて帰納的に導出した
    # だるいしs<=100なので愚直に数えるわ
    pre, suf = 0, 0
    for c in s:
        if c == s[0]:
            pre += 1
        else:
            break
    for c in s[::-1]:
        if c == s[-1]:
            suf += 1
        else:
            break
    # 先頭と末尾の連続する文字を除いたやつのうち連続するやつからいらないやつを数える
    idx = 0
    cc = 0
    t = s[pre : len(s) - suf]
    while idx < len(t):
        c = 0
        tmp = idx
        while tmp < len(t) and t[tmp] == t[idx]:
            tmp += 1
            c += 1
        if c > 1:
            cc += floor(c / 2)
        idx = tmp
    ans = floor(pre / 2) + cc * k + floor((pre + suf) / 2) * (k - 1) + floor(suf / 2)
    print(ans)
else:
    idx = 0
    cc = 0
    t = s[:]
    while idx < len(t):
        c = 0
        tmp = idx
        while tmp < len(t) and t[tmp] == t[idx]:
            tmp += 1
            c += 1
        if c > 1:
            cc += floor(c / 2)
        idx = tmp
    ans = cc * k
    print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100001,INF=1<<30;

int main(){
    
    int N,M;cin>>N>>M;
    vector<int> S(N),T(M);
    for(int i=0;i<N;i++){
        cin>>S[i];
    }
    for(int i=0;i<M;i++){
        cin>>T[i];
    }
    sort(all(S));
    sort(all(T));
    
    ll ans=1;
    
    for(int i=1;i<N;i++){
        if(S[i-1]==S[i]) ans=0;
    }
    for(int i=1;i<M;i++){
        if(T[i-1]==T[i]) ans=0;
    }
    
    int cana=0,canb=0;
    
    for(int i=N*M;i>=1;i--){
        if(binary_search(all(S),i)){
            if(binary_search(all(T),i)){
                cana++;
                canb++;
            }else{
                ans*=canb;
                cana++;
            }
        }else{
            if(binary_search(all(T),i)){
                ans*=cana;
                canb++;
            }else{
                ans*=(cana*canb-(N*M-i));
            }
        }
        ans=ans%mod;
    }
    
    cout<<ans<<endl;
    
}


Measured memory_bytes: 256