akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007; //998244353;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}

static void B();

int main()
{
	B();
	fflush(stdout);
	return 0;
}

static void B()
{
	LLONG N, D;
	get(N, D);

	LLONG D2 = D * D;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		LLONG x, y;
		get(x, y);

		if ((x * x + y * y) <= D2) {
			ans++;
		}
	}
	printf("%d\n", ans);
}


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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
const ll mod = 1e9 + 7;
const int INF = 1e9;
const int MAX_N = 200002;
//BIT	[1,n]
int bit[MAX_N + 1], siz;
int sum(int i){
	int s = 0;
	while (i > 0) {
		s += bit[i];
		i -= i&-i;//最後の1bit
	}
	return s;
}
void add(int i, int x){
	while (i <= siz) {
		bit[i] += x;
		i += i&-i;//最後の1bit
	}
}


int main() {
	cin.sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<ll>b(N+1),tmp(N+1);
	map<ll, int>mp;
	b.push_back(0);
	reps(i,1, N+1) {
		ll a;
		cin >> a;
		b[i] = b[i-1]+a - K;
		tmp[i] = b[i];
	}
	sort(tmp.begin(), tmp.end());
	rep(i, N + 1)mp[tmp[i]] = i;
	ll ans = 0;
	siz = N + 1;
	rep(i, N + 1) {
		ans += sum(mp[b[i]] + 1);
		add(mp[b[i]] + 1, 1);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 18020
#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(long long i=a; i<b; i+=1)
#define repr(i,a,b) for(long long i=a; i<=b; i+=1)
#define vec vector<ll>
#define map map<string,int>
#define repa(p,A) for(auto p:A)
#define pb push_back
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())

using namespace std;
int main() {
  ll K;
  cin>>K;
  string S,T;
  cin>>S;
  
  if(S.size()<=K) {
    cout<<S<<endl;
  }
  else {
    std::string str = S;
    T=str.substr(0, K);
    cout<<T+"..."<<endl;
  
     
    
  }
}
    

Measured memory_bytes: 3632
INF = float("inf")
MAX = 101
n = int(input())
z = []
m = [[0] * MAX for _ in range(MAX)]
for i in range(1, n + 1):
    a, b = map(int, input().split())
    z.append(a)
z.append(b)
for l in range(2, n + 1):
    for i in range(1, n - l + 2):
        j = i + l - 1
        m[i][j] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + z[i - 1] * z[k] * z[j])
print(m[1][n])



Measured memory_bytes: 5672
#include<iostream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  cout << setprecision(10);
  int M, D;
  cin >> M >> D;
  int c=0;
  for(int d1=2; d1<=9; d1++){
    for(int d0=2; d0<=9; d0++){
      if(d1*10+d0<=D && d0*d1<=M) c++;
    }
  }
  cout << c << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
        // 自分の得意な言語で
        // Let's チャレンジ！！

        Scanner sc = new Scanner(System.in);
        boolean can = true;
        int positionCount = sc.nextInt();
        int time_p = 0;
        int x_p = 0;
        int y_p = 0;
        while (positionCount-- > 0) {
            int time_q = sc.nextInt();
            int x_q = sc.nextInt();
            int y_q = sc.nextInt();
            
            if (!canGo(time_p, x_p, y_p, time_q, x_q, y_q)) {
                can = false;
            }
            
            time_p = time_q;
            x_p = x_q;
            y_p = y_q;
        }
        
        if (can) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
    
    public static boolean canGo(int time_p, int x_p, int y_p, int time_q, int x_q, int y_q) {
        int timeDifference = time_q - time_p;
        int length_x = Math.abs(x_q - x_p);
        int length_y = Math.abs(y_q - y_p);
        int moveLength = length_x + length_y;
        
        if (timeDifference < moveLength) return false;
        if (timeDifference == moveLength) return true;
        
        while (timeDifference != moveLength) {
            timeDifference -= 2;
            if (timeDifference < moveLength) return false;
            if (timeDifference == moveLength) return true;
        }
        
        return true;
    }
}

Measured memory_bytes: 88476
/*
 *  author: chw0501
 *  created: 15.04.2020 02:46:15(UTC)
*/
#include <bits/stdc++.h>

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

int n;
int num[4];

//dp[i][j][k]: 아직 남아있는 1의 개수 i, 2의 개수, 3의 개수
double dp[301][301][301];

double solve(int i,int j,int k){
	double& ret= dp[i][j][k];
	if(ret>=0) return ret;
	if(i==0 && j==0 && k==0){
		return ret=0;
	}
	ret=(double)n/(i+j+k);
	if(i>0){
		ret+=(double)i/(i+j+k)*solve(i-1,j,k);
	}
	if(j>0){
		ret+=(double)j/(i+j+k)*solve(i+1,j-1,k);
	}
	if(k>0){
		ret+=(double)k/(i+j+k)*solve(i,j+1,k-1);
	}
	return ret;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		num[x]++;
	}
	memset(dp,-1.0,sizeof(dp));
	printf("%.9lf",solve(num[1],num[2],num[3]));
	return 0;
}

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

int main(){
  int N;
  cin >>N;
  
  vector<double> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec.at(i);
  }
  vector<double> vec1(N);
  for(int j=0;j<N;j++){
    vec1.at(j)=1/vec.at(j);
  }
  double sum=0;
  for(int k=0;k<N;k++){
    sum+=vec1.at(k);
  }
  cout<<1/sum<<endl;
}
  

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<cstdlib>
#include<ctime>
#include<cctype>

using namespace std;

int n;
int h[100010];
int dp[100010];
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> h[i];
	}
	dp[1] = 0;
	dp[2] = abs(h[2] - h[1]);
	for(int i = 3; i <= n; i++)
	{
		dp[i] = min(dp[i-2] + abs(h[i] - h[i-2]), dp[i-1] + abs(h[i] - h[i-1]));
	}
	cout << dp[n] << endl; 
	return 0;
}

Measured memory_bytes: 1024
n, k = input().split()
l = list(map(int,input().split()))
n = int(n)
k = int(k)

rn_0 , rn_2 = 0, 0

for i in range(n-1):
  for j in range(i+1, n):
    if l[i] > l[j]:
      rn_0 += 1

for i in range(n):
  for j in range(0, i):
    if l[i] > l[j]:
      rn_2 += 1

rn_0 *= k*(k+1)//2
rn_2 *= k*(k-1)//2

rn = (rn_0 % (10**9+7)) + (rn_2 % (10**9+7))
print(rn%(10**9+7))


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




int main() {
  int h,w,a,b,x,t;
  cin>>h>>w>>a>>b;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if((j<a)^(i<b)){
        cout<<'0';
      }else{
        cout<<'1';
      }
    }
    cout<<endl;
  }
}

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

inline bool isPrime(int a){
  if(a<=1)return false;
  for(int i=2;i*i<=a;i++){
    if(a%i==0)return false;
  }
  return true;
}

int main(){
  bool pt[30030] = {};
  vector<int> pl;
  for(int i=0;i<=30000;i++){
    if(isPrime(i)){
      pt[i] = 1; pl.push_back(i);
    }
  }

  int t;
  while(cin >> t,t){
    int res = 0;
    for(int i=0;i<(int)pl.size();i++){
      for(int j=i;j<(int)pl.size();j++){
	int rem = t - pl[i] - pl[j];
	if(rem < pl[j])break;
	if(pl[i]+pl[j]>rem && pt[rem])res++;
      }
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 1280
#include <stdio.h>
#define min(p,q)((p)<(q)?(p):(q))

int a[100010];
int cnt[100010];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	int ans=1e6;
	int r=0,kind=0;
	for(int l=0;l<n;l++){
		while(r<n&&kind<k){
			if(a[r]<=k)kind+=!cnt[a[r]]++;
			r++;
		}
		if(kind==k)ans=min(ans,r-l);
		if(a[l]<=k)kind-=!--cnt[a[l]];
	}
	printf("%d\n",ans==1e6?0:ans);
}



Measured memory_bytes: 2552
import math

A, B, H, M = map(int, input().split())

short_v = 360 / (12*60)
long_v = 360 / 60

short_arg = (short_v * (H * 60) + short_v * M)
long_arg = long_v * M

tmp = abs(short_arg-long_arg)
if tmp > 180:
    tmp = 360 - tmp
theta = math.radians(tmp)

result_2 = A**2 + B**2 - 2*A*B*math.cos(theta)

print(math.sqrt(result_2))


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }

int q;

int main() {
	cin >> q;
	inc(qq, q) {
		LL a, b, c, d;
		cin >> a >> b >> c >> d;
		
		bool ans = true;
		a -= b;
		LL s = (a <= c ? a : a - b * ce(a - c, b));
		if(s < 0) { ans = false; }
		else if(b > d) { ans = false; }
		else if(b == d) { ans = true; }
		else if(b <= c + 1) { ans = true; }
		else {
			assert(inII(s, 0, c) && c + 1 < b && b < d);
			ans = ((s + d - (c + 1)) % (gcd(b, d)) >= b - (c + 1));
		}
		
		cout << (ans ? "Yes" : "No") << "\n";
	}
	
	return 0;
}


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

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef priority_queue< int, vector< int >, greater< int > >  minHeap;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define mod 1000000007
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bug(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"

int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int N,int pos)
{
    return N = N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}

inline int addmod(lli x,lli y)
{
    return (x%mod + y%mod)%mod;
}
inline int submod(lli x,lli y)
{
    return (x%mod - y%mod + mod)%mod;
}
inline int mulmod(lli x,lli y)
{
    return (x%mod * y%mod)%mod;
}


inline int nextSubMask(int i, int mask)
{
    return (i-1)&mask;   /// returns next  submask
}

template<typename T>
void we_r_done(T mssg)
{
    cout<<mssg;
    exit(0);
}


int main()
{
    ///freopen("output.txt","w",stdout);
    //freopen("input.txt","r",stdin);
    FastIO;

    const int N = 52;
    lli p[N] , len[N];

    p[0] = len[0] = 1;
    for(int i=1; i<N; i++){
        p[i] = 2*p[i-1] + 1;
        len[i] = 2*len[i-1] + 3;
    }

    int n;
    while(cin>>n){

        lli x;
        cin>>x;
        lli ans = 0;
        while(x){
            if(len[n] == x){
                ans += p[n];
                break;
            }
            lli fh = (len[n-1]+1);
            if(fh>=x){
                x--;
                n--;
            }
            else{
                ans += (p[n-1]+1);
                if((fh+1) == x){
                    break;
                }
                else{
                    x -= (fh+1);
                    n--;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)
///using bs = bitset<MX>; // how many distinct number can be form?
///sort(atoz(v), [](const data x, const data y){return (x.a==y.a?x.b>y.b : x.a<y.a);});


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define nn 200006
#define ll long long
ll n,t,e;
ll x[nn];ll f[nn];
int main()
{
	scanf("%lld%lld%lld",&n,&e,&t);
	for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
	deque<int> q;ll oops=1e17;
	q.push_back(0);x[0]=0;int ls=0;
	for(int i=1;i<=n;i++)
	{
		while(ls<i and 2*(x[i]-x[ls+1])>t)
		{
			if(q.size() and ls==q.front()) q.pop_front();
			oops=min(oops,f[ls]-x[ls+1]*2-x[ls]);
			ls++;
		}
		
		if(q.size()) f[i]=f[q.front()]+t+x[i]-x[q.front()];
		else f[i]=1e17;
		f[i]=min(f[i],oops+x[i]*3);
		while(q.size() and f[q.back()]-x[q.back()]>=f[i]-x[i]) 
			q.pop_back();
		q.push_back(i);
	}	
	
	printf("%lld\n",f[n]+e-x[n]);
}

Measured memory_bytes: 2048
main :: IO ()
main = do
  [r, g, b, n] <- map read . words <$> getLine
  print $ solve r g b n

solve :: Int -> Int -> Int -> Int -> Int
solve r g b n = length
  [ (l, m, p)
  | l <- [0 .. n]
  , m <- [0 .. n - r * l]
  , let (p, q) = (n - r * l - g * m) `divMod` b
  , q == 0
  , p >= 0
  ]


Measured memory_bytes: 1020
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ll N, T;
    cin >> N >> T;
    ll A[N + 5];
    map<ll, ll> mp;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    ll max_v = -20000000000000;
    ll min_v = A[0];
    for (int i = 1; i < N; i++)
    {
        max_v = max(max_v, A[i] - min_v);
        min_v = min(min_v, A[i]);
    }
    ll dis = max_v;
    ll cnt = 0;
    for (int i = 0; i < N; i++)
    {
        mp[A[i]]++;
        if (mp[A[i] - dis])
        {
            cnt++;
        }
    }
    if(T<=1)cout<<0<<endl;
    else cout<<cnt<<endl;
}

Measured memory_bytes: 13568
import itertools

directions = list(itertools.product((-1, 0, 1), repeat=2))


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                continue
            cnt = 0
            for d in directions:
                if d[0] == 0 and d[1] == 0:
                    continue
                ni = i + d[0]
                nj = j + d[1]
                if 0 <= ni and 0 <= nj and ni < H and nj < W:
                    if S[ni][nj] == '#':
                        cnt += 1
            S[i][j] = str(cnt)
    for i in range(H):
        print("".join(S[i]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 40816
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    string s; cin >> s;
    if(s[2]==s[3] && s[4]== s[5])cout << "Yes" << ln;
    else cout << "No" << ln;
}


Measured memory_bytes: 3616
//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <limits>
#include <map>
#include <vector>
#include <queue> 
#define LL long long
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
//#define int LL
using namespace std;
const int N   = 3e5+10;
//const int mod = ;
const int INF =numeric_limits<int >::max();

#define rep(i,x,y) for (int i=x;i<=y;++i)
void read(int &x)
{
	x=0;
	char ch=getchar();
	int f=1;
	while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
	while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}
int buf[30];
void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    buf[0]=0;
    while (x) buf[++buf[0]]=x%10,x/=10;
    if (!buf[0]) buf[0]=1,buf[1]=0;
    while (buf[0]) putchar('0'+buf[buf[0]--]);
}

int n,m,l[N],r[N];
int cnt[N];
void wk(int L,int R)
{
	for (int k=1;k<=m;)
	{
		int b=(L-1)/k;
		int c=L-1-k*b;
		int len=b?(c/b+1):100000;
		++cnt[k];--cnt[min(R/(b+1),k+len-1)+1];
		k+=len;		
	}
	return ;
}

signed main()
{
	
	read(n);read(m);
	rep(i,1,n) read(l[i]),read(r[i]);
	rep(i,1,n) wk(l[i],r[i]);
	rep(i,1,m) cnt[i]+=cnt[i-1];
	rep(i,1,m) write(cnt[i]),putchar('\n');
	return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define INF 1000000000000000000
#define MOD 1000000007
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;

int main() {
	string s;
	cin >> s;
	int n = (int) s.size();
	int k;
	cin >> k;
	int l = 1;
	while(l < n && s[l] == s[l - 1])
		l++;
	int r = n - 2;
	while(r >= 0 && s[r] == s[r + 1])
		r--;
	if (l == n) {
		cout << (1LL * n * k) / 2;
		return 0;
	}
	int pre = l;
	int suf = n - r - 1;
	int midAns = 0;
	int c = 0;
	for (int i = l; i <= r; i++) {
		if (s[i] != s[i - 1]) {
			midAns += c / 2;
			c = 1;
		}
		else {
			c++;
		}
	}
	midAns += c / 2;
	if (s[0] != s[n - 1]) {
		ll ansForOne = pre / 2 + midAns + suf / 2;
		cout << (1LL * ansForOne * k);
	}
	else {
		ll totalAns = pre / 2 + 1LL * midAns * k + 1LL * ((pre + suf) / 2) * (k - 1) + suf / 2;
		cout << totalAns;
	}
}



Measured memory_bytes: 256
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
ll n, s, a[maxn], ss, val, ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            a[++s] = i;
            if (i != n / i) a[++s] = n / i;
        }
        if ((n - 1) % i == 0) {
            a[++s] = i;
            if (i != (n - 1) / i) a[++s] = (n - 1) / i;
        }
    }
    sort(a + 1, a + 1 + s);
    int cnt = unique(a + 1, a + 1 + s) - a;
    for (int i = 1; i <= cnt; i++) {
        if (a[i] == 1) continue;
        val = n;
        while (val % a[i] == 0) {
            val = val / a[i];
        }
        if (val % a[i] == 1) ss++;
    }
    cout << ss - 1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

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

  if (b - a <= 1) {
    cout << k + 1 << endl;
    return 0;
  }

  if (k <= a) {
    cout << k + 1 << endl;
    return 0;
  }

  // k > a & a > b
  ll remain = k - a + 1;
  ll kaisuu = remain / 2;
  ll sub = b - a;
  ll ans = 0;
  if (remain % 2 == 0) {
    ans = sub * kaisuu + a;
  } else {
    ans = sub * kaisuu + a + 1;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int MAX_N = 10000;
const int V = 10000;

vector<int> G[MAX_N];
vector<int> rG[MAX_N];
vector<int> vs; //??°?????????????????????
bool used[MAX_N]; //?????§????????????????????????
int cmp[MAX_N];	//?±????????????£????????????????????????????????????

void add_edge(int from,int to)
{
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v)
{
	used[v] = true;
	for(int i=0;i<G[v].size();i++){
		if(!used[G[v][i]]){
			dfs(G[v][i]);
		}
	}
	vs.push_back(v);
}

void rdfs(int v,int k)
{
	used[v] = true;
	cmp[v] = k;
	for(int i=0;i<rG[v].size();i++){
		if(!used[rG[v][i]]){
			rdfs(rG[v][i],k);
		}
	}
}

int scc(int n)	//?????£??????????????°?????????
{
	memset(used,0,sizeof(used));
	vs.clear();
	for(int v=0;v<n;v++){
		if(!used[v]){
			dfs(v);
		}
	}
	memset(used,0,sizeof(used));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!used[vs[i]]){
			rdfs(vs[i],k++);
		}
	}
	return k;
}

int main()
{
	int n,m,from,to,k,l,u,v;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		cin >> from >> to;
		add_edge(from,to);
	}
	k = scc(n);	
	cin >> l;
	for(int i=0;i<l;i++){
		cin >> u >> v;
		printf("%d\n",(cmp[u] == cmp[v]));
	}
}

Measured memory_bytes: 4724
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int N, K;
ll cnt0, cnt2 = 0;
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N >> K;

	for (int i = 1; i <= N; ++i) {
		if (i%K == 0) cnt0++;
		else if (i%K == K / 2) cnt2++;
	}
	if (K % 2 == 1) cnt2 = 0;
	cout << cnt0*cnt0*cnt0 + cnt2*cnt2*cnt2;
}

Measured memory_bytes: 256
n, c, k = gets.split.map(&:to_i)
ts = n.times.map { gets.to_i }.sort!

ans = 1
base = ts.last
ps = [base]

(n - 2).downto(0) do |i|
  if ts[i] + k < base
    base = ts[i]
    ps = []
    ans += 1
  elsif ts[i] + k <= base * k
    if ps.count == c
      base = ts[i]
      ps = []
      ans += 1
    end
  end
  ps << ts[i]
end

puts ans


Measured memory_bytes: 4228
#include<stdio.h>

int reverse(int num);

int main() {
	int a, b, i, cnt;
	scanf("%d%d", &a, &b);
	cnt = 0;
	for (i = a; i <= b; i++) {
		if (i == reverse(i)) cnt++;
	}
	printf("%d", cnt);
	return 0;
}

int reverse(int num) {
	int num_rev = 0;
	while (num > 0) {
		num_rev = num_rev * 10 + num % 10;
		num /= 10;
	}
	return num_rev;
}

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

const int mod = 1e9+7;
const int INF = 2000000;
const double PI = acos(-1.0);

int main() {
    int N;
    cin >> N;
    int A[N],maxValue=0,cnt[1000050]={};
    for(int i=0;i<N;++i) {
        cin >> A[i];
        maxValue = max(maxValue, A[i]);
        cnt[A[i]]++;
    }
    vector<bool> dp(maxValue+1,false);
    sort(A, A+N);
    for(int i=0;i<N;++i) {
        if(cnt[A[i]] >= 2) dp[A[i]] = true;
        for(int j=2;j*A[i]<=maxValue;++j) {
            dp[j*A[i]] = true;
        }
    }
    int count = 0;
    for(int i=0;i<N;++i) {
        if(!dp[A[i]]) count++;
    }
    cout << count << endl;
}


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

using namespace std;

#define LL long long

const int maxn=2e5+1e2;

char s[maxn];
int top=0;

int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	LL ans=0;
	int last=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='B')last++;
		else if(s[i]=='W')
		{
			ans+=last;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main(){

  int a,b,c,k;
  int sum;
  
  cin >> a >> b >> c >> k;
  
  if(k <= a)
    sum = k;
  else
    if(k <= a+b)
      sum = a;
  	else
      sum = a - 1*(k-a-b);
  
  cout << sum << endl;
  
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;
#define forn(i, x, n) for (int i = x; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long double ld;
typedef long long ll;

int main() {
    int n, x;
    scanf("%d %d", &n, &x);
    int count = 0;
    int mn = 1e5 + 7;
    forn(c, 0, n) {
        int m;
        scanf("%d", &m);
        mn = min(mn, m);
        x -= m;
        count++;
    }
    printf("%d\n", count + (x / mn));
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int n,k,s1,s2,s3;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&k);
		k%=4;
		if (!k)s1++;
		else 
			if (k!=2)s2++;
			else s3++;
	} 
	if ((s1>=s2)||(s1+1==s2)&&(!s3))printf("Yes");
	else printf("No");
}

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a, b) accumulate(all(a), b)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(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)=(n)-1; (i)>=(m); i--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
ll const INF = 1e18;

template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    string s;
    cin >> s;
    int ans1 = 0, ans2 = 0;
    REP(i, size(s)){
        if(i%2 == 0 && s[i] == '0') ans1++;
        if(i%2 == 1 && s[i] == '1') ans1++;
    }
    REP(i, size(s)){
        if(i%2 == 0 && s[i] == '1') ans2++;
        if(i%2 == 1 && s[i] == '0') ans2++;
    }
    cout << min(ans1, ans2) << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

template<typename T> 
void show(T a){
  for(auto i : a){ cout << i << " "; }
  cout << endl;
}


int main(int argc, char *argv[]){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, y;
  cin >> n >> y;
  int a, b, c;
  a = y / 10000;
  a = a > n ? n : a;
  b = y / 5000;
  b = b > n ? n : b;
  c = y / 1000;
  c = c > n ? n : c;
  int count = 0;
  for(int i = 0; i <= a; i++){
    for(int j = 0; j <= b; j++){
      int tmp = y - 10000*i - 5000*j;
      tmp /= 1000;
      if(tmp < 0) break;
      if(i+j+tmp != n) continue;
      //printf("%d %d %d\n", i, j, tmp);
      //count += tmp >= 0 && tmp <= c ? 1 : 0;
      if(tmp <= c){
        printf("%d %d %d\n", i, j, tmp);
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
  //cout << count << endl;
}


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << max({a,b,c})-min({a,b,c}) << endl;
    return 0;
}


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


int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b >= c)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}



Measured memory_bytes: 256
main(a,b,c,p,q,r,s,S,i){for(;scanf("%d%d%d",&a,&b,&c),a;){
if(!c)a==1&&b<0?printf("1 0 %d %d\n",a,b):printf("%d %d 1 0\n",a,b);
else{
	for(r=1;r*r<=a;r++)if(a%r==0)for(p=a/r,S=1;S<=abs(c);S++)if(c%S==0){
		for(s=S,i=0;i<2;i++,s=-s)if(q=c/s,p*s+q*r==b){
			p==r&&q<s?printf("%d %d %d %d\n",r,s,p,q):printf("%d %d %d %d\n",p,q,r,s);
			goto next;
		}
	}
	puts("Impossible");
}next:;}exit(0);}

Measured memory_bytes: 608
import Data.List

main = interact $ unlines . map (show . enclose_pins . map read') . parse' . lines
 where
  parse' = splitBy (notElem ',') . takeWhile (/= "0")
  read' str = let [x,y] = map read (splitOn ',' str) in (x,y)

enclose_pins pins = length pins - length sides
 where sides = [(p1,p2)| p1<-pins, p2<-pins, p1<p2, are_counterparts p1 p2 (pins\\[p1,p2])]

are_counterparts (x1,y1) (x2,y2) xys =
 alleq $ filter (/= EQ) $ map (\(x,y) -> compare y (x * slope (x1,y1) (x2,y2) + intercept_y)) xys
  where
   alleq xs = and $ zipWith (==) xs (tail xs)
   intercept_y = snd $ intercept (x1,y1) (x2,y2)
  
slope (x1,y1) (x2,y2)
 | x2 == x1  = (y2-y1) / 1e-9
 | otherwise = (y2-y1) / (x2-x1)

intercept (x1,y1) (x2,y2) = (axis_x, axis_y)
 where
  axis_x = x1 - y1 / slope (x1,y1) (x2,y2)
  axis_y = y1 - x1 * slope (x1,y1) (x2,y2)

splitOn c xs
 | null xs = []
 | head xs == c = splitOn c (tail xs)
 | otherwise = (takeWhile (/= c)) xs : splitOn c (dropWhile (/= c) xs)

splitBy p xs
 | null xs = []
 | p (head xs) = splitBy p (tail xs)
 | otherwise = (takeWhile (not.p) xs : splitBy p (dropWhile (not.p) xs))

Measured memory_bytes: 4316
/***
**   AUTHOR::ASHUTOSH MOUDGIL
***/


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

#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define F first
#define S second
#define int long long
//#define ll long long
#define all(x) x.begin(),x.end()
#define rsort(x) sort(all(x)); reverse(all(x));
#define endl '\n'
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define vi vector<int>
#define vlli vector<long long>
#define pii pair<int,int>
#define mod 1000000007
#define LMAX 1e18
#define deb(x) cout<<#x<<" : "<<x<<endl;

void mymain(){
    string s,ans;
    cin >> s;
    if(s=="Sunny")
        ans = "Cloudy";
    else if(s=="Cloudy")
        ans = "Rainy";
    else
        ans = "Sunny";
    cout << ans <<endl;
}

signed main(){
IOS;
///freopen("input.txt", "r", stdin);
///freopen("output.txt", "w", stdout);
int t=1;
///cin>>t;
for(int tt=0;tt<t;tt++){
   ///cout << "Case #" << tt+1 <<": ";
   mymain();
   }
return 0;
}


Measured memory_bytes: 256
from collections import deque

n, m = map(int, input().split())
rooms = [[] for i in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    rooms[a].append(b)
    rooms[b].append(a)

q = deque()
q.append(1)
signs = [-1]*(n + 1)
signs[1] = 0

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if signs[i] == -1:
            signs[i] = rnum
            q.append(i)

print("Yes")

for i in signs[2:]:
    print(i)

Measured memory_bytes: 35000
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <bits/stdc++.h>

using namespace std;
long long ans,flag,sum,mn;
int main()                                    
{
	long long a,b,c;
	cin >> a >> b >> c;
	sum = max (a , b);
	sum = max (sum , c); 
	if (sum == a){
		flag = max (b, c);
	}
	else if (sum == b){
		flag = max (a , c);
	}
	else
		flag = max (a , b);
	ans = sum - flag;
	mn = min(a , b );
	mn = min( mn , c);
	ans += flag - mn;
	cout << ans << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using u64 = uint_fast64_t;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln = '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

using Tu = tuple<int, int, int>; 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);   
    int N; cin >> N;
    //N = 160000;
    vector<string> S(N);
    rep(i,N) cin >> S[i];

    map<Tu, ll> dic;
    ll ans = 0;
    rep(i,N) {
        ll A = 0;
        int K = S[i].size();
        rep(j,K) {
            if (S[i][j]=='.') continue;
            A *= 10;
            A += S[i][j] - '0';
        }
        int a = 0, b = 0, c = 0;
        while (A % 2 == 0) {
            A /= 2;
            a++;
        }
        while (A % 5 == 0) {
            A /= 5;
            b++;
        }
        bool ok = false;
        rep(j,K) {
            if (S[i][j]=='.') ok = true;
            else if (ok) c++;
        }
        for (auto j : dic) {
            auto[d,e,f] = j.first;
            ll v = min(a+d,b+e);
            if (v >= c+f) ans += j.second;
        }
        dic[Tu(a,b,c)]++;
        // clock_t end = clock();
        // double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
        // cout << i << endl;
    }

    cout << ans << ln;
}


Measured memory_bytes: 9388
n=int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

sum=0

for i in reversed(range(0,n)):
    if b[i]<=a[i+1]:
        sum+=b[i]
    elif b[i]<=a[i+1]+a[i]:
        sum+=b[i]
        a[i]-=b[i]-a[i+1]
    elif a[i+1]+a[i]<=b[i]:
        sum+=a[i+1]+a[i]
        a[i]=0

print(sum)

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

template<typename T>
void fin (T a){
    cout<<a<<endl;
    exit(0);
}

template<typename S>
void print(S a){
    cout<<a<<endl;
}

template<typename U>
void pprint(U a){
    cout<<a<<" ";
}

const ll M = 1000000000+7;


vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)
//a,bの範囲的にこれだけ配列を用意していけば十分

ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % M;
        x = x*x % M;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % M;
    return tmp * fac[a] % M;
}

/*
int main()
{
    ll n,k;
    cin >> n >> k;

    //大した量ではないので，先にfax[i]とifax[i]を全て計算しておく
    fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i<300000; i++){
        fac[i+1] = fac[i]*(i+1) % M; // n!(mod M)
        ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }


    ll ans=0;
    ans = comb(n, k)%M;
    cout << ans << endl;
    return 0;
}

*/

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


    ll s;
    cin>> s;
    ll n = s/3;

    fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i<300000; i++){
        fac[i+1] = fac[i]*(i+1) % M; // n!(mod M)
        ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }

    ll ans = 0;
    for(int i=1;i<=n;i++){
//        pprint(s-i*3);
//        print(i-1);
        ans += comb(s-i*2-1,i-1)%M;
        if(ans>=M){
            ans%=M;
        }
    }

    fin(ans);

    /*
    ll ans9 = 1;
    ll ans8 = 1;
    ll ans7 = 1;
    rep(i,n){
        ans9*=10;
        ans8*=9;
        ans7*=8;
        if(ans9>dev){
            ans9 %=dev;
        }
        if(ans8>dev){
            ans8 %=dev;
        }
        if(ans7>dev){
            ans7 %=dev;
        }
    }

    ll ans = ans9+ans7-2*ans8;
    ans %= dev;

    if(ans>=0){
        fin(ans);
    }else{
        fin(dev+ans);
    }


    */

    return 0;
}




Measured memory_bytes: 7864
#include<stdio.h>
#include<string.h>
int main(){
   char S[4];
   scanf("%s",S);

   if(strcmp(S, "ARC")==0){
      printf("%s","ABC");

      }else if(strcmp(S, "ABC")==0){
      printf("%s","ARC");
   }
   return 0;
}

Measured memory_bytes: 1668
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int d[10][10];

void warshall_floyd(int n){
	REP(k,n){
		REP(i,n){
			REP(j,n){
				d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
			}
		}
	}
}

int main(){
	int h,w;
	cin >> h >> w;
	REP(i,10) REP(j,10) cin >> d[i][j];
	vector<vector<int>> a(h, vector<int>(w));
	REP(i,h) REP(j,w) cin >> a[i][j];
	
	warshall_floyd(10);
	
	int ans=0;
	REP(i,h) REP(j,w){
		if(a[i][j]==-1) continue;
		ans += d[a[i][j]][1];
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3740
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int n;
    int w=0;
    cin >> n;
    vector<int> A(n,0);
    for(int i=0 ;i<n; i++){
        cin >> A[i];
        if(i%2==0) w+= A[i];
        else w-= A[i];
    }
    //M[i]= A[i-1]-A[i-2]+A[i-3]-..A[0].A[n-1]...+A[i] となる。(環状)
    // cerr << w << endl;
    for(int i=0; i<n; i++){
        if(i!=0){
            w=-w+2*A[i-1];
        }
        cout << w;
        if(i!=n-1) cout << " ";
    }
    cout << endl;
 
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const ll MOD = 1000000007;

int H, W;
vector<string> X;
ll dp[1005][1005];

int main(){
  cin >> H >> W;
  rep(i,H){
    string s;
    cin >> s;
    X.push_back(s);
  }
  
  dp[0][0] = 1;
  rep(i,H){
    rep(j,W){
      if(i == 0 && j == 0) continue;
      if(X[i][j] == '#') continue;
      if(i-1>=0 && X[i-1][j] != '#'){
        dp[i][j] += dp[i-1][j];
        dp[i][j] %= MOD;
      }
      if(j-1>=0 && X[i][j-1] != '#'){
        dp[i][j] += dp[i][j-1];
        dp[i][j] %= MOD;
      }
    }
  }

  cout << dp[H-1][W-1] << endl;
  
  return 0;
}


Measured memory_bytes: 9216
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <numeric>
#include <complex>
#include <iomanip>

using namespace std;

#define bitcount(n) __builtin_popcount(n)

#define debug(n) cout << n << endl;

#define PREC(n) setprecision(n)
#define DOTPREC(n) fixed << setprecision(n)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define rep(i,x) for(int i=0;i<(x);++i)
#define rep1(i,x) for(int i=1;i<=(x);++i)
#define rrep(i,x) for(int i=(x)-1;i>=0;--i)
#define rrep1(i,x) for(int i=(x);i>=1;--i)
#define FOR(i,a,x) for(int i=(a);i<(x);++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define omajinai ios::sync_with_stdio(false); cin.tie(0)

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

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

const ll MOD = 1000000007;

int a, b, h;

int main(void)
{
    cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
    return 0;
}


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

typedef struct {
    double x;
    double y;
} point;

void koch(int n, point p1, point p2){
    static const double pi = 3.141592653589793;
    point s, t, u;

    if(n == 0){
        cout << p2.x << " " << p2.y << endl;
        return ;
    }else{
        s.x = (2/3.0) * p1.x + (1/3.0) * p2.x;
        s.y = (2/3.0) * p1.y + (1/3.0) * p2.y;
        t.x = (1/3.0) * p1.x + (2/3.0) * p2.x;
        t.y = (1/3.0) * p1.y + (2/3.0) * p2.y;
        u.x = s.x + (t.x - s.x) * cos(pi/3) - (t.y - s.y) * sin(pi/3);
        u.y = s.y + (t.x - s.x) * sin(pi/3) + (t.y - s.y) * cos(pi/3);
        koch(n-1, p1, s);
        koch(n-1, s, u);
        koch(n-1, u, t);
        koch(n-1, t, p2);
    }
}
int main(){
    int n;
    cin >> n;
    point p1, p2;
    p1.x = 0; p1.y = 0;
    p2.x = 100; p2.y = 0;
    cout << p1.x << " " << p1.y << endl;
    koch(n, p1, p2);
    return 0;
}


Measured memory_bytes: 3288
#include <stdio.h>

int main(void) {

  long n;
  scanf("%ld", &n);
  long a[n];
  for (long i = 0; i < n; i++) {
    scanf("%ld", &a[i]);
  }
  long rain[n];
  rain[0] = 0;
  for (long i = 1; i < n; i++) {
    rain[i] = a[i-1]*2-rain[i-1];
  }
  if (a[n-1]*2 != rain[0]+rain[n-1]) {
    rain[0] = (a[n-1]*2-rain[0]-rain[n-1])/2;
    for (long i = 1; i < n; i++) {
      rain[i] = a[i-1]*2-rain[i-1];
    }
  }
  printf("%ld", rain[0]);
  for (long i = 1; i < n; i++) {
    printf(" %ld", rain[i]);
  }
  printf("\n");

  return 0;
}

Measured memory_bytes: 2816
#include<stdio.h>

int main(void){
    int a,b,c;
    int i;
    int count;
    
    scanf("%d %d %d",&a,&b,&c);
    for(i=a;i<=b;i++)
        if(!(c%i))
            count++;

    printf("%d\n",count);
    return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
const int maxn=105;

int main()
{
	string stu;
	cin>>stu;
	cout<<stu[0];
	cout<<stu.size()-2<<stu[stu.size()-1]<<endl;
	return 0;
} 

Measured memory_bytes: 256
from itertools import chain
def query(indices):
    print('? '+' '.join(map(lambda x: str(x+1),indices)), flush=True)
    r = input()
    if r == '-1':
        exit()
    return r == 'Red'

def answer(colors):
    print('! '+''.join(map(lambda x: 'R' if x else 'B', colors)), flush=True)

def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

from random import shuffle

def solve(N):
    # detect change

    check = lambda i: query(range(i,i+N)) if i <= N else query(chain(range(i-N),range(i,2*N)))

    L = list(range(2*N))
    shuffle(L)
    x = L[-1]
    orig = check(x)
    for y in reversed(L[:-1]):
        if orig != check(y):
            break

    if y < x:
        x -= N*2


    while abs(x-y) > 1:
        mid = (x+y)//2
        r = check((mid)%(2*N))
        if r == orig:
            x = mid
        else:
            y = mid

    x %= 2*N

    res = [None]*(2*N)
    a,b = x, (x+N)%(2*N)
    res[a] = orig
    res[b] = not orig
    # [i+1, ... , i+N] is even
    n1 = list(range(a+1,b)) if a < b else list(chain(range(a+1,2*N),range(0,b)))
    # [0...i-1] + [i+N+2, ... 2*N] is even
    n2 = list(range(b+1,a)) if b < a else list(chain(range(b+1,2*N),range(0,a)))
    for i in n1:
        res[i] = query(n2+[i])
    for i in n2:
        res[i] = query(n1+[i])

    answer(res)


if __name__ == '__main__':
    N = int(input())
    solve(N)

Measured memory_bytes: 4804
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
const int INF=1e9;
using namespace std;

int main(){
    int n, a;
    cin>>n>>a;
    if((n%500)<=a) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2149>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

int N,A,B,C,X;
ll solve(){
    ll res = -1;
    vector<ll> Y(N); for(auto& in:Y) cin >> in;
    ll L = 0;
    int idx = 0;
    while(L <= 10000){
        if(X == Y[idx]) idx++;
        if(idx == N) return L;
        X = (A*X+B)%C;
        L++;
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    while(cin >> N >> A >> B >> C >> X,N){
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 3072