akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void kmp_table(char *str, int *table, int size) {
    int i = 2;
    int j = 0;

    table[0] = -1;
    table[1] = 0;

    while (i < size) {
        if (str[i-1] == str[j]) {
            table[i] = j+1;
            i++;
            j++;
        } else if (j > 0) {
            j = table[j];
        } else {
            table[i] = 0;
            i++;
        }
    }
}

/*
 * Return index if substring is found, otherwise -1.
 */
int kmp_search(char *text, int text_size, char *word, int word_size, int *table) {
    int m = 0;
    int i = 0;

    // printf("text_size: %d, word_size: %d\n", text_size, word_size);
    // printf("text=%.*s, word=%.*s\n", text_size, text, word_size, word);
    // printf("table:");
    // for (int i = 0; i < word_size; i++) {
    //     printf(" %d", table[i]);
    // }
    // printf("\n");

    while (m + i < text_size) {
        if (word[i] == text[m + i]) {
            i++;
            if (i == word_size) {
                return m;
            }
        } else {
            m = m + i - table[i];
            if (i > 0) {
                i = table[i];
            }
        }
    }

    return -1;
}

#define MAX_LEN 5000

int main(void) {
    int n;
    char s[MAX_LEN + 1];
    int table[MAX_LEN];
    int max_len = 0;

    scanf("%d\n", &n);
    fgets(s, n + 1, stdin);

    char *cur = s+1;
    while (cur < (s + n)) {
        int text_len = ((long) cur) - max_len - ((long) s);
        kmp_table(cur - max_len, table, max_len + 1);
        if (kmp_search(s, text_len, cur - max_len, max_len + 1, table) >= 0) {
            max_len++;
        }
        cur++;
    }

    printf("%d\n", max_len);

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

main(){
  int w, n, a, b;
  int data[31];
  int i, temp;

  for(i=0;i<30;i++){
    data[i]=i+1;
  }

  scanf("%d %d", &w, &n);
  data[w]=-1;
  for(i=0;i<n;i++){
    scanf("%d,%d", &a, &b);
    temp=data[a-1];
    data[a-1]=data[b-1];
    data[b-1]=temp;
  }

  for(i=0;;i++){
    if(data[i]==-1) break;
    printf("%d\n", data[i]);
  }
  return 0;
}

Measured memory_bytes: 0
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean[] dp = new boolean[100 * 100 + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            int num = sc.nextInt();
            for (int j = 100 * 100; j >= num; j--) {
                if (dp[j - num]) {
                    dp[j] = true;
                }
            }
        }
        for (int i = 100 * 100; i >= 0; i--) {
            if(i % 10 != 0 && dp[i]) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(0);
    }
}


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

int main(){
  string s;
  cin >> s;
  
  string s_new="";
  for(int i=0; i < s.size(); i+=2){
    s_new = s_new + s.at(i);
  }
  cout << s_new << endl;
  
}


Measured memory_bytes: 3612
n=int(input())
xy=[[int(i) for i in input().split()] for _ in range(n)]
res=0
for i in range(n):
    for j in range(n):
        if i!=j:
            res+=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5
print(res/n)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<"="<<x<<endl
#define fgx cerr<<"-------------"<<endl
#define N 4010
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int mod=998244353;
int f[N][N],s[N]; char c[N];
int main()
{	int n,ans=0; scanf("%s",c+1); n=strlen(c+1);
	for(rint i=1;i<=n;i++)
	{	s[i]=s[i-1];
		if(c[i]=='0') s[i]+=2;
		else if(c[i]=='1') s[i]++;
	}
	f[0][0]=1;
	for(rint i=0;i<n+n;i++)
	for(rint j=0;j<=i;j++)
	{	if(s[min(i+1,n)]-j>0) (f[i+1][j+1]+=f[i][j])%=mod;
		if(2*min(i+1,n)-s[min(i+1,n)]-(i-j)>0) (f[i+1][j]+=f[i][j])%=mod;
	}
	for(rint i=0;i<=n+n;i++) (ans+=f[n+n][i])%=mod;
	cout<<ans;
	return 0;
}



Measured memory_bytes: 61568
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => {{
        let mut line = String::new();
        ::std::io::stdin().read_line(&mut line).unwrap();
        line.trim_right();
        line
    }};
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => {{
        let mut line = String::new();
        ::std::io::stdin().read_line(&mut line).unwrap();
        let iter = line.split_whitespace();
        iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
    }};
}

fn main() {
    let _n = parse_line!(usize);
    let xs = parse_vec!(isize);

    let mut ans = std::isize::MAX;

    for p in 1..101isize {
        let mut a = 0;
        for x in xs.iter() {
            a += (x - p) * (x - p);
        }

        if a < ans {
            ans = a;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
const int maxn = 600;
vector<int> to[maxn];
double f[maxn];
int main(){
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i++){
		int s, t; cin >> s >> t;
		to[s].push_back(t);
	}
	double ans = 1e9;
	for(int v = 0; v <= n - 1; v++){
		for(int i = n - 1; i >= 1; i--){
			f[i] = 0.;
			int sz = to[i].size();
			if(i == v){
				if(sz != 1){
					double sum = 0;
					for(int j : to[i]) sum += (1. / (sz - 1)) * (f[j] + 1);
					f[i] = 1e9;
					for(int j : to[i]) f[i] = min(f[i], sum - (1. / (sz - 1)) * (f[j] + 1));
				} else {
					for(int j : to[i]) f[i] += (1. / sz) * (f[j] + 1);	
				}
			} else {
				for(int j : to[i]) f[i] += (1. / sz) * (f[j] + 1);	
			}
		}
		ans = min(ans, f[1]);
	}
	cout << fixed << setprecision(12) << ans << endl;
	return 0;
}


Measured memory_bytes: 1408
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;
const int maxn = 2000100;



int main(){
        _
        string s; cin >> s;
        int _0 = 0;
        int _1= 0;
        for(char ch : s){
            if(ch=='0')_0++;
            if(ch=='1')_1++;
        }
        cout<<min(_0,_1)*2<<endl;
return 0;
}




Measured memory_bytes: 512
import math


K = int(input())

sum = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        sum += math.gcd(i, j)
        if j == K:
            break
        else:
            for k in range(j + 1, K + 1):
                sum += math.gcd(i, math.gcd(j, k)) * 2

print(sum)



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

int main() {
  int x;
  cin >> x;
  int n = int(x/100);
  int m = x%100;
  bool flag=false;
  for(int i1=0;i1<=n;i1++){
    for(int i2=0;i2<=n-i1;i2++){
      for(int i3=0;i3<=n-i1-i2;i3++){
        for(int i4=0;i4<=n-i1-i2-i3;i4++){
          for(int i5=0;i5<=n-i1-i2-i3-i4;i5++){
            for(int i6=0;i6<=n-i1-i2-i3-i4-i5;i6++){
              if(0*i1 + 1*i2  + 2*i3 + 3*i4 + 4*i5 + 5*i6 == m){
              flag=true;
              cout << 1;
              }
            }
            if(flag==true){
              break;
            }
          }   
          if(flag==true){
            break;
          }         
        }   
        if(flag==true){
          break;
        }        
      }   
      if(flag==true){
        break;
      }     
    }   
    if(flag==true){
      break;
    }    
  }
  if(flag==false){
    cout << 0;
  }
}


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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  int n; std::cin >> n;
  int a, b; std::cin >> a >> b;
  auto check = [&](int x) {
    int sum = 0;
    while (x) sum += x % 10, x /= 10;
    return (sum >= a && sum <= b);
  };
  int ans = 0;
  rrep(i, n) if (check(i)) ans += i;
  std::cout << ans << "\n";
}


Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String[] input = scan.nextLine().split(" ");

		Deque<Integer> stack = new ArrayDeque<Integer>();

		for(int i = 0; i < input.length; i++) {
			if(input[i].equals("+") || input[i].equals("-")
					|| input[i].equals("*") || input[i].equals("/")) {
				int b = stack.pop();
				int a = stack.pop();
				switch(input[i]) {
				case "+":
					stack.push(a + b);
					break;
				case "-":
					stack.push(a - b);
					break;
				case "*":
					stack.push(a * b);
					break;
				case "/":
					stack.push(a / b);
					break;
				}

			} else {
				stack.push(Integer.parseInt(input[i]));
			}
		}
		System.out.println(stack.pop());
		scan.close();
	}
}


Measured memory_bytes: 26200
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long int
#define INF 100000000
#define INFLL 100000000000
#define MOD 1000000007
#define PI 3.14159265359
#define All(a) (a).begin(), (a).end()

using namespace std;
using P = pair<ll, ll>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Edge {
  int to;     
  ll weight; 
  Edge(int t, ll w) : to(t), weight(w) { }
};

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

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



int N, K;

int main () {
  cin >> N >> K;

  int cri = (N-1) * (N-2) / 2;

  if (K > cri) {
    cout << -1 << "\n";
  } else {
    cri -= K;

    cout << (N - 1) + cri << "\n";

    for (int i=2;i<=N;++i) {
      cout << 1 << " " << i << "\n";
    }

    for (int i=2;i<=N-1;++i) {
      for (int j=i+1;j<=N;++j) {
        if (cri == 0) {
          break;
        }
        cout << i << " " << j << "\n";
        cri--;
      }
    }
  }


}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------
int n;
vector<long long>xi(100010);
vector<long long>len(100010);
vector<long long>inv(100010);
long long fac; //factorial, (n-1)!の値をしまう
long long ans;
long long modinv(long long a, long long m) { //modの逆元を求める
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
void solve(){
    dbg = true; //あとで消す*/
    long long num;
    num = 0;
    ans = 0;
    for(int i = 0; i < n - 1; i++){
        num += inv.at(i + 1);
        num %= mod;
        ans += num * (len.at(i) % mod);
        ans %= mod;
    }
    ans *= fac;
    ans += mod;
    ans %= mod;
    cout << ans << endl;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> xi.at(i);
        if(i != 0){
            len.at(i - 1) = xi.at(i) - xi.at(i - 1);
        }
    }
    fac = 1;
    for(int i = 1; i < n; i++){
        fac *= i;
        fac %= mod;
    }//n-1の階乗のmodを計算
    for(int i = 1; i <= n; i++){
        inv.at(i) = modinv(i,mod);
    }//1/1から1/nまで計算しておく下処理
    solve();
    return 0;
}



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

int main() {

  int N,K;
  cin >> N >> K;
  
  vector<int> x(N);
  for(int i=0;i<N;i++)
    cin >> x.at(i);
 
  int A,B;
  int sum=0;
  for(int i=0;i<N;i++){
    A=2*x.at(i);
    B=2*(K-x.at(i));
    sum+=min(A,B);
  }
  cout << sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
int mx[12];
using namespace std;
int main()
{
    int r,g,b,n,i,j;long long s=0;
    scanf("%d %d %d %d",&r,&g,&b,&n);
    if(r>n&&g>n&&b>n)
    {
        printf("0");return 0;
    }
    for(i=0;i<=(n/b);i++)
    {
        for(j=0;j<=(n-(i*b))/g;j++)
        {
            if((n-i*b-j*g)%r==0)
            {
                s++;
            }
        }
    }printf("%I64d",s);
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
 
long long n,ans=0;
void dfs(long x,bool a,bool b,bool c){
  if(x>n)return;
  
  if(a&&b&&c)ans++;
  dfs(x*10+7,true,b,c);
  dfs(x*10+5,a,true,c);
  dfs(x*10+3,a,b,true);
  
}
 
int main(){
  cin>>n;
  dfs(0,false,false,false);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
#define Jewel ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define M 10005
int main()
{
    Jewel;
    int n, i, a;
    map<int, bool>mp;
    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>a;
        if(mp[a])
            return cout<<"NO"<<endl, 0;
        mp[a]=true;
    }
    cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
int main(){
	int w,h;
	char c;
	cin >> w >> h >> c;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(i==0 || i==h-1){
				if(j==0 || j==w-1){
					cout << '+';
				}else{
					cout << '-';
				}
			}else{
				if(j==0 || j==w-1){
					cout << '|';
				}else{
					if(i==h/2 && j==w/2){
						cout << c;
					}else{
						cout << '.';
					}
				}
			}
		}
		cout << endl;
	}
}


Measured memory_bytes: 3088
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class CSquaredGraph {
public:

    std::vector<int> par;
    std::vector<int> rak; // number of the vertices

    void init(int n) {
      par.resize(n);
      rak.resize(n);
      for(int i=0; i<n; i++) {
        par[i] = i;
        rak[i] = 1;
      }
    }

    int find(int x) {
      if (par[x] == x) {
        return x;
      } else {
        return par[x] = find(par[x]);
      }
    }

    void unite(int x, int y) {
      x = find(x);
      y = find(y);
      if (x==y) return;
      if (rak[x] < rak[y]) {
        rak[y] += rak[x];
        par[x] = y;
      } else {
        rak[x] += rak[y];
        par[y] = x;
      }
    }

    bool same(int x, int y) {
      return find(x) == find(y);
    }

    vector<int> graph[100005];
    vector<int> color;

    bool dfs(int p) {
      bool ret = true;
      for(auto e: graph[p]) {
        if (color[e] == 0) {
          color[e] = -color[p];
          if (!dfs(e)) ret = false;
        } else if (color[e] == color[p]) {
          ret = false;
        }
      }
      return ret;
    }

    void solve(istream& cin, ostream& cout) {
      SPEED;
      ll n, m; cin >> n >> m;
      init(n);
      color.resize(n);
      rep(i, m) {
        int u, v; cin >> u >> v;
        u--; v--;
        unite(u, v);
        graph[u].push_back(v);
        graph[v].push_back(u);
      }

      ll a = 0;
      ll b = 0;
      ll c = 0;
      rep(i, n) {
        if (find(i) == i) {
          if (rak[i] == 1) {
            c++;
          } else {
            color[i] = 1;
            bool ret = dfs(i);
            if (ret) {
              a++;
            } else {
              b++;
            }
          }
        }
      }
      debug(a, b, c);
      ll ans = 2*a*a + 2*a*b + b*b + 2*c*n - c*c;
      cout << ans << endl;




    }
};

signed main() {
  CSquaredGraph solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 9600
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;
    vector<vector<ll> > days(M + 1);
    ll A, B;
    for (int i = 0; i < N; ++i) {
        cin >> A >> B;
        if (M - A + 1 < 0) continue;
        days[M - A + 1].push_back(B);
    }
    priority_queue<ll> pq;
    ll ans = 0;
    for (int i = M; i >= 1; --i) {
        for (int j = 0; j < days[i].size(); ++j) {
            pq.push(days[i][j]);
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5632
from itertools import accumulate
from operator import add

n=int(input())
l=[int(i) for i in input().split()]
left=list(accumulate(l,add))
s=sum(l)
right=[s-i for i in left]
m=s
for i in range(n):
  m=min(m , abs(left[i]-right[i]))
print(m)  


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int x;
    cin >> x;
    int count=0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(i*500+j*100+k*50==x)count++;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
bool factorize(int n, set<int>& uniq_fact){
	if(n%2 == 0){
		if(uniq_fact.count(2)){
			return false;
		}
		while(n%2==0){
			n/=2;
		}
		uniq_fact.insert(2);
	}
	for(int i=3; i<=sqrt(n); i += 2){
		if(n%i == 0){
			if(uniq_fact.count(i)){
				return false;
			}
			while(n % i == 0) n/=i;
			uniq_fact.insert(i);
		}
	}
	if(n > 2){
		if(uniq_fact.count(n)){
			return false;
		}
		uniq_fact.insert(n);
	}
	return true;
}
int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int>a(n);
	set<int>uniq_fact;
	bool pairwise = true;
	for(int i=0; i<n; i++){
		cin >> a[i];
		if(pairwise){
			if(!factorize(a[i], uniq_fact)){
				pairwise = false;
			}
		}
	}
	if(pairwise){
		cout << "pairwise coprime" << endl;
		return 0;
	}
	int g = a[0];
	for(int i=1; i<n; i++){
		g = __gcd(g,a[i]);
		if(g == 1)
			break;
	}
	if(g == 1){
		cout << "setwise coprime" << endl;
	}
	else{
		cout << "not coprime" << endl;
	}
	return 0;
}

Measured memory_bytes: 7304
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
typedef vector<int> vi;
typedef vector<ll> vl;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define IN cin >> 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (m-1); i >= (int)(n); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////


int main(){
    int n;
    IN n;
    set<int> s;
    rep(i,0,n){
        int a;
        IN a;
        s.it(a);
    }
    P(sz(s));
    
	return  0;
}

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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = euclid(b, a % b, y, x);
        return y -= a/b * x, d; }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1) ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1); return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this ^ (e / 2); r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);

    string s; cin >> s;
    rep(i, 0, 8) {
        if (s.substr(0, i) + s.substr(s.size() - (7 - i)) == "keyence") {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>

#define REP(i,n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define ALLOF(c) c.begin(), c.end()
#define RANGEOF(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define EPS 1e-9
#define INF 1000000000
using namespace std;

template <class T> T read() { T t; cin >> t; return t; }
template <class T> vector<T> read(int n) { vector<T> v; REP(i,n) { v.push_back(read<T>()); } return v; }
template <class T> vector<vector<T>> read(int n, int m)
{
	vector<vector<T>> v;
	REP(i,n) { v.push_back(read<T>(m)); }
	return v;
}

template <class T> void write(const T &t) { cout << t << endl; }
template <class T> void write(const T &t, const T &t2) { cout << t << ' ' << t2 << endl; }
template <class T> void write(const vector<T> &v)
{
	ostringstream ss; 
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	cout << s.substr(0, s.length() - 1) << endl;
}

struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__

void solve();
int main() { solve(); return 0; }

/// template end ///

void solve()
{
	while (true)
	{
		READ(int, n, m);
		if (!n && !m) { break; }

		auto taro = read<int>(n);
		auto hana = read<int>(m);

		int ret = INF, tr = 0, hr = 0;
		auto tx = accumulate(ALLOF(taro), 0);
		auto hx = accumulate(ALLOF(hana), 0);
		for (auto t:taro) for (auto h:hana)
		{
			if (tx - t + h == hx - h + t && ret > t + h)
			{
				ret = t + h;
				tr = t;
				hr = h;
			}
		}
		if (ret == INF) { write(-1); }
		else { write(tr, hr); }
	}
}

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

int main() {
    long long N;
    cin >> N;
    string res = "";
    while (N) {
        --N;
        res += (char)('a' + (N % 26));
        N /= 26;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

const int NMAX = 1e5 + 10;
const int MMAX = 2e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

struct edge {
  int to;
  ll cost;
};

int N, M;
int L[MMAX], R[MMAX];
ll D[MMAX];
vector<vector<edge> > graph(NMAX);
bool used[NMAX];
ll w[NMAX];

void dfs(int v, ll sum) {
  used[v] = true;

  for (int i = 0; i < graph[v].size(); i++) {
    edge e = graph[v][i];
    if (used[e.to]) continue;

    w[e.to] = sum + e.cost;
    dfs(e.to, sum + e.cost);
  }
}

int main() {
  // 入力
  cin >> N >> M;
  for (int i = 0; i < M; i++) cin >> L[i] >> R[i] >> D[i];

  // 有向重み付きグラフを作成
  edge e;
  for (int i = 0; i < M; i++) {
    e.cost = D[i];
    e.to = R[i];
    graph[L[i]].push_back(e);
    e.cost *= -1;
    e.to = L[i];
    graph[R[i]].push_back(e);
  }

  // 各頂点に適当に重みを割り当てる
  for (int i = 1; i <= N; i++) {
    if (used[i]) continue;

    dfs(i, 0);
  }

  // 矛盾しないかチェック
  bool ans = true;
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < graph[i].size(); j++) {
      edge e = graph[i][j];
      if (w[e.to] - w[i] != e.cost) ans = false;
    }
  }

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

  return 0;
}


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

vector<vector<int>> edge;

void dfs(int idx, int y, int d, vector<int> &vv) {
    if (vv[idx] >= 0) return;
    vv[idx] = d;
    for(int x: edge[idx]) {
        if (x == y) continue;
        dfs(x, idx, d+1, vv);
    }
}


int main(){
    int N;
    cin >> N;
    edge = vector<vector<int>>(N);
    for(int i=0; i<N-1; i++) {
        int a,b;
        cin >> a >> b;
        a--,b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    vector<int> vv(N, -1);
    dfs(0, -1, 0, vv);
    int idx = 0;
    for(int i=0; i<N; i++) {
        if (vv[idx] < vv[i]) {
            idx = i;
        }
    }
    vv = vector<int>(N, -1);
    dfs(idx, -1, 0, vv);
    int mx = 0;
    for(int i=0; i<N; i++) {
        mx = max(mx, vv[i]);
    }
    cout << (mx % 3 == 1 ? "Second" : "First") << endl;
}

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

int main(){
    int N, M; cin >> N >> M;
    vector<vector<int>> s(M);
    for(int i = 0; i < M; i++){
        int k; cin >> k; 
        for(int j = 0; j < k; j++){
            int a; cin >> a; a--;
            s[i].push_back(a);
        }
    }
    vector<int> p(M);
    for(int i = 0; i < M ; i++) cin >> p[i];

    long long res = 0;
    for(int bit = 0; bit < (1 << N); bit++){
        bool ok = true;
        for(int i = 0; i < M; i++){
            int con = 0;
            for(auto v : s[i]){
                if(bit & (1 << v)) con++;
            }
            if(con % 2 != p[i]) ok = false;
        }
        if(ok) res++;
    }

    cout << res << endl;
}

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

vector<string> split(string s) {
    vector<string> result;
    istringstream iss(s);
    string tmp;
    while (getline(iss, tmp, ' ')) result.push_back(tmp);
    return result;
}

int main(void) {
    string str;cin>>str;
    int q;cin>>q;
    cin.ignore();
    for (int i = 0; i < q; i++) {
        string s;
        getline(cin, s);
        vector<string> vc = split(s);
        if (vc.at(0) == "replace") {
            int a = stoi(vc.at(1));
            int b = stoi(vc.at(2));
            string c = vc.at(3);
            str = (a > 0) ? str.substr(0, a) + c + str.substr(b + 1, str.size() - b - 1) : c + str.substr(b + 1, str.size() - b - 1);            
        } else if (vc.at(0) == "reverse") {
            int a = stoi(vc.at(1));
            int b = stoi(vc.at(2));
            string rev_str = str.substr(a, b - a + 1);
            string new_rev_str;
            for (int i = 0; i < rev_str.size(); i++) {
                new_rev_str += rev_str.substr(rev_str.size() - i - 1, 1);
            }
            str = (a > 0) ? str.substr(0, a) + new_rev_str + str.substr(b + 1, str.size() - b - 1) : new_rev_str + str.substr(b + 1, str.size() - b - 1);
        } else if (vc.at(0) == "print") {
            int a = stoi(vc.at(1));
            int b = stoi(vc.at(2));
            cout << str.substr(a, b - a + 1) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; 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 ALL(v) (v).begin(),(v).end()
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    int n;cin >> n;
    vector<ll> x(n),y(n),p(n);
    REP(i,n){
        cin >> x[i] >> y[i] >> p[i];
    }
    vector<vector<ll>> hp(1<<n,vector<ll>(n)),wp(1<<n,vector<ll>(n));
    REP(t,1<<n){
        vector<int> h;
        h.push_back(0);
        REP(i,n){
            if(t&(1<<i)){
                h.push_back(x[i]);
            }
        }
        REP(i,n){
            ll res=INF;
            REP(j,h.size()){
                chmin(res,abs(h[j]-x[i]));
            }
            hp[t][i]=res;
        }
    }
    REP(t,1<<n){
        vector<int> w;
        w.push_back(0);
        REP(i,n){
            if(t&(1<<i)){
                w.push_back(y[i]);
            }
        }
        REP(i,n){
            ll res=INF;
            REP(j,w.size()){
                chmin(res,abs(w[j]-y[i]));
            }
            wp[t][i]=res;
        }
    }
    vector<ll> ans(n+1,INF);
    ll T=1;
    REP(i,n){
        T*=3;
    }
    REP(t,T){
        int u=0,v=0;
        int cnt=0;
        int num=t;
        REP(i,n){
            if(num%3==2){
                cnt++;
                u+=1<<i;
            }
            else if(num%3==1){
                cnt++;
                v+=1<<i;
            }
            num/=3;
        }
        ll res=0;
        REP(i,n){
            res+=min(hp[u][i],wp[v][i])*p[i];
        }
        chmin(ans[cnt],res);
    }
    REP(i,n+1){
        cout << ans[i] << endl;
    }
}



Measured memory_bytes: 13028
//url:
//problem name:

#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long,long>;
using veci = vector<int>;
using vecl = vector<long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long,long>>;

int main() {
    ll N;
    cin >> N;
    ll ans = 0;
    for(ll i = 1; i <= N; i++) {
        if(i%3 != 0 && i%5 != 0) ans += i;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

	int n,a[20],b[20];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cin>>b[i];

	int res=1e9;

	for(int i=0;i<(1<<n);i++)
	{
		int s[20],t[20],c[20];
		for(int j=0;j<n;j++)
		{
			s[j]=(i&(1<<j))>0;
			if(s[j])
				t[j]=a[j];
			else
				t[j]=-b[j];
			c[j]=abs(t[j]);
		}
		sort(c,c+n);

		int cnt=0;
		for(int j=0;j<n;j++)
		{
			bool ok=false;
			for(int k=j;k<n;k++)
			{
				if(c[j]==abs(t[k])&&(1-2*((k-j)%2)==t[k]/abs(t[k])))
				{
					for(int l=k;l>j;l--)
					{
						t[l]*=-1;
						t[l-1]*=-1;
						swap(t[l],t[l-1]);
						cnt++;
					}
					ok=true;
					break;
				}
			}
			if(!ok)
			{
				cnt=1e9;
				break;
			}

		}

		res=min(res,cnt);

	}

	if(res==1e9)
		cout<<-1<<endl;
	else
	cout<<res<<endl;

    return 0;
}

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

using namespace std;

typedef long long ll;

ll comb[55][55];

void init() {
	for(int i = 0; i <= 50; i++) {
		comb[i][0] = 1;
		comb[i][i] = 1;
		for(int j = 1; j < i; j++) {
			comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
		}
	}
}

ll l[55];

int main() {
	init();
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	map<ll, int> dp;
	for(int i = 0; i < n; i++) {
		scanf("%lld", &l[i]);
		dp[l[i]]++;
	}
	sort(l, l+n);
	for(int i = 0; i < n-1-i; i++) {
		l[i] ^= l[n-1-i];
		l[n-1-i] ^= l[i];
		l[i] ^= l[n-1-i];		
	}
	if(l[0] == l[a-1]) {
		printf("%lld\n", l[0]);
		ll amt = 0;
		for(int i = a; i <= b; i++) {
			if(i <= dp[l[0]]) {
				amt += comb[dp[l[0]]][i];
			}
		}
		printf("%lld\n", amt);
	}
	else {
		ll pref = 0;
		for(int i = 0; i < a; i++) pref += l[i];
		printf("%.9f\n", pref / (double)a);
		int use = 0;
		for(int i = 0; i < a; i++) if(l[i] == l[a-1]) use++;
		printf("%lld\n", comb[dp[l[a-1]]][use]);
	}
}

Measured memory_bytes: 256
import sys
import math

import heapq

def input():
    return sys.stdin.readline().rstrip()


def tc():
    N = int(input())



def main():
    N = int(input())

    dp = [0]*(N+1)
    rt = int(N **0.5) +2
    for i in range(1,rt):
        for j in range(1,rt):
            if int( i**2 + j **2 + 1 + i*j + i*1 + j*1 ) >N:
                break
            for k in range(1,rt):
                case =int( i**2 + j **2 + k **2 + i*j + i*k + j*k )
                if case <=N:
                    dp[case] +=1
                else:
                    break

    for l in range(1,N+1):
        print(dp[l])










if __name__ == "__main__":
    main()


Measured memory_bytes: 9588
import java.util.*;
public class Main{
    public static void main(String[] args){
	Scanner kbd = new Scanner(System.in);
	int n = kbd.nextInt();
	int m = kbd.nextInt();
	int s = n*m;
	int t = (n+m)*2;
	System.out.println(s+" "+t);
    }
}

Measured memory_bytes: 17156
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define PI 3.1415926535897932384626433
#define mod 1000000007
 
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
 
int lcm(int a, int b) { return a * b / gcd(a, b); }
 
int main(){
    ll n, h, w;
    cin >> n >> h >> w;
    ll a[n], b[n];
    for (ll i = 0; i < n; i++){
        cin >> a[i] >> b[i];
    }

    ll ans = 0;
    for (ll i = 0; i < n; i++){
        if(h <= a[i] & w <= b[i]){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(void){
    int n, y;
    cin >> n >> y;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=n;++j){
            int k = n - i - j;
            if(k<0) break;
            int sum = 10000*i + 5000*j + 1000*k;
            if(sum == y){
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

ll Pow(ll A, ll N){
  if (N == 0) return 1;
  else{
    if (N % 2 == 0){
      return Pow(A * A % Mod, N / 2) % Mod;
    }else{
      return A * Pow(A * A % Mod, N / 2) % Mod;
    }
  }
}


int main(){

  int N; cin >> N;
  ll ans = Pow(3, N);
  
  ll Pow2 = 1, nCr = 1;
  ll sum = 1;
  for (ll i = 1; i < N / 2; i++){
    Pow2 *= 2; Pow2 %= Mod;

    nCr *= N + 1 - i; nCr %= Mod;
    nCr *= Pow(i, Mod - 2); nCr %= Mod;

    sum += Pow2 * nCr % Mod;
    sum %= Mod;
  }
  ans -= sum * 2; ans %= Mod;

  if (ans < 0) ans += Mod;
  
  cout << ans << endl;
  

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) x.begin(),x.end()
#define len(x) (int)(x).size()
//#define endl "\n"
#define m_p make_pair
#define int long long


using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ld,ld> pari;

ld PI = 3.14159265358979323846;


struct Point{
    string a;
    int x,ind;
};

typedef tree<int, null_type, less<int >,
    rb_tree_tag, tree_order_statistics_node_update> ordered_set;

void volodya22(){
    #ifdef THERE
        freopen("input.txt", "r", stdin);
    //    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(15);
    cout << fixed;
}


int n,m;
const int N = 1e6+7;
const int alphabet = 256;
const int INF = 1e18;
const ll MOD = 1e9+7;
const ld eps = 1e-10;
const int L = 30;

int m1 = 137*137*137*137*13;
int m2 = 1e9+9;
//int p = 347;

Point arr[N];

int comp(Point a,Point b){
    if(a.a != b.a)
        return a.a < b.a;
    return a.x > b.x;
}

void input(){
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> arr[i].a>> arr[i].x;
        arr[i].ind = i+1;
    }
    sort(arr,arr+n,comp);
    for(int i = 0;i < n;i++) cout << arr[i].ind << endl ;
}


void solve(){

}

signed main(){
    volodya22();
    input();
    solve();
}


Measured memory_bytes: 23680
using System;
namespace atcorderpractice
{
    class Mainclass
    {
        public static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int n = int.Parse(input[0]);
            int ksin = int.Parse(input[1]);
            int keta = 0;


            while (n!= 0)
            {
                n = n / ksin;
                keta++;
            }

            Console.WriteLine(keta);




        }
    }
}

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

int main(){

    int N;
    cin>>N;
    vector<int>P(N+1, 0);
    for(int i=1;i<=N;i++){
        char c;
        cin>>c;
        P[i] = P[i-1] + (c=='W' ? 1 : 0);
    }
    int ans = N;
    for(int i=1;i<=N;i++){
        int l = P[i - 1];
        int r = N - i- (P[N] - P[i]);
        //cout<<i<<" "<<l<<" "<<r<<endl;
        ans = min(ans, l+r);
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<stdio.h>
using namespace std;
inline void output(long long o);
string s;
int main()
{
	cin>>s;int n=s.length()-1;
	return putchar(s[0]),output(n-1),putchar(s[n]),0;
}
inline void output(long long o)
{
	if(o<0)putchar('-'),o=-o;
	if(o>=10)output(o/10);
	putchar(o%10+'0');
}

Measured memory_bytes: 256
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    use std::cmp;

    input! {
        N: usize,
        A: [[i64; 3]; N],
    }

    let mut dp = vec![vec![0; 3]; N + 1];

    for i in 0..N {
        dp[i + 1][0] = cmp::max(dp[i + 1][0], cmp::max(dp[i][1] + A[i][1], dp[i][2] + A[i][2]));
        dp[i + 1][1] = cmp::max(dp[i + 1][1], cmp::max(dp[i][0] + A[i][0], dp[i][2] + A[i][2]));
        dp[i + 1][2] = cmp::max(dp[i + 1][2], cmp::max(dp[i][0] + A[i][0], dp[i][1] + A[i][1]));
    };

    println!("{}", cmp::max(dp[N][0], cmp::max(dp[N][1], dp[N][2])));
}

Measured memory_bytes: 18684
#include<bits/stdc++.h>
using namespace std;
int h(vector<int> &height, vector<int> &dp){
	int n = height.size();
	if(n == 1)
	return 0;
	else if(n == 2)
	return abs(height[1]-height[0]);
	else
	dp[0] = 0;
	dp[1] = abs(height[1] - height[0]);
	for(int k = 2; k < n; k++){
		dp[k] = min(abs(height[k] - height[k-1]) + dp[k-1], abs(height[k] - height[k-2]) + dp[k-2]);
	//	cout << dp[k];
	//	cout << endl;
	}
        //printf("%d\n", n);
        return dp[n-1];


}


int main(){

	int n;
        cin >> n;
	vector<int> height(n);
        for(int i = 0; i< n; i++)
		cin >> height[i];
	vector<int> height_dp(n,-1);
	int val = h(height, height_dp);
        cout << val << endl;
}


Measured memory_bytes: 1024
{-# LANGUAGE CPP #-}
module Main where

import qualified Data.Vector as V 
import qualified Data.Map.Strict as M
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

dump :: (Show a) => a -> IO()
#if __GLASGOW_HASKELL__ >= 850
dump x = print x
#else
dump _ = pure ()
#endif

-- "101010" -> [1,0,1,0,1,0]
readToList :: String -> [Int]
readToList [] = []
readToList (x:xs) = read [x] : readToList xs

-- "10 10 10" -> [10, 10, 10]
readvec :: IO [Int]
readvec = (fmap (read . BS.unpack) . BS.words) <$> BS.getLine

newtype UF a = UF (M.Map a a) deriving (Show) -- Map node parent

makeuf :: Int -> UF Int
makeuf n = let m = M.fromList $ zip [0..n] [0..n]
                in UF m

union :: (Eq a, Ord a) => a -> a -> UF a -> UF a
union l r uf@(UF m) = let lp = find l uf
                          rp = find r uf
                      in if lp == rp
                         then uf
                         else if size l uf < size r uf
                              then UF $ M.update (const $ Just rp) lp m
                              else UF $ M.update (const $ Just lp) rp m

find :: (Eq a, Ord a) => a -> UF a -> a
find x uf@(UF m) = let px = m M.! x
                in if px == x
                   then px
                   else find px uf -- TODO 貼り直し

size :: (Eq a, Ord a) => a -> UF a -> Int
size x (UF m) = M.size $ M.filter (\par -> par==x) m

main :: IO()
main = do
  xs <- readvec 
  if sum xs >= 22
     then putStrLn "bust"
     else putStrLn "win"



Measured memory_bytes: 508