Рус Uzb Eng

C15C. Perestanovka
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

TATU talabasi Abdulla informatika fanidan masalalar ishlashga juda ham qiziqadi. U yaqinda codeforces.ru saytidan “Farqli perestanovka” masalasini ishlaganda vaqt limiti oldi. Bu masala sharti quyidagicha: Perestanovka p deb n ta bir-biridan farqli va qiymati 1<= pi <=n oraliqda bo’lgan musbat butun sonlardan tashkil topgan p1, p2, …, pn ketma-ketlikka aytiladi. n bu p1, p2, …, pn perestanovkaning uzunligini bildiradi. Sizning vazifangiz uzunligi n ga teng bo’lgan shunday p ning perestanovkasini topingki bunda |p1-p2|, |p2-p3|, ..., |pn-1-pn| qiymatlar to’plami k ta bir – biridan farqli sonlardan iborat bo’lsin. Bu masalani Abdulla quyidagicha ishladi, va uning do{}while(); qismi necha marta ishlaganini tekshirish maqsadida buni count o’zgaruvchisida sanadi :
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
int count = 0;
void solve(int n, int k){
	int *a = new int[n];
	for(int i = 0; i < n; i ++) a[i] = i + 1;
	setb;
	do{
		b.clear();
		count ++;
		for(int i = 1; i < n; i ++) b.insert(abs(a[i] - a[i-1]));
		if(b.size() == k) return break;
	}while(next_permutation(a,a+n));
	for(int i = 0; i < n; i ++) cout << a[i] << “ ”;
}
int main(){
 	int n, k;
	cin >> n >> k;
	solve(n,k);
	return 0;
}
Abdulla bu yechimi oxirida cout << count; qo’yib count ning oxirgi natijasini ko’rmoqchi bo’ldi. Ammo uning dasturi juda sekin ishlashi bois ko’p natijalarni juda sekin topyapti. Abdullaga dasturi tugaganida count ning oxirgi qiymatini topishga yordam bering.

Входные данные:
Bitta qatorda 2 ta butun n va k soni kiritiladi (1 <= k < n);

Выходные данные:
Bitta butun son count ning dastur nihoyasidagi qiymatini chiqaring. Bunda qiymat juda katta bo’lib ketishi mumkin shuning uchun uni 1000000007 (1e9 + 7) ga bo’lgandagi qoldiqni chiqaring.

Пример ввода Пример вывода
3 2
3 1
5 2
5 4
2
1
2
20
Область: Kombinatorika
Источник задачи: Sunnat TUIT

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.