15 | 10月 | 2015 | 超客的水墨烟雨

poj2739

maksyuki 发表于 oj 分类，标签: 其他-追逐法

15 10月 2015

Sum of Consecutive Prime Numbers

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime
numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.
Your mission is to write a program that reports the number of representations for the given positive integer.

Input

The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.

Output

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.

Sample Input

2
3
17
41
20
666
12
53
0

Sample Output

Source

Japan 2005

题目类型：追逐法

算法分析：维护两个指针分别指向区间的头和尾，当前区间(素数序列)的和小于n，则移动尾指针并加上尾指针所指向的数，否则从区间删去头指针所指向的数

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 6666;

int primelist[maxn], len;
bool prime[maxn];

void PP ()
{
    memset (prime, true, sizeof (prime));
    len = 0;
    prime[0] = prime[1] = false;
    for (int i = 2; i < maxn; i++)
    {
        if (prime[i])
            primelist[len++] = i;

        for (int j = 0; j < len; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}

int main()
{
//    CFF;
    PP ();
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        if (n == 0)
            break;

        int res = 0, pa = 0, pb = 0, sum = 0;
        while (1)
        {
            while (pb < len && sum < n)
            {
                sum += primelist[pb++];
            }

            if (sum == n) res++;

            if (pa == pb) break;
            sum -= primelist[pa++];
        }

        printf ("%d\n", res);
    }
    return 0;
}

100

101

102

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6666;

int primelist[maxn], len;

bool prime[maxn];

void PP ()

{

memset (prime, true, sizeof (prime));

len = 0;

prime[0] = prime[1] = false;

for (int i = 2; i < maxn; i++)

{

if (prime[i])

primelist[len++] = i;

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

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

int main()

{

// CFF;

PP ();

int n;

while (scanf ("%d", &n) != EOF)

{

if (n == 0)

break;

int res = 0, pa = 0, pb = 0, sum = 0;

while (1)

{

while (pb < len && sum < n)

{

sum += primelist[pb++];

}

if (sum == n) res++;

if (pa == pb) break;

sum -= primelist[pa++];

}

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

}

return 0;

}

poj3421

maksyuki 发表于 oj 分类，标签: 数论-素因子分解, 组合数学-计数

15 10月 2015

X-factor Chains

Given a positive integer X, an X-factor chain of length m is a sequence of integers, 1 = X₀, X₁, X₂, …, X_m = X satisfying X_i < X_i₊₁ and X_i | X_i₊₁ where a | b means a perfectly divides into b. Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

Input

The input consists of several test cases. Each contains a positive integer X (X ≤ 2²⁰).

Output

For each test case, output the maximum length and the number of such X-factors chains.

Sample Input

2
3
4
10
100

Sample Output

1 1

2 1

2 2

4 6

Source

POJ Monthly--2007.10.06, ailyanlu@zsu

题目类型：整数素因子分解+组合计数

算法分析：为了得到最长的序列，除了头尾1和n之外，其他的约数应该按照递增排列且后一个约数要比前一个恰好多一个素因子，这样才能保证得到的序列是最长的。最长序列的数目是素因子幂和的可重排列(即素因子幂之和的阶乘/每个素因子幂的阶乘)

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e7 + 48579;

LL fac[27];

void PP ()
{
    fac[1] = 1;
    for (LL i = 2; i <= 21; i++)
        fac[i] = fac[i-1] * i;
}

int aa[maxn], len;

int main()
{
//    CFF;
    PP ();
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        int res = 0;
        len = 0;
        for (int i = 2; i * i <= n; i++)
        {
            while (n % i == 0)
            {
                n /= i;
                aa[len++] = i;
                res++;
            }
        }

        if (n > 1)
        {
            aa[len++] = n;
            res++;
        }

        LL ans = fac[res], tt = 0;
        for (int i = 1; i < len; )
        {
            if (aa[i-1] == aa[i])
            {
                while (i < len && aa[i-1] == aa[i])
                {
                    tt++;
                    i++;
                }
            }

            else
            {
                ans /= fac[tt+1];
                tt = 0;
                i++;
            }
        }

        if (tt)
            ans /= fac[tt+1];

        printf ("%d %lld\n", res, ans);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e7 + 48579;

LL fac[27];

void PP ()

{

fac[1] = 1;

for (LL i = 2; i <= 21; i++)

fac[i] = fac[i-1] * i;

}

int aa[maxn], len;

int main()

{

// CFF;

PP ();

int n;

while (scanf ("%d", &n) != EOF)

{

int res = 0;

len = 0;

for (int i = 2; i * i <= n; i++)

{

while (n % i == 0)

{

n /= i;

aa[len++] = i;

res++;

}

if (n > 1)

{

aa[len++] = n;

res++;

}

LL ans = fac[res], tt = 0;

for (int i = 1; i < len; )

{

if (aa[i-1] == aa[i])

{

while (i < len && aa[i-1] == aa[i])

{

tt++;

i++;

}

else

{

ans /= fac[tt+1];

tt = 0;

i++;

}

if (tt)

ans /= fac[tt+1];

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

}

return 0;

}

poj3292

maksyuki 发表于 oj 分类，标签: 数论-筛法

15 10月 2015

Semi-prime H-numbers

An H-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,... are the H-numbers. For this problem we pretend that these are the only numbers. The H-numbers are closed under multiplication.This problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of 4n+1 numbers. Here, we do only a bit of that.

As with regular integers, we partition the H-numbers into units, H-primes, and H-composites. 1 is the only unit. An H-number h is H-prime if it is not the unit, and is the product of two H-numbers in only one way: 1 × h. The rest of the numbers are H-composite.

For examples, the first few H-composites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.

Your task is to count the number of H-semi-primes. An H-semi-prime is an H-number which is the product of exactly two H-primes. The two H-primes may be equal or different. In the example above, all five numbers are H-semi-primes. 125 = 5 × 5 × 5 is not an H-semi-prime, because it's the product of three H-primes.

Input

Each line of input contains an H-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.

Output

For each inputted H-number h, print a line stating h and the number of H-semi-primes between 1 and h inclusive, separated by one space in the format shown in the sample.

Sample Input

21
85
789
0

Sample Output

21 0

85 5

789 62

Source

Waterloo Local Contest, 2006.9.30

题目类型：Euler筛法

算法分析：将每个H-素数定义好后，使用类似Euler筛法的思想预打表，维护前缀和并查询

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

int primelist[maxn], len, sum[maxn];
bool prime[maxn];

void PP()
{
    memset (sum, 0, sizeof (sum));
    memset (prime, true, sizeof (prime));
    len = 0;
    prime[0] = prime[1] = false;
    for (int i = 5; i < maxn; i += 4)
    {
        if (prime[i])
            primelist[len++] = i;

        for (int j = 0; j < len; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            if (prime[i] && prime[primelist[j]])
                sum[i*primelist[j]] = 1;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
    for (int i = 1; i < maxn; i++)
        sum[i] += sum[i-1];
}

int main()
{
//    CFF;
    PP ();
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        if (n == 0)
            break;

        printf ("%d %d\n", n, sum[n]);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

int primelist[maxn], len, sum[maxn];

bool prime[maxn];

void PP()

{

memset (sum, 0, sizeof (sum));

memset (prime, true, sizeof (prime));

len = 0;

prime[0] = prime[1] = false;

for (int i = 5; i < maxn; i += 4)

{

if (prime[i])

primelist[len++] = i;

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

{

if (i * primelist[j] > maxn)

break;

if (prime[i] && prime[primelist[j]])

sum[i*primelist[j]] = 1;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

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

sum[i] += sum[i-1];

}

int main()

{

// CFF;

PP ();

int n;

while (scanf ("%d", &n) != EOF)

{

if (n == 0)

break;

printf ("%d %d\n", n, sum[n]);

}

return 0;

}

poj3273

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

15 10月 2015

Monthly Expense

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ money_i≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

Output

Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500

Hint

If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.

Source

USACO 2007 March Silver

题目类型：二分搜索

算法分析：直接二分每个fajmoonth的最大钱数，注意二分部分的写法！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

int aa[maxn], n, m;

bool PP (int val)
{
    int res = 1, tt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (tt + aa[i] <= val)
        {
            tt += aa[i];
        }

        else
        {
            res++;
            tt = aa[i];
        }
    }

    if (res > m) return true;
    else return false;
}

int main()
{
//    CFF;
    while (scanf ("%d%d", &n, &m) != EOF)
    {
        int l = 0, r = 0, mid;
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d", &aa[i]);
            r += aa[i];
            if (l < aa[i]) l = aa[i];
        }
        r += 5;
        while (l < r)
        {
            mid = (l + r) >> 1;
            if (PP (mid)) l = mid + 1;
            else r = mid - 1;
        }
        printf ("%d\n", r);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

int aa[maxn], n, m;

bool PP (int val)

{

int res = 1, tt = 0;

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

{

if (tt + aa[i] <= val)

{

tt += aa[i];

}

else

{

res++;

tt = aa[i];

}

if (res > m) return true;

else return false;

}

int main()

{

// CFF;

while (scanf ("%d%d", &n, &m) != EOF)

{

int l = 0, r = 0, mid;

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

{

scanf ("%d", &aa[i]);

r += aa[i];

if (l < aa[i]) l = aa[i];

}

r += 5;

while (l < r)

{

mid = (l + r) >> 1;

if (PP (mid)) l = mid + 1;

else r = mid - 1;

}

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

}

return 0;

}

poj3258

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

15 10月 2015

River Hopscotch

Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance D_i from the start (0 < D_i < L).

To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.

Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).

FJ wants to know exactly how much he can increase the shortest distance *before* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

Input

Line 1: Three space-separated integers: L, N, and M
Lines 2..N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.

Output

Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks

Sample Input

25 5 2
2
14
11
21
17

Sample Output

Hint

Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).

Source

USACO 2006 December Silver

题目类型：二分搜索

算法分析：二分两个石块之间的最小值，每次计算以这个值是否能够安排n-m个石块

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

int aa[maxn], L, n, m;

bool PP (int val)
{
    int res = 2, tt = 0;
    aa[n+1] = L;
    for (int i = 1; i <= n + 1; i++)
    {
        if (aa[i] - aa[tt] >= val)
        {
            res++;
            tt = i;
        }
    }

    if (res > n - m + 2) return true;
    else return false;
}

int main()
{
//    CFF;
    while (scanf ("%d%d%d", &L, &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
            scanf ("%d", &aa[i]);
        sort (aa + 1, aa + 1 + n);
        int l = 0, r = L + 6, mid;
        while (r - l > 1)
        {
            mid = (l + r) >> 1;
            if (PP(mid)) l = mid;
            else r = mid;
        }

        printf ("%d\n", l);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

int aa[maxn], L, n, m;

bool PP (int val)

{

int res = 2, tt = 0;

aa[n+1] = L;

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

{

if (aa[i] - aa[tt] >= val)

{

res++;

tt = i;

}

if (res > n - m + 2) return true;

else return false;

}

int main()

{

// CFF;

while (scanf ("%d%d%d", &L, &n, &m) != EOF)

{

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

scanf ("%d", &aa[i]);

sort (aa + 1, aa + 1 + n);

int l = 0, r = L + 6, mid;

while (r - l > 1)

{

mid = (l + r) >> 1;

if (PP(mid)) l = mid;

else r = mid;

}

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

}

return 0;

}

超客的水墨烟雨

poj2739

poj3421

poj3292

poj3273

poj3258

分类目录

标签云

书签

近期评论

2015年10月
一	二	三	四	五	六	日
« 9月				11月 »
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31