Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2288-ec91d01f
この記事にトラックバックする(FC2ブログユーザー)

ARC 004 C - 平均値太郎の憂鬱 (The melancholy of Taro Heikinchi) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #004
問題文

問題概要

1からNまで平均値を求めるのに,1つの整数Mを足すのを忘れた.
つまり,(1+2+...+N - M) / Nの値が分数の形で与えられるので,考えうるNとMの値の組を全部求める問題.
存在しないならそれを指摘する.

解法

Mは1以上M以下なので,(1+2+...+N - M) / Nの値から大体のNの値を推定できる.
考えうるNの値は高々2個.
Nを決めれば,Mは計算できる.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
ll GCD(ll a,ll b){ll r; while(a){r=b; b=a; a=r%a;} return b;}

int solve(ll x, ll y, ll n){
  ll i, j, k, m;
  ll up, down;

  if(n < 1) return 0;
  if(GCD(2*n,y)!=y) return 0;

  up = n*(n+1) - (2*n)/y * x;
  if(up%2) return 0;
  m = up / 2;
  if(m < 1 || m > n) return 0;
 
  printf("%lld %lld\n",n,m);
  return 1;
}

int main(){
  ll i,j,k,l,m,n;
  ll x, y;
  int ok = 0;

  scanf(" %lld/%lld",&x,&y);
  k = GCD(x,y);
  x /= k; y /= k;

  n = 2*x / y - 5;
  rep(i,15) ok += solve(x, y, n+i);
  if(!ok) puts("Impossible");

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2288-ec91d01f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。