akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        long x=in.nextLong();
        long k=in.nextLong();
        long d=in.nextLong();
        if(x<0)
        {
            long y=Math.abs(x)/d;
            long x1=x+y*d;
            if(y>=k)
                System.out.println(Math.abs(x+k*d));
            else
            {
                if(((k-y)&1)==0)
                    System.out.println(Math.abs(x1));
                else
                    System.out.println(x1+d);
            }
        }
        else if(x>0)
        {
            long y=x/d;
            long x1=x-y*d;
            if(y>=k)
                System.out.println(x-k*d);
            else
            {
                if(((k-y)&1)==0)
                    System.out.println(x1);
                else
                    System.out.println(Math.abs(x1-d));
            }
        }
        else
        {
            if((k&1)==0)
                System.out.println(0);
            else
                System.out.println(d);
        }
    }
}


Measured memory_bytes: 35576
import java.util.*;
import java.util.stream.*;

class Main{
	public static void main(String[]$){
		Scanner s=new Scanner(System.in);
		System.out.println(
				IntStream.range(1,s.nextInt()+1)
				.filter(i->i%2==1)
				.filter(i->IntStream.range(1,i+1)
						.filter(j->i%j==0)
						.count()==8)
				.count()
				);
	}
}


Measured memory_bytes: 28876
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

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

    int maxVal = -2 * std::pow(10, 9);
    int minVal = 2 * std::pow(10, 9);
    
    int val;
    for(int i = 0; i < n; ++i){
        std::cin >> val;
        maxVal = std::max(maxVal, val - minVal);
        minVal = std::min(minVal, val);
    }

    std::cout << maxVal << std::endl;

    return 0;
}



Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
#define mod 1000000007;

int main(void){
  string str;
  cin >> str;
  if(str[0] == 'Y' && str[1] == 'A' && str[2] == 'K' && str[3] == 'I'){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		int i = 0;
		while (i < 1000) {
			String line = sc.nextLine();
			String[] array = line.split(" ");
			int H = Integer.parseInt(array[0]);
			int W = Integer.parseInt(array[1]);

			if (W == 0 && H == 0) {
				break;

			} else {

				for (int k = 0; k < H; k++) {

					for (int j = 0; j < W; j++) {
						System.out.print("#");
					}
					System.out.println();
				}
				System.out.println();
			}
		}

	}

}

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

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

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

const int maxn = 2e5 + 5;
vector<int> adj[maxn];
int a[maxn] , b[maxn];
int n;
int sz[maxn];
void dfs(int u){
    sz[u] = 1;
    for(auto c : adj[u]){
        if(sz[c] == -1){
            dfs(c);
            sz[u] += sz[c];
            sz[c] = 2;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i];
        a[0] ^= a[i];
    }
    for(int i = 1 ; i <= n ; ++i){
        cin >> b[i];
        b[0] ^= b[i];
    }
    vector<int> val;
    for(int i = 0 ; i <= n ; ++i)val.pb(a[i]);
    for(int i = 0 ; i <= n ; ++i)val.pb(b[i]);
    sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
    memset(sz,-1,sizeof sz);
    auto Get = [&](int x)->int{
        return lower_bound(val.begin(),val.end(),x) - val.begin();
    };
    int res = 0;
    for(int i = 1 ; i <= n ; ++i){
        int u = Get(a[i]) , v = Get(b[i]);
        if(u == v)continue;
        adj[u].pb(v);adj[v].pb(u);
        res++;
    }
//    return 0;
    for(int i = 0 ; i < val.size() ; ++i){
        if(sz[i] == -1){
            dfs(i);
            res += sz[i] > 1;
        }
    }
    if(sz[Get(a[0])] == 1)res++;
    sort(a , a + n + 1);
    sort(b , b + n + 1);
    for(int i = 0 ; i <= n ; ++i){
        if(a[i] != b[i])return cout << -1 , 0;
    }
    cout << res - 1;
}


Measured memory_bytes: 15476
#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair
#define pb push_back
#define pp pop_back
#define pii pair<int,int>
#define fi first
#define se second 
#define in insert
#define er erase
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int mx=1e5+10;
int main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n;cin>>n;
	ll ans=1,mod=1e9+7;
	for(ll i=1;i<=n;i++) ans=(ans*i)%mod;
	cout<<ans;
	return 0;

}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int a,b,c,d,m;
scanf("%d %d %d %d",&a,&b,&c,&d);
if(a<c)
    if(b<d)
      if(b>c) 
        m=b-c;
      else m=0;
    else m=d-c;
else
    if(b>d)
      if(a<d) m=d-a;
      else m=0;
    else m=b-a;
 printf("%d",m) ;  
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  if(s=="abc"){cout<<"Yes";}
  else if(s=="acb"){cout<<"Yes";}
  else if(s=="bac"){cout<<"Yes";}
  else if(s=="bca"){cout<<"Yes";}
  else if(s=="cab"){cout<<"Yes";}
  else if(s=="cba"){cout<<"Yes";}
  else{cout<<"No";}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;
  cin>>N>>K;
  int totalDistance=0;
  
  for (int i=0; i<N; i++){
    int x;
    cin>>x;
    if(fabs(x-K)>fabs(x-0)){
      totalDistance+=2*x;
    }
    else{
      totalDistance+=2*fabs(x-K);
    }
  }
  
  cout<<totalDistance<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int a,b;
    
    do{
        scanf("%d %d",&a,&b);
    }while(!(1<=a && a<=9 && 1<=b && b<= 9));
    
    if(a+b<10)
    	printf("%d\n",a+b);
    else
    	puts("error");
    	
    return 0;
}

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

using namespace std;

int a[200005];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    long long res = 0;

    sort(a, a + n, greater<int>());

    for (int i = k; i < n; i++) res += a[i];

    printf("%lld\n", res);
}


Measured memory_bytes: 4532
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main() {
    string S, T;
    int ans=0;

    cin >> S >> T;

    int n = S.size();

    rep(i,n) {
        if(S[i]!=T[i]) {
            S[i] = T[i];
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
    
}

Measured memory_bytes: 3896
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int main() {
  string S;
  cin >> S;
  int N = S.size() / 2;
  int co = 0;
  int ans = 0;
  rep(i, N - 1) {
    rep(j, i) {
      if(S.at(j - 1) == S.at(j - 1 + i)) {
        co++;
      }
    }
    if(co == i) {
      ans = i * 2;
    }
    co = 0;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll,ll> pll;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define MOD 1000000007
#define ARRAY_MAX 200005

const int INF = 1e9+7;


//ユークリッド互除法
int gcd(int x,int y){

    if(y == 0){
        return x;
    }else{
        return gcd(y,x % y);
    }
}

int main(){

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

    int ans = a[0];
    for(int i = 0;i < n;i++){
        ans = gcd(ans,a[i]);
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var < (end); var++)
#define RFOR(var, begin, end) for (int var = (begin) - 1; var >= (end); var--)
#define REP(var, length) FOR(var, 0, length)
#define RREP(var, length) RFOR(var, length, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)

const ll MOD = 1e9 + 7;

void solve(istream& cin, ostream& cout) {
  int n;
  double p;
  cin >> n;

  vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));

  dp[0][0] = 1;
  REP(i, n) {
    cin >> p;
    REP(j, i + 2) {
      dp[i + 1][j] = dp[i][j] * (1 - p);
      if (j != 0) {
        dp[i + 1][j] += dp[i][j - 1] * p;
      }
    }
  }
  double ans = 0;

  FOR(i, (n + 1) / 2, n + 1) {
    ans += dp[n][i];
  }

  cout << setprecision(15) << ans << endl;
}

#ifndef TEST
int main() {
  solve(cin, cout);
}
#endif


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
const int64_t INF=999999999;

int main() {
   char a,b;
   cin>>a>>b;
   if(a=='H'&&b=='H'){cout<<'H'<<endl;}
   if(a=='H'&&b=='D'){cout<<'D'<<endl;}
   if(a=='D'&&b=='H'){cout<<'D'<<endl;}
   if(a=='D'&&b=='D'){cout<<'H'<<endl;}
return 0;}

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

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

void insertionSort(int A[], int n, int g){
    for(int i=g;i<n;i++){
        int v=A[i];
        int j=i-g;
        while(j>=0&&A[j]>v){
            A[j+g]=A[j];
            j-=g;
            cnt++;
        }
        A[j+g]=v;
    }
}

void shellSort(int A[], int n){
    for(int h=1;;){
        if(h>n)break;
        G.push_back(h);
        h = 3*h+1;
    }
    for(int i=G.size()-1; i >=0;i--){
        insertionSort(A, n, G[i]);
    }
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)scanf("%d", &A[i]);
    cnt=0;
    shellSort(A,n);
    cout << G.size() << endl;
    for(int i=G.size()-1;i>=0;i--){
        printf("%d", G[i]);
        if(i) printf(" ");
    }
    printf("\n");
    printf("%d\n", cnt);
    for(int i=0;i<n;i++)printf("%d\n", A[i]);

    return 0;
}

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
h,w = [int(i) for i in readline().split()]


if h==1 or w==1:
    print(1)
    exit()


if h%2==1 and w%2==1:
    print(h*w//2+1)
else:
    print(h*w//2)




Measured memory_bytes: 3060
import java.util.*

fun main(args : Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val c = sc.nextInt()
    val d = sc.nextInt()

    val square1Size = a * b
    val square2Size = c * d

    val answer = Math.max(square1Size, square2Size)
    println(answer)
}

Measured memory_bytes: 31524
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int sum=1;
    for(int i=0;i<n;i++){
        if(sum<k) sum *= 2;
        else sum += k; 
    }
    cout<<sum<<endl;
}


    

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD 1000000007
using namespace std;

int main(){
ll N;
cin>>N;
ll ans=0;
for(ll i=1;i<=N-1;i++){
ans+=i;
}

cout<<ans<<endl;


}


Measured memory_bytes: 256
/*
(1)for binary shift operator always use 'LL' 1LL<<63

*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set_pair tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define Luv(...) [&] (auto &&u, auto &&v) { return __VA_ARGS__; }
  const double  pi=3.1415926535; 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	double a,b,h,m;cin>>a>>b>>h>>m;
	double tot=h*60+m;
	double hr=0.5*tot,mn=6*m;
	double co=cos((pi/180)*(hr-mn));
	double s=a*a+b*b,p=2*a*b;
	co=co*p;
	co=s-co;
	co=sqrt(co);
	std::cout << std::fixed;
    std::cout << std::setprecision(10);
    std::cout << co<<endl;

	return 0;
} 

Measured memory_bytes: 4208
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        Reader r = new Reader();    
        int N, M;
        {int[] a = r.ii(); N = a[0]; M = a[1];}
        int[][] sw = new int[M][];
        for(int i = 0; i < M; i++)
            sw[i] = r.ii();
        int[] p = r.ii();
        int ans = 0;
        int caseNum = (int)Math.pow(2, N);
        loop: for(int i = 0; i < caseNum; i++){
            String swS = String.format("%0"+N+"d", Int(Integer.toBinaryString(i)));
            int num = 0;
            for(int j = 0; j < M; j++){
                int t = 0;
                int[] sj = sw[j];
                for(int k = 0; k < sj[0]; k++){
                    if(swS.charAt(sj[k+1]-1) == '1')
                        t++;
                }
                if(t%2 != p[j])
                    continue loop;
            }            
            ans++;
        }
        println(ans);
    }

    static void print(Object o){
        System.out.print(o.toString());
    }

    static void println(Object o){
        System.out.println(o.toString());
    }

    static int Int(String s){
        return Integer.parseInt(s);
    }

    static long Long(String s){
        return Long.parseLong(s);
    }
    static class Reader extends BufferedReader{
        Reader(){
            super(new InputStreamReader(System.in));
        }

        String s() throws IOException{
            return readLine();
        }

        String[] ss() throws IOException{
            return s().split(" ");
        }

        int i() throws IOException{
            return Int(s());
        }

        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }

        long l() throws IOException{
            return Long(s());
        }

        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}


Measured memory_bytes: 25244
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 3010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int r,g,b,n;
ll f[N];
signed main()
{
	r=read(),g=read(),b=read(),n=read();
	f[0]=1;
	for (int i=r;i<=n;i++) f[i]+=f[i-r];
	for (int i=g;i<=n;i++) f[i]+=f[i-g];
	for (int i=b;i<=n;i++) f[i]+=f[i-b];
	cout<<f[n];
	return 0;
	//NOTICE LONG LONG!!!!!
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
const ll Mod=1000000007;
const ll INF=999999999999999999;
const ll NN=(ll)(1e6+5);
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {
	   ll n,i,mx=-1,ans=0;
	   cin>>n;
	   vector <ll> v(n);
	   for(auto &u:v)
	    cin>>u;
	   for(i=0;i<n;i++)
	   {
		   if(v[i]>=mx)
		    mx=v[i];
		  else
		   ans+=mx-v[i];		
	   }	
	   cout<<ans;
   }
}

Measured memory_bytes: 4752
#include<cstdio>
#include<cmath>

int main(){
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  double d = c * acos(-1) / 180;
  double s = a * b * sin(d) / 2;
  double h = b * sin(d);
  double l = sqrt(pow(h,2) + pow(a - b * cos(d),2))
             + a + b;
  
  printf("%f\n%f\n%f\n", s, l, h);

  return 0;
}

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

const int N = 2e5+10;
int head[N],e[N],nxt[N],vis[N],ans[N],color[N];
int tot,n,m,k;
pii heat[N];
void add(int u,int v){
    e[++tot] = v;
    nxt[tot] = head[u]; 
    head[u] = tot;
}
vector<int> instack;
void dfs(int u){
    instack.push_back(u);
    vis[u]++;
    for(int i=head[u];i;i=nxt[i]){
        vis[u]++;
        if(vis[e[i]])   continue;
        dfs(e[i]);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int u,v;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=k;++i){
        scanf("%d%d",&u,&v);
        heat[i].first = u;
        heat[i].second = v;
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            instack.clear();
            dfs(i);
            int sz = instack.size();
            for(auto u:instack){
                ans[u] = sz - vis[u];
                color[u] = i;
            }
        }
    }
    for(int i=1;i<=k;++i){
        if(color[heat[i].first] == color[heat[i].second]){
            ans[heat[i].first]--;
            ans[heat[i].second]--;
        }
    }
    for(int i=1;i<=n;++i){
        printf("%d ",ans[i]);
    }


    return 0;
}

Measured memory_bytes: 7288
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+1],flag,count=1,min ;
	for(int i=1;i<=n;i++) cin>>a[i] ;
	min=a[1];
	for(int i=2;i<=n;i++)
	{
		if(a[i]<=min)
		{
			min=a[i] ;
			count++ ;
		}
	}
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define pr pair<int,int>
#define N 200005
#define mod 1000000007
#define INF 2147483647
using namespace std;
struct line{int to,next;}e[2*N];
int h[N],cnt,rt,k;
void add(int u,int v){e[++cnt]=line{v,h[u]};h[u]=cnt;}
ll son[N];
void dfs(int u,int fa){
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].to;
        if(v!=fa){
            dfs(v,u);
            son[u]++;
        }
    }
}
ll qpow(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }
ll inv(ll x) { return qpow(x, mod - 2); }
ll ans,a[N];
bool los=0;
bool dfs1(int u,int fa){
    if(u==rt&&(k-1<son[u]||k<1)||u!=rt&&(k-2<son[u]||k<2)){
        los=1;
        return 1;
    }
    if(u==rt)ans=ans*a[k-1]%mod*inv(a[k-1-son[u]])%mod;
    else ans=ans*a[k-2]%mod*inv(a[k-2-son[u]])%mod;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].to;
        if(v!=fa){
            if(dfs1(v,u))return 1;
        }
    }
    return 0;
}
void geta(){
    a[0]=a[1]=1;
    for(ll i=2;i<=k+1;i++){
        a[i]=a[i-1]*i%mod;
    }
}
int main() {
	IOS;
    int n;
    cin>>n>>k;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    geta();
    dfs(1,-1);
    ans=k;
    rt=1;
    dfs1(1,-1);
    if(!los)cout<<ans%mod;
    else cout<<0<<'\n';
	return 0;
}

Measured memory_bytes: 11012
A_1 = list(map(int, input().split()))
A_2 = list(map(int, input().split()))
A_3 = list(map(int, input().split()))
A = A_1 + A_2 + A_3
N = int(input())

for i in range(N):
  B = int(input())
  if B in A:
    A[A.index(B)] = 0

bingo = [A[0] + A[1] + A[2],
         A[3] + A[4] + A[5],
         A[6] + A[7] + A[8],
         A[0] + A[4] + A[8],
         A[2] + A[4] + A[6],
         A[0] + A[3] + A[6],
         A[1] + A[4] + A[7],
         A[2] + A[5] + A[8]]

if 0 in bingo:
  print('Yes')
else:
  print('No')

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

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define FF first
#define SS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 807;

const int MOVE[4][2] =
{
	1, 0,
	-1, 0,
	0, 1,
	0, -1
};

int n, m, K;
char g[MAXN][MAXN];
int lev[MAXN][MAXN];
PII q[MAXN*MAXN];

void init ();
void input ();
void work ();

int getans ( int x, int y )
{
	return ( ( ( min ( min ( min ( x - 1, y - 1 ), n - x ), m - y ) ) + K - 1 ) / K );
}



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%d%d%d", &n, &m, &K );
	lpi ( i, 1, n ) scanf ( "%s", g[i]+1 );
}

void work ()
{
	// main work
	
	int sx, sy;
	lpi ( i, 1, n ) lpi ( j, 1, m ) if ( g[i][j] == 'S' ) sx = i, sy = j;
	
	int ans = INF, l = 0, r = 0, nx, ny, vx, vy;
	q[r++] = MP ( sx, sy );
	INIT ( lev, -1 );
	lev[sx][sy] = 0;
	while ( l < r ){
		nx = q[l].FF, ny = q[l].SS, ++l;
		ans = min ( ans, getans ( nx, ny ) );
		if ( !ans ) break;
		if ( lev[nx][ny] ^ K ){
			lp ( d, 0, 4 ){
				vx = nx + MOVE[d][0], vy = ny +  MOVE[d][1];
				if ( g[vx][vy] != '#' && lev[vx][vy] == -1 ){
					lev[vx][vy] = lev[nx][ny] + 1;
					q[r++] = MP ( vx, vy );
				}
			}
		}
	}
	
	cout << ( ( getans ( sx, sy ) ) ? ( ans + 1 ) : 0 ) << endl;
}

Measured memory_bytes: 4864
# Lバーガーのパティの数はL-1バーガーのパティ*2 + 1枚
# Lバーガーのバンの数はL-1バーガーのバン*2 + 2枚
n, x = map(int, input().split())
P = [1]
B = [0]
for _ in range(n):
    P.append(P[-1]*2+1)
    B.append(B[-1]*2+2)


# レベルLバーがの下からx層に含まれるパティの数
# B (L-1) P (L-1) B
def dfs(L, x):
    
    if L == 0:  # レベル0バーガーはパティ1枚のみ
        return 1
      
    l = P[L]+B[L]  # 厚さはP[i]+B[i](必ず奇数)
    mid = l//2 + 1
    
    if x == mid:  # どのレベルでも真ん中はパティ
        return 1 + P[L-1]
    elif x == 1:  # どのレベルでも一番下はバン
        return 0
    elif x == l:
        return 1 + P[L-1]*2        
    elif x < mid:
        return dfs(L-1, x-1) 
    elif x > mid:
        return dfs(L-1, x-1-(P[L-1]+B[L-1])-1) + 1 + P[L-1]

print(dfs(n, x))

Measured memory_bytes: 3064
s,t = input(),input()
n,m=len(s),len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
  for j in range(n):
    if t[i] == s[j]:
      dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j+1])
    dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
ans = ""
cnt = 0
i,j = m,n
while cnt != dp[-1][-1]:
  if dp[i][j] == dp[i][j-1]:
    j -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    ans += s[j-1]
    cnt += 1
    i,j = i-1,j-1

print(ans[::-1])

Measured memory_bytes: 113244
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	n := scanNums()
	vs := scanNums()
	cs := scanNums()

	ans := 0
	for i := 0; i < n[0]; i++ {
		if vs[i] > cs[i] {
			ans += vs[i] - cs[i]
		}
	}
	fmt.Println(ans)
}

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}
func oneStr() string {
	var a string
	fmt.Scan(&a)
	return a
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func scanNums() (nums []int) {
	s := nextLine()
	numStr := strings.Split(s, " ")

	for _, n := range numStr {
		i, _ := strconv.Atoi(n)
		nums = append(nums, i)
	}
	return nums
}

func scanStrings() (strs []string) {
	s := nextLine()
	list := strings.Split(s, " ")
	strs = append(strs, list...)
	return strs
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func sortAsc(a []int) []int {
	sort.Ints(a)
	return a
}

func sortDesc(a []int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	if a == 0 && b == 0 {
		return 0
	}
	return a * b / gcd(a, b)
}


Measured memory_bytes: 640
//hinagata.cpp
/*includes*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <stdio.h>
#include <numeric>
/*namespace*/
using namespace std;
/*define macro*/
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPi(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(x) (x).begin(),(x).end()

long long int gcd(long long int a,long long int b){
    if(b==0)return a;
    return gcd(b,a%b);
}

int main(){
    int N;
    cin>>N;
    vector<int> A(N);
    REP(i,N){
        cin>>A[i];
    }
    int GCD=A[0];
    REPi(i,1,N){
        GCD=gcd(GCD,A[i]);
    }
    cout<<GCD<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include<string>
#include<cmath>
#include<ciso646>
#include<cstring>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;

//解説ac
int main()
{
	int n; cin >> n;
	vector<int> h(n);
	rep(i, n) cin >> h[i];
	int ans = 0;
	int active = 0;
	rep(i, n) {
		if (active < h[i]) {
			ans += h[i] - active;
			active = h[i];
		}
		else
			active = h[i];
	}
	cout << ans;

}


Measured memory_bytes: 3604
n = int(input())
b = {}
for i in range(n):
    temp = input()
    if temp not in b:
        b[temp] = 1
    else:
        b[temp] += 1

list1 = sorted(b.items(), key=lambda x: x[1])

a = len(list1)-1
temp = len(list1)-1
list2 = []
while a >= 0 and list1[temp][1] == list1[a][1]:
    list2.append(list1[a][0])
    a -= 1
list2.sort()

for a in list2:
    print(a)


Measured memory_bytes: 45788
// https://atcoder.jp/contests/dp/tasks/dp_n

#include <bits/stdc++.h>
using namespace std;
typedef std::pair<int, int> ipair;
#define int long long
#define pb push_back
#define ff first
#define INF INT_MAX
#define ss second
#define fr(i, j, a) for (int i = j; i < a; i++)
#define cnt_ones(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define sz size()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<ipair>
#define mp make_pair
#define mod 1000000007
#define IOS                                                                    \
  std::ios::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
void init() {
  int n;
  cin >> n;
  vector<int> slimes(n);
  for (int &i : slimes)
    cin >> i;
  vector<vector<int>> dp(n, vector<int>(n));
  // dp[l][r] - min cost occured while merging [l,r]
  auto sum = [&](int L, int R) {
    int s = 0;
    for (int i = L; i <= R; ++i) {
      s += slimes[i];
    }
    return s;
  };
  for (int l = n - 1; l >= 0; l--) {
    for (int r = l; r < n; r++) {
      if (l == r)
        dp[l][r] = 0;
      else {
        int s = sum(l, r);
        dp[l][r] = 1e18;
        for (int k = l; k < r; k++) {
          dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + s);
        }
      }
    }
  }
  cout << dp[0][n - 1] << endl;
}
int32_t main() {
  IOS;
  init();
  return 0;
}


Measured memory_bytes: 1536
/*

  "With age, comes wisdom. With travel, comes understanding.
   Remember that happiness is a way of travel – not a destination"

*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
     int x = 1;
     while (b)
     {
          if (b & 1) x *= a;
          a *= a;
          b >>= 1;
     }
     return x;
}

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> Set;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 3005;
int a[N], n, m, k;
int cache[N][N][2];

int dp(int i, int j, int who)
{
     if (i > j)
          return 0;
     int &ans = cache[i][j][who];
     if (ans != -1)
          return ans;

     if (who)
     {
          ans = dp(i + 1, j, who ^ 1) - a[i];
          ans = min(ans, dp(i, j - 1, who ^ 1) - a[j]);
     }
     else
     {
          ans = dp(i + 1, j, who ^ 1) + a[i];
          ans = max(ans, dp(i, j - 1, who ^ 1) + a[j]);
     }
     return ans;

}

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

     memset(cache, -1, sizeof cache);
     cout << dp(1, n, 0);

}

int32_t main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     cout << setprecision(9) << fixed;
     clock_t z = clock();
     solve();
     cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);

     return 0;
}

Measured memory_bytes: 141568
//============================================================================
// Name        : abc102.cpp
// Author      : sep
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cmath>
#include <ctime>
#include <functional>
#include <algorithm>
#include <vector>

using namespace std;

inline void main102A() {

	long int n;

	cin >> n;

	if (n % 2 == 0) {
		cout << n;
	} else {
		cout << n * 2;
	}

}

inline void main102B() {

	long long int n;
	int i;
	long long int a;
	long long int min = 10000000000, max = 0;

	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> a;
		if (a < min) {
			min = a;
		}
		if (a > max) {
			max = a;
		}
	}

	cout << abs(max - min);

}

int main() {

#ifdef TEST
	struct timespec startTime, endTime;
	while (1) {
		clock_gettime(CLOCK_REALTIME, &startTime);
#endif

		main102B();

#ifdef TEST
		cout << flush;
		cerr << flush;
		cerr << endl << "Elapsed Time:";
		clock_gettime(CLOCK_REALTIME, &endTime);
		if (endTime.tv_nsec < startTime.tv_nsec) {
			cerr << endTime.tv_sec - startTime.tv_sec - 1 << "."
					<< endTime.tv_nsec + 1000000000 - startTime.tv_nsec << "s"
					<< endl;
		} else {
			cerr << endTime.tv_sec - startTime.tv_sec << "."
					<< endTime.tv_nsec - startTime.tv_nsec << "s" << endl;
		}

		cerr << endl;
	}
#endif

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,K,MOD;
int dp[305][305],sum[305][305],C[305][305];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void update(int &x,int y) {
    x = inc(x,y);
}
void Solve() {
    read(N);read(K);read(MOD);
    C[0][0] = 1;
    for(int i = 1 ; i <= N ; ++i) {
	C[i][0] = 1;
	for(int j = 1 ; j <= i ; ++j) {
	    C[i][j] = inc(C[i - 1][j - 1],C[i - 1][j]);
	}
    }
    for(int j = 0 ; j <= K ; ++j) {sum[1][j] = (j + 1) % MOD;dp[1][j] = 1;}
    for(int i = 2 ; i <= N + 1; ++i) {
	for(int j = 1 ; j < i ; ++j) {
	    for(int k = 0 ; k <= K ; ++k) {
		update(dp[i][k],mul(mul(dp[j][k],inc(sum[i - j][K],MOD - sum[i - j][k])),C[i - 2][i - j - 1]));
	    }
	}
	sum[i][0] = dp[i][0];
	for(int k = 1 ; k <= K ; ++k) sum[i][k] = inc(sum[i][k - 1],dp[i][k]);
    }
    out(dp[N + 1][0]);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


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

namespace practice
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            long a = long.Parse(str[0]);
            long b = long.Parse(str[1]);
            long k = long.Parse(str[2]);

            if (k >= a + b)
            {
                Console.WriteLine("0 0");
            }else if (k > a)
            {
                Console.WriteLine("0 {0}", b + a - k);
            }
            else
            {
                Console.WriteLine("{0} {1}", a - k, b);
            }



        }
    }
}

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

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

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

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

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

/*
*/

int main()
{
  int h, w;
  cin >> h >> w;

  string s[h];
  rep(i, h) cin >> s[i];

  map<char, int> cnt;
  rep(i, h){
    rep(j, w){
      cnt[s[i][j]]++;
    }
  }

  vi c(4, 0);
  for(auto j : cnt){
    c[j.second%4]++;
  }

  bool ans = true;
  if(h%2 and w%2){
    if(c[3] or c[1] != 1) ans = false; 
    if(c[2] > (h-1)/2 + (w-1)/2) ans = false;
  }else if(h%2 or w%2){
    if(w%2) swap(h, w);
    if(c[1] || c[3]) ans = false;
    if(c[2] > w/2) ans = false;
  }else{
    if(c[1] or c[2] or c[3]){
      ans = false;
    }
  }

  cout << (ans ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
/*
https://open.spotify.com/track/1nEjpWJlqcOsf2ZaRQ3XdW?si=w4JqYIANSL2OFpe68ZaBdQ

In the particularly cold night
Perhaps you couldn’t sleep well
In the bright morning woken up from sleep
You are full of darkness
You, who were so worried for some reason that you
Hugged me tightly and asked for my love

You broke and ruined my everything
My daily life and even my people yeah
I resent you all day
But to leave you I oh I

Don’t worry babe
I love you babe
I’ll be by your side
Maybe

Maybe

Looks about to collapse but remains
And the cycle continues unsteadily
I’m about to give up but when I see you I Oh I

No babe
I love you babe
I’ll hold your hand
Maybe

Maybe
I’ll be by your side
Maybe
I’ll trust you

Stay with me, stay with me
So you won’t think of anything
I’ll stay here pretending to be reluctant
So hold me back
Maybe

Maybe
I will be by your side
Maybe
I’ll trust you

Maybe

*/

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define for1(i, a, b) for(i = a; i <= b; ++i)
#define for0(i, a, b) for(i = a; i < b; ++i)
#define forw1(i, a, b) for(i = a; i >= b; --i)
#define forw0(i, a, b) for(i = a - 1; i >= b; --i)
#define fora(v, a) for(auto v : a)
#define bp __builtin_popcount
#define bpll __builtin_popcountll

using namespace std;
using cd = complex<double>;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<cd> vcd;
typedef vector<ii> vii;
typedef vector<vector<int> > vvi;

const int modd1 = 1e9 + 7, modd2 = 998244353, maxn = 2010, K = 26, inf = 1e9, infll = 1e18;
const double pi = acos(-1);
bitset<maxn * maxn> dp(1);
int n, a[maxn];

void solve(){
    int i, j, k, l, r; cin >> n;
    int s = 0;
    for0(i, 0, n){
    	cin >> a[i]; s += a[i];
	}
	for0(i, 0, n){
		dp |= (dp << a[i]);
	}
	for1(i, (s + 1) / 2, s){
		if(dp.test(i)){
			cout << i; break;
		}
	}
}

signed main() {
    //freopen(".INP", "r", stdin); 
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}


Measured memory_bytes: 5164
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<iomanip>

#define rep(i, n) for (int i = 0; i < n; i++) 
#define rrep(i, n) for(int i = n-1; i>=0; i--)
#define range(i, n, m) for (int i = n; i < m; i++) 
#define rrange(i, n, m) for (int i = n - 1; i => m; i--) 
#define MOD 1000000007;

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


using namespace std;

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

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

	string B;

	cin >> B;

	if (B == "A") {
		cout << "T";
	}
	else if (B == "T") {
		cout << "A";
	}
	else if (B == "C") {
		cout << "G";
	}
	else if (B == "G") {
		cout << "C";
	}


	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

//============================================================================
#define pred(x) ((x)-1)
#define succ(x) ((x)+1)
//============================================================================
//----------------------------------------------------------------------------
void exchange(long *x, long *y)
{
    long z;
    z=*x, *x=*y, *y=z;
}
//----------------------------------------------------------------------------
long Partition(long *A, long p,  long r)
{
    long i,j,x;

    x = A[r];
    i = p-1;
    for (j = p; j<r; j++)
        if (A[j] <= x){
            i++;
            exchange(&A[i], &A[j]);
        }
    exchange(&A[i+1], &A[r]);
    return i+1;
}
//----------------------------------------------------------------------------
/*
12
13 19 9 5 12 8 7 4 21 2 6 11
*/
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
void input(FILE *file)
{
    long i,n,x; long *A;

    fscanf(file, "%ld", &n);
    A = malloc(succ(n)*sizeof(long));
    for (i=0; i<n; i++){
        fscanf(file, "%ld", &A[i]);
    }
    x=Partition(A, 0, pred(n));
    for (i=0; i<n; i++){
        if (i) printf(" ");
        if (i==x)
            printf("[%ld]", A[i]);
        else
            printf("%ld", A[i]);
    }
    printf("\n");
    free(A);
}
//============================================================================
#ifndef DESKTOP
int main()
{
    input(stdin);
    return 0;
}
#endif

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define fore(i,a,b) for(ll i=(a);i<=(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define rfore(i,a,b) for(ll i=(b);i>=(a);--i)
#define rrep(i,n) rfore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
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;}
template<class T>
ll sum(const T& a){return accumulate(all(a),0LL);}

void solve(){
    while(1){
        ll h,w;cin>>h>>w;
        if(h==0&&w==0)return;
        rep(i,h){
            rep(j,w){
                if((i+j)%2)cout<<'.';
                else cout<<'#';
            }
            cout<<endl;
        }
        cout<<endl;
    }
}

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



Measured memory_bytes: 3164
#include <algorithm>
#include <cmath>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <numeric>
#include <vector>

using namespace std;
using ll = long long;
template<typename T> void print(T t) {cout << t << endl;}
;
int main() {
	int N, a;
	cin >> N;
	vector<int> Xlist(100000 + 3, 0);
	for (int i = 0; i < N; i++) {
		cin >> a;
		Xlist[a+0]++;
		Xlist[a+1]++;
		Xlist[a+2]++;
	}
	print(*max_element(Xlist.begin(), Xlist.end()));
}

Measured memory_bytes: 3760
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const int N = 1e5;
int a[N+5];

int main()

{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int arr[5], mod[5], sum = 0;

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

        cin >> arr[i];

        if (arr[i]%10) mod[i] = 10-(arr[i]%10);
        else mod[i] = 0;

        sum+=arr[i]+mod[i];
    }

    sort(mod, mod+5);

    cout << sum-mod[4];

    return 0;
}


Measured memory_bytes: 256
int w,h;
int d[9][9],q[9][9];
int a[4]={-1,0,1,0};
int X,Y,C,t;
int b=0;
int chk(int x,int y){
	int i=0,ans=1;
	if(q[y][x])return 0;
	q[y][x]=1;
	if(d[y][x])return y==Y&&x==X;

	for(;i<4;i++)ans+=chk(x+a[i],y+a[(i+1)%4]);
	return ans;
}
void output(int a[9][9]){
	int i,j;
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++)printf("%d",!!a[i][j]);
		puts("");
	}
}
int dfs(int x,int y,int c){
	int i=0;
	if(!c&&x==X&&y==Y)return 1;
	memset(q,0,324);
	if(d[y][x]||chk(x,y) != c+(x!=X||y!=Y))return 0;
	if(b++ > 100000)return 2;
	d[y][x]=1;
	for(;i<4;i++)if(t=dfs(x+a[i],y+a[(i+1)%4],c-1))return t;
	return d[y][x]=0;
}
int main(i,j){
	for(;C=0,b=0,scanf("%d%d\n",&w,&h),h;puts(C>3&&dfs(X,Y,C)==1?"Yes":"No")){
		memset(d,-1,324);
		for(j=1;j<=h;j++)for(i=1;i<=w;i++)scanf("%d",&t),(d[j][i]=t)||(++C,X=i,Y=j);
	}
	return 0;
}

Measured memory_bytes: 388
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

int rec(int h) {
    if (h == 0) return 0;
    return 1 + 2 * rec(h / 2);
}

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

    int H;
    cin >> H;
    cout << rec(H) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
ll n;int t=0;
deque<int> q;
void solve(ll n) {
    if(n==1) return;
    if(n&1) solve(n-1),q.push_front(++t);
    else solve(n>>1),q.push_back(++t);
}
int main() {
    cin>>n;solve(n+1);
    printf("%d\n",sz(q)*2);
    for(int v:q) printf("%d ",v);
    for(int i=1;i<=sz(q);i++) printf("%d ",i);
    return 0;
}


Measured memory_bytes: 256
# coding: utf-8
import math
X, K, D = list(map(int, input().split(" ")))

x = abs(X)
k = int(math.floor(x/D))
if k>=K:
    print(abs(x - K*D))
    exit()
x -= k*D
if (K-k)%2==0:
    print(abs(x))
else:
    print(abs(x - D))

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

int main() {
	int A, B; cin >> A >> B;
	bool T = false;
	int ans = 0;
	for (int i = 1; i <= 1000; i++)
	{
		if ((int)(i * 0.08) == A && (int)(i * 0.1) == B) {
			T = true;
			ans = i;
			break;
		}
	}
	if (T)cout << ans << endl;
	else cout << -1 << endl;
}

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

int main()
{
    int N;
    cin >> N;
    ll B[N];
    for(int i = 0; i < N-1; ++i) cin >> B[i];

    ll A[N+1];
    A[0] = B[0];
    for(int i = 1; i < N - 1; ++i) {
        A[i] = min(B[i-1], B[i]);
    }
    A[N-1] = B[N-2];
    ll ans = 0;
    for(int i = 0; i < N; ++i) ans += A[i];
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main() {
    
    string s,t;
    cin >> s >> t;
    
    int ans = 0;
    for (int i = 0; i < (int)s.size(); ++i)
        ans += s[i] == t[i];

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


Measured memory_bytes: 256