23 | 12月 | 2017 | 超客的水墨烟雨

uva1591

maksyuki 发表于 oj 分类，标签: 基础算法-枚举

23 12月 2017

Dr. Tuple is working on the new data-mining application for Advanced Commercial Merchandise Inc. One of the subroutines for this application works with two arrays P and Q containing N records of data each (records are numbered from 0 to N − 1). Array P contains hash-like structure with keys. Array P is used to locate record for processing and the data for the corresponding record is later retrieved from the array Q.

All records in array P have a size of SP bytes and records in array Q have size of SQ bytes. Dr. Tuple needs to implement this subroutine with the highest possible performance because it is a hot-spot of the whole data-mining application. However, SP and SQ are only known at run-time of application which complicates or makes impossible to make certain well-known compile-time optimizations.

The straightforward way to find byte-offset of i-th record in array P is to use the following formula:

Pofs(i) = SP · i, (1)

and the following formula for array Q:

Qofs(i) = SQ · i. (2)

However, multiplication computes much slower than addition or subtraction in modern processors. Dr. Tuple avoids usage of multiplication while scanning array P by keeping computed byte-offset Pofs(i) of i-th record instead of its index i in all other data-structures of data-mining application. He uses the following simple formulae when he needs to compute byte-offset of the record that precedes or follows i-th record in array P:

Pofs(i + 1) = Pofs(i) + SP

Pofs(i − 1) = Pofs(i) − SP

Whenever a record from array P is located by either scanning of the array or by taking Pofs(i) from other data structures, Dr. Tuple needs to retrieve information from the corresponding record in array Q. To access record in array Q its byte-offset Qofs(i) needs to be computed. One can immediately derive formula to compute Qofs(i) with known Pofs(i) from formulae (1) and (2):

Qofs(i) = Pofs(i)/SP · SQ (3)

Unfortunately, this formula not only contains multiplication, but also contains division. Even though only integer division is required here, it is still an order of magnitude slower than multiplication on modern processors. If coded this way, its computation is going to consume the most of CPU time in data-mining application for ACM Inc.

After some research Dr. Tuple has discovered that he can replace formula (3) with the following fast formula:

Qofs’(i) = (Pofs(i) + Pofs(i) << A) >> B (4)

where A and B are non-negative integer numbers, “<< A” is left shift by A bits (equivalent to integer multiplication by 2A), “ >> B” is right shift by B bits (equivalent to integer division by 2B).

This formula is an order of magnitude faster than (3) to compute, but it generally cannot always produce the same result as (3) regardless of the choice for values of A and B. It still can be used if one is willing to sacrifice some extra memory.

Conventional layout of array Q in memory (using formula (2)) requires N · SQ bytes to store the entire array. Dr. Tuple has found that one can always choose such K that if he allocates K bytes of memory for the array Q (where K ≤ N · SQ) and carefully selects values for A and B, the fast formula (4) will give non-overlapping storage locations for each of the N records of array Q.

Your task is to write a program that finds minimal possible amount of memory K that needs to be allocated for array Q when formula (4) is used. Corresponding values for A and B are also to be found. If multiple pairs of values for A and B give the same minimal amount of memory K, then the pair where A is minimal have to be found, and if there is still several possibilities, the one where B is minimal. You shall assume that integer registers that will be used to compute formula (4) are wide enough so that overflow will never occur.

Input

Input consists of several datasets. Each dataset consists of three integer numbers N, SP , and SQ separated by spaces (1 ≤ N ≤ 2 20 , 1 ≤ SP ≤ 2 10 , 1 ≤ SQ ≤ 2 10).

Output

For each dataset, write to the output file a single line with three integer numbers K, A, and B separated by spaces.

Sample Input

20 3 5
1024 7 1

Sample Output

119 0 0

1119 2 5

题目类型；简单枚举

算法分析：按照题目要求对A和B暴力枚举即可

/**************************************************
filename       :d.cpp
author         :maksyuki
created time   :2017/12/23 18:54:16
last modified  :2017/12/23 19:01:56
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#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 ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#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 = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    LL n, sp, sq;
    while(scanf("%lld %lld %lld", &n, &sp, &sq) != EOF) {
        LL ans = (1LL << 62);
        LL va = -1, vb = -1;
        for(int i = 0; i < 32; i++)
            for(int j = 0; j < 32; j++) {
                LL tmp = (((n - 1) * sp + (((n - 1) * sp) << i)) >> j) + sq;
                if(tmp >= n * sq && tmp < ans) {
                    ans = tmp;
                    va = i, vb = j;
                }
            }
        printf("%lld %lld %lld\n", ans, va, vb);
    }
    return 0;
}

/**************************************************

filename :d.cpp

author :maksyuki

created time :2017/12/23 18:54:16

last modified :2017/12/23 19:01:56

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#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 ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

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

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#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 = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

LL n, sp, sq;

while(scanf("%lld %lld %lld", &n, &sp, &sq) != EOF) {

LL ans = (1LL << 62);

LL va = -1, vb = -1;

for(int i = 0; i < 32; i++)

for(int j = 0; j < 32; j++) {

LL tmp = (((n - 1) * sp + (((n - 1) * sp) << i)) >> j) + sq;

if(tmp >= n * sq && tmp < ans) {

ans = tmp;

va = i, vb = j;

}

printf("%lld %lld %lld\n", ans, va, vb);

}

return 0;

}

uva12108

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

23 12月 2017

When a student is too tired, he can’t help sleeping in class, even if his favorite teacher is right here in front of him. Imagine you have a class of extraordinarily tired students, how long do you have to wait, before all the students are listening to you and won’t sleep any more? In order to complete this task, you need to understand how students behave.

When a student is awaken, he struggles for a minutes listening to the teacher (after all, it’s too bad to sleep all the time). After that, he counts the number of awaken and sleeping students (including himself). If there are strictly more sleeping students than awaken students, he sleeps for b minutes. Otherwise, he struggles for another a minutes, because he knew that when there is only very few sleeping students, there is a big chance for them to be punished! Note that a student counts the number of sleeping students only when he wants to sleep again.

Now that you understand each student could be described by two integers a and b, the length of awaken and sleeping period. If there are always more sleeping students, these two periods continue again and again. We combine an awaken period with a sleeping period after it, and call the combined period an awaken-sleeping period. For example, a student with a = 1 and b = 4 has an awaken-sleeping period of awaken-sleeping-sleeping-sleeping-sleeping. In this problem, we need another parameter c (1 ≤ c ≤ a + b) to describe a student’s initial condition: the initial position in his awaken-sleeping period. The 1st and 2nd position of the period discussed above are awaken and sleeping, respectively.

Now we use a triple (a, b, c) to describe a student. Suppose there are three students (2, 4, 1), (1, 5, 2) and (1, 4, 3), all the students will be awaken at time 18. The details are shown in the table below.

Write a program to calculate the first time when all the students are not sleeping.

Input

The input consists of several test cases. The first line of each case contains a single integer n (1 ≤ n ≤ 10), the number of students. This is followed by n lines, each describing a student. Each of these lines contains three integers a, b, c (1 ≤ a, b ≤ 5), described above. The last test case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the first time all the students are awaken. If it’ll never happen, output ‘-1’.

Sample Input

3
2 4 1
1 5 2
1 4 3
3
1 2 1
1 2 2
1 2 3
0

Sample Output

Case 1: 18

Case 2: -1

题目类型：简单模拟

算法分析：最大枚举的范围为所有成员周期之积，超出即输出-1，然后对于每个时间位置模拟每个人的操作即可

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2017/12/22 20:10:53
last modified  :2017/12/23 18:27:28
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#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 ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#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 = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

struct node {
    int a, b, c, p;
    int cur;
};

node aa[66];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int n, id = 1;
    while(scanf("%d", &n) != EOF) {
        if(!n) break;
        
        int len = 1;
        for(int i = 1; i <= n; i++) {
            scanf("%d %d %d", &aa[i].a, &aa[i].b, &aa[i].c);
            aa[i].p = aa[i].a + aa[i].b;
            aa[i].cur = aa[i].c;
            len *= aa[i].p;
        }
            
        int ans = -1;
        int awk = 0, slp = 0;
        for(int i = 1; i <= n; i++) {
            if(aa[i].cur <= aa[i].a) awk++;
            else slp++;
        }
        
        int awk_pre = awk, slp_pre = slp;
        for(int i = 2; i <= len; i++) {
            
//            for(int j = 1; j <= n; j++) DB(aa[j].cur);
            for(int j = 1; j <= n; j++) {
                if(aa[j].cur == aa[j].a) {
                    if(awk_pre >= slp_pre) aa[j].cur = 1;
                    else {
                        aa[j].cur++;
                        awk--, slp++;
                    }
                }
                else {
                    if(aa[j].cur == aa[j].p) {
                        aa[j].cur = 1, awk++, slp--;
                    }
                    else aa[j].cur++;
                }
            }
            awk_pre = awk, slp_pre = slp;
//            cout << i << endl;
//            DB(awk), DB(slp);
//            cout << endl;
            if(awk == n) {
                ans = i;
                break;
            }
        }
        
        printf("Case %d: %d\n", id++, ans);

    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

/**************************************************

filename :c.cpp

author :maksyuki

created time :2017/12/22 20:10:53

last modified :2017/12/23 18:27:28

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#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 ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

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

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#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 = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

struct node {

int a, b, c, p;

int cur;

};

node aa[66];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int n, id = 1;

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

if(!n) break;

int len = 1;

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

scanf("%d %d %d", &aa[i].a, &aa[i].b, &aa[i].c);

aa[i].p = aa[i].a + aa[i].b;

aa[i].cur = aa[i].c;

len *= aa[i].p;

}

int ans = -1;

int awk = 0, slp = 0;

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

if(aa[i].cur <= aa[i].a) awk++;

else slp++;

}

int awk_pre = awk, slp_pre = slp;

for(int i = 2; i <= len; i++) {

// for(int j = 1; j <= n; j++) DB(aa[j].cur);

for(int j = 1; j <= n; j++) {

if(aa[j].cur == aa[j].a) {

if(awk_pre >= slp_pre) aa[j].cur = 1;

else {

aa[j].cur++;

awk--, slp++;

}

else {

if(aa[j].cur == aa[j].p) {

aa[j].cur = 1, awk++, slp--;

}

else aa[j].cur++;

}

awk_pre = awk, slp_pre = slp;

// cout << i << endl;

// DB(awk), DB(slp);

// cout << endl;

if(awk == n) {

ans = i;

break;

}

printf("Case %d: %d\n", id++, ans);

}

return 0;

}

超客的水墨烟雨

uva1591

uva12108

分类目录

标签云

书签

近期评论

2017年12月
一	二	三	四	五	六	日
« 3月				1月 »
				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