fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string.h>
  4. #include <stdio.h>
  5. #include <set>
  6. #include <cmath>
  7. #include <vector>
  8. #include <string>
  9. #include <cstdio>
  10. #include <cstdlib>
  11. #include <vector>
  12. #include <algorithm>
  13. #include <map>
  14. #include <queue>
  15. #define ll long long
  16. #define INF 1e9
  17. #define PI acos(-1.0)
  18. using namespace std;
  19. ll f(int n) {
  20. return n*(n+1)/2;
  21. }
  22. int main() {
  23. while(1) {
  24.     int n;
  25.     cin >> n;
  26.     if(n==0)break;
  27.     int diff = 1e9; int x = 1,y=n;
  28.     for(int i = 1; i < n; i++) {
  29.         int left = i; int right = n;
  30.         int mid = 0;
  31.         while(right-left > 1) {
  32.              mid = (right+left)>>1;
  33.             int fir = f(mid)-f(i-1);
  34.             int sec = (f(n)-f(mid))+f(i-1);
  35.             if(fir < sec) left = mid;
  36.             else right = mid;
  37.         }
  38.         int newf = f(mid)-f(i-1);
  39.         int news = (f(n)-f(mid))+f(i-1);
  40.         int newd = abs(newf-news);
  41.      //   printf("%d %d %d\n",i,mid,newd);
  42.         if(newd < diff) {
  43.             diff = newd;
  44.             x = i;
  45.             y = mid;
  46.         }
  47.  
  48.     }
  49.     printf("%d %d\n",x,y);
  50. }
  51. return 0;
  52. }
  53.  
Success #stdin #stdout 0s 2732KB
comments (?)
stdin
copy 
12
5
13
0
stdout
copy 
4 9
3 4
1 9
https://ideone.com/GRdOq5
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!