akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define regsiter register
#define CL fclose(stdin),fclose(stdout)
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
	long long G()
	{
		long long n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
}
char map[111][111];
struct edge
{
	int to;
	int res;
	int next;
}e[88888];
int pe=222;
void insert(int a,int to,int cap)
{
	e[pe]=(edge){to,cap,e[a].next};
	e[a].next=pe++;
}
void addedge(int a,int to,int cap)
{
	insert(a,to,cap);
	insert(to,a,0);
}
int s,t;
int d[3333];
int q[3333],hq,tq;
int vis[3333],pv;
int cur[3333];
bool bfs()
{
	for(q[hq=1]=t,tq=2,vis[t]=++pv,d[t]=0;hq!=tq;++hq)
		for(register int p=e[q[hq]].next;p;p=e[p].next)
			if(e[p^1].res&&vis[e[p].to]!=pv)
				vis[e[p].to]=pv,d[e[p].to]=d[q[hq]]+1,q[tq++]=e[p].to;
	return vis[s]==pv;
}
int dfs(int o,int min)
{
	if(o==t||min==0)return min;
	int f=0,tmp;
	for(register int p;cur[o];cur[o]=e[cur[o]].next)
	{
		p=cur[o];
		if(e[p].res&&d[e[p].to]==d[o]-1&&(tmp=dfs(e[p].to,dmin(min,e[p].res))))
		{
			f+=tmp;
			e[p].res-=tmp;
			e[p^1].res+=tmp;
			min-=tmp;
			if(min==0)return f;
		}
	}
	return f;
}
int dinic()
{
	int fl=0;
	while(bfs())
	{
		for(register int i=1;i<=t;++i)cur[i]=e[i].next;
		fl+=dfs(s,0x7fffffff);
	}
	return fl;
}
int main()
{
	int n=io::F(),m=io::F();
	for(register int i=1;i<=n;++i)gets(map[i]+1);
	s=n+m+1,t=n+m+2;
	int sx,sy,tx,ty;
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
		{
			if(map[i][j]=='o')addedge(i,j+n,1),addedge(j+n,i,1);
			if(map[i][j]=='S')sx=i,sy=j;
			if(map[i][j]=='T')tx=i,ty=j;
		}
	if(sx==tx)return puts("-1"),0;
	if(sy==ty)return puts("-1"),0;
	addedge(s,sx,100000);
	addedge(s,sy+n,100000);
	addedge(tx,t,100000);
	addedge(ty+n,t,100000);
	int tmp=dinic();
	if(tmp>=100000)puts("-1");
		else printf("%d\n",tmp);
	return 0;
}




Measured memory_bytes: 640
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]

ans = 0
for i in range(n-1):
  for j in range(i+1,n):
    ans += ((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)**0.5
print(ans*2/n)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int N = 0;
		int B = 0;
		int T = 0;
		Scanner sc = new Scanner(System.in);
		N = Integer.parseInt(sc.next());
		int i;
		int[] V = new int[N];
		int[] C = new int[N];
		for (i = 0; i < N; i++) {
			V[i] = Integer.parseInt(sc.next());
		}
		for (i = 0; i < N; i++) {
			C[i] = Integer.parseInt(sc.next());
		}
		int count = 0;
		int price = 0;
		for (i = 0; i < N; i++) {
			price = V[i] - C[i];
			if (price > 0) {
				count += price;
			}
		}
		System.out.println(count);

	}

}

Measured memory_bytes: 21588
main = do
    s <- getLine
    t <- getLine
    putStrLn$show$solve s t

solve :: String -> String -> Int
solve s t = minimum $ minList s t

minList :: String -> String -> [Int]
minList s t= getList 0 [] s t

getList :: Int -> [Int] -> String -> String -> [Int]
getList i l s t = if i < length s - length t + 1 then getList (i+1) (putMin i l s t) s t else l

putMin :: Int -> [Int] -> String -> String -> [Int]
putMin i l s t = l ++ [getMin i 0 l s t]

getMin :: Int -> Int -> [Int] -> String -> String -> Int
getMin i j l s t = if j < length t then if (s !! (i+j)) /= t !! j then 1 + getMin i (j+1) l s t else 0 + getMin i (j+1) l s t else 0

Measured memory_bytes: 5004
import java.util.Scanner;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long M = sc.nextLong();
        long[] A = new long[N];
        long Ans = 0;
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextLong();
        }
        for (int i = 1; i < N; i++) {
            A[i] += A[i - 1];
        }
        for (int i = 0; i < N; i++) {
            A[i] %= M;

        }
        Arrays.sort(A);
        long c = 1;
        for (int i = 0; i < N - 1; i++) {
            if (A[i] == A[i + 1]) {
                c++;
            } else {
                Ans += c * (c - 1) / 2;
                c = 1;
            }
        }
        Ans += c * (c - 1) / 2;
        for (int i = 0; i < N; i++) {
            if (A[i] == 0) {
                Ans++;
            }
        }
        System.out.println(Ans);
    }
}


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

int c_moon(long long n);

signed main()
{
    long long n;
    int ans ;
    
    cin >> n;
    ans = c_moon(n);
    
    cout << ans << endl;
    return(0);
}

int c_moon(long long n)
{
    int ans = 0, make[10000] , step = 0 , sum;
    long long tem;
    make[0] = 0;
    
    for(int i=1 ;i<10000 ;i++ ){
        make[i] = i + make[i-1];
    }
    
    tem = n;
    
    for(long long i=2 ;i<=1000000 && tem > 1;i++ ){
        if(tem%i == 0){
            sum = 0 , step = 0;
            while(tem%i == 0){
                tem = tem / i;
                sum++;
                
                if(sum >= make[step+1]){
                    step++;
                }
            }
            ans += step;
        }
    }
    
    if(tem > 1){
        ans++;
    }
    return(ans);
}

Measured memory_bytes: 3672
#include <stdio.h>

#define swap( x, y ) do { double tmp; tmp = x; x = y; y = tmp; } while ( 0 )

int rel_l_l( double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double *x, double *y ) {
	double a, b, c, d;
	int rel;

	if ( x1 < x0 ) {
		swap( x0, x1 );
		swap( y0, y1 );
	}
	if ( x3 < x2 ) {
		swap( x2, x3 );
		swap( y2, y3 );
	}

	if ( x0 != x1 ) {
		a = ( y0 - y1 ) / ( x0 - x1 );
		b = ( x0 * y1 - x1 * y0 ) / ( x0 - x1 );
	}
	if ( x2 != x3 ) {
		c = ( y2 - y3 ) / ( x2 - x3 );
		d = ( x2 * y3 - x3 * y2 ) / ( x2 - x3 );
	}

	rel = 1;
	if ( x0 == x1 ) {
		*x = x0;
		if ( x2 == x3 )
			if ( x0 == x2 ) {
				if ( y1 < y0 )
					swap( y0, y1 );
				if ( y3 < y2 )
					swap( y2, y3 );

				if ( y3 < y0 || y1 < y2 )
					rel = 3;
				else if ( y3 == y0 || y1 == y2 ) {
					*y = y3 == y0 ? y0 : y1;
					rel = 4;
				} else
					rel = 5;
			} else
				rel = 2;
		else {
			*y = c * *x + d;
			if ( *x < x2 || x3 < *x || *y < ( y0 < y1 ? y0 : y1 ) || ( y0 < y1 ? y1 : y0 ) < *y )
				rel = 0;
		}
	} else {
		if ( x2 == x3 ) {
			*x = x2;
			*y = a * *x + b;
			if ( *x < x0 || x1 < *x || *y < ( y2 < y3 ? y2 : y3 ) || ( y2 < y3 ? y3 : y2 ) < *y )
				rel = 0;
		} else {
			if ( a == c ) {
				if ( b == d )
					if ( x3 < x0 || x1 < x2 )
						rel = 3;
					else if ( x3 == x0 || x1 == x2 ) {
						*x = x3 == x0 ? x0 : x1;
						rel = 4;
					} else
						rel = 5;
				else
					rel = 2;
			} else {
				*x = ( -b + d ) / ( a - c );
				if ( *x < x0 || x1 < *x || *x < x2 || x3 < *x )
					rel = 0;
			}
			*y = a * *x + b;
		}
	}

	return rel;
}


int main( void ) {
	int q;

	scanf( "%d", &q );
	while ( q-- ) {
		int rel;
		double x0, y0, x1, y1, x2, y2, x3, y3, x, y;

		scanf( "%lf %lf %lf %lf %lf %lf %lf %lf", &x0, &y0, &x1, &y1, &x2, &y2, &x3, &y3 );

		rel = rel_l_l( x0, y0, x1, y1, x2, y2, x3, y3, &x, &y );

		printf( "%d\n", rel == 1 || rel == 4 || rel == 5 ? 1 : 0 );
	}

	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef vector<llong> V;

#define _ cin.tie(0);ios::sync_with_stdio(false);
llong n,k;
llong dp[100010];
llong h[100010];

int main(){ _;
  cin>>n>>k;
  REP(i,n){
    cin>>h[i];
    dp[i]=INF;
  }

  dp[0]=0;

  REP(i,n){
    FOR(kk,0,k+1){
      if (i+kk>=n) break;
      dp[i+kk] = min(dp[i+kk],dp[i]+abs(h[i]-h[i+kk]));
    }
  }
  cout<<dp[n-1]<<endl;

  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int N = getint();
	int D[100001] = {};
	rep(i, N) D[getint()]++;
	int S = 0;
	int kotae = 0;
	for (int i = 100000; i > 0; i--) {
		S += D[i];
		if (S == N / 2) kotae++;
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  int H,W;
  cin >> H >> W;
  
  string line="";
  for(int j=0;j<W+2;j++){
    line += '#';
  }
  
  for(int i=0;i<H+2;i++){
    if(i==0||i==H+1){
      cout << line << endl;
    }
    else{
      string tmp;
      cin >> tmp;
      cout << '#' << tmp << '#' << endl;
    }
  }
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define PI M_PI
#define ll long long
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define REP(i, n) for (int i=0; i<n; i++)
#define REPD(i, n) for (int i=n-1; i>=0; i--)
#define print(x) cout << x << endl;
#define debug(x) cout << #x << " = " << endl;

using namespace std;

void solve()
{
    int N, A, B;
    cin >> N >> A >> B;
    print(min({N*A, B}));
}

int main()
{
    solve();

    return 0;
}


Measured memory_bytes: 384
n=int(input())
x={}
for i in range(n):
    s=input()
    if s in x: x[s]+=1
    else :     x[s] =0
m=max(x[i] for i in x)
q=[]
for i in x:
    if x[i]==m: q.append(i)
print(*sorted(q),sep='\n')

Measured memory_bytes: 34012
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=998244353;
const long double eps=1e-60;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}

int main(){
    string s;cin>>s;
    ll n=s.size();
    vi sum(n);
    sum[0]=s[0]-'0';
    rep(i,n-1)sum[i+1]=sum[i]+s[i+1]-'0';
    ll r=sum[n-1],b=n*2-r;
    vvi dp(r+1,vi(b+1));
    dp[0][0]=1;
    rep(i,r+1)rep(j,b+1){
        ll k=min(i+j,n-1);
        if(sum[k]>i)dp[i+1][j]=(dp[i][j]+dp[i+1][j])%mod;
        if(2*(k+1)-sum[k]>j)dp[i][j+1]=(dp[i][j]+dp[i][j+1])%mod;
    }
    out(dp[r][b]);
}

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

int main() {
	int n,k;
	cin>>n>>k;
	int a[n],dp[n];
	fill(dp,dp+n,INT_MAX);
	for(int i=0;i<n;i++)
	cin>>a[i];
	dp[0]=0;
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=k;j++){
			if(i-j<0)
			break;
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
		}
	}
	cout<<dp[n-1];
	return 0;
}

Measured memory_bytes: 1024
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [h, w] <- getIntList
  let ans = if h == 1 || w == 1
            then 1
            else (h*w+1) `div` 2
  print ans

Measured memory_bytes: 380
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
ll gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<int>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
int main(){
  int n;
  cin >> n;
  int a[n];
  rep(i,n)cin >> a[i];
  int cnt=0;
  rep(i,n){
    rep(j,i){
      rep(o,j){
        if(a[i]+a[j]>a[o]&&a[i]+a[o]>a[j]&&a[j]+a[o]>a[i]&&a[i]!=a[j]&&a[j]!=a[o]&&a[i]!=a[o])cnt++;
      }
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3632
N = int(input())
L = list(map(int,input().split()))
L.sort()
cmax = L[-1] + L[-2]
csum = list(0 for _ in range(cmax+1))
for i in range(N): csum[L[i]] += 1
for i in range(1,cmax+1): csum[i] += csum[i-1]
ans = 0
for ib in range(N):
    b = L[ib]
    for ia in range(ib):
        a = L[ia]
        minL, maxL = abs(a-b), a+b
        ans += csum[maxL-1] - csum[minL]
        if minL < a < maxL: ans -= 1
        if minL < b < maxL: ans -= 1
print(ans//3)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using Graph = vector<vector<int>>;

const int INF = 1 << 30;
const ll INFL = 1LL << 60;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const int MOD = 1000000007;

int H, W;
Graph G;

// メモ再帰
int dp[1005][1005]; //---- dp[i][j]: 経路の数
bool isEmpty[1005][1005];

int main(){
    cin >> H >> W;
    for(int i=0; i < H; ++i){
        for(int j=0; j < W; ++j){
            char tmp;
            cin >> tmp;
            if( tmp=='#' ) isEmpty[i][j] = false;
            else isEmpty[i][j] = true;
        }
    }
    dp[0][0] = 1;
    for(int i=1; i < H; ++i){
        if( !isEmpty[i][0] ) dp[i][0] = 0;
        else dp[i][0] = dp[i-1][0];
    }
    for(int j=1; j < W; ++j){
        if( !isEmpty[0][j] ) dp[0][j] = 0;
        else dp[0][j] = dp[0][j-1];
    }
    for(int i=1; i < H; ++i){
        for(int j=1; j < W; ++j){
            if( !isEmpty[i][j] ) dp[i][j] = 0;
            else dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
        }
    }
    cout << dp[H-1][W-1];
}

Measured memory_bytes: 5120
#include <stdio.h>

int main(void)
{
    int N;
    scanf("%d", &N);
    int A[110];
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &A[i]);
    }

    // 承認するかどうか
    int isApproval = 1;

    for (int i = 0; i < N; ++i)
    {
        // 偶数かどうか
        if (A[i] % 2 == 0)
        {
            // 3 または 5 で割り切れるか => どちらでも割り切れないなら承認しない
            if (A[i] % 3 != 0 && A[i] % 5 != 0)
            {
                isApproval = 0;
            }
        }
    }

    if (isApproval)
    {
        printf("APPROVED\n");
    }
    else
    {
        printf("DENIED\n");
    }

    return 0;
}


Measured memory_bytes: 1632
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>

using namespace std;


int main(){
    int M1, D1, M2, D2;
    cin >> M1 >> D1;
    cin >> M2 >> D2;
    if(M1 != M2){
      cout << "1" << endl;
    }else{
      cout << "0" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const X = parseInt(arg[0].split(" ")[1]);
    const L = arg[1].split(" ").map(n=>parseInt(n));
    
    let answer = 1;
    let now = 0;
    
    for(let i=0; i<N; i++) {
        if(now + L[i] <= X) {
            answer++;
            now += L[i];
        } else {
            break;
        }
    }
    
    console.log(answer);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
# よくわからんが隣接リストのDFSで間に合うのでは

n, m = map(int, input().split())
gets = []  # とっておく
for _ in range(m):
    s, t = map(int, input().split())
    gets.append([s-1, t-1])
ans = 0
for i in range(m):
    graph = [[] for _ in range(n)]  # 隣接リスト
    for j in range(m):
        # 採用しない橋以外を採用する
        if i != j:
            s, t = gets[j]
            graph[s].append(t)
            graph[t].append(s)
    stack = [0]
    visited = [False for _ in range(n)]
    # 適当に0から始めて伸ばす
    visited[0] = True
    while len(stack):
        nex = stack.pop()
        for g in graph[nex]:
            if visited[g] == False:
                visited[g] = True
                stack.append(g)
    count = list(filter(lambda x: x == True, visited))
    ans += 1 if n-len(count) > 0 else 0

print(ans)


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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
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; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

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

int main(){

  string s;cin>>s;
  out(s.substr(0,s.size()-8));

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n[8], c[8];
int debug = 0;

void rotate(){
	int tmp=c[7];
	
	for(int i=7;i>=0;i--){
		c[i] = c[i-1];
	}
	c[0] = tmp;
}

int main(void){
	
	while(cin >> n[0] >> n[1] >> n[2] >> n[3] >> n[4] >> n[5] >> n[6] >> n[7]){
		int maxi=0;
		string maxistr="12121414";
		if(debug){
			for(int i=0;i<8;i++){
				cout << n[i];
			}
			cout << endl;
		}
		c[0] = 1; c[1] = 2; c[2] = 1; c[3] = 2;
		c[4] = 1; c[5] = 4; c[6] = 1; c[7] = 4;
		
		for(int i=0;i<8;i++){
			int tmp = 0;
			string tmpstring = "";
			for(int j=0;j<8;j++){
				if(c[j] > n[j]){
					tmp += n[j];
				}else{
					tmp += c[j];
				}
			}
			if(debug) cout << "tmp = " << tmp << endl;
			if(tmp < maxi){
				//do nothing
			}else{
				//make string
				for(int j=0;j<8;j++){
					tmpstring += c[j] + '0';
				}
				if(debug) cout << "tmp maxi = " << tmpstring << endl;
				if(tmp > maxi){
					maxi = tmp;
					maxistr = tmpstring;
				}else if(tmp == maxi){
					if(tmpstring < maxistr){
						maxistr = tmpstring;
					}
				}else{
					//bugged here
				}
			}
			rotate();
		}
		for(int i=0;i<7;i++){
			cout << maxistr[i] << " ";
		}
		cout << maxistr[7] << endl;
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
    using namespace std;
    #define PAIN___ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define ll long long int
    #define fi first
    #define se second
    #define pb push_back
    #define pii pair < ll, ll >
    #define mp make_pair
    #define vec vector < ll >
    #define vecp vector < pii  >
    #define forl(i,q1,n,q2) for(ll i=q1;i<q2;i++)
    #define null NULL
    #define mm 100005
   /* string with spaces   getline(cin,s);*/

int main(){
    PAIN___;
   ll n;
	cin>>n;
	ll a[n+1];
	forl(i,0,n,n)cin>>a[i+1];
	vec v;
	ll b[n+1];
	b[0]=0;
	forl(i,0,n,n)b[i+1]=0;
	for(ll i=n;i>0;i--){
		b[i]=a[i];
		for(ll j=i*2;j<=n;j+=i){
			b[i]=b[i]^b[j];
		}
	}
	forl(i,0,n,n)if(b[i+1])v.pb(i+1);
	cout<<v.size()<<endl;
	forl(i,0,n,v.size())
        cout<<v[i]<<" ";
}


Measured memory_bytes: 5108
#include<stdio.h>

main(){
  int key;
  int A[100];
  int i,j,a,l;

    scanf("%d",&a);

  for(i=0;i<a;i++){
    scanf("%d",&A[i]);
  }


  for(i=0;i<a;i++){
    key = A[i];
    j=i-1;
    
    while(j >= 0 && A[j] > key){
      A[j+1]=A[j];
      j--;
    }
    
    A[j+1]=key;
    
    
 for(l=0;l<a;l++){
   printf("%d",A[l]);
   if(l == a-1)break;
   printf(" ");
 }
   printf("\n");
   
  }
    return 0;
}

Measured memory_bytes: 604
while True :
    n = int(input())
    if n == 0 :
        break
    
    s = 1000 - n
    count = 0
    if s >= 500 :
        count += 1
        s = s - 500
    if s >= 100 :
        count += int(s / 100)
        s = int(s % 100)
    if s >= 50 :
        count += 1
        s = s - 50
    if s >= 10 :
        count += int(s / 10)
        s = int(s % 10)
    if s >= 5 :
        count += 1
        s = s - 5
    count += s
    print(count)


Measured memory_bytes: 5592
mod = 1000000007

N = int(input())

pos = []
neg = []
zer = []
inf = []
sol = 0

###除外すべき組み合わせの個数を数える
NG = []

for i in range(N):
    a,b = map(int,input().split())
    if a*b > 0:
        pos.append((abs(a),abs(b)))
    elif a*b < 0:
        neg.append((-abs(a),abs(b)))
    elif a == 0 and b != 0:
        inf.append((0,1))
    elif a != 0 and b == 0:
        zer.append((1,0))
    else:
        sol += 1

NG.append((len(inf),len(zer)))
free = len(pos)+len(neg)


# 以下しばらくneg,posに含まれるものに関する議論

pos.sort(key=lambda x:(x[1]/x[0]))
neg.sort(key=lambda x:(x[1]/x[0]))

x = 0
y = 0


while (x < len(pos) and y < len(neg)):
    if pos[x][0]*neg[y][0]+pos[x][1]*neg[y][1] == 0:
        s = 1
        t = 1
        while x+1 < len(pos) and pos[x+1][0]*neg[y][0]+pos[x+1][1]*neg[y][1] == 0:
            x += 1
            s += 1
        while y+1 < len(neg) and pos[x][0]*neg[y+1][0]+pos[x][1]*neg[y+1][1] == 0:
            y += 1
            t += 1
        NG.append((s,t))
        x += 1
        y += 1
        free -= (s+t)
        continue


    if x >= len(pos)-1 and y >= len(neg)-1:
        break

    elif y+1 < len(neg) and pos[x][0]*neg[y][0]+pos[x][1]*neg[y][1] > 0:
        y += 1
    elif x+1 < len(pos) and pos[x][0]*neg[y][0]+pos[x][1]*neg[y][1] < 0:
        x += 1
    elif x >= len(pos)-1:
        y += 1
    elif y >= len(neg)-1:
        x += 1

ans = pow(2,free,mod)

for s,t in NG:
    # s個のうち1個以上入れる or t個のうち1個以上入れる or どちらも1つも入れない
    ans *= pow(2,s,mod)-1 +pow(2,t,mod)-1 +1
    ans %= mod

#print('free',free)
#print('NG',NG)

# 1つも選ばないものの除外、solは単体で選べばOK
print((ans+sol-1)%mod)



Measured memory_bytes: 100620
#include<stdio.h>
main(){
  int a,b,c,d,A[100];
  scanf("%d",&a);
  for(b=0;b<a;b++){
    scanf("%d",&A[b]);
  }
  for(b=0;b<a;b++){
    for(c=a-1;c>b;c--){
      d=A[c];
      A[c]=A[c-1];
      A[c-1]=d;
    }
  }
  for(b=0;b<a;b++){
    if(b==a-1){
      printf("%d\n",A[b]);
    }
    else{
      printf("%d ",A[b]);
    }
  }
  return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<string.h>
#include<bitset>
#include<cstdio>
#include<set>
using namespace std;

int main(){
	int n, k, ruiseki[11][2001] = {}, dp[11][2001] ={};
	int a, b;
	vector<int> books[11];
	cin >> n >> k;
	for(int i = 0; i < n;i++){
		scanf("%d%d", &a, &b);
		books[b].push_back(-a);
	}
	for(int i = 1; i < 11; i++){
		sort(books[i].begin(), books[i].end());
		for(int j = 0; j < books[i].size(); j++){
			ruiseki[i][j + 1] = -books[i][j] + ruiseki[i][j] + j * 2;
		}
	}

	for(int i = 1; i < 11; i++){
		for(int j = 0; j <= k; j++){
			for(int l = 0; l + j <= k; l++){
				dp[i][l + j] = max(max(dp[i][l + j], dp[i - 1][l + j]), max(dp[i - 1][j] + ruiseki[i][l], dp[i - 1][l] + ruiseki[i][j]));
			}
		}
	}
	cout << dp[10][k] << endl;
}

Measured memory_bytes: 1460
alp_tot = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

alp_to_num = {}
num_to_alp = {}
for num, alp in enumerate(alp_tot):
    alp_to_num[alp] = num
    num_to_alp[num] = alp

n = int(input())
row = input()

ans = ''
for alp in row:
    num = (alp_to_num[alp] + n) % (len(alp_tot))
    ans += num_to_alp[num]

print(ans)

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

int main() {
   int N;
   cin >> N;
   vector<int> S={1,2,3,4,5,6,7,8,9,10,11,12,13};
   vector<int> H={1,2,3,4,5,6,7,8,9,10,11,12,13};
   vector<int> C={1,2,3,4,5,6,7,8,9,10,11,12,13};
   vector<int> D={1,2,3,4,5,6,7,8,9,10,11,12,13};
   for(int i=0; i<N; i++){
       int x=0;
       char z='A';
       cin >> z >> x;
       if(z=='S')  S.at(x-1)=0;
       if(z=='H')  H.at(x-1)=0;
       if(z=='C')  C.at(x-1)=0;
       if(z=='D')  D.at(x-1)=0;
   }
   for(int x : S){
       if(x>0) cout << "S " << x << endl; 
   }
   
   for(int x : H){
       if(x>0) cout << "H " << x << endl; 
   }
   
   for(int x : C){
       if(x>0) cout << "C " << x << endl; 
   }
   
   for(int x : D){
       if(x>0) cout << "D " << x << endl; 
   }
    return 0;
}




Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
#define ll                      long long
#define pb                      push_back
#define rep(i,a,b,c)            for(ll i=(a);i<=(b);i+=(c))
#define repb(i,a,b,c)           for(ll i=(a);i>=(b);i-=(c))
#define MOD                     1000000007
#define inf                     3e18
#define ld                      long double
#define mp                      make_pair
#define vpll                    vector<pair<ll,ll> >
#define vll                     vector<ll>
#define vld                     vector<ld>
#define vvll                    vector<vector<ll>>
#define vvld                    vector<vector<ld>>
#define pll                     pair<ll,ll>
#define vvpll                   vector<vector<pair<ll,ll>>>
#define pqll                    priority_queue<ll>
#define mll                     map<ll,ll>
#define mlc                     map<ll,char>
#define um                      unordered_map
#define umll                    um<ll,ll>
#define umlc                    um<ll,char>
#define all(x)                  x.begin(),x.end()
#define fi                      first
#define se                      second
#define ln                      cout<<"\n";
#define endl                    "\n"
#define test                    ll T;cin>>T;while(T--)
#define isvowel(a)              (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define show(w,size)            for(ll i=0;i<size;i++) cout<<w[i]<<" ";
#define prll(a)                 cout<<a<<"\n";
#define mset(dp,no)             memset(dp,no,sizeof(dp))
#define input(a,n)              rep(i,0,n-1,1) cin>>a[i];
#define countbit                __builtin_popcount                                           //Number of setbits in decimal notation
#define lb(v,val)               lower_bound(all(v),val)-v.begin()
#define ub(v,val)               upper_bound(all(v),val)-v.begin()
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
ll pows(ll b,ll e){if(e==0)return 1;else if(e%2==0){ll a=pow(b,e/2);return a*a;}else {ll a=pow(b,e/2);return b*a*a;}}
ll powm(ll x,ll y,ll m){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
ll modInverse(ll a, ll m=MOD){if(m == 1)return 0;ll m0=m,y=0,x=1;while(a>1){ll q=a/m,t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0) x+=m0;return x;}
int main()
{
fastIO
ll n,m,i,j,k,x,y,z,e,f,p,q,g,l,r,w,h,count1=0,prod=1,a,b,c,d,index,x1,x2,diff,ans=0,sum=0,sum1=0,sum2=0,flag=0,flag1=0,flag2=0;
string s,s1,s2;
cin>>n;
if(n%2==1)
{
  cout<<"0";
  return 0;
}
else
{
  p=2;
  n/=2;
  ll two=0;
  while(n>=p)
  {
    two+=n/p;
    p*=2;
  }
  ll five=0;
  p=5;
  while(n>=p)
  {
    five+=n/p;
    p*=5;
  }
  two++;
  cout<<min(two,five);
}
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int N, C[510], S[510], F[510];
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		cin >> C[i] >> S[i] >> F[i];
	}
	int ans = 0;
	for (int i = 0; i < N - 1; i++) {
		ans = 0;
		for (int j = i; j < N - 1; j++) {
			if (ans < S[j]) ans = S[j];
			if (ans % F[j] != 0) ans += F[j] - ans % F[j];
			ans += C[j];
		}
		cout << ans << endl;
	}
	cout << 0 << endl;
}

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


int N, A[100001];

int main(){
    cin >> N;
    long long ans = 0;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
    }
    for(int i = 1; i <= N; i++){
        ans += A[i] / 2;
        A[i] %= 2;
        if(i < N && A[i] == 1 && A[i+1] > 0){
            ans++;
            A[i]--;
            A[i+1]--;
        }
    }
    cout << ans << endl;
}

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

#define check(val) std::cout << "\033[31m" << #val << ": " << val << "\033[m" << std::endl
#define check_v(vec) \
  std::cout << "\033[31m" << #vec << ": [ ";\
  for(auto it=vec.begin(); it!=vec.end(); it++){cout << *it << " ";}\
  cout << "]"<< "\033[m" << endl;

int main() {
  vector<int> a(9);
  vector<int> b(9);
  rep(i,9) cin >> a[i];
  int n;
  cin >> n;
  // check_v(a);
  // check(n);
  rep(i,n){
    int tmp;
    cin >> tmp;
    rep(j,9) {
      if(a[j] == tmp) {
        b[j] = 1;
      }
    }
  }
  // check_v(b);
  if(b[0] == 1 && b[1] ==1 && b[2] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  if(b[3] == 1 && b[4] ==1 && b[5] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  if(b[6] == 1 && b[7] ==1 && b[8] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  if(b[0] == 1 && b[3] ==1 && b[6] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  if(b[1] == 1 && b[4] ==1 && b[7] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  if(b[5] == 1 && b[2] ==1 && b[8] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  if(b[0] == 1 && b[4] ==1 && b[8] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  if(b[6] == 1 && b[4] ==1 && b[2] == 1) {
    cout << "Yes" << endl;
      return 0;
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn._
import scala.math._

/**
 * ABC106B
 */
object Main extends App {

  val n = readInt

  def fcnt(num: Int) = {
    (1 to num).filter(_ % 2 == 1).count(v => num % v == 0)
  }

  val ans = (2 to n).count(fcnt(_) == 8)

  println(ans)
}


Measured memory_bytes: 25536
#include <stdio.h>

int main()
{
	char c1, c2, pos;

	pos = 'A';

	while(scanf("%c,%c", &c1, &c2) != EOF){
		if(c1 == pos) pos = c2;
		else if(c2 == pos) pos = c1;
	}

	printf("%c\n", pos);

	return 0;
}

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

int n;
int h[100010];
int memo[100010];

int dp(int pos) {
    if (pos > n - 1) return 1 << 30;
    if (pos == n - 1) return 0;
    if (memo[pos] != -1) return memo[pos];
    int x = abs(h[pos + 1] - h[pos]) + dp(pos + 1);
    int y = abs(h[pos + 2] - h[pos]) + dp(pos + 2);
    return memo[pos] = min(x,y);
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    memset(memo, -1, sizeof(memo));
    int ans = dp(0);
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 4096
#include <iostream>

using namespace std;

int main(){
    double W, H, x, y;
    cin >> W >> H >> x >> y;

    cout << W*H/2 << " ";
    if(x == W/2 && y == H/2){
        cout << "1" << endl;
    }else{
        cout << "0" << endl;
    }


    return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))

start=1
list=[1]
kenti=[0 for i in range(n)]
kenti[0]=1

zan=-1

for i in range(k):
  start-=1
  next=a[start]
  start=next

  if kenti[start-1]!=0:
    zan=k-(i+1)
    inx=list.index(start)
    list=list[inx:]
    break
  else:
    list.append(start)
    kenti[start-1]+=1

if zan==-1:
  print(list[-1])
  exit()
elif zan==0:
  print(list[0])
  exit()

#zan-=1
#print(list,zan)
zan%=len(list)
#print(zan)
'''
if zan==0:
  print(list[-1])
else:
  print(list[zan])
'''
print(list[zan])

Measured memory_bytes: 32380
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	while(n)
	{
		int k=n%10;
		n/=10;
		if(k==9)
		{
			cout<<"Yes"<<endl;
			return 0;	
		} 
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
from copy import deepcopy
s = ['_']
s.extend(list(input()))
t = ['.']
t.extend(list(input()))
N = len(s)
M = len(t)
DP = [[0]*(M+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if s[i-1] == t[j-1]:
            DP[i][j] = DP[i-1][j-1]+1
        else:
            DP[i][j] = max(DP[i-1][j],DP[i][j-1])

i = N
j = M
ans = []
while i != 0 and j != 0:
    if DP[i-1][j] < DP[i][j] and DP[i][j-1] < DP[i][j]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif DP[i-1][j] == DP[i][j]:
        i -= 1
    elif DP[i][j-1] == DP[i][j]:
        j -= 1

print(*reversed(ans),sep="")

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

using namespace std;

int c[100010];

int main() {
	ios::sync_with_stdio(false);
	int n, x;
	cin >> n;
	int mi = n + 2, mx = -1;
	for(int i = 1; i <= n; i++) {
		cin >> x;
		c[x]++;
		mi = min(mi, x);
		mx = max(mx, x);
	}
	if(mx - mi > 1) puts("No");
	else if(mx == mi) {
		if(mi == n - 1 || (mi << 1) <= n) puts("Yes");
		else puts("No");
	} else {
		int c1 = c[mi], c2 = c[mx];
		if(c1 > mi) puts("No");
		else if(n - c1 >= (mx - c1) * 2) puts("Yes");
		else puts("No");
	}
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
double a[4][4];
int main(){
    for(int i = 1;i <= 3;i++){
        for(int j = 1;j <= 3;j++) cin >> a[i][j];
    }
    if(a[1][2] + a[2][3] + a[3][1] + a[1][3] + a[2][1] + a[3][2] == (a[1][1] + a[2][2] + a[3][3]) * 2) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dpL[2020][2020],dpR[2020][2020],dpU[2020][2020],dpD[2020][2020];
int h,w;
string st[2020];
int main()
{
	cin>>h>>w;
	for(int i=0;i<h;i++)
		cin>>st[i];
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(st[i][j]=='#')
				continue;
			dpL[i][j]=(j?dpL[i][j-1]:0)+1;
			dpU[i][j]=(i?dpU[i-1][j]:0)+1;
		}
	}
	for(int i=h-1;i>=0;i--)
	{
		for(int j=w-1;j>=0;j--)
		{
			if(st[i][j]=='#')
				continue;
			dpR[i][j]=(j+1<w?dpR[i][j+1]:0)+1;
			dpD[i][j]=(i+1<h?dpD[i+1][j]:0)+1;
		}
	}
	int ans=0;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(st[i][j]=='.')
				ans=max(ans,dpL[i][j]+dpR[i][j]+dpU[i][j]+dpD[i][j]-3);
		}
	}
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 67968
from collections import Counter
N = int(input())
s_counter = Counter([input() for _ in range(N)])
M = int(input())
t_counter = Counter([input() for _ in range(M)])
d = {}
for key, value in s_counter.items():
  d[key] = [value]
for key, value in t_counter.items():
  if key not in d:
    d[key] = [-value]
  else:
    d[key].append(-value)
result = 0
for value in d.values():
  if sum(value) > result:
    result = sum(value)
print(result)
    


Measured memory_bytes: 3316
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int DMAX=100000+5;
const int MOD=1000000000+7;
template<class T> inline void read(T &x){
	x=0;
	T f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch<='9' && ch>='0'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	x*=f;
}
ll n;
int main(){
	read(n);
	ll p=n/500;
	n%=500;
	ll q=n/5;
	cout<<p*1000+q*5<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s=sc.next();
		int x =sc.nextInt();
		int y =sc.nextInt();
		ArrayList<Integer> xlist=new ArrayList<>();
		ArrayList<Integer> ylist=new ArrayList<>();
		int count=0;
		boolean isX=true;
		for(int i=0; i<s.length(); i++){
			if(s.charAt(i)=='T'){
				if(isX){
					xlist.add(count);
				}else{
					ylist.add(count);
				}
				isX=!isX;
				count=0;
			}else{
				count++;
			}
		}
		if(isX){
			xlist.add(count);
		}else{
			ylist.add(count);
		}
		int sumx=0;
		boolean[][] dpx=new boolean[xlist.size()][16000];
		boolean[][] dpy=new boolean[ylist.size()+1][16001];
		int nx=0;
		int ny=1;
		for(int i:xlist){
			if(nx==0){
				sumx+=i;
				dpx[nx][sumx+7999]=true;
				nx++;
				continue;
			}
			for(int j=-sumx; j<=sumx; j++){
				if(dpx[nx-1][j+7999]){
					dpx[nx][j+7999+i]=true;
					dpx[nx][j+7999-i]=true;
				}
			}
			nx++;
			sumx+=i;
		}
		int sumy=0;
		dpy[0][8000]=true;
		for(int i:ylist){
			for(int j=-sumy; j<=sumy; j++){
				if(dpy[ny-1][j+8000]){
					dpy[ny][j+8000+i]=true;
					dpy[ny][j+8000-i]=true;
				}
			}
			ny++;
			sumy+=i;
		}
		if(x==-8000){
			System.out.println("No");
			return;
		}
		if(dpx[xlist.size()-1][7999+x] && dpy[ylist.size()][8000+y]){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 164052
#include <bits/stdc++.h>
 
using namespace std;
 
bool check(int n)
{
    return (0 <= n && n < 8);
}
 
void init(map<string, int> &count)
{
    const int d[4] = {1, -1, 4, -4};
    queue<string> Q;
    string t = "01234567";
    Q.push(t);
 
    while (!Q.empty()) {
	string now = Q.front(); Q.pop();
	int zero = now.find('0');
	int dist = count[now];    
 
	for (int i = 0; i < 4; i++) {
	    int next = zero + d[i];
   
	    if (!check(next) || (zero == 3 && d[i] == 1)
	       || (zero == 4 && d[i] == -1)) continue;
 
	    swap(now[zero], now[next]);
	    //not visit
	    if (!count[now]) { 
		Q.push(now);
		if (now != t) {
                    count[now] = dist + 1;
                }
	    }
	    swap(now[zero], now[next]);
	}
    }
}
 
int main()
{
    char in;
    string puzzle;
    map<string, int> count;
 
    init(count);
    while (cin >> in) {
	puzzle = in;
	for (int i = 0; i < 7; i++) {
	    cin >> in;
	    puzzle += in;
	}
	cout << count[puzzle] << endl;
    }
    return 0;
}

Measured memory_bytes: 5280
#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define fl long double
#define pb push_back
#define mk make_pair
#define endl "\n"
#define ff first
#define ss second
#define mt make_tuple
#define np next_permutation
#define pi 3.141592653589793238
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
#define vll vector<ll>
#define vp vector<pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define revpq priority_queue <int, vector<int>, greater<int>>
const ll mod=1000000007;
const ll INF=10000000000;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod%mod;a=a*a%mod;}return res;}

int main()
{
    fastio
    ll i,j,k,n,m;
    cin>>n>>m>>k;
    ll a[n],b[m];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=0;i<m;i++)
    {
        cin>>b[i];
    }
    vll sa(n);
    sa[0]=a[0];
    for(i=1;i<n;i++)
    {
        sa[i]=sa[i-1]+a[i];
    }
    vll sb(m);
    sb[0]=b[0];
    for(i=1;i<m;i++)
    {
        sb[i]=sb[i-1]+b[i];
    }
    ll ans=0;
    i=0;
    auto it1=lower_bound(sb.begin(),sb.end(),k+1);
    it1--;
    ll va=it1-sb.begin()+1;
    ans=max(ans,va);
    while(i<n)
    {
        ll tp=0;
        if(sa[i]<=k)
        {
            tp=i+1;
        }
        else
        {
            break;
        }
        auto it=lower_bound(sb.begin(),sb.end(),k-sa[i]+1);
        it--;
        ll lef=it-sb.begin()+1;
        tp=tp+max(lef,0LL);
        ans=max(ans,tp);
        i++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 9468
#include <stdio.h>
#include <string.h>

int main(void)
{
	char str[2000];
	char ans[2000];
	int x, y, len;
	
	scanf("%s", str);
	len = strlen(str);
	
	for (x = 0; x < len; x++) {
		if (str[x] == 'A') {
			ans[x] = 'X';
		}
		else if (str[x] == 'B') {
			ans[x] = 'Y';
		}
		else if (str[x] == 'C') {
			ans[x] = 'Z';
		}
		else {
			ans[x] = (str[x] - 0x03);
		}
	}
	ans[x] = '\0';
	
	printf("%s\n", ans);
	
	return (0);
}

Measured memory_bytes: 524
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,k = m()

a = l()

po = [-1 for i in range(n)]

po[0] = 0
now = 0
for i in range(1,n):
    aaa = a[now]-1
    if po[aaa] == -1:
        po[aaa] = po[now]+1
        now = aaa
    else:
        break

un = po[aaa]
if k <= un:
    for i in range(n):
        if k == po[i]:
            print(i+1)
else:
    k -= un
    mod = po[now]+1 - po[aaa]
    ap = k % mod
    for i in range(n):
        if un + ap == po[i]:
            print(i+1)




Measured memory_bytes: 96092
using System.Collections.Generic;
using System;

public class Po
{
    public int x { get; set; }
    public int y { get; set; }
}

public class Hello
{
    public static void Main()
    {
        var dx = new int[] { 0, 1, 0, -1 };
        var dy = new int[] { 1, 0, -1, 0 };
        var d = new Dictionary<string, int> { { "N", 0 }, { "E", 1 }, { "S", 2 }, { "W", 3 } };
        while (true)
        {
            var map = new int[21, 21];
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            for (int i = 0; i < n; i++)
            {
                string[] line = Console.ReadLine().Trim().Split(' ');
                map[int.Parse(line[0]), int.Parse(line[1])] = 1;
            }
            var gcount = 0;
            var p = new Po { x = 10, y = 10 };
            if (map[10,10] == 1) { gcount = 1; map[10,10] = 0; }
            var m = int.Parse(Console.ReadLine().Trim());
            for (int i = 0; i < m; i++)
            {
                string[] line2 = Console.ReadLine().Trim().Split(' ');
                gcount += getGem(map, d, dx, dy, line2[0], int.Parse(line2[1]), p);
            }
            Console.WriteLine(gcount == n ? "Yes" : "No");
        }
    }
    public static int getGem(int[,] map, Dictionary<string, int> d, int[] dx, int[] dy, string dir, int L, Po p)
    {
        var count = 0;
        for (int i = 0; i < L; i++)
        {
            p.x += dx[d[dir]];
            p.y += dy[d[dir]];
            if (map[p.x,p.y] == 1) { count++; map[p.x,p.y] = 0; }
        }
        return count;
    }
}

Measured memory_bytes: 9248
#include <bits/stdc++.h>
#define MAX_N 200000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-48);
}
int n, l, a[MAX_N+5], b[MAX_N+5];
lnt mx, sl[MAX_N+5], sr[MAX_N+5];
int main() {
	read(l), read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i <= n; i++) b[i] = l-a[n-i+1];
	for (int i = 1; i <= n; i++) sl[i] = sl[i-1]+a[i];
	for (int i = 1; i <= n; i++) sr[i] = sr[i-1]+b[i];
	for (int i = 0, c = n>>1; i < n; c = (n-++i)>>1)
		if ((c<<1) == n-i)
			mx = max(mx, ((sl[i+c]-sl[i])<<1)+(sr[c]<<1)+(a[i]<<1)-a[i+c]), 
			mx = max(mx, ((sr[i+c]-sr[i])<<1)+(sl[c]<<1)+(b[i]<<1)-b[i+c]);
		else
			mx = max(mx, ((sl[i+c]-sl[i])<<1)+(sr[c]<<1)+(a[i]<<1)+b[c+1]), 
			mx = max(mx, ((sr[i+c]-sr[i])<<1)+(sl[c]<<1)+(b[i]<<1)+a[c+1]);
	return printf("%lld\n", mx), 0;
}


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

int main() {
    int d = 0 , t = 0 , s = 0;
    cin >> d >> t >> s;
    if(s>= (double)d/t){
		cout << "Yes";
	}else{
		cout << "No";
	}
	return 0;
}


Measured memory_bytes: 3576
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define ret return puts("-1"),0;
#define mod 1000000007
#define N 500055
#define int ll
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}
int ans,n,m,pd,p,a[N],b[N];
signed main(){
	n=read();
	F(i,1,n) a[i]=read(),b[i]=read();
	p=inf;
	F(i,1,n){
		pd|=a[i]!=b[i];
		ans+=a[i];
		if (a[i]>b[i]) p=min(p,b[i]);
	}
	if (!pd) puts("0");
	else wrn(ans-p);
	return 0;
}

Measured memory_bytes: 2432