[Google Code Jam]2016_Qualification Round_ProblemC_Coin Jam

문제 출처 : https://code.google.com/codejam/contest/6254486/dashboard#s=p2

+)i solve only small dataset (Cannot solve problem perfectly)

Problem

A jamcoin is a string of N ≥ 2 digits with the following properties:

• Every digit is either 0 or 1.
• The first digit is 1 and the last digit is 1.
• If you interpret the string in any base between 2 and 10, inclusive, the resulting number is not prime.

Not every string of 0s and 1s is a jamcoin. For example, 101 is not a jamcoin; its interpretation in base 2 is 5, which is prime. But the string 1001 is a jamcoin: in bases 2 through 10, its interpretation is 9, 28, 65, 126, 217, 344, 513, 730, and 1001, respectively, and none of those is prime.

We hear that there may be communities that use jamcoins as a form of currency. When sending someone a jamcoin, it is polite to prove that the jamcoin is legitimate by including a nontrivial divisor of that jamcoin's interpretation in each base from 2 to 10. (A nontrivial divisor for a positive integer K is some positive integer other than 1 or K that evenly divides K.) For convenience, these divisors must be expressed in base 10.

For example, for the jamcoin 1001 mentioned above, a possible set of nontrivial divisors for the base 2 through 10 interpretations of the jamcoin would be: 3, 7, 5, 6, 31, 8, 27, 5, and 77, respectively.

Can you produce J different jamcoins of length N, along with proof that they are legitimate?

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with two integers N and J.

Output

For each test case, output J+1 lines. The first line must consist of only Case #x:, where xis the test case number  (starting from 1). Each of the last J lines must consist of a jamcoin of length N followed by nine integers. The i-th of those nine integers (counting starting from 1) must be a nontrivial divisor of the jamcoin when the jamcoin is interpreted in base i+1.

All of these jamcoins must be different. You cannot submit the same jamcoin in two different lines, even if you use a different set of divisors each time.

Limits

T = 1. (There will be only one test case.)
It is guaranteed that at least J distinct jamcoins of length N exist.

Small dataset

N = 16.
J = 50.

Large dataset

N = 32.
J = 500.

#include <iostream> #include <vector> #include <math.h> #include <fstream> using namespace std; vector<unsigned long long> digit; vector<unsigned long long> answer; fstream fout; int for_count, answer_count, digit_count; void erase_vector(); int check_divisor(unsigned long long num); unsigned long long make_decimal(int num); int make_result(); void change_decimal_to_binary(int num) { while (num != 0) { digit.push_back(num % 2); num /= 2; } while (digit.size()<digit_count - 2) { digit.push_back(0); } reverse(digit.begin(), digit.end()); } void change_digit() { for (unsigned long long j = 0; j < pow(2, digit_count - 2); j++) { change_decimal_to_binary(j); digit.insert(digit.begin(), 1); digit.insert(digit.end(), 1); if (make_result()) break; digit.clear(); } } int check_divisor(unsigned long long num) { for (int j = 2; j <= sqrt(num); j++) { if ((num % j == 0) && answer.empty() == 0) { vector<unsigned long long>::iterator iter; iter = find(answer.begin(), answer.end(), j); if (iter == answer.end()) { answer.push_back(j); return 0; } iter = find(answer.begin(), answer.end(), num / j); if (iter == answer.end()) { answer.push_back(num / j); return 0; } } if ((num % j == 0) && answer.empty()) { answer.push_back(j); return 0; } } return 1; } unsigned long long make_decimal(int num) { unsigned long long number = 0; int number_pow = 0; for (int j = digit.size() - 1; j >= 0; j--) { number += digit[j] * pow(num, number_pow); number_pow++; } return number; } int make_result() { for (int m = 2; m < 11; m++) { if (check_divisor(make_decimal(m))) { answer.clear(); break; } } if (!answer.empty()) { cout << answer_count << " "; answer_count--; for (int m = 0; m < digit.size(); m++) fout << digit[m]; for (int m = 0; m < 9; m++) { fout << " " << answer[m]; } fout << endl; } answer.clear(); if (answer_count <= 0) { return 1; } else { return 0; } } int main() { ifstream fcin; fcin.open("problemc_small_input.txt"); fcin >> for_count; fout.open("problemc_small_output.txt"); for (int i = 0; i < for_count; i++) { fcin >> digit_count >> answer_count; fout << "Case #" << i + 1 << ":" << endl; change_digit(); } system("pause"); }