akhauriyash/Code-Regression huggingface dataset:
# 希尔排序
def insertion_sort(arr, step):
    swap_cnt = 0
    for i in range(step, len(arr)):
        val = arr[i]
        j = i - step
        while (j >= 0) and (arr[j] > val):
            arr[j + step] = arr[j]
            j -= step
            swap_cnt += 1
        arr[j + step] = val
    return swap_cnt

def shell_sort(arr):
    # generate G = [1, 4, 13, 40, 121, 364, 1093, ...]
    swap_cnt = 0
    G = []
    h = 1
    while h <= len(arr):
        G.append(h)
        h = 3*h + 1
    G.reverse()
    print(len(G))
    print(' '.join(map(str, G)))

    for i in G:
        swap_cnt += insertion_sort(arr, i)
    return swap_cnt

if __name__ == '__main__':
    N = int(input())
    arr = []
    for i in range(N):
        arr.append(int(input()))

    
    print(shell_sort(arr))
    for i in arr:
        print(i)



Measured memory_bytes: 45516
import math
n,k = map(int,input().split())
count=0

for a in range(1,n+1):
    modk = (k-a)%k
    if((modk*2)%k == 0):
        nums = math.floor((n-(k-a)%k)/k)-math.ceil((1-(k-a)%k)/k)+1
        count+=(nums*nums)
    
print(count)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
#define MOD 1000000007
using ll = long long;
using namespace std;
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 (a>b) { a=b; return 1; } return 0; }

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
float a,b;
cin>>a>>b;
cout<<ceil((a+b)/2)<<endl;
//system("pause");
return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a,b;
	scanf("%d%d",&a,&b);
	if(a<b){
		printf("a < b\n");
	}
	else if(a>b){
		printf("a > b\n");
	}
	else {
		printf("a == b\n");
	}
	return 0;
}

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

typedef long long ll;

ll A,B;

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

int main(){
	cin>>A>>B;
	cout<<ll(ll(A*B)/ll(gcd(A,B)));
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
 
int T[110];
int v[110];

int hantei(int t, int ve, int i){
    int nv;
    if(t <= T[i]){
        nv = (v[i] + (T[i]-t)); 
    }
    //else if(t > T[i+1]){
    //    nv = (v[i] + (t-T[i+1]));
    //}
    else if(t <= T[i+1]){
        nv = v[i]; 
    }
    else return 1;

    if(nv > ve) return 1;
    else if(nv < ve) return -1;
    else return 0;
}

int main(){
    int N;
    cin >> N;
    T[0] = 0;
    REP(i,N+1){
        if(i == 0) continue;
        int t;
        cin >> t;
        if(i != 0)
            T[i] = 2*t + T[i-1];
    }
    REP(i,N){
        int ve;
        cin >> ve;
        v[i] = 2*ve;
    }

    int ve = 0;
    double S = 0;
    REP(t, T[N]){
        int acc = 1;
        REP(i,N+1){
            int h = hantei(t+1, ve, i);
            acc = min(acc, h);
        }
        int tmp = ve;
        if(acc == 1) ve+=1;
        else if(acc == -1) ve-=1;
        S += tmp + (ve-tmp)*0.5;
        //printf("t:%d\tve:%d\n", t, ve);
        //cout << S/4 << endl;
    }
    //cout << S/4 << endl;
    printf("%lf\n", 0.25*S);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ll n;
  cin >> n;
  vector<ll> x(n), y(n), h(n);
  ll inot0;
  REP(i, n) {
    cin >> x[i] >> y[i] >> h[i];
    if (h[i] != 0) inot0 = i;
  }

  REP(cx, 101) {
    REP(cy, 101) {
      ll h_pre = h[inot0] + abs(x[inot0] - cx) + abs(y[inot0] - cy);
      bool f = true;
      REP(i, n) {
        if (h[i] != max(0ll, h_pre - abs(x[i] - cx) - abs(y[i] - cy)))
          f = false;
      }
      if (f) {
        cout << cx << ' ' << cy << ' ' << h_pre << endl;
        return 0;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 3604
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
using namespace std;
typedef long long int lli;
int main(void)
{
    string s;
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

Measured memory_bytes: 3628
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		Set<String> set = new HashSet<String>();
		for(int i=0; i<n; i++) {
			set.add(sc.next());
		}
		System.out.println(set.size() < 4 ? "Three":"Four");
	}
}


Measured memory_bytes: 22228
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }

int main() {
    fast_io();

    long long n;
    cin >> n;

    cout << n * (n-1) /2 <<endl;
}


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

ll F(ll x)
{
  switch (x%4) {
    case 0:
      return x^0;
      break;
    case 1:
      return 1;
      break;
    case 2:
      return x^1;
      break;
    case 3:
      return 0;
  }
  return -1;
}

int main()
{
  ll a,b;
  cin >> a >> b;
  if(a==0){
    ll tmp = 0^F(b);
    cout << tmp << endl;
    return 0;
  }
  ll tmp = F(a-1)^F(b);
  cout << tmp << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
import math
a, b, c, d = map(int, input().split())
if (max(a, c) - min(a, c) <= d or (max(a, b) - min(a, b) <= d and max(c, b) - min(c, b) <= d)):
    print('Yes')
else:
    print('No')

    

Measured memory_bytes: 3060
import java.awt.geom.Point2D;
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n;
		Point2D.Double a, b, c;
		Point2D.Double middle1, middle2;
		double slope1, slope2;
		Point2D.Double solve;
		double r;

		n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			a = new Point2D.Double(sc.nextDouble(), sc.nextDouble());
			b = new Point2D.Double(sc.nextDouble(), sc.nextDouble());
			c = new Point2D.Double(sc.nextDouble(), sc.nextDouble());

			middle1 = new Point2D.Double((a.x + b.x) / 2.0, (a.y + b.y) / 2.0);
			middle2 = new Point2D.Double((b.x + c.x) / 2.0, (b.y + c.y) / 2.0);
			slope1 = getSlope(a, b);
			slope2 = getSlope(b, c);
			solve = makeSolution(middle1, slope1, middle2, slope2);
			r = Math.sqrt((solve.x - a.x) * (solve.x - a.x) + (solve.y - a.y) * (solve.y - a.y));
			System.out.printf("%.3f %.3f %.3f\n", solve.x, solve.y, r);
		}
	}

	public static double getSlope(Point2D.Double a, Point2D.Double b) {
		if (a.y == b.y) {
			return Double.POSITIVE_INFINITY;
		}
		return -(b.x - a.x) / (b.y - a.y);
	}

	public static Point2D.Double makeSolution (Point2D.Double p1, double e1, Point2D.Double p2, double e2) {
		double a, b, c, d;
		double x = 0.0, y = 0.0;

		a = e1;
		if (!Double.isInfinite(a)) {
			b = p1.y - a * p1.x;
		} else {
			b = Double.NaN;
		}
		c = e2;
		if (!Double.isInfinite(c)) {
			d = p2.y - c * p2.x;
		} else {
			d = Double.NaN;
		}

		if (!Double.isNaN(b) && !Double.isNaN(d)) {
			x = (d - b) / (a - c);
			y = (a * d - b * c) / (a - c);
		} else if (Double.isNaN(b)) {
			x = p1.x;
			y = c * x + d;
		} else if (Double.isNaN(d)) {
			x = p2.x;
			y = a * x + b;
		}

		return new Point2D.Double(x, y);
	}
}

Measured memory_bytes: 12000
n = int(input())
x = list(map(int,input().split()))
x_2 = sorted(x)
m_1 = x_2[n//2-1]
m_2 = x_2[n//2]
for i in range(n):
    if x[i] <= m_1:
        print(m_2)
    elif x[i] >= m_2:
        print(m_1)



Measured memory_bytes: 30772
INF = 1e20

A, B, Q = [int(i) for i in input().split()]
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]

from bisect import bisect_left

mins = []
for _ in range(Q):
    x = int(input())
    s = bisect_left(S, x)
    t = bisect_left(T, x)
    mi = INF
    for ss in [S[s], S[s - 1]]:
        for tt in [T[t], T[t - 1]]:
            mi = min(mi, abs(ss - x) + abs(tt - ss), abs(tt - x) + abs(ss - tt))
    mins.append(mi)
print(*mins, sep='\n')


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

using ll = long long;

int main() {
    int N, amin = 0, bmin = 0;
    cin >> N;
    vector<int> p(N), ad(N + 1, 0), bd(N + 1, 0), a(N, 0), b(N, 0);
    rep(i, N) {
        cin >> p[i];
        bd[p[i]] = -i;
        p[i]--;
        ad[p[i]] = i;
    }
    rep(i, N - 1) {
        a[i + 1] = a[i] + 1;
        a[i + 1] += ad[i + 1];
        b[i + 1] = b[i] - 1;
        b[i + 1] += bd[i + 1];
        amin = min(amin, a[i + 1]);
        bmin = min(bmin, b[i + 1]);
    }
    rep(i, N) {
        a[i] -= amin - 1;
        b[i] -= bmin - 1;
    }
    rep(i, N) {
        cout << a[i];
        if (i == N - 1) cout << "\n";
        else cout << " ";
    }
    rep(i, N) {
        cout << b[i];
        if (i == N - 1) cout << "\n";
        else cout << " ";
    }
}

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

int main(){
    int a,k;
    int ctr=0;
    int h[100000]={};

    cin >>a >>k ;

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

    for(int i=0;i<a;i++){
        if(h[i]>=k){
            ctr++;
        }
    }

    cout << ctr <<endl;
}

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

int main(){
  int N;
  int A[222222];
  int i,x;
  cin >> N;
  for(i=0;i<=N-1;i++)
    cin >> A[i];
  sort(A,A+N);
  x = 1;
  for(i=0;i<=N-2;i++)
    if(A[i] == A[i+1]) x = 0;
  if(x == 1) cout << "YES" <<endl;
  else cout << "NO" <<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;

int main(void)
{
	int cnt = 0;
	std::vector<int> m(50, 0), f(50, 0), r(50, 0);
	
	while( cnt < 50 )
	{
		int a, b, c;
		
		std::cin >> a >> b >> c;
		
		if( a == -1 && b == -1 && c == -1 ) break;
		
		m[cnt] = a;
		f[cnt] = b;
		r[cnt] = c;
		cnt++;
	}
	
	for(int i = 0; i < cnt; ++i)
	{
		if( m[i] == -1 || f[i] == -1 || m[i] + f[i] < 30 )
			std::cout << "F" << std::endl;
		
		else if( m[i] + f[i] >= 80 )
			std::cout << "A" << std::endl;
		
		else if( m[i] + f[i] >= 65 && m[i] + f[i] < 80 )
			std::cout << "B" << std::endl;
		
		else if( m[i] + f[i] >= 50 && m[i] + f[i] < 65 )
			std::cout << "C" << std::endl;
		
		else if( m[i] + f[i] >= 30 && m[i] + f[i] < 50 )
		{
			if( r[i] >= 50 )
				std::cout << "C" << std::endl;
			
			else 
				std::cout << "D" << std::endl;
		}
	}
	
	return 0;
}



Measured memory_bytes: 3076
#Union Findで連結を判定
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    x-=1
    y-=1
    U.merge(x,y)
print(sum(U.is_united(i,p-1) for i,p in enumerate(P)))

Measured memory_bytes: 34528
/**
 * 	ЫЫ
**/
#include <bits/stdc++.h>
    
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
    
using namespace std;

const int N = 1e5 + 5;

int n, a[N], ans;

main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] == i) {
			if (i == n) {
				ans++;
				break;
			}
			swap(a[i], a[i + 1]);
			ans++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 640
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long ans = 1;
    for(int i = 1; i <= N; i++) {
      ans = (ans * (long)i) % 1000000007;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int gcd(int x, int y)
{
    if (x < y)
    {
        swap(x, y); //小さい方をyとする
    }
    int r = x % y;
    while( r != 0 )
    {
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}

int gcd3(int a, int b, int c)
{
    int g = gcd(a, b);
    return gcd(g, c);
}

int main()
{
    int K;
    cin >> K;
    long long sum = 0;
    for (int a = 1; a <= K; ++a)
    {
        for (int b = 1; b <= K; ++b)
        {
            for (int c = 1; c <= K; ++c)
            {
                sum += gcd3(a, b, c);
            }
        }
    }
    cout << sum << endl;
    return 0;
}


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

int main(){
	int data[5];
	cin>>data[0]>>data[1]>>data[2]>>data[3]>>data[4];
	sort( data, data+5, greater<int>() );
	for( int i=0;i<5;i++ ){
		cout<<data[i];
		if( i!=4 )cout<<" ";
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 1176
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n:usize = read();
    let mut arr: Vec<u64> = (0..5).map(|_| 0).collect();

    for _ in 0..n {
        let s:String = read();
        match s.chars().nth(0).unwrap() {
            'M' => arr[0] += 1,
            'A' => arr[1] += 1,
            'R' => arr[2] += 1,
            'C' => arr[3] += 1,
            'H' => arr[4] += 1,
            _ => ()
        }
    }
    let mut ans = 0;
    for i in 0..5 {
        for j in 0..i {
            for k in 0..j {
                ans += arr[i] * arr[j] * arr[k];
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2088
import sys
import math
import time
import itertools
from collections import defaultdict
import collections
from functools import reduce

def ep(*params):
    print(*params,file=sys.stderr)

start = time.time()

r = 0
g = 0
b = 0

ans = 0
total = 0
N = int(input())
inp = input().rstrip()
for i in range(N):
    c = inp[i]
    if c == 'R':
        r += 1
    elif c == 'G':
        g += 1
    elif c == 'B':
        b += 1
    else:
        assert False
total = r*g*b
ep(r,g,b,total)
ep(time.time() - start)
ans = total
for i in range(0,N-2):
    for j in range(i+1, (N+i+1)//2):
        k = j+j-i
        if inp[i] != inp[j] and inp[j] != inp[k] and inp[k] != inp[i]:
            ans -= 1
ep(time.time() - start)
ep(total, ans)
print(ans)

Measured memory_bytes: 9472
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <math.h>
//#include <map>
#include <iomanip>
#include <vector>

using namespace std;



string in;
int now, max_i, min_i;
char syaryo[1024];

void saiki(string in)
{
	string yajirusi;
	
	yajirusi = in.substr(0, 2);
	if (yajirusi == "") return;
	if (yajirusi == "->")
	{
		now++;
		max_i = max(now, max_i);
		syaryo[now] = in.substr(2, 1).c_str()[0];
		saiki(in.substr(3));
	} else {
		now--;
		min_i = min(now, min_i);
		syaryo[now] = in.substr(2, 1).c_str()[0];
		saiki(in.substr(3));
	}
}

int main()
{
	int n;
	
	cin >> n;
	for (int i=0; i<n; i++)
	{
		cin >> in;
		now = max_i = min_i = 512;
		syaryo[now] = in[0];
		saiki(in.substr(1));
		for (int j=min_i; j<=max_i; j++)
		{
			cout << syaryo[j];
		}
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1452
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = 10**10

t = ['Sunny', 'Cloudy', 'Rainy']
i = t.index(input())
print(t[(i+1)%3])


Measured memory_bytes: 38256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		String ans = "Yes";
		sc.close();
		while (true) {
			if (c-b <= 0) {
				break;
			} else {
				c -= b;
			}
			if (a-d <= 0) {
				ans = "No";
				break;
			} else {
				a -= d;
			}

		}
		System.out.println(ans);

	}

}

Measured memory_bytes: 27008
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define INF 1000000000

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
	
	ll n;
	cin>>n;
	VI a(n);
	REP(i,n)cin>>a[i];
	ll co=0,coo=0;
	ll sum=0,summ=0;
	REP(i,n){
		if(i%2==0){
			if(sum+a[i]>0)
				sum+=a[i];
			else{
				co+=abs(sum+a[i])+1;
				sum=1;
			}
		}
		else{
			if(sum+a[i]<0) sum+=a[i];
			else{
				co+=sum+a[i]+1;
				sum=-1;
			}
		}
	}
	REP(i,n){
		if(i%2==1){
			if(summ+a[i]>0)
				summ+=a[i];
			else{
				coo+=abs(summ+a[i])+1;
				summ	=1;
			}
		}
		else{
			if(summ+a[i]<0) summ+=a[i];
			else{
				coo+=summ+a[i]+1;
				summ=-1;
			}
		}
	}
	cout<<min(co,coo)<<endl;
	
	return 0;
}


Measured memory_bytes: 640
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int D=sc.nextInt();

		int[][] points=new int [N][D];
		int count=0;

		for(int i=0;i<N;i++){
			for(int j=0;j<D;j++){
				points[i][j]=sc.nextInt();
			}
		}

		for(int i=0;i<N-1;i++){
			for(int j=i+1;j<N;j++){
			
				int sum=0;
				for(int k=0;k<D;k++){
					sum+=Math.pow(points[i][k]-points[j][k],2);
				}
				double distance=Math.sqrt(sum);
			
				double flooredDistance=Math.floor(distance);
				if(distance==flooredDistance){
					count++;
				}
			}
		}
		System.out.print(count);
	}
}

Measured memory_bytes: 21716
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long n = Long.parseLong(sc.next());
		
		long k = Long.parseLong(sc.next());
		
		long ans1 = n % k;
		long ans2 = Math.abs(k - n% k);
		
		System.out.println(Math.min(ans1, ans2));

	}

}


Measured memory_bytes: 22996
#include <stdio.h>

int main(void)
{
	int x, sum;

	while (1)
	{
		x = getchar();
		if(x == '0')
			break;
		else {
			sum = x - '0';
			while (1) {
				x = getchar();
				if (x == '\n')
					break;
				sum += x - '0'; 
			}
		}
	printf("%d\n", sum);
	}

	return 0;
}

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

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

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

    long long kane = 1000;
    long long kabu = 0;
    for (int i = 1; i < as.size(); i++) {
        if (as[i - 1] < as[i]) {
            kabu += kane / as[i - 1];
            kane %= as[i - 1];
        } else {
            kane += kabu * as[i - 1];
            kabu = 0;
        }
    }
    kane += kabu * as.back();
    cout << kane << endl;
}


Measured memory_bytes: 3588
import random
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)

N, M = map(int, raw_input().split())
# N, K = 5000, 100
AN = defaultdict(list)
for i in range(M):
    u, v = map(int, raw_input().split())
    AN[u].append(v)
longest_path_from_vertex_cache = {}

def get_longest_path(V):


    if V in longest_path_from_vertex_cache:
        return longest_path_from_vertex_cache[V]

    adjacent_vertices = AN[V]
    longest_path = 0
    for vertex in adjacent_vertices:
        current_path_len = 1 + get_longest_path(vertex)
        if longest_path < current_path_len:
            longest_path = current_path_len

    longest_path_from_vertex_cache[V] = longest_path
    return longest_path

print max(get_longest_path(vertex) for vertex in range(1, N+1))

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

int main(){
    long long a, b, x, ax, bx;
    cin >> a >> b >> x;
    ax = (a + x - 1) / x;
    bx = b / x;
    if (ax <= bx) {
        cout << (bx - ax) + 1 << "\n";
    }
    else {
        cout << 0 << "\n";
    }
}

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

#define fs first
#define sc second

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; }


// std::vector Declaration
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// std::vector Initialization
template<typename T>
void fill_all(T& arr, const T& v) { arr = v; }
template<typename T, typename U>
void fill_all(T& arr, const U& v) { for (auto& i : arr) fill_all(i, v); }

// std::vector Debug
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    bool a = 1;
    for (auto e : v) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "]";
    return os;
}

// std::deque Debug
template<typename T>
ostream& operator<<(ostream& os, const deque<T>& d) {
    os << "[";
    bool a = 1;
    for (auto e : d) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "]";
    return os;
}

// std::pair Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << " " << p.second << ")";
    return os;
}

// std::set Debug
template<typename T>
ostream& operator<<(ostream& os, const set<T>& st) {
    os << "{";
    bool a = 1;
    for (auto e : st) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "}";
    return os;
}

// std::multiset Debug
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& st) {
    os << "{";
    bool a = 1;
    for (auto e : st) {
        os << (a ? "" : " ");
        os << e;
        a = 0;
    }
    os << "}";
    return os;
}

// std::map Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& mp) {
    os << "{";
    bool a = 1;
    for (auto e : mp) {
        os << (a ? "" : " ");
        os << e.first << ":" << e.second;
        a = 0;
    }
    os << "}";
    return os;
}

// std::tuple Debug
template<int N, class Tuple>
void out(ostream& os, const Tuple& t){}
template<int N, class Tuple, class H, class ...Ts>
void out(ostream& os, const Tuple& t) {
    if (N) os << " ";
    os << get<N>(t);
    out<N+1,Tuple,Ts...>(os, t);
}
template<class ...Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
    os << "(";
    out<0,tuple<Ts...>,Ts...>(os, t);
    os << ")";
    return os;
}

// Debug
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl


struct edge { int to, cost; };
ostream& operator<<(ostream& os, const edge& e) {
    os << "(" << e.to << ", " << e.cost << ")";
    return os;
}

const LL LINF = 1LL<<60;
const int IINF = 1<<30;
const LL MOD = 1e9+7;

int main()
{
    int n, k; cin >> n >> k;
    vector<int> h(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
        if (h[i] >= k) {
            ++ans;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define fi first
#define se second
#define PI (acos(-1))

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;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;
const int INF=1e9;

typedef pair<P,int> PP;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	ll l;
	cin>>n>>m>>l;
	vector<vector<ll>> g(n,vector<ll>(n,inf));
	rep(i,n) g[i][i]=0;
	rep(i,m){
		int a,b;
		ll c;
		cin>>a>>b>>c;
		a--,b--;
		g[a][b]=g[b][a]=c;
	}
	//(補給回数、満タンから使用した燃料)としてi→jの最短距離
	vector<vector<P>> dist(n,vector<P>(n,P(inf,inf)));
	rep(i,n){
		priority_queue<PP,vector<PP>,greater<PP>> que;
		dist[i][i]=P(0,0);
		que.push(PP(P(0,0),i));
		while(!que.empty()){
			auto now=que.top();
			que.pop();
			int v=now.se;
			ll kaisu=now.fi.fi;
			ll used=now.fi.se;
			if(now.fi>dist[i][v]) continue;
			rep(j,n){
				if(j==v) continue;
				if(g[v][j]>l) continue;
				P ne;
				if(used+g[v][j]>l){
					ne.fi=kaisu+1;
					ne.se=g[v][j];
				}else{
					ne.fi=kaisu;
					ne.se=used+g[v][j];
				}
				if(chmin(dist[i][j],ne)){
					que.push(PP(ne,j));
				}
			}
		}
	}
	int q;
	cin>>q;
	while(q--){
		int s,t;
		cin>>s>>t;
		s--,t--;
		ll ans=dist[s][t].fi;
		if(ans>=inf) cout<<-1<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3904
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#define int long long
#define ll long long
#define mod  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
#define ps push_back
double pi = 3.141592653589793;
using namespace std;
int z=0;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
//ここから始めよう
int mul[114514];int di[114514];
int fact(int x,int y){
    if(y==1)return x;
    else if(y%2==0)return fact(x*x%mod,y/2);
    else return fact(x*x%mod,y/2)*x%mod;
}
void init(){
    mul[0]=1;
    rep(i,1,114514)mul[i]=mul[i-1]*i%mod;
    di[114513]=fact(mul[114513],mod-2);
    for(int i=114512;i>=0;i--)di[i]=di[i+1]*(i+1)%mod;
}
signed main(){
    int n;cin>>n;
    init();
    int a[141514];rep(i,0,n)cin>>a[i];
    int d[114514];d[0]=1;
    rep(i,1,n+1)d[0]=d[0]*i%mod;
    rep(i,1,n){
        //cout<<di[i]<<" ";
        d[i]=((d[i-1]*i)%mod*fact(i+1,mod-2))%mod;
    }
    int sum[114514];sum[0]=d[0];
    rep(i,0,n-1){
        sum[i+1]=sum[i]+d[i+1];sum[i+1]%=mod;
        //cout<<sum[i]<<" ";
    }//cout<<sum[n-1]<<endl;
    int ans=0;
    rep(i,0,n){
        ans+=a[i]*(sum[i]+sum[n-i-1]-sum[0]);ans%=mod;
    }
    cout<<ans<<endl;return 0;
}

Measured memory_bytes: 4608
#include <bits/stdc++.h>
#define fi first
#define se second
#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 srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int x;
  cin >> x;
  if(x>=30)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

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

int bubblesort(int A[],int N);

int main(){
    int N,ans;
    cin>>N;
    int A[N];

    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    ans=bubblesort(A,N);
    for(int i=0;i<N-1;i++){
        cout<<A[i]<<" ";
    }
    cout<<A[N-1]<<endl;
    cout<<ans<<endl;

    return 0;
}

int bubblesort(int A[],int N){
    int sw=0;
    int j=0;
    while(j!=N-1){
        for(int i=N-1;i!=j;i--){
            
            if(A[i]<A[i-1]){
                int tmp;
                tmp=A[i];
                A[i]=A[i-1];
                A[i-1]=tmp;
                
                sw++;
            }
        }
        j++;
    }
    return sw;
}


Measured memory_bytes: 3064
import numpy as np

N, M, C = map(int, input().split())
B = np.array(list(map(int, input().split())))

ans = 0
for i in range(N):
    A = np.array(list(map(int, input().split())))
    if np.dot(A, B) + C > 0:
        ans += 1
print(ans)



Measured memory_bytes: 20388
from collections import defaultdict


def main():
    _ = int(input())
    heights = list(map(int, input().split()))

    """
    for j>i, j-i = Ai + Aj
    i + Ai = j -Aj
    """

    L = defaultdict(int)
    R = defaultdict(int)

    for i, height in enumerate(heights):
        L[i + height] += 1
        R[i - height] += 1

    total_count = 0
    for x, count_l in L.items():
        if x in R:
            count_r = R[x]
            total_count += count_l * count_r

    print(total_count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 57704
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i ++)
#define _min(x, y) x = min(x, y)
#define _max(x, y) x = max(x, y)

using namespace std;

int main() {
  vector<double> edges(3);
  rep(i, 3) cin >> edges[i];
  sort(edges.begin(), edges.end());
  cout << edges[0] * edges[1] / 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main( ) {
    //freopen("b.01.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    vi a(256);
    rep(i, 0, s.length()){
        a[s[i]] = 1;
    }
    // a['z'] = 1;
    rep(i, 97, 26+97){
        if (a[i] == 0){
            cout << char(i) << endl;
            return 0;
        }
    } 
    cout << "None"<<endl;
    return 0;
}

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

typedef long long ll;

int main() {
  int N;
  cin >> N;
  ll a[N];
  ll sum = 0;
  for (int i = 0; i < N; i++) {
    scanf("%lld", a + i);
    sum += a[i];
  }

  // 累積和をとる
  for (int i = 1; i < N; i++) a[i] += a[i-1];

  ll mini = 1e18;
  for (int i = 0; i < N - 1; i++) {
    mini = min(mini, abs(a[i] - (sum - a[i])));
  }

  // 解答
  cout << mini << endl;

  return 0;
}


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

struct cand{int id, v;};
int C[105], cnt[30];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    while(true){
        int N; cin >> N;
        if(!N) return 0;
        for(int i=0;i<N;i++){
            char c; cin >> c;
            C[i] = c - 'A';
        }

        bool ok = false;
        fill(cnt, cnt+26, 0);
        cand mx = {-1, 0}, nx = {-1, 0};
        for(int i=0;i<N;i++){
            cnt[C[i]]++;
            if(C[i]==mx.id){
                mx.v++;
            }
            else if(C[i]==nx.id){
                nx.v++;
                if(nx.v>mx.v){
                    swap(mx.id, nx.id);
                    swap(mx.v, nx.v);
                }
            }
            else if(cnt[C[i]]>mx.v){
                nx.id = mx.id, nx.v = mx.v;
                mx.id = C[i], mx.v = cnt[C[i]];
            }
            else if(cnt[C[i]]>nx.v){
                nx.id = C[i], nx.v = cnt[C[i]];
            }

            if(mx.v>nx.v+N-i-1){
                printf("%c %d\n", 'A'+mx.id, i+1);
                ok = true;
                break;
            }
        }
        if(!ok) printf("TIE\n");
    }
}


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


Measured memory_bytes: 3592
package main

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

func main() {
	a := float64(readInt())
	b := float64(readInt())
	h := float64(readInt())
	m := float64(readInt())

	radianDegree360 := 2 * math.Pi
	radianDegree90 := math.Pi / 2
	//	fmt.Printf("radianDegre360 = %f, degree = %f\n", radianDegree360, radianDegree360*360/radianDegree360)
	//	fmt.Printf("radianDegre90  = %f, degree = %f\n", radianDegree90, radianDegree90*360/radianDegree360)

	radianH := radianDegree90 - (h/12.0)*radianDegree360 - (1.0/12.0)*radianDegree360*(m/60)
	posHx := a * math.Cos(radianH)
	posHy := a * math.Sin(radianH)

	radianM := radianDegree90 - (m/60.0)*radianDegree360
	posMx := b * math.Cos(radianM)
	posMy := b * math.Sin(radianM)

	//	fmt.Printf("radianH = %f, degree = %f\n", radianH, radianH*360/radianDegree360)
	//	fmt.Printf("radianM = %f, degree = %f\n", radianM, radianM*360/radianDegree360)

	//	fmt.Printf("H = (%f, %f)\n", posHx, posHy)
	//	fmt.Printf("M = (%f, %f)\n", posMx, posMy)

	ans := math.Sqrt((posHx-posMx)*(posHx-posMx) + (posHy-posMy)*(posHy-posMy))
	fmt.Println(ans)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 1788
//Volume1-0133
import java.util.Scanner;

class Main {

	private static final int      L      = 8;
	private static       char[][] board,
	                              temp;

	public static void main(String[] arg){
		Scanner sc = new Scanner(System.in);
		board = new char[L][L];
		temp  = new char[L][L];
		for(int i=0;i<L;i++){
			board[i] = sc.nextLine().toCharArray();
		}
		for(int i=0;i<3;i++){
			turn();
			print(i);
		}
	}

	private static void turn(){
		copy(board,temp);
		for(int i=0;i<L;i++){
			for(int j=0;j<L;j++){
				board[j][L-1-i] = temp[i][j];
			}
		}
	}

	private static void copy(char[][] a,char[][] b){
		for(int i=0;i<L;i++){
			for(int j=0;j<L;j++){
				b[i][j] = a[i][j];
			}
		}
	}

	private static void print(int angle){
		System.out.println((angle+1)*90);
		for(int i=0;i<L;i++){
			for(int j=0;j<L;j++){
				System.out.print(board[i][j]);
			}
			System.out.println();
		}

	}
}

Measured memory_bytes: 17156
#include <iostream>

using namespace std;

typedef long long ll;
const ll MOD = 998244353;

int a, b;

int main(){
    cin >> a >> b;
    if (a > 0) {
        cout << "Positive" << endl;
    } else if (a == 0){
        cout << "Zero" << endl;
    } else if (b >= 0) {
        cout << "Zero" << endl;
    } else {
        if ((b - a)%2 == 1){
            cout << "Positive" <<endl;
        } else {
            cout << "Negative" << endl;
        }
    }
}


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

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

using namespace std;

int main() {
  int64_t n, T;
  std::cin >> n >> T;
  std::vector<int64_t> t(n);
  rep(i, n) std::cin >> t[i];

  int64_t sum = 0;
  rep(i, n - 1) {
    int dt = t[i + 1] - t[i];
    if (dt < T) {
      sum += dt;
    } else {
      sum += T;
    }
  }
  sum += T;

  std::cout << sum << std::endl;
  return 0;
}


Measured memory_bytes: 4784
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m,x=map(int, readline().rstrip().split())
    memo=[[0 for i in range(m+1)] for j in range(n)]
    for i in range(n):
        memo[i]=list(map(int, readline().rstrip().split()))

    loops=[[0,1] for i in range(n)]

    minCost=9999999999
    for loop2 in list(itertools.product(*loops)):
        cost=0
        loop=list(loop2)
        algo=[0]*m
        for l in range(len(loop)):
            if loop[l]==1:
                cost+=memo[l][0]
                for a in range(m):
                    algo[a]+=memo[l][a+1]
        if min(algo) >=x:
            minCost=min(minCost,cost)
    if minCost==9999999999:
        print(-1)
    else:
        print(minCost)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Measured memory_bytes: 16748
#include <iostream>
#include <string>
#include <stdio.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cfloat>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <iomanip>

using namespace std;

#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
// #define req(j, n) for (ll j = 1; j < (n+1); j++)
// #define rer(k, n) for (ll k = 1; k < (n+1); k++)


int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    int ans=0;
    rep(i, N) {
        cin >> p[i];
    }
    sort(p.begin(), p.end());
    rep(i, K) {
        ans += p[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n = I()
U = S()
D = S()
ans = 3
if U[0] != D[0]:
    ans *= 2
for i in range(1, n):
    if U[i-1] == U[i] or (U[i] == D[i] and U[i-1] != D[i-1]):
        continue
    elif U[i-1] != D[i-1] and U[i] != D[i]:
        ans = ans * 3 % mod
    else:
        ans = ans * 2 % mod



print(ans)

Measured memory_bytes: 39664
import sys

def main():
    def input(): return sys.stdin.readline().rstrip()
    
    N = int(input())
    S = input()
    
    r, g, b = S.count('R'), S.count('G'), S.count('B')
    
    exce = 0
    for i in range(N):
        for j in range(i, N):
            k = 2*j - i
            if k < len(S):
                if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                    exce += 1
    print(r*g*b - exce)
    
        
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9068
n, x = [int(x) for x in input().split()]
def patties(n):
    return 1 if n == 0 else 2 * patties(n - 1) + 1
def layers(n):
    return 1 if n == 0 else 2 * layers(n - 1) + 3
def eat(n, x):
    if n == 0:
        return x
    else:
        if x <= layers(n - 1) + 1:
            return eat(n - 1, max(0, x - 1))
        elif x == layers(n):
            return patties(n)
        else:
            return patties(n - 1) + 1 + eat(n - 1, x - (layers(n - 1) + 1) - 1)

print(eat(n, x))


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

int main(){
  string S;
  cin >> S;
  int L=S.size();
  sort(S.begin(), S.end());
  int ans=0;
  for(int i=0; i<L-1; i++){
    if(S.at(i)==S.at(i+1)) ans++;
  }
  if(ans==0) cout << "yes" << endl;
  else cout << "no" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
	int N,M,K; cin >> N >> M >> K;
	bool ok = false;
	rep(i,N/2+1){
		int start = i * M;
		if(K == start) ok = true;
		int d = N-2*i;
		rep(j,M){
			start += d;
			if(K == start) ok = true;
		}
	}
	cout << (ok ? "Yes" : "No") << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl;
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0;

#define MAX 105


int n,m,d;
int mass[MAX][MAX];

bool check_yoko(int i,int j){
  int dd=d;
  for(int v=j; v<m; v++){
    if(mass[i][v]) return false;
    dd--;
    if(!dd) return true;
  }
  return false;
}


bool check_tate(int i,int j){
  int dd=d;
  for(int v=i; v<n; v++){
    if(mass[v][j]) return false;
    dd--;
    if(!dd) return true;
  }
  return false;
}

int main(){
  cin>>n>>m>>d;
  for(int i=0;i<n; i++){
    for(int j=0; j<m; j++){
      char ch;
      cin>>ch;
      if(ch=='#') mass[i][j]=1;
      else mass[i][j]=0;
    }
  }
  
  int ans=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(mass[i][j]) continue;
      if(check_yoko(i, j)) ans++;
      if(check_tate(i,j)) ans++;
    }
  }
  
  cout<<ans<<en
}



Measured memory_bytes: 3120
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <cstdlib>

using namespace std;

class sci1
{
private:
   
public:
   int s[6];
   //string hougaku;
   
   void set_scikoro(int* m1);
   void set_up_m(string m2);
   void m_print();
};

void sci1::set_scikoro(int* m1)
{
    int i;

    for ( i = 0; i < 6; ++i){
        s[i]=m1[i];
    }
}

void sci1::set_up_m(string m2)
{
    int i;
    int len_m2;
    int temp1;
    
    len_m2 = m2.length();
    
    for ( i = 0; i < len_m2; ++i){
        if (m2[i]== 'E'){
            temp1 =s[3];
            s[3] = s[5];
            s[5] = s[2];
            s[2] = s[0];
            s[0] = temp1;
            //cout << m2[i] <<endl;
        }else if (m2[i]== 'W'){
            temp1 =s[2];
            s[2] = s[5];
            s[5] = s[3];
            s[3] = s[0];
            s[0] = temp1;
            //cout << m2[i] <<endl;
        }else if (m2[i]== 'S'){
            temp1 =s[0];
            s[0] = s[4];
            s[4] = s[5];
            s[5] = s[1];
            s[1] = temp1;
            //cout << m2[i] <<endl;
        }else if (m2[i]== 'N'){
            temp1 =s[0];
            s[0] = s[1];
            s[1] = s[5];
            s[5] = s[4];
            s[4] = temp1;
            //cout << m2[i] <<endl;
        }
    }
    //cout << s[0] <<endl;
    /*
    for ( i = 0; i < len_m2 ; ++i){
        cout << m2[i] << endl;
    }
    */
    //hougaku = m2[0];
}

void sci1::m_print()
{
    int i;
  
    /*
    for ( i = 0; i < 6 ; ++i){
        cout << s[i] << endl;
    }
    */
    cout << s[0] << endl;
}

int main(){
    int i;
    int m[6];
    string hougaku1;
    
    for ( i = 0; i < 6; ++i){
        cin >> m[i];
    }
    cin >> hougaku1;
   
    sci1 saikoro1;
    
    saikoro1.set_scikoro(m);
    saikoro1.set_up_m(hougaku1);
    saikoro1.m_print();
    
    return 0;
}

Measured memory_bytes: 3192
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();  // 花札の枚数
            int r = sc.nextInt();  // 交換回数
            if (n == 0 && r == 0) {
                break;
            }
            ArrayList<Integer> hanahuda = new ArrayList<Integer>();
            for (int i = 0; i < n; i++) {
                hanahuda.add(i + 1);
            }
            for (int i = 0; i < r; i++) {
                int p_ = n - sc.nextInt(); // 花札の交換する部分の一番上（1～）
                int c = sc.nextInt(); // 交換する枚数

                ArrayList<Integer> buf = new ArrayList<Integer>();
                for (int j = 0; j < p_ - c + 1; j++) {
                    buf.add(hanahuda.get(j));
                }
                for (int j = p_ + 1; j < n; j++) {
                    buf.add(hanahuda.get(j));
                }
                for (int j = p_ - c + 1; j <= p_; j++) {
                    buf.add(hanahuda.get(j));
                }
                hanahuda = buf;
            }
            System.out.println(hanahuda.get(hanahuda.size() - 1));
        }
        sc.close();
    }
}



Measured memory_bytes: 39132