stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



using VS = vector<string>;    using LL = long long;

using VI = vector<int>;       using VVI = vector<VI>;

using PII = pair<int, int>;   using PLL = pair<LL, LL>;

using VL = vector<LL>;        using VVL = vector<VL>;



#define ALL(a)  begin((a)),end((a))

#define RALL(a) (a).rbegin(), (a).rend()

#define PB push_back

#define EB emplace_back

#define MP make_pair

#define SZ(a) int((a).size())

#define SORT(c) sort(ALL((c)))

#define RSORT(c) sort(RALL((c)))

#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)

#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)

#define debug(x) cerr << #x << ": " << x << endl

const int INF = 1e9;                          const LL LINF = 1e16;

const LL MOD = 1000000007;                    const double PI = acos(-1.0);

int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };



/* -----  2018/02/23  Problem: 068_arc_b / Link: https://arc068.contest.atcoder.jp/tasks/arc068_b?lang=en  ----- */

/* ------問題------



すぬけくんはカードゲームで遊ぶことにしました。 N 枚からなるカードの山があり、上から i 枚目のカードには整数 Ai が書かれています。

すぬけくんはこのカードの山に対し 0 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、N は奇数であり、少なくとも 1 枚のカードを残すことが可能であることが保証されます。

操作：カードの山から任意の 3 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード 1 枚と最小であるようなカード 1 枚の合計 2 枚を選んで食べる。その後残った 1 枚をカードの山に戻す。



-----問題ここまで----- */

/* -----解説等-----



数字をまとめて個数で考える。

3個以上のものは同じものだけを選択することで全部1か2になる。

2についてこれらは全て選択し他の2あるいは1も選択する。

2が偶数個あるときは数自体を減らさずに個数のみを減らせる。

奇数個のときは最後の1つだけが相手が見つからず誰かを消すことになる。

これを書けば良い。



----解説ここまで---- */



LL N;



LL ans = 0LL;



int main() {

	cin.tie(0);

	ios_base::sync_with_stdio(false);



	cin >> N;

	VI a(N);

	VI cnt(100005);

	FOR(i, 0, N) {

		cin >> a[i];

		cnt[a[i]]++;

	}

	VI pq;

	FOR(i, 0, 100005) {

		if (cnt[i])pq.push_back(cnt[i]);



	}

	int even = 0;

	FOR(i, 0, SZ(pq)) {

		if (pq[i] % 2 == 0)even++;

	}

	ans = SZ(pq);

	if (even % 2 == 1)ans--;

	cout << ans << "\n";



	return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

const int M = 1e5+5;



int arr[M] = {0};



int main(){

	int n,i,j;

	int num1 = 0;

	int num2 = 0;

	int ans = 0;

	scanf("%d",&n);

	for(i = 0; i < n; i++){

		scanf("%d",&j);

		if(arr[j] == 0){

			arr[j] = 1;

			num1++;

		}

		else{

			num2++;

		}

	}

	if(num2 % 2 == 0) ans = num1;

	else ans = num1 -1;

	printf("%d",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define     SZ  50500

#define     LIM 2500005

#define     pii pair<int, int>

#define     pb  push_back

#define     ff  first

#define     ss  second





int main()

{

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int i, j, k;

    int n; cin>>n;

    int x;

    set<int> st;

    for (i = 0; i < n; i++)

    {

        cin>>x;

        st.insert(x);

    }

    int sz = st.size();



    if (sz % 2 == 0) cout<<(sz-1)<<"\n";

    else cout<<sz<<"\n";

    return 0;

}




// Optimized solution to the same problem (faster):
#include<stdio.h>

const int M = 1e5+5;



int arr[M] = {0};



int main(){

	int n,i,j;

	int num1 = 0;

	int num2 = 0;

	int ans = 0;

	scanf("%d",&n);

	for(i = 0; i < n; i++){

		scanf("%d",&j);

		if(arr[j] == 0){

			arr[j] = 1;

			num1++;

		}

		else{

			num2++;

		}

	}

	if(num2 % 2 == 0) ans = num1;

	else ans = num1 -1;

	printf("%d",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/* ===================================*/

/* Author :   MD FAHAD                */

/* Email  :   fahad.mohad99@gmail.com */

/* Institute: HSTU                    */

/* ===================================*/



#include <cstdio>

#include <iostream>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <cctype>

#include <algorithm>

#include <string>

#include <sstream>

#include <vector>

#include <queue>

#include <stack>

#include <list>

#include <map>

#include <set>

using  namespace  std;







#define PI              acos(-1.0)

#define lcm(a,b)        (a * (b / __gcd(a,b)))



#define READ_IN freopen("Input.txt","r",stdin)

#define READ_OUT freopen("Output.txt","w",stdout)



typedef long long int           ll;

typedef unsigned long long int  llu;



int main(void)

{

    int N; cin >> N;



    set<int> a;



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



        int x; cin >> x;



        a.insert(x);

    }



    int k = a.size();





    if(k%2==0)

    cout << k-1 << "\n";

    else

        cout << k << "\n";





    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

const int M = 1e5+5;



int arr[M] = {0};



int main(){

	int n,i,j;

	int num1 = 0;

	int num2 = 0;

	int ans = 0;

	scanf("%d",&n);

	for(i = 0; i < n; i++){

		scanf("%d",&j);

		if(arr[j] == 0){

			arr[j] = 1;

			num1++;

		}

		else{

			num2++;

		}

	}

	if(num2 % 2 == 0) ans = num1;

	else ans = num1 -1;

	printf("%d",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<map>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<string>

using namespace std;

int a[100005],x,ans;

int main(){

	int n;

	cin >> n;

	for(int i = 1;i <= n;i++){

		cin >> x;

		a[x]++;

	}

	for(int i = 1;i <= 100003;i++){

		if(a[i]>1)ans+=(a[i]-1);

		}

	if(ans%2)ans+=1;

	cout << n - ans <<endl;

	return 0;

	}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define int long long

using namespace std;

 



int mm[100004];

signed main()

{

 

ios_base::sync_with_stdio(false);

cin.tie(NULL);  

cout.tie(0);   

 

 

#ifndef ONLINE_JUDGE

    if(fopen("INPUT.txt","r"))

    {

    freopen ("INPUT.txt" , "r" , stdin);

    freopen ("OUTPUT.txt" , "w" , stdout);

    }

#endif    



    int n;

    cin>>n;

    int a[n];

    int cnt=0;

    for(int i=0;i<n;i++)

    {

        cin>>a[i];

        mm[a[i]]++;

        if(mm[a[i]]==1)

        {

            cnt++;

        }

    }



    if((n-cnt)%2==0)

    {           

        cout<<cnt;

    }

    else

    {

        cout<<cnt-1;

    }

    

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int M=1e5+10;

int a[M],cnt;

int main()

{

    int n;scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        int x;scanf("%d",&x);

        a[x]++;

    }

    int cost=0;

    for(int i=1;i<M;i++)if(a[i]>=2)

    {

        if(a[i]%2==0)

        {

            cost+=a[i]-2;

            cnt++;

        }

        else cost+=a[i]-1;



    }

    cost+=(cnt/2)*2;

    if(cnt%2==1)cost+=2;

    printf("%d\n",n-cost);

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define int long long

using namespace std;

 



int mm[100004];

signed main()

{

 

ios_base::sync_with_stdio(false);

cin.tie(NULL);  

cout.tie(0);   

 

 

#ifndef ONLINE_JUDGE

    if(fopen("INPUT.txt","r"))

    {

    freopen ("INPUT.txt" , "r" , stdin);

    freopen ("OUTPUT.txt" , "w" , stdout);

    }

#endif    



    int n;

    cin>>n;

    int a[n];

    int cnt=0;

    for(int i=0;i<n;i++)

    {

        cin>>a[i];

        mm[a[i]]++;

        if(mm[a[i]]==1)

        {

            cnt++;

        }

    }



    if((n-cnt)%2==0)

    {           

        cout<<cnt;

    }

    else

    {

        cout<<cnt-1;

    }

    

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<cmath>

#include<iomanip>

#include<map>

using namespace std;

int main() {

  int n,a[100000]={},cnt=0;

  cin >> n;

  map<int,int> m;

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

    cin >> a[i];

    m[a[i]]++;

  }

  for(auto p:m) {

    if(p.second>1) {

      cnt+=p.second-1;

    }

  }

  if(cnt%2==0) {

    cout << n-cnt << endl;

  }

  else {

    cout << n-cnt-1 << endl;

  }

}

// Optimized solution to the same problem (faster):
//   _/                _/                 _/_/_/   _/

//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/

// _/     _/    _/   _/     _/    _/  _/_/_/     _/

//_/     _/    _/   _/     _/    _/  _/    _/   _/

// _/_/   _/_/       _/_/   _/_/      _/_/     _/

#include<iostream>

#include<algorithm>

#include<cmath>

#include<iomanip>

#include<set>

#include<map>

#include<queue>

#include<vector>

using namespace std;

typedef long long ll;

const int MOD=1e9+7;

const int inf=1e9;

const ll INF=1e18;

const double pi=3.1415926535897932384626433832;

int main() {

  cin.tie(0),cout.tie(0);

  ios::sync_with_stdio(false);

  // 初めに思ったこと：重複していない値は全て残したい

  ll n,a,cnt=0;

  cin >> n;

  map<int,int> m;

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

    cin >> a;

    m[a]++;

  }

  // 重複していたら1つを残して食べる

  for(auto p:m) {

    if(p.second>1) {

      cnt+=p.second-1;

    }

  }

  // 1回の操作で2つずつ減っていくので食べた数=cntは2の倍数である必要がある

  if(cnt%2==0) {

    cout << n-cnt << endl;

  }

  // cntが奇数のとき、1つしか残っていない数を余計に1つだけ食べている

  else {

    cout << n-cnt-1 << endl;

  }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



int main() {

    int N;

    cin >> N;



    static int counter[100000];

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

        int a;

        cin >> a;



        counter[a - 1]++;

    }



    // 基本的には重複しているカードが2枚ずつ消えていく

    int even = 0,

        odd  = 0;

    for (int a = 0; a < 100000; a++) {

        if (counter[a] == 0) continue;

        else if (counter[a] % 2) odd++;

        else even++;

    }

    cout << even + odd - (even % 2) << endl;



    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define repeat(i, x) for (int64_t i = 0; (i) < (int64_t)(x); (i)++)



int main() {

    cin.tie(nullptr);

    ios::sync_with_stdio(false);



    int n;

    cin >> n;



    map<int, int> counter;

    repeat (i, n) {

        int a;

        cin >> a;

        counter[a]++;

    }



    int numEven = 0;

    for (auto& mp : counter) {

        if (mp.second % 2 == 0) numEven++;

    }



    cout << counter.size() - numEven % 2 << endl;



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#import<iostream>

main(){int n,c,i,a[1<<17]={};for(std::cin>>n;n--;){std::cin>>i;if(!a[i]++){++c;a[i]++;}}for(i=1<<17;i--;)n^=a[i]&1;std::cout<<(n&1?c:c-1);}

// Optimized solution to the same problem (faster):
#import<iostream>

int n,c,i,a[1<<17];

main(){for(std::cin>>n;std::cin>>i;)c+=!!a[i]++;std::cout<<n-c-c%2;}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int M=1e5+5;

int a[M],cnt;

int main()

{

    int n;scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        int x;scanf("%d",&x);

        a[x]++;

    }

    int cost=0;

    for(int i=1;i<M;i++)if(a[i]>=2)

    {

        if(a[i]%2==0)

        {

            cost+=a[i]-2;

            cnt++;

        }

        else cost+=a[i]-1;



    }

    cost+=(cnt/2)*2;

    if(cnt%2==1)cost+=2;

    printf("%d\n",n-cost);

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <cstring>

#include <set>

using namespace std;



int main()

{

    int n,i,x,m=0;

    cin>>n;

    set<int> s;

    for(i=0;i<n;i++)

    {

        cin>>x;

        if(s.count(x))m++;

        s.insert(x);

    }

    cout<<s.size()-m%2;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <map>

using namespace std;

#define ll long long

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

#define dump(x) cerr << #x << " = " << (x) << endl;

int A[100010];

int cnt[100010];

int main(void){

    int N; cin >> N;

    rep(i, N) cin >> A[i];

    rep(i, N) cnt[A[i]]++;

    rep(i, 100010) {

      if (cnt[i] % 2 == 1) cnt[i] = 1;

      else if (cnt[i] % 2 == 0 && cnt[i] >= 2) cnt[i] = 2;

    }

    int cnt1 = 0;

    int cnt2 = 0;

    rep(i, 100010) if (cnt[i] == 1) cnt1++;

    rep(i, 100010) if (cnt[i] == 2) cnt2++;

    //rep(i, 20) cout << i << " " << cnt[i] << endl;

    cout << cnt1 + cnt2 - cnt2 % 2 << endl;





    return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



int cnt[100010];

int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N; cin >> N;

    int a[100010];

    rep(i, N) cin >> a[i];

    rep(i, N) cnt[a[i]]++;

    int ans = 0;

    rep(i, 100010) if(cnt[i] > 0) ans++;

    int k = 0;

    rep(i, 100010) if(cnt[i] > 1) k += cnt[i] - 1;

    cout << ans - k % 2 << endl;

    





    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



int cnt[100010];

int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N; cin >> N;

    int A[100010];

    rep(i, N) cin >> A[i];

    rep(i, N) cnt[A[i]]++;

    vector<int> v;

    rep(i, 100010) if(cnt[i] > 0) v.push_back(cnt[i]);

    int ans = 0;

    sort(v.begin(), v.end());

    int cnt = 0;

    for(auto& e: v) {

        cnt += max(0, e - 1);

    }

    if(cnt % 2 == 0) {

        cout << v.size() << endl;

    } else {

        cout << v.size() - 1 << endl;

    }

    //cout << cnt << endl;



    return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



int cnt[100010];

int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N; cin >> N;

    int a[100010];

    rep(i, N) cin >> a[i];

    rep(i, N) cnt[a[i]]++;

    int ans = 0;

    rep(i, 100010) if(cnt[i] > 0) ans++;

    int k = 0;

    rep(i, 100010) if(cnt[i] > 1) k += cnt[i] - 1;

    cout << ans - k % 2 << endl;

    





    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int h, n;

vector<int> b;



int dp[101010][10];



int dfs(int i = 1, int bit = 0) {

  if (i == h) {

    return 0;

  }

  bit |= b[i];



  int &ret = dp[i][bit];

  if (~ret)

    return ret;



  ret = 0;

  if (bit == 0)

    ret = max(ret, dfs(i + 1, 0b111) + 2);

  if ((bit & (0b100)) == 0)

    ret = max(ret, dfs(i + 1, 0b110) + 1);

  if ((bit & (0b010)) == 0)

    ret = max(ret, dfs(i + 1, 0b111) + 1);

  if ((bit & (0b001)) == 0)

    ret = max(ret, dfs(i + 1, 0b011) + 1);

  ret = max(ret, dfs(i + 1, 0));



  return ret;

}



int main() {

  memset(dp, -1, sizeof(dp));

  cin >> h >> n;



  int ei[4] = {0b100, 0b110, 0b011, 0b001};

  b.assign(h + 1, 0);

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

    int x, y;

    cin >> x >> y;

    b[y + 1] |= ei[x];

    b[y] |= ei[x];

  }



  cout << dfs() << endl;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp



using namespace std;



typedef pair<int, int> P;

typedef long long ll;

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

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

#define all(c) (c).begin(), (c).end()

#define uniq(c) c.erase(unique(all(c)), (c).end()) // ユニークなvectorにする。連続した値を除去して切り出す。

#define _1 first

#define _2 second

#define pb push_back

#define INF 1145141919

#define MOD 1000000007

#define DEBUG(x) cout << #x << ": " << x << endl;



__attribute__((constructor))

void initial() {

  cin.tie(0);

  ios::sync_with_stdio(false);

}



int h, n;

vector<int> b;



int dp[10000][8];



int dfs(int i = 1, int bit = 0) {

  if (i == h) { // 最後まで来た場合

    return 0;

  }

  bit |= b[i]; // 置ける状況を取得



  int &ret = dp[i][bit]; // おける最大数、配列の中身を変えたいので参照取得

  if (~ret)

    return ret;  // 計算済みなら返す  retが-1だと~retは0となり計算するために次へ



  ret = 0;

  if (bit == 0) // 2つ置く場合

    ret = max(ret, dfs(i + 1, 0b111) + 2);

  if ((bit & (0b100)) == 0) // 左に置く場合

    ret = max(ret, dfs(i + 1, 0b110) + 1);

  if ((bit & (0b010)) == 0) // 中に置く場合

    ret = max(ret, dfs(i + 1, 0b111) + 1);

  if ((bit & (0b001)) == 0) // 右に置く場合

    ret = max(ret, dfs(i + 1, 0b011) + 1);

  ret = max(ret, dfs(i + 1, 0)); // 置かない場合



  // 5パターンの最大値がretに

  return ret;

}



int main() {

  memset(dp, -1, sizeof(dp));

  cin >> h >> n;



  // eiはそれぞれ x の値に対応するおけない箇所

  int ei[4] = {0b100, 0b110, 0b011, 0b001};

  b.assign(h + 1, 0);

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

    int x, y;

    cin >> x >> y;

    // 置けなくなる箇所をパターンとして用意

    b[y + 1] |= ei[x];

    b[y] |= ei[x];

  }



  cout << dfs() << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

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

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

char ma[888][888];

int n,m,k,dist[888][888],pis[888][888],mn;

queue<pair<int,int> > q;

bool In(int x,int y)

{

	return (x>=0 && x<n && y>=0 && y<m);

}

int main()

{

	mn=1e9;

	scanf("%d%d%d",&n,&m,&k);

	for (int i=0;i<n;i++)

	scanf("%s",ma[i]);

	for (int i=0;i<n;i++)

	{

		for (int j=0;j<m;j++)

		{

			pis[i][j]=min(min(i,j),min(n-i-1,m-j-1));

			pis[i][j]=(pis[i][j]+k-1)/k;

		}

	}

	memset(dist,-1,sizeof(dist));

	for (int i=0;i<n;i++)

	{

		for (int j=0;j<m;j++)

		{

			if (ma[i][j]=='S') 

			{

				q.push(make_pair(i,j));

				dist[i][j]=0;

				mn=min(mn,pis[i][j]+1);

			}

		}

	}

	while(!q.empty())

	{

		int x=q.front().first,y=q.front().second;

		q.pop();

		if (dist[x][y]==k) break;

		for (int i=0;i<4;i++)

		{

			int xx=x+dx[i],yy=y+dy[i];

			if (In(xx,yy) && ma[xx][yy]=='.' && dist[xx][yy]==-1)

			{

				mn=min(mn,pis[xx][yy]+1);

				dist[xx][yy]=dist[x][y]+1;

				q.push(make_pair(xx,yy));

			}

		}

	}

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

	return 0;

}

// Optimized solution to the same problem (faster):
#include <algorithm>

#include <cstring>

#include <cstdio>

#include <queue>

#include <cmath>

 

#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)

 

using namespace std;

 

const int MAXN = 800 + 5;

const int DIRX[] =

{ 1, -1, 0, 0 };

const int DIRY[] =

{ 0, 0, 1, -1 };

 

int H, W, K;

int stX, stY;

char mz[MAXN][MAXN];

bool vist[MAXN][MAXN];

 

int answer = 0x7F7F7F7F;

 

void BFS()

{

	queue<pair<pair<int, int>, int> > Q;

	Q.push(make_pair(make_pair(stX, stY), 0));

 

	while (!Q.empty())

	{

		pair<pair<int, int>, int> cur = Q.front();

		Q.pop();

 

		if(vist[cur.first.first][cur.first.second])

			continue;

		vist[cur.first.first][cur.first.second] = true;

 

		int curAns = min(min(cur.first.first - 1, H - cur.first.first),

				min(cur.first.second - 1, W - cur.first.second));

		curAns = (curAns + K - 1) / K;

		answer = min(answer, curAns + 1);

 

		if (cur.second >= K)

			continue;

 

		for (int i = 0; i < 4; i++)

		{

			pair<int, int> newPos = make_pair(cur.first.first + DIRX[i],

					cur.first.second + DIRY[i]);

			if(newPos.first <= 0 || newPos.first > H)

				continue;

			if(newPos.second <= 0 || newPos.second > W)

				continue;

			if(mz[newPos.first][newPos.second] != '#' && !vist[newPos.first][newPos.second])

				Q.push(make_pair(newPos, cur.second + 1));

		}

	}

}

 

int main()

{

 

	//REDIRECT("room");

 

	scanf("%d%d%d", &H, &W, &K);

	for (int i = 1; i <= H; i++)

	{

		scanf("%s", mz[i] + 1);

		for (int j = 1; j <= W; j++)

			if (mz[i][j] == 'S')

				stX = i, stY = j;

	}

 

	BFS();

 

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

 

	CLOSEALL();

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<stdio.h>

#include<fstream>

#include<algorithm>

#include<ctime>

#include<cstdlib>

#include<cstring>

#include<vector>

#include<set>

#include<string>

#include<queue>

#include<map>

#include<iomanip>

#include<cassert>

#include<complex>

#include<functional>

#include<list>

#include<cmath>

#include<stack>

#define ll long long

#define pb push_back

#define mp make_pair

using namespace std;

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

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

int n,m,k,d[1024][1024],xs,ys,x,y,xx,yy;

char a[1024][1024];

queue<pair<int,int> > q;

bool valid(int i,int j)

{

	return i>=0 && i<n && j>=0 && j<m && a[i][j]!='#';

}

int asd(int i,int j)

{

	int r=i;

	r=min(r,j);

	r=min(r,n-1-i);

	r=min(r,m-1-j);

	return r;

}

int main()

{

	cin>>n>>m>>k;

	for (int i=0;i<n;i++)

		for (int j=0;j<m;j++)

		{

			cin>>a[i][j];

			if (a[i][j]=='S') xs=i,ys=j;

		}

	memset(d,-1,sizeof(d));

	d[xs][ys]=0;

	q.push(mp(xs,ys));

	while (!q.empty())

	{

		x=q.front().first; y=q.front().second;

		q.pop();

		for (int i=0;i<4;i++)

		{

			xx=x+dx[i]; yy=y+dy[i];

			if (valid(xx,yy) && d[xx][yy]<0)

			{

				d[xx][yy]=d[x][y]+1;

				q.push(mp(xx,yy));

			}

		}

	}

	int r=1<<20;

	for (int i=0;i<n;i++)

		for (int j=0;j<m;j++)

			if (d[i][j]>=0 && d[i][j]<=k)

				r=min(r,1+(asd(i,j)+k-1)/k);

	cout<<r;

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

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

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

int n,m,k,d[801][801],xs,ys,ans=INF;

char s[801][801];

int asd(int i,int j)

{

	int r=i;

	r=min(r,j);

	r=min(r,n-1-i);

	r=min(r,m-1-j);

	return r;

}

queue<pair<int,int> > q;

int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	cin>>n>>m>>k;

	for (int i=0;i<n;++i)

		for (int j=0;j<m;++j)

		{

			cin>>s[i][j];

			if (s[i][j]=='S') xs=i,ys=j;

		}

	memset(d,-1,sizeof(d));

	d[xs][ys]=0;

	q.push(make_pair(xs,ys));

	while (!q.empty())

	{

		int x=q.front().first;

		int y=q.front().second;

		q.pop();

		for (int i=0;i<4;++i)

		{

			int xx=x+dx[i];

			int yy=y+dy[i];

			if (xx>=0 && xx<n && yy>=0 && yy<m && s[xx][yy]=='.' && d[xx][yy]<0)

			{

				d[xx][yy]=d[x][y]+1;

				q.push(make_pair(xx,yy));

			}

		}

	}

	for (int i=0;i<n;++i)

		for (int j=0;j<m;++j)

			if (d[i][j]>=0 && d[i][j]<=k)

				ans=min(ans,1+(asd(i,j)+k-1)/k);

	cout<<ans;

	return 0;

}

// Fastest known solution for this problem: