- محدودیت زمان: ۶ ثانیه
- محدودیت حافظه: ۳۲ مگابایت
مجید که از کار در مزرعه خسته شده است، به هنر آشپزی روی آورده و می‌خواهد سبک جدیدی از آشپزی را ارائه بدهد. به این منظور او با استفاده از فرمول‌های پیچیده‌ای که دارد تعدادی غذا درست می‌کند و هر غذا از تعدادی ماده‌ی اولیه درست می‌شود. مواد اولیه را با اعداد صحیح بین ۰ تا $10^9$ نشان می‌دهیم و تعداد غذاهایی که مجید می‌پزد را با $n$ مشخص می‌کنیم.
مجید در آشپزی هم رفتارهای عجیبی دارد! مثلاً همه‌ی غذاهایی که مجید می‌پزد تعداد مواد اولیه‌شان برابر است. تعداد مواد اولیه‌ی غذاهای مجید را با $m$ مشخص می‌کنیم. همچنین هر غذایی یک دستور پخت دارد که مشخص می‌کند مواد اولیه به چه ترتیبی باید اضافه شوند؛ یعنی می‌توان گفت به ازای غذای $j$ام، مجید دنباله‌ای از مواد اولیه $a_{j, 1}, a_{j, 2}, a_{j, 3}, ..., a_{j, m}$ دارد که شماره مواد اولیه‌ی آن و ترتیب اضافه شدن آن‌ها را مشخص می‌کند. ($1 \le j \le n$)
عجیب‌ترین رفتار مجید در آشپزی این است که تعداد غذاهایی که می‌پزد خیلی زیاد است! آنقدر زیاد است که در حافظه نمی‌گنجد و نمی‌تواند بطور مستقیم دستور پخت آن غذاها را به فرد دیگری توضیح دهد؛ برای همین دنباله‌ی مواد اولیه‌ی غذاهای خود را کاملاً اتفاقی می‌سازد! برای این کار از الگوریتم KISS (مخفف Keep It Simple Stupid)استفاده می‌کند. کد این الگوریتم در زبان ++C به شکل زیر است. (مقادیر اولیه‌ی متغیرهای $x$ و $y$ و $z$ و $c$ در ورودی به شما داده می‌شود.)
unsigned long long x, y, z, c;
unsigned long long uint32(unsigned long long i)
{
return i & 0xFFFFFFFF;
}
unsigned long long kiss()
{
x = uint32( 69069 * x + 12345 );
y ^= uint32(y << 13);
y ^= uint32(y >> 17);
y ^= uint32(y << 5);
unsigned long long t = 698769069 * z + c;
c = uint32(t >> 32);
z = uint32(t);
return uint32(x + y + z);
}
سپس مجید بصورت کد زیر، دستور پخت غذاها را تولید می‌کند. (مقدار $e$ نیز در ورودی مسئله آمده است.)
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
a[i][j] = kiss() % e;
مجید پس از مدتی طولانی متوجه شد که با اینکه دستور پخت‌هایش بصورت کاملاً اتفاقی و پخش هستند، ولی ممکن است تعدادی از این غذاها عیناً یکسان باشند؛ یعنی تمام مواد اولیه و ترتیب اضافه کردنشان داخل دستور پخت یکی باشد. (دقت کنید که تعداد مواد اولیه در دستور پخت غذاها هم برابر است.)
حال مجید از شما می‌خواهد برنامه‌ای بنویسید که با ورودی گرفتن همه‌ی اطلاعات، تعداد انواع غذاهای مختلفی را که تولید می‌کند بصورت تقریبی را خروجی دهد. برای چالش‌برانگیزتر شدن مسئله مجید اطلاعات چند روز مختلفش را به برنامه‌ی شما می‌دهد که چندین سناریوی مختلف تولید می‌کنند و شما باید به همه‌ی آن‌ها پاسخ بدید. (به بخش ورودی توجه کنید.)
البته نیازی نیست شما پاسخ دقیق را خروجی دهید؛ شما می‌توانید با کمی خطا پاسخ مسئله را بیابید. هرچه خروجی شما دقیق‌تر باشد، در نهایت نمره‌ای که برنامه‌ی شما از این سوال دریافت می‌کند بیشتر خواهد بود.
ورودی
در خط اول ورودی $t$ آمده که نمایانگر تعداد روزهایی است که مجید آشپزی می‌کند.
به ازای هر روز، دو خط ورودی آمده.
در خط اول روز $i$ام، ورودی ابتدا $n$ و سپس $m$ آمده است که تعداد غذاهای آن روز و تعداد مواد اولیه استفاده شده در هریک از آن غذاها را مشخص می‌کند.
سپس در خط بعدی ورودی هر روز، به ترتیب ۵ عدد $x$ و $y$ و $z$ و $c$ و $e$ برای آن روز آمده است که نمایانگر مقادیر اولیه‌ی تابع تصادفی مورد استفاده‌ی مجید برای آن روز هستند.
$$1 \le t \le 3$$ $$1 \le n \le 20\ 000\ 000$$ $$1 \le m \le 3$$ $$0 \le x , y , z , c \le 1\ 000\ 000\ 000$$ $$1 \le e \le 1\ 000\ 000\ 000$$
مجموع $n \times m$ برای همه‌ی $t$ روز حداکثر برابر $20\ 000\ 000$ است.
خروجی
خروجی باید شامل $t$ خط باشد و در خط $i$ام تقریب‌تان از تعداد غذاهای متمایزی که مجید در روز $i$ام درست می‌کند را چاپ خواهید کرد.
مثال
ورودی نمونه
3
10 1
1 2 3 4 10
10 2
1 2 3 4 10
10 3
4 3 2 1 3
خروجی نمونه
7
9
7
**توضیح ورودی نمونه : ** در این مثال مجید ۳ روز آشپزی خواهد کرد که اطلاعات هر روز در ۲ خط متوالی آمده است. در خط دوم و سوم ورودی اطلاعات روز اول آشپزی، در خط چهارم و پنجم ورودی اطلاعات روز دوم آشپزی و در ۲ خط آخر اطلاعات روز سوم آشپزی آمده است.
ارسال پاسخ برای این سؤال