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

uva1583

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

01 12月 2017

For a positive integer N, the digit-sum of N is defined as the sum of N itself and its digits. When M is the digitsum of N, we call N a generator of M.

For example, the digit-sum of 245 is 256 (= 245 + 2 + 4 + 5). Therefore, 245 is a generator of 256. Not surprisingly, some numbers do not have any generators and some numbers have more than one generator. For example, the generators of 216 are 198 and 207.

You are to write a program to find the smallest generator of the given integer.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case takes one line containing an integer N, 1 ≤ N ≤ 100, 000.

Output

Your program is to write to standard output. Print exactly one line for each test case. The line is to contain a generator of N for each test case. If N has multiple generators, print the smallest. If N does not have any generators, print ‘0’.

Sample Input

216

121

2005

Sample Output

198

1979

题目类型：简单数学

算法分析：可以先预处理，用ans[i]表示i的最小generator的值，初始化为0，然后从1~100000+6枚举每个数。对于每个数计算其digit-sum，判断ans[digit-sum]是否比当前的大，大的话就更新。注意ans[digit-sum]=0时需特判

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/12/1 12:27:04
last modified  :2017/12/1 12:35:06
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 ans[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    memset(ans, 0, sizeof(ans));
    for(int i = 1; i <= maxn - 6; i++) {
        int v = i, tmp = i;
        while(tmp) {
            v += tmp % 10;
            tmp /= 10;
        }
        if(!ans[v] || ans[v] > i) ans[v] = i;
    }


    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}

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

filename :e.cpp

author :maksyuki

created time :2017/12/1 12:27:04

last modified :2017/12/1 12:35:06

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 ans[maxn];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

memset(ans, 0, sizeof(ans));

for(int i = 1; i <= maxn - 6; i++) {

int v = i, tmp = i;

while(tmp) {

v += tmp % 10;

tmp /= 10;

}

if(!ans[v] || ans[v] > i) ans[v] = i;

}

int t;

scanf("%d", &t);

while(t--) {

int n;

scanf("%d", &n);

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

}

return 0;

}

uva340

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

01 12月 2017

MasterMind is a game for two players. One of them, Designer, selects a secret code. The other, Breaker, tries to break it. A code is no more than a row of colored dots. At the beginning of a game, the players agree upon the length N that a code must have and upon the colors that may occur in a code.

In order to break the code, Breaker makes a number of guesses, each guess itself being a code. After each guess Designer gives a hint, stating to what extent the guess matches his secret code.

In this problem you will be given a secret code s1 . . . sn and a guess g1 . . . gn, and are to determine the hint. A hint consists of a pair of numbers determined as follows.

A match is a pair (i, j), 1 ≤ i ≤ n and 1 ≤ j ≤ n, such that si = gj . Match (i, j) is called strong when i = j, and is called weak otherwise. Two matches (i, j) and (p, q) are called independent when i = p if and only if j = q. A set of matches is called independent when all of its members are pairwise independent.

Designer chooses an independent set M of matches for which the total number of matches and the number of strong matches are both maximal. The hint then consists of the number of strong followed by the number of weak matches in M. Note that these numbers are uniquely determined by the secret code and the guess. If the hint turns out to be (n, 0), then the guess is identical to the secret code.

Input

The input will consist of data for a number of games. The input for each game begins with an integer specifying N (the length of the code). Following these will be the secret code, represented as N integers, which we will limit to the range 1 to 9. There will then follow an arbitrary number of guesses, each also represented as N integers, each in the range 1 to 9. Following the last guess in each game will be N zeroes; these zeroes are not to be considered as a guess.

Following the data for the first game will appear data for the second game (if any) beginning with a new value for N. The last game in the input will be followed by a single ‘0’ (when a value for N would normally be specified). The maximum value for N will be 1000.

Output

The output for each game should list the hints that would be generated for each guess, in order, one hint per line. Each hint should be represented as a pair of integers enclosed in parentheses and separated by a comma. The entire list of hints for each game should be prefixed by a heading indicating the game number; games are numbered sequentially starting with 1. Look at the samples below for the exact format.

Sample Input

4
1 3 5 5
1 1 2 3
4 3 3 5
6 5 5 1
6 1 3 5
1 3 5 5
0 0 0 0
10
1 2 2 2 4 5 6 6 6 9
1 2 3 4 5 6 7 8 9 1
1 1 2 2 3 3 4 4 5 5
1 2 1 3 1 5 1 6 1 9
1 2 2 5 5 5 6 6 6 7
0 0 0 0 0 0 0 0 0 0
0

Sample Output

Game 1:
(1,1)
(2,0)
(1,2)
(1,2)
(4,0)
Game 2:
(2,4)
(3,2)
(5,0)
(7,0)

题目类型：简单数学

算法分析：ans1直接对比对应位上的值是否相等，ans2需要计算1~9中每个数字对在两个位子上出现次数的贡献，然后减去对应位上相同的，剩下的就是对应位上不同但出现的个数

/**************************************************
filename       :d.cpp
author         :maksyuki
created time   :2017/12/1 11:55:08
last modified  :2017/12/1 12:13:03
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 v[maxn], p[maxn];
int cnt1[16], cnt2[16];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif

    int n, id = 1;
    while(scanf("%d", &n) != EOF) {
        if(!n) return 0;

        for(int i = 1; i <= n; i++) scanf("%d", &v[i]);
        
        printf("Game %d:\n", id++);
        while(1) {
            for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
            if(!p[1]) break;
            memset(cnt1, 0, sizeof(cnt1));
            memset(cnt2, 0, sizeof(cnt2));
            int ans1 = 0, ans2 = 0;
            for(int i = 1; i <= n; i++) {
                if(v[i] == p[i]) ans1++;
                cnt1[v[i]]++, cnt2[p[i]]++;
            }
            
            for(int i = 1; i <= 9; i++) ans2 += min(cnt1[i], cnt2[i]);
            printf("    (%d,%d)\n", ans1, ans2 - ans1);            
        }
        
    }
    return 0;
}

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

filename :d.cpp

author :maksyuki

created time :2017/12/1 11:55:08

last modified :2017/12/1 12:13:03

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 v[maxn], p[maxn];

int cnt1[16], cnt2[16];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int n, id = 1;

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

if(!n) return 0;

for(int i = 1; i <= n; i++) scanf("%d", &v[i]);

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

while(1) {

for(int i = 1; i <= n; i++) scanf("%d", &p[i]);

if(!p[1]) break;

memset(cnt1, 0, sizeof(cnt1));

memset(cnt2, 0, sizeof(cnt2));

int ans1 = 0, ans2 = 0;

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

if(v[i] == p[i]) ans1++;

cnt1[v[i]]++, cnt2[p[i]]++;

}

for(int i = 1; i <= 9; i++) ans2 += min(cnt1[i], cnt2[i]);

printf(" (%d,%d)\n", ans1, ans2 - ans1);

}

return 0;

}

uva10082

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

01 12月 2017

A common typing error is to place the hands on the keyboard one row to the right of the correct position. So ‘Q’ is typed as ‘W’ and ‘J’ is typed as ‘K’ and so on. You are to decode a message typed in this manner.

Input

Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (‘)]. Keys labelled with words [Tab, BackSp, Control, etc.] are not represented in the input.

Output

You are to replace each letter or punction symbol by the one immediately to its left on the ‘QWERTY’ keyboard shown above. Spaces in the input should be echoed in the output.

Sample Input

O S, GOMR YPFSU/

Sample Output

I AM FINE TODAY.

题目类型：字符处理题

算法分析：本题使用常量数组保存键盘的字符位置，然后对于每次查询直接判断输出，注意空格和回车的处理

/**************************************************
filename       :b.cpp
author         :maksyuki
created time   :2017/12/1 11:13:10
last modified  :2017/12/1 11:21:27
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;

char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int c;
    while((c = fgetc(stdin)) != EOF) {
        int p;
        if(c == ' ' || c == '\n') {
            putchar(c);
            continue;
        }
        for(p = 0; s[p] && c != s[p]; p++);
        putchar(s[p-1]);
    }
    return 0;
}

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

filename :b.cpp

author :maksyuki

created time :2017/12/1 11:13:10

last modified :2017/12/1 11:21:27

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;

char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int c;

while((c = fgetc(stdin)) != EOF) {

int p;

if(c == ' ' || c == '\n') {

putchar(c);

continue;

}

for(p = 0; s[p] && c != s[p]; p++);

putchar(s[p-1]);

}

return 0;

}

一	二	三	四	五	六	日
« 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

超客的水墨烟雨

uva1583

uva340

uva10082

分类目录

标签云

书签

近期评论