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

#include <iostream>

#include <vector>

#include <queue>

#include <set>

#include <string>

#include <map>

#include <cstring>



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

#define Rep(i, sta, n) for (int i = sta; i < (n); ++i)

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



using namespace std;

typedef long long ll;

const int mod = 1000000007;



int color[100100];

typedef pair<int, int> wedge;

vector<wedge> to[100100];



void dfs(int i, int c) {

    color[i] = c;

    for(auto e: to[i]) {

        if (color[e.first]==0 && e.second % 2 == 0) dfs(e.first, c); 

        else if (color[e.first]==0 && e.second % 2 != 0) dfs(e.first, -c); 

    }

    return;

}



int main() {

    int n;

    cin >> n;



    int u, v, w;

    rep(i, n-1) {

        cin >> u >> v >> w;

        --u, --v;

        to[u].push_back(wedge(v, w));

        to[v].push_back(wedge(u, w));

    }

    memset(color, 0, sizeof(color));

    rep(i, n) {

        if (color[i]==0) {

            dfs(i, 1);

        }

    }

    rep(i, n) {

        if (color[i]==1) cout << "0" << endl;

        else cout << "1" << endl;

    }

    return 0;

}


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

#include <iostream>

#include <vector>

#include <queue>

#include <set>

#include <string>

#include <map>

#include <cmath>

#include <cstring>



#define fi first

#define se second

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

#define rrep(i,n) for (int i = 1; i < (n); ++i)

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

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

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

#define maxs(x,y) (x = max(x,y))

#define mins(x,y) (x = min(x,y))

#define pb push_back

#define sz(x) (int)(x).size()

#define PQ(T) priority_queue<T, v(T), greater<T> >



using namespace std;

typedef long long ll;

typedef unsigned uint;

typedef unsigned long long ull;

typedef pair<int,int> P;



const ll LINF = 1001002003004005006ll;

const int INF = 1001001001;



const int mod = 1000000007;



struct Edge {

    int to;

    ll d;

};



int colors[100100];

bool visited[100100];

vector<vector<Edge> > es;



void dfs(int v, int p) {

    if (visited[v]) return;

    visited[v] = true;

    for (auto e: es[v]) {

        //cout << "to: " << e.to << " cost: " << e.d << endl;

        if (p == e.to) continue;



        if (e.d % 2 == 0) colors[e.to] = colors[v]; 

        else colors[e.to] = (colors[v]+1) % 2;

        dfs(e.to,v);

    }

    return;

}



int main() {

    int n; cin >> n;

    es.resize(n);



    rep(i,n-1) {

        int u, v;

        ll w;

        cin >> u >> v >> w;

        --u; --v;

        Edge edge1 = {v,w};

        es[u].pb(edge1);

        Edge edge2 = {u,w};

        es[v].pb(edge2);

    }



    dfs(0,-1);

    rep(i,n) cout << colors[i] << endl;

    return 0;

}
























































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

#define debug(x) cerr << #x << ": " << x << '\n';

using namespace std;

using ll = long long;

using P = pair<int, int>;

const int INF = (int)1e9;



struct edge{

    int to, len;

};



vector<edge> G[100000];

int N;

bool color[100000], used[100000];



void dfs(int n){

    used[n] = true;

    for(edge e: G[n]){

        if(used[e.to]) continue;

        if(e.len & 1){

            color[e.to] = not color[n];

        }else{

            color[e.to] = color[n];

        }

        dfs(e.to);

    }

}



int main(void){

    cin >> N;

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

        int u, v, w;

        cin >> u >> v >> w; u--; v--;

        edge e; e.to = v; e.len = w;

        G[u].push_back(e);

        e.to = u;

        G[v].push_back(e);

    }



    color[0] = 0;

    dfs(0);



    for(int i = 0; i < N; i++) cout << color[i] << '\n';



    return 0;

}

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

#define debug(x) cerr << #x << ": " << x << '\n';

using namespace std;

using ll = long long;

using P = pair<int, int>;

const int INF = (int)1e9;

const int MOD = (int)1e9 + 7;



// graph template

template<typename T>

class Edge{

    public:

        int src, to; T cost;



        Edge(int to, T cost): src(-1), to(to), cost(cost){}

        Edge(int src, int to, T cost): src(src), to(to), cost(cost){}

};

template<typename T>

using Edges = vector<Edge<T>>;

template<typename T>

using AdjacencyList = vector<Edges<T>>;

template<typename T>

using Matrix = vector<vector<T>>;



template<typename T>

vector<bool> bipartite_matching(AdjacencyList<T> &g){

    int V = (int)g.size();

    vector<bool> color(V), used(V, false);

    

    stack<int> s;

    color[0] = false;

    s.push(0);

    while(not s.empty()){

        int v = s.top(); s.pop();

        used[v] = true;



        for(auto e: g[v]){

            if(used[e.to]){

                if((e.cost & 1) == (color[v] ^ color[e.to])) continue;

                else return vector<bool>();

            }else{

                color[e.to] = (e.cost & 1) ^ color[v];

                s.push(e.to);

            }

        }

    }



    return color;

}



int main(void){

    int N;

    cin >> N;

    AdjacencyList<int> g(N);

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

        int u, v, w;

        cin >> u >> v >> w;

        u--; v--;

        g[u].push_back(Edge<int>(v, w));

        g[v].push_back(Edge<int>(u, w));

    }



    vector<bool> vec = bipartite_matching(g);

    if(not vec.empty()){

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

            cout << vec[i] << '\n';

        }

    }



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// In the name of God



#include <bits/stdc++.h>



using namespace std;



const int N = 1e5+5;



int n, c[N];

vector<pair<int,int>> adj[N];



void dfs(int u, int p, int col) {

	c[u] = col;

	for(auto v : adj[u]) {

		if(v.first == p) continue;

		dfs(v.first, u, col ^ v.second);

	}

}	



int main() {

	ios_base::sync_with_stdio(false);

	cin.tie(0);



	cin >> n;



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

		int u, v, w;

		cin >> u >> v >> w;

		w = w & 1;

		u--;

		v--;

		adj[u].push_back(make_pair(v, w));

		adj[v].push_back(make_pair(u, w));

	}



	dfs(0, 0, 0);



	for(int i = 0; i < n; i++) cout << c[i] << "\n";



	return 0;

}


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

#define ll long long int

#define ff first

#define ss second

#define eps 1e-9



using namespace std;

vector< vector<pair<ll,ll> > > g;

vector< ll> col;

vector< bool > vis;



void bfs()

{

    vis[1]=1;

    col[1]=0;

    queue<ll>  q;

    q.push(1);



    while(!q.empty())

    {

        ll top = q.front();

        q.pop();



        for(int i=0;i<g[top].size();i++)

        {

            if(vis[g[top][i].ff]==0)

            {

                vis[g[top][i].ff] =1;



                if(g[top][i].ss %2 )

                {

                    col[ g[top][i].ff ] = 1 - col[top];



                }

                else

                {

                    col[ g[top][i].ff ] = col[top];

                }



                q.push(g[top][i].ff);

            }

        }



    }

}





int main()

{



    ll t,n,m,f,a,b,c,l,r,q,k,x,y,w,z,ans,mn,mx,sum=0;



    cin>>n;



    g.resize(n+1);

    col.resize(n+1);

    vis.resize(n+1);



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

    {

        cin>>x>>y>>w;



        g[x].push_back({y,w});

        g[y].push_back({x,w});

    }



    bfs();



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

    {

        cout<<col[i]<<endl;

    }









}


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

using namespace std;

#define ll long long

#define gcd(a,b) __gcd(a,b)

#define ff first

#define ss second

#define p pair<ll,ll>

#define pb push_back

#define endl '\n'

#define w(t) ll test;cin>>test;while(test--)

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);

#define pi acos(-1)

const int mx=1e5+7;

vector<p>adj[mx];

vector<ll> vis(mx),dis(mx);

 queue<ll> q;

void bfs(ll s)

{



    q.push(s);

    vis[s]=1;

    dis[s]=0;

    while(!q.empty())

    {

        ll u=q.front();

        q.pop();

        for(auto i:adj[u])

        {

            if(!vis[i.ff])

            {

                q.push(i.ff);

                vis[i.ff]=1;

                dis[i.ff]=dis[u]+i.ss;

            }

        }

    }

}

//for a tree

int main()

{

    fast;

    ll n;

    cin>>n;

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

    {

        ll u,v,w;

        cin>>u>>v>>w;

        adj[u].pb({v,w});

        adj[v].pb({u,w});

    }

    bfs(1);

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

    {

       // cout<<dis[i]<<" ";

        cout<<(dis[i]&1?1:0)<<endl;

    }

}


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

#define ll long long int

#define ff first

#define ss second

#define eps 1e-9



using namespace std;

vector< vector<pair<ll,ll> > > g;

vector< ll> col;

vector< bool > vis;



void bfs()

{

    vis[1]=1;

    col[1]=0;

    queue<ll>  q;

    q.push(1);



    while(!q.empty())

    {

        ll top = q.front();

        q.pop();



        for(int i=0;i<g[top].size();i++)

        {

            if(vis[g[top][i].ff]==0)

            {

                vis[g[top][i].ff] =1;



                if(g[top][i].ss %2 )

                {

                    col[ g[top][i].ff ] = 1 - col[top];



                }

                else

                {

                    col[ g[top][i].ff ] = col[top];

                }



                q.push(g[top][i].ff);

            }

        }



    }

}





int main()

{



    ll t,n,m,f,a,b,c,l,r,q,k,x,y,w,z,ans,mn,mx,sum=0;



    cin>>n;



    g.resize(n+1);

    col.resize(n+1);

    vis.resize(n+1);



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

    {

        cin>>x>>y>>w;



        g[x].push_back({y,w});

        g[y].push_back({x,w});

    }



    bfs();



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

    {

        cout<<col[i]<<endl;

    }









}


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

#include<vector>

#include<map>

#include<algorithm>

#include<cmath>

#include<string>

#include<cstdlib>

#include<iomanip>



#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define REP(i,n)   FOR(i,0,n)

#define MOD 1000000007



using namespace std;



typedef long long int ll;



const ll INF=(ll)1e18;



vector<vector<pair<int,ll> > > d(100001);



int color[100001];

bool visited[100001];



void dfs(int n, int col){

//  printf("%d %d\n",n,col);

  if(visited[n])return;

  visited[n] = true;

  color[n]=col;

  int col2 = col == 0 ? 1 : 0;



  REP(i,d[n].size()){

    if(d[n][i].second % 2 == 0){

      dfs(d[n][i].first, col);

    }else{

      dfs(d[n][i].first, col2);

    }

  }

}



int main(){



  int N;

  cin >> N;





  REP(i,N-1){

    int u,v;

    ll w;

    cin >> u >> v >> w;

    d[u].push_back(make_pair(v,w));

    d[v].push_back(make_pair(u,w));

  }



  // FOR(i,1,N+1){

  //   cout << i << endl;

  //   REP(j,d[i].size()){

  //     printf("%d %lld\n", d[i][j].first,d[i][j].second);

  //   }

  // }



  FOR(i,1,N+1)visited[i]=false;



  dfs(1,0);



  FOR(i,1,N+1){

    cout << color[i] << endl;

  }



}


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

using namespace std;



#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define REP(i,n)   FOR(i,0,n)

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

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

#define PRINT(a)   cout << (a) << endl



#define pb push_back

#define eb emplace_back

#define mp make_pair

#define Fi first

#define Se second



#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';



using ll = long long int;

using P = pair<int,int>;

using vi = vector<int>;

using vvi = vector<vi>;

using vvvi = vector<vvi>;

using pii = pair<int, int>;



template <typename T> using PQ = priority_queue<T>;

template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;



template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



const int INF = 1001001001;

const ll LINF = 1001001001001001001ll;

const int MOD = 1e9 + 7;



int main(){

  int N;

  cin >> N;



  vector<vector<P>> edge(N);

  vi col(N,-1);



  REP(i,N-1){

    int u,v,w;

    cin >> u >> v >> w;

    u--; v--;

    edge[u].emplace_back(v,w);

    edge[v].emplace_back(u,w);

  }



  queue<P> q;

  col[0]=0;

  q.emplace(0,0);



  while(!q.empty()){

    int x = q.front().first;

    int c = q.front().second;

    q.pop();



    for(auto e: edge[x]){

      int y = e.first;

      int w = e.second;

      if(col[y]!=-1)continue;



      if(w%2==0){

        col[y] = c;

      }else{

        col[y] = c ^ 1;

      }

      q.emplace(y, col[y]);

    }

  }



  REP(i,N){

    cout << col[i] << endl;

  }

}




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

using namespace std;

typedef long long ll;

const int N=2e3+5;

vector<pair<ll,ll> >v(N);//vector对pair排序时按'键'排序 即第一元素first 

ll dp[N][N];

int n;

ll fun(int l,int r){

	if(l>r) return 0;

	if(dp[l][r]) return dp[l][r];

	int i=n-(r-l+1);//当前要放入的数的下标 

	return dp[l][r]=max(fun(l,r-1)+v[i].first*(r-v[i].second),fun(l+1,r)+v[i].first*(v[i].second-l));//放两端取最大 

}

int main(){

	scanf("%d",&n);

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

		scanf("%d",&x),v.push_back({x,i});

	sort(v.rbegin(),v.rend());//贪心从大到小排 

	fun(0,n-1);

	printf("%lld\n",dp[0][n-1]);

	return 0;

}

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

#include <algorithm>

#include <vector>

#include <utility>

using namespace std;



typedef long long LL;

typedef pair <LL, LL> PII;



vector<PII> a;

LL dp[2005][2005];

int n;



LL solve(int l, int r){

	if (l > r) return 0;

	if (dp[l][r]) return dp[l][r];

	int i = n - (r - l + 1);

	return dp[l][r] = max(solve(l, r - 1) + a[i].first * (r - a[i].second), solve(l + 1, r) + a[i].first * (a[i].second - l));

}



int main(){

	scanf("%d", &n);

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

		int x;

		scanf("%d", &x);

		a.push_back({x, i});

	}

	sort(a.rbegin(), a.rend());

	solve(0, n - 1);

	printf("%lld\n", dp[0][n - 1]);

	return 0;

}


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

using namespace std;

typedef long long ll;

const int N=2e3+5;

vector<pair<ll,ll> >v(N);

ll dp[N][N];

int n;

ll fun(int l,int r){

	if(l>r) return 0;

	if(dp[l][r]) return dp[l][r];

	int i=n-(r-l+1);

	return dp[l][r]=max(fun(l,r-1)+v[i].first*(r-v[i].second),fun(l+1,r)+v[i].first*(v[i].second-l));

}

int main(){

	scanf("%d",&n);

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

		scanf("%d",&x),v.push_back({x,i});

	sort(v.rbegin(),v.rend());

	fun(0,n-1);

	printf("%lld\n",dp[0][n-1]);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=2e3+5;

ll dp[N][N];

struct p{

	int x,id;

	bool operator<(const p&a)const{

		return x>a.x; 

	}

}a[N];

int main(){

	int n;

	scanf("%d",&n);

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

		scanf("%d",&a[i].x),a[i].id=i;

	sort(a+1,a+n+1);//从大到小排序 

	for(int k=1;k<=n;k++)//对第k个元素进行放置(前k-1个元素所有情况都已知) 

		for(int i=0;i<k;i++)//遍历前k-1元素的所有情况. i为往左放置的个数. 

		{

			int j=k-1-i;//前k-1元素往右放置的个数. 

			dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(ll)a[k].x*(a[k].id-(i+1)));//往左放 

			dp[i][j+1]=max(dp[i][j+1],dp[i][j]+(ll)a[k].x*(n-j-a[k].id));//往右放 

		}

	ll ans=0;

	for(int i=0;i<=n;i++) ans=max(ans,dp[i][n-i]);//取最大值. 

	printf("%lld\n",ans);

	return 0;

}

 

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

#include <cstdio>

#include <iostream>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <vector>

#include <stdlib.h>

#include <stdio.h>

#include <bitset>

#include <cstring>

#include <deque>

using namespace std;

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define CLR(mat) memset(mat, 0, sizeof(mat))

typedef long long ll;

ll n, m, k;

map<ll, ll> MAP;

ll num;

void dfs(int cnt) {

  if(cnt == n) {

    MAP[max(1LL, num-k)]++;

  } else {

    FOR(i,1,m+1) {

      num += i;

      dfs(cnt+1);

      num -= i;

    }

  }

}

int main()

{

  ios::sync_with_stdio(false);

  cin.tie(0);

  while(cin>>n>>m>>k,n||m||k) {

    num = 0;

    MAP.clear();

    ll waru = pow(m, n);

    dfs(0);

    double ans = 0;

    for(auto M : MAP) {

      ans += (double)M.first * M.second / waru;

    }

    printf("%.10lf\n", ans);

  }

  return 0;

}

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

#include <cstdio>

#include <iostream>

#include <map>

#include <cmath>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <vector>

#include <stdlib.h>

#include <stdio.h>

#include <bitset>

#include <cstring>

#include <deque>

using namespace std;

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define CLR(mat) memset(mat, 0, sizeof(mat))

typedef long long ll;

int main()

{

  ll n,m,k;

  while(cin>>n>>m>>k,n||m||k) {

    ll dp[n+1][n*m+1]; CLR(dp);

    dp[0][0] = 1;

    FOR(i,0,n) {

      FOR(j,0,m*i+1) {

        FOR(t,1,m+1) {

          dp[i+1][j+t] += dp[i][j];

        }

      }

    }

    double ans = 0;

    ll waru = pow(m, n);

    FOR(i,0,n*m+1) {

      ans += (double)dp[n][i] * max(1LL, i-k) / waru;

    }

    printf("%.10lf\n", ans);

  }

}

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

#include <cstdio>

#include <cmath>



using namespace std;



int n, m, k, x;

double ans;



void dfs(int node, int sum) {

    if (node == n) {

        if (sum-k < 1) sum = 1;

        else sum -= k;

        ans += (double)sum / x;

        return;

    }

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

        dfs(node+1, sum+i);

    }

    return;

}



int main(void){

    while (cin>>n>>m>>k && n) {

        ans = 0;

        x = pow(m,n);

        dfs(0, 0);

        printf("%.12lf\n",ans);

    }

}

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

#include <cstdio>

#include <vector>

#include <cmath>



using namespace std;



int main(void){

    int n, m, k;

    while (cin>>n>>m>>k && n) {

        vector<vector<int> > dp(n+1, vector<int>(n*m+1, 0));

        dp[0][0] = 1;

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

            for (int j = 0; j < n*m+1; j++) {

                if (dp[i][j] == 0) continue;

                for (int dice = 1; dice < m+1; dice++) {

                    dp[i+1][j+dice] += dp[i][j];

                }

            }

        }

        

        double ans = 0;

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

            if (dp[n][i] == 0) continue;

            if (i-k < 1) ans += 1 * dp[n][i];

            else ans += (i-k) * dp[n][i];

        }

        printf("%.12lf\n", ans / pow(m,n));

    }

}

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

#include <cstdio>

#include <cmath>



using namespace std;



int n, m, k;

double ans;



void dfs(int node, int sum) {

    if (node == n) {

        if (sum-k < 1) sum = 1;

        else sum -= k;

        ans += sum;

        return;

    }

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

        dfs(node+1, sum+i);

    }

    return;

}



int main(void){

    while (cin>>n>>m>>k && n) {

        ans = 0;

        dfs(0, 0);

        printf("%.12lf\n", ans / pow(m,n));

    }

}

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

#include <cstdio>

#include <vector>

#include <cmath>



using namespace std;



int main(void){

    int n, m, k;

    while (cin>>n>>m>>k && n) {

        vector<vector<int> > dp(n+1, vector<int>(n*m+1, 0));

        dp[0][0] = 1;

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

            for (int j = 0; j < n*m+1; j++) {

                if (dp[i][j] == 0) continue;

                for (int dice = 1; dice < m+1; dice++) {

                    dp[i+1][j+dice] += dp[i][j];

                }

            }

        }

        

        double ans = 0;

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

            if (dp[n][i] == 0) continue;

            if (i-k < 1) ans += 1 * dp[n][i];

            else ans += (i-k) * dp[n][i];

        }

        printf("%.12lf\n", ans / pow(m,n));

    }

}

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

#include <iomanip>

#include <vector>

#include <algorithm>



using namespace std;



vector<int> buffer;



int dfs(int m, int sum, int rem){

        if(rem == 0){

                ++(buffer[sum]);

                return 1;

        }

        int retval = 0;

        for(int i = 1; i <= m; ++i){ retval += dfs(m, sum + i, rem - 1); }

        return retval;

}



int main(){

        cout << setprecision(10);

        while(true){

                int n, m, k;

                cin >> n >> m >> k;

                if(n == 0 && m == 0 && k == 0){ break; }

                buffer.resize(n * m + 1);

                fill(buffer.begin(), buffer.end(), 0);

                int num = dfs(m, 0, n);

                double answer = 0.0;

                for(int i = 0; i < buffer.size(); ++i){

                        if(i <= k){

                                answer += 1.0 * buffer[i] / num;

                        }else{

                                answer += (double)(i - k) * buffer[i] / num;

                        }

                }

                cout << answer << endl;

        }

        return 0;

}

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

#include <iomanip>

#include <string>

#include <vector>

#include <algorithm>



using namespace std;



int main(){

	ios_base::sync_with_stdio(false);

	cout << setiosflags(ios::fixed) << setprecision(10);

	while(true){

		int n, m, k;

		cin >> n >> m >> k;

		if(n == 0 && m == 0 && k == 0){ break; }

		double answer = 0;

		if(n == 1){

			const double r = 1.0 / m;

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

				answer += max(1, i - k) * r;

			}

		}else{

			const double r = 1.0 / m;

			const int len = n * m + 1;

			vector<double> dp(len);

			dp[0] = 1.0;

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

				vector<double> next(len);

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

					for(int k = 1; k <= m; ++k){

						next[j + k] += r * dp[j];

					}

				}

				dp.swap(next);

			}

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

				answer += dp[i] * max(1, i - k); 

			}

		}

		cout << answer << endl;

	}

	return 0;

}

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

using namespace std;

int main()

{

    int r;

    cin>>r;

    if(r>0&&r<101)

    {

        r=r*r;

        cout<<r<<endl;

    }

    return 0;

}


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

int main()

{

    int i;

    scanf("%d",&i);

    printf("%d",i*i);

    return 0;

}


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

using namespace std;

int main()

{

    int r;

    cin>> r;

    cout<<r*r<<endl;



    return 0;

}

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

int main()

{

    int r,p;



    scanf("%d",&r);



    p = (r * r);



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



    return 0;

}


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

using namespace std;

int main(){

	int k;

	cin>>k;

	cout<<k*k<<endl;

	

	

}

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

int main()

{

    int r,p;



    scanf("%d",&r);



    p = (r * r);



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



    return 0;

}


// Fastest known solution for this problem: