#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <random>
#include <string>
using namespace std;
void ScoreCalicurater(string inputTextFile,string OutputTextFile,long long int MagicTimes) {
ifstream inputFileA(inputTextFile);
cin.rdbuf(inputFileA.rdbuf());
long long int N, M, K;
cin >> N >> M >> K;
vector<long long int> MonsterPower(N);
for (int i = 0; i < N; i++) {
cin >> MonsterPower[i];
}
ifstream inputFile(OutputTextFile);
cin.rdbuf(inputFile.rdbuf());
int zerocount = 0;
for (int i = 0; i < MagicTimes; i++) {
int p, q;
cin >> p >> q;
MonsterPower[p] = (MonsterPower[p] + MonsterPower[q]) % K;
}
long double Score=0;
for (auto A:MonsterPower) {
Score += log2l(K)-log2l(A+1);
if (A == 0) { zerocount++; }
}
Score = ceil(Score);
if (zerocount>=MonsterPower.size()-1) {
Score += M - MagicTimes;
}
cout << Score;
}
struct MonsterInfo
{
long long int Power;
long long int Number;
bool operator<(const MonsterInfo& right) const {
if (Power<right.Power) {
return true;
}
else {
return false;
}
}
};
bool PowerUpMonstersNtimes(long long int& MagicTimes,
vector<MonsterInfo>& Monsters, long long int K, int GroupNumber, long long int difflimit) {
//sort(Monsters.begin(),Monsters.end());
//reverse(Monsters.begin(), Monsters.end());
for (int i = 0; i < pow(Monsters.size(), GroupNumber);i++) {
if (MagicTimes<GroupNumber) {
return false;
}
vector<int> eachOrderNumber(GroupNumber);
for (int k = 0; k < GroupNumber;k++) {
eachOrderNumber[k] = ((int)(i / pow(GroupNumber, k))) % Monsters.size();
}
long long int SumPower=0;
for (auto p : eachOrderNumber) {
SumPower = (SumPower + Monsters[p].Power) % K;
}
if (SumPower+difflimit<Monsters[eachOrderNumber[0]].Power) {
Monsters[eachOrderNumber[0]].Power = SumPower;
for (int k = 1; k < GroupNumber;k++ ) {
cout << eachOrderNumber[0] << " " << eachOrderNumber[k]<<endl;
}
MagicTimes =MagicTimes - ((long long int)GroupNumber - 1);
}
}
return true;
}
bool PowerUpMonstersNtimesStringVer(long long int& MagicTimes,
vector<MonsterInfo>& Monsters, long long int K, int GroupNumber,
long long int difflimit,string& mess) {
//sort(Monsters.begin(),Monsters.end());
//reverse(Monsters.begin(), Monsters.end());
for (int i = 0; i < pow(Monsters.size(), GroupNumber); i++) {
if (MagicTimes < GroupNumber) {
return false;
}
vector<int> eachOrderNumber(GroupNumber);
for (int k = 0; k < GroupNumber; k++) {
eachOrderNumber[k] = ((int)(i / pow(GroupNumber, k))) % Monsters.size();
}
long long int SumPower = 0;
for (auto p : eachOrderNumber) {
SumPower = (SumPower + Monsters[p].Power) % K;
}
if (SumPower + difflimit < Monsters[eachOrderNumber[0]].Power) {
Monsters[eachOrderNumber[0]].Power = SumPower;
for (int k = 1; k < GroupNumber; k++) {
mess=mess+ to_string(eachOrderNumber[0])+ " " +to_string(eachOrderNumber[k])+"\n";
}
MagicTimes = MagicTimes - ((long long int)GroupNumber - 1);
}
}
return true;
}
long long int getScore(int K ,vector<MonsterInfo> monsters) {
long double Score = 0;
for (int i = 0; i < monsters.size();i++) {
Score += log2l(K) - log2l(monsters[i].Power + 1);
}
Score = ceil(Score);
return Score;
}
vector<MonsterInfo> randChangeMonsters(int K, vector<MonsterInfo> Monsters, string& message, long long int& MagicCount) {
message = "";
for (int i = 0; i < 100; i++) {
int p = rand() % Monsters.size();
int q = rand() % Monsters.size();
Monsters[p].Power = (Monsters[p].Power + Monsters[q].Power) % K;
message = message + to_string(p) + " " + to_string(q) + "\n";
}
return Monsters;
}
void UseMagic(long long int M,long long int K,vector<MonsterInfo> Monsters,int MaxPare) {
long long int MagicTimes = M;
for (int i = 2; i <MaxPare;i++) {
bool DoContinue = PowerUpMonstersNtimes(MagicTimes, Monsters, K, i,0);
if (DoContinue==false) {
return;
}
}
srand((unsigned int)time(NULL));
long long int MaxScore=getScore(K,Monsters);
string messP="";
//vector<MonsterInfo> MonstersP = Monsters;
for (int i = 0; i < 100;i++) {
vector<MonsterInfo> nextMonsters=Monsters;
string mes;
long long int Count = MagicTimes;
nextMonsters=randChangeMonsters(K,Monsters,mes,Count);
PowerUpMonstersNtimesStringVer(Count,
nextMonsters, K, 2,
0, mes);
int tempScore = getScore(K, nextMonsters);
if (tempScore>MaxScore) {
tempScore = MaxScore;
messP = mes;
//MonstersP = nextMonsters;
}
}
cout << messP;
return;
}
int main() {
/*ifstream inputFile("input.txt");
cin.rdbuf(inputFile.rdbuf());
ofstream outputFile("output.txt");
cout.rdbuf(outputFile.rdbuf());*/
long long int N, M, K;
cin >> N >> M >> K;
vector<MonsterInfo> Monster(N);
for (int i = 0; i < N;i++) {
cin >> Monster[i].Power;
Monster[i].Number = i;
}
int MaxPare = 3;
UseMagic(M,K,Monster,MaxPare);
//ScoreCalicurater("input.txt","output.txt",7);
return 0;
}
./Main.cpp: In function ‘void ScoreCalicurater(std::string, std::string, long long int)’:
./Main.cpp:39:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
39 | if (zerocount>=MonsterPower.size()-1) {
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp: In function ‘long long int getScore(int, std::vector<MonsterInfo>)’:
./Main.cpp:123:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<MonsterInfo>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
123 | for (int i = 0; i < monsters.size();i++) {
| ~~^~~~~~~~~~~~~~~~~
./Main.cpp: In function ‘std::vector<MonsterInfo> randChangeMonsters(int, std::vector<MonsterInfo>, std::string&, long long int&)’:
./Main.cpp:131:109: warning: unused parameter ‘MagicCount’ [-Wunused-parameter]
131 | vector<MonsterInfo> randChangeMonsters(int K, vector<MonsterInfo> Monsters, string& message, long long int& MagicCount) {
| ~~~~~~~~~~~~~~~^~~~~~~~~~