TCO13 Round 1C 생명연장 매치

TCO13 Round1 (Qual Round) 3차까지 가는 졸전끝에 겨우 통과.. 2라운드 진출했다..
아.. 오랜만에 하니깐 잘 안된다.. 요즘 애들 너무 잘해.. ㅠ_ㅠ;;
2라운드는 탈락이 거의 확실시되니.. 블챌이나 신나게 해봐야겠다~~

레이팅은.. 블루로 떨어진지 오래됐음;;

근데 신기하게 이번에 250, 500 둘다 같은 솔루션으로 풀었다..
이거 뭔가.. 출제자 의도가 아닌거같은데;;


Level1 - TheArray

 Problem Statement for TheArray

Problem Statement

    John has an array of n integers. Each pair of neighboring elements differs by at most d. The first and the last elements of the array are equal to first and last, respectively. 

Brus does not know John's array. He only knows n, d, first and last. He wants to compute the maximal possible element John might have in his array. 

You are given ints n, d, first and last. Return the maximal possible element the array might contain.

 

Definition

   

Class: TheArray

Method: find

Parameters: int, int, int, int

Returns: int

Method signature: int find(int n, int d, int first, int last)

(be sure your method is public)

    

 

Notes

- The constraints given below guarantee that there will always be at least one array that matches the values Brus knows.

- For the constraints given below, the correct answer will always fit into an int.

 

Constraints

- n will be between 2 and 1,000,000, inclusive.

- d will be between 0 and 1000, inclusive.

- first will be between -1000 and 1000, inclusive.

- last will be between -1000 and 1000, inclusive.

- |first - last| will be at most (n-1)*d.

 

Examples

0)

   

3

5

2

4

Returns: 7

Only the second element of the array is unknown. Its maximal valid value is 7.

1)

   

10

100

999

100

Returns: 999

Due to the limitations, the first element is the largest element of the array.

2)

   

1000000

0

474

474

Returns: 474

All elements of the array are equal.

3)

   

97

53

-92

441

Returns: 2717

4)

   

99

3

-743

-619

Returns: -535

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

딱히 좋은 방법이 생각나지 않아서.. 무식하게 binary search

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

#define min(x, y) ((x) > (y) ? (y) : (x))

#define max(x, y) ((x) > (y) ? (x) : (y))

//#define INF 999999999

//#define EPS 1e-14

class TheArray {

public:

int find(int n, int d, int first, int last)

{

    int sol;

    int cnt, cnt2;

    int l, r, m;

    int dif;

    if (n == 2)

        return max(first, last);

    sol = max(first, last);

    l = -1000;

    r = 1000000000;

    while (l <= r) {

        m = (l+r) / 2;

        if (m <= first || m <= last) {

            l = m+1;

            sol = m;

            continue;

        }

        if (m > first + (d * (n-2))) {

            r = m-1;

            continue;

        }

        dif = m - first;

        if (dif % d == 0) {

            cnt = dif / d;

        }

        else {

            cnt = dif / d + 1;

        }

        cnt2 = n-1-cnt;

        if (cnt2 <= 0) {

            r = m-1;

            continue;

        }

        if (abs(m-last) <= d * cnt2) {

            l = m+1;

            sol = m;

            continue;

        }

        else {

            r = m-1;

        }

    }

    return max(first, max(last, sol));

}

Level2 - TheOlympiadInInformatics

Problem Statement

    John takes part in a regional olympiad in informatics together with other participants. At the contest each participant gains some nonnegative integer score. Each participant (except for John) is assigned to one of the N contest rooms (numbered from 0 to N-1) and John is the only contestant in the room number N. John has no idea how many participants are in the other rooms. For each of the other rooms he only knows the sum of scores of all participants in it. 

You are given a int[] sums containing N elements and an int k. The i-th element of sums is the sum of participants' scores in the i-th contest room. Return the minimal score John has to gain to be sure that there are at most k participants with strictly higher scores.

 

Definition

   

Class: TheOlympiadInInformatics

Method: find

Parameters: int[], int

Returns: int

Method signature: int find(int[] sums, int k)

(be sure your method is public)

    

 

Constraints

- sums will contain between 1 and 47 elements, inclusive.

- Each element of sums will be between 0 and 1,000,000,000, inclusive.

- k will be between 0 and 1,000,000,000, inclusive.

 

Examples

0)

   

{4, 7, 0, 5}

0

Returns: 7

John has to gain at least 7 points, because there might be a competitor with 7 points in room number 1 (0-based index).

1)

   

{4, 7}

2

Returns: 3

It is possible that there are three contestants who scored more than 2 points: there can be one in room 0 and two more in room 1. There can only be at most two contestants who scored more than 3 points: there can be at most one such contestant in each of the two rooms. (Note that the score of each contestant has to be an integer.) Therefore, John has to score at least 3 points.

2)

   

{999999999}

1000000000

Returns: 0

Here it is enough to gain 0 points.

3)

   

{95, 23, 87, 23, 82, 78, 59, 44, 12}

70

Returns: 6

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

문제 이해를 돕기 위해..
sum = 10 일 경우 내가 10을 먹으면 내가 무조건 1등이지만,
내가 4 일 경우, 다른 방에는 5, 5 가 되서 내가 3등이 될 수 있다..
내가 2 일 경우 ,다른 방에는 3, 3, 3 이 되어 내가 4등이 될 수 있다..

어쨋든 이것도 간단히 binary search

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

#define min(x, y) ((x) > (y) ? (y) : (x))

#define max(x, y) ((x) > (y) ? (x) : (y))

//#define INF 999999999

//#define EPS 1e-14

class TheOlympiadInInformatics {

public:

int find(vector <int> sums, int k)

{

    int n;

    int l, r, m;

    int cnt, sol;

    int i;

    n = sums.size();

    sol = 1000000000;

    l = 0;

    r = 1000000000;

    while (l <= r) {

        m = (l+r)/2;

        cnt = 0;

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

            cnt += sums[i] / (m+1);

            if (cnt > k)

                break;

        }

        if (i == n && cnt <= k) {

            sol = m;

            r = m-1; 

        }

        else {

            l = m+1;

        }

    }

    return sol;

}

};