#125438 (C++11) No.389 ロジックパズルの組み合わせ

提出ソース

結果

問題	No.389 ロジックパズルの組み合わせ
ユーザー	ku_material_ro
提出日時	2016-10-22 03:29:21
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	2,999 bytes
コンパイル時間	643 ms
コンパイル使用メモリ	64,380 KB
実行使用メモリ	15,152 KB
最終ジャッジ日時	2024-11-23 17:03:52
合計ジャッジ時間	142,879 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 8,320 KB
testcase_01	AC	2 ms 8,448 KB
testcase_02	AC	1 ms 10,496 KB
testcase_03	AC	2 ms 8,576 KB
testcase_04	TLE	-
testcase_05	AC	1 ms 8,576 KB
testcase_06	AC	2 ms 10,496 KB
testcase_07	AC	2 ms 8,704 KB
testcase_08	AC	2 ms 8,704 KB
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	AC	32 ms 10,496 KB
testcase_13	AC	1,483 ms 8,576 KB
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	WA	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	AC	2 ms 10,496 KB
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	AC	2 ms 8,448 KB
testcase_34	TLE	-
testcase_35	TLE	-
testcase_36	TLE	-
testcase_37	TLE	-
testcase_38	TLE	-
testcase_39	TLE	-
testcase_40	TLE	-
testcase_41	TLE	-
testcase_42	TLE	-
testcase_43	TLE	-
testcase_44	TLE	-
testcase_45	AC	2 ms 10,496 KB
testcase_46	TLE	-
testcase_47	TLE	-
testcase_48	TLE	-
testcase_49	TLE	-
testcase_50	AC	19 ms 10,496 KB
testcase_51	AC	13 ms 9,644 KB
testcase_52	AC	195 ms 10,496 KB
testcase_53	AC	40 ms 10,160 KB
testcase_54	AC	327 ms 9,648 KB
testcase_55	AC	2 ms 9,852 KB
testcase_56	AC	28 ms 9,776 KB
testcase_57	AC	954 ms 5,248 KB
testcase_58	TLE	-
testcase_59	TLE	-
testcase_60	AC	469 ms 5,248 KB
testcase_61	TLE	-
testcase_62	AC	486 ms 5,248 KB
testcase_63	TLE	-
testcase_64	AC	300 ms 5,248 KB
testcase_65	AC	99 ms 5,248 KB
testcase_66	AC	330 ms 5,248 KB
testcase_67	AC	293 ms 5,248 KB
testcase_68	AC	356 ms 5,248 KB
testcase_69	AC	1 ms 5,248 KB
testcase_70	AC	2 ms 5,248 KB
testcase_71	AC	2 ms 5,248 KB
testcase_72	AC	2 ms 5,248 KB
testcase_73	AC	1 ms 5,248 KB
testcase_74	AC	1 ms 5,248 KB
testcase_75	AC	2 ms 5,248 KB
testcase_76	AC	2 ms 5,248 KB
testcase_77	AC	2 ms 5,248 KB
testcase_78	AC	2 ms 5,248 KB
testcase_79	AC	2 ms 5,248 KB
testcase_80	AC	2 ms 5,248 KB
testcase_81	AC	1 ms 5,248 KB
testcase_82	AC	2 ms 5,248 KB
testcase_83	AC	2 ms 5,248 KB
testcase_84	AC	2 ms 5,248 KB
testcase_85	AC	2 ms 5,248 KB
testcase_86	AC	2 ms 5,248 KB
testcase_87	AC	1 ms 5,248 KB
testcase_88	AC	1 ms 5,248 KB
testcase_89	AC	655 ms 5,248 KB
testcase_90	AC	1,747 ms 5,248 KB
testcase_91	TLE	-
testcase_92	AC	106 ms 5,248 KB
testcase_93	TLE	-
testcase_94	AC	2 ms 5,248 KB
testcase_95	TLE	-
testcase_96	AC	1,410 ms 5,248 KB
testcase_97	AC	1,260 ms 5,248 KB
testcase_98	AC	332 ms 9,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std;

int kaijo(long a){
	long n=1;
	if (a > 0){
		for (long i = a; i > 0; i--){
			n *= i;
			n = n % 1000000007;
		}
	}
	else{
		n = 1;
	}
	return n;
}

int permtation(long a,long b){
	long n = 1;
	if (b != 0){
		for (long i = 0; i < b; i++){
			n *= (a-i);
			n = n % 1000000007;
		}
	}
	else{
		n = 1;
	}
	return n;
}

int main(){
	long m;
	long p1;
	long a = 0;
	long sho;
	long amari;
	long cnt2=0;
	string s;
	string s1;
	long h;
	long cnt = 0;
	long ans;
	long p, k;
	int flag=0;
	cin >> m;
	cin.ignore();
	getline(cin, s);
	if (s == "0") flag = 1;
	while (1){
		s1 = s;
		//cout << s1 << endl;
		a = s1.find(" ", 0);
		if (a == -1){
			h = stoi(s1);
			m -= h;
			cnt++;
			break;
		}
		else{
			s1.erase(a,s1.length());
			h = stoi(s1);
			m -= h;
			cnt++;
			s.erase(0, a + 1);
			//cout << s << endl;
		}
	}
	long judge = m - cnt + 1;
	//cout << m << endl;
	//cout << cnt << endl;
	//cout << judge << endl;
	if (flag == 1){
		cout << "1" << endl;
	}else if (judge <0){
		cout << "NA" << endl;
	}
	else{
		if (judge>cnt){
			p = permtation(m + 1, cnt);
			k = kaijo(cnt);
			
			while (1){
				ans = p / k;
				if (ans*k == p){
					cout << ans << endl;
					break;
				}
				else{
					if (p <k){
						p1 = p;
						while (1){
							sho = (k - p1) / (1000000007 / k);
							amari = (k - p1) %(1000000007 / k);
							if (amari == 0){
								cnt2 += sho;
								break;
							}
							else{
								cnt2 += sho + 1;
								p1 = (p1 + (sho + 1) * 1000000007 / k) - k;
							}
						}
						p += 1000000007 * cnt2;
					}
					if (p >k){
						p1 = p-k;
						while (1){
							sho = (k - p1) / (1000000007 / k);
							amari = (k - p1) % (1000000007 / k);
							if (amari == 0){
								cnt2 += sho;
								break;
							}
							else{
								cnt2 += sho + 1;
								p1 = (p1 + (sho + 1) * 1000000007 / k) - k;
							}
						}
						p += 1000000007 * cnt2;
					}
				}
			}
		}
		else{
			p = permtation(m + 1, judge);
			k = kaijo(judge);
			
			while (1){
				ans = p / k;
				if (ans*k == p){
					cout << ans << endl;
					break;
				}
				else{
					if (p <k){
						p1 = p;
						while (1){
							sho = (k - p1) / (1000000007 / k);
							amari = (k - p1) % (1000000007 / k);
							if (amari == 0){
								cnt2 += sho;
								break;
							}
							else{
								cnt2 += sho + 1;
								p1 = (p1 + (sho + 1) * 1000000007 / k) - k;
							}
						}
						p += 1000000007 * cnt2;
					}
					if (p >k){
						p1 = p - k;
						while (1){
							sho = (k - p1) / (1000000007 / k);
							amari = (k - p1) % (1000000007 / k);
							if (amari == 0){
								cnt2 += sho;
								break;
							}
							else{
								cnt2 += sho + 1;
								p1 = (p1 + (sho + 1) * 1000000007 / k) - k;
							}
						}
						p += 1000000007 * cnt2;
					}
				}
			}
		}
		//ans = kaijo(m + 1) / (kaijo(m - cnt + 1)*kaijo(cnt));
		//cout << ans << endl;
		//cout << m << endl;
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード