Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

 | 

2012-10-13

codeforces 144 div 2

| 16:04

A

P_{P_i}=iという条件をよく考える。P_i=jとするとP_{P_i}=P_j=i。従って、P_i=P_{P_j}=j

上の考察とP_i\neq iから、nが奇数なら条件を満たす順列は無い。nが偶数なら、適当なペアを作ってお互いに移り合うようにすれば良い

/*! if g++ -g a.cpp -o a.out; then ./a.out < a.test; fi
 */

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>



using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int n;

int main(int argc, char *argv[]){
  scanf("%d", &n);
  if(n%2==1){
    printf("%d\n", -1);
  }
  else{
    for(size_t i = 0; i < n/2; ++i){
      printf("%d %d", 2*i+2, 2*i+1);
      if(i==n/2-1) printf("\n");
      else printf(" ");
    }
  }
  return 0;
}

B

s(x)>=0は自明。適当な単調関数gで、g(x)>=s(s)なるものを探してくる。すると、方程式の解はx(x+g(x))=nの解とx^2=nの解の間にある。

/*! if g++ -g b.cpp -o b.out; then ./b.out < b.test; fi
 */

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>



using namespace std;
typedef unsigned long long ull;
typedef long long ll;

ull n;


double mysqrt(ull x){
  if(x==1) return 1;
  else return sqrt(x);
}
double mylog(ull x){
  return log(x)/log(10);
}
double f(ull x){
  return x*(x+10*mylog(x));
}
ull search(ull l, ull r){
  if(r-l<=1) return l;
  ull c = (l+r)/2;
  if(f(c)>=n) return search(l, c);
  else return search(c, r);
}
int s(ull x){
  if(x==0) return 0;
  return x%10 + s(x/10);
}
int main(int argc, char *argv[]){
  cin >> n;
  for(ull i = search(1,n); i <= mysqrt(n); i++){
    if(i*(i+s(i))==n){
      cout << i << endl;
      return 0;
    }
  }
  printf("-1\n");
  return 0;
}

 |