İki peçenye

Bu interaktiv bir tapşırıqdır. Proqramınız standart çıxışa məlumat yazaraq və standart girişdən məlumat oxuyaraq qiymətləndirici ilə ünsiyyət quracaq.

Sofi əkizlərinin ad gününü hazırlayır. Əkizlər peçenye sevirlər və ad günündə Unique Cookie Tastiness Company (UCTC) şirkətindən yeni bir şey sınamaq istəyirlər.

UCTC tərəfindən istehsal olunan hər bir peçenye $1$-dən $10^{16}$-ə qədər daxil olmaqla tam ədəd şirinlik dəyərinə malikdir. Sofinin əkizləri bir-birinə qısqanc olduqları üçün hər biri eyni ümumi şirinlik dəyərinə malik peçenye almalıdır.

UCTC yalnız dəqiq $n$ peçenyedən ibarət sifarişləri qəbul edir. Hər bir sifarişdə müştəri istədiyi $n$ peçenyenin şirinlik dəyərini göstərir.

Adına sadiq qalaraq, Unique Cookie Tastiness Company bir müştəri üçün eyni şirinlik dəyərinə malik iki peçenye istehsal etməkdən imtina edir. Sofi əmin olmalıdır ki, o, heç vaxt eyni şirinlik dəyərini iki dəfə sifariş etmir - nə bir sifarişdə, nə də iki fərqli sifarişdə. Sofi əvvəllər UCTC-dən peçenye almamışdır, ona görə də hər bir şirinlik dəyərini yalnız bir dəfə sifariş edə bilər.

Sofinin qarşısında başqa bir maneə var: UCTC-nin çatdırılma xidməti dəhşətli olduğu məlumdur. Müştəri hər dəfə $n$ peçenye sifariş etdikdə, bu $n$ peçenyedən yalnız biri müştəriyə çatdırılır. Qalanları çatdırılma xidməti işçiləri tərəfindən yolda yeyilir. Sofi hansı sifariş edilmiş $n$ peçenyenin ona çatdırılacağını təsir edə bilmir.

Ad günü çox yaxın olduğu üçün Sofinin ən çox 101 sifariş verməyə vaxtı var. Sizin vəzifəniz ona kömək etməkdir.

Daha konkret olaraq, siz aşağıdakıları etməlisiniz:

1. Əvvəlcə peçenye sifariş edin. Siz ən çox 101 sifariş verə bilərsiniz, hər biri dəqiq $n$ istənilən şirinlik dəyərlərindən ibarətdir. Siz bir anda bir sifariş verirsiniz. Hər sifarişdən dərhal sonra sizə faktiki olaraq çatdırılan bir peçenyenin şirinlik dəyəri verilir.

   Unutmayın ki, eyni şirinlik dəyərini bir neçə dəfə istifadə etməyə icazə verilmir, hətta fərqli sifarişlər üçün də. (Xüsusilə, əgər siz müəyyən bir şirinlik dəyərinə malik peçenye sifariş edirsinizsə, lakin o gəlmirsə, siz eyni şirinlik dəyərinə malik peçenyeni yenidən sifariş edə bilərsiniz.)

2. Sonra peçenyeləri bölüşdürün. Kifayət qədər peçenye aldıqdan sonra, siz bəzi peçenyeləri əkizlər arasında bölüşdürməlisiniz. Hər iki əkiz ən azı bir peçenye almalıdır və hər bir əkiz eyni ümumi şirinlik dəyərinə malik peçenye almalıdır. Sizə verilən bütün peçenyeləri istifadə etmək məcburiyyətində deyilsiniz.

Qarşılıqlı təsir

Proqramınız aşağıdakı ardıcıllıqla hərəkət etməlidir:

1. Standart girişdən $n$ ədədini oxuyun.

2. Ən çox 101 dəfə:

   • Əvvəlcə standart çıxışa $n$ peçenyeni təsvir edən bir sətir yazın.

   • Sonra standart girişdən sizə verilən peçenyenin şirinlik dəyərini oxuyun. Bu dəyərin iştirakçı tərəfindən yeni çıxarılan $n$ dəyərlər arasında olması təmin edilir.

3. Əkizlərə bəzi peçenyeləri vermək üçün bir etibarlı üsulu təsvir edən üç sətir yazın.

Qiymətləndirici hər tam ədədi ayrı bir sətirdə çıxaracaq.

Peçenye sifariş etmək üçün, ? işarəsi və sonra $n$ tam ədəd: istədiyiniz peçenyelərin şirinlik dəyərlərini bir sətirdə çıxarın. Hər bir $n$ tam ədədin qarşısında bir boşluq qoyun.

Unutmayın ki, ən çox 101 sifariş verə bilərsiniz və eyni şirinlik dəyərini iki dəfə istifadə etməyə icazə verilmir.

Kifayət qədər peçenye sifariş etdikdən sonra, Sofinin əkizlərə verməli olduğu peçenyeləri təsvir edən son üç sətiri çıxarın.

Bu sətirlərdən birincisi «! $m$ $k$» şəklində olmalıdır, burada $m,k>0$: müvafiq olaraq, birinci və ikinci əkizin almalı olduğu peçenyelərin sayı.

Bu sətirlərdən ikincisi birinci əkizin almalı olduğu peçenyelərin şirinlik dəyərlərini tək boşluqlarla ayrılmış $m$ tam ədəd şəklində olmalıdır.

Bu sətirlərdən üçüncüsü ikinci əkizin almalı olduğu peçenyelərin şirinlik dəyərlərini tək boşluqlarla ayrılmış $k$ tam ədəd şəklində olmalıdır.

Çıxış aşağıdakı şərtlərə cavab verməlidir:

• Hər bir əkiz ən azı bir peçenye almalıdır.

• Hər bir əkiz eyni ümumi şirinlik dəyərinə malik peçenye almalıdır.

• Yalnız sifarişlərdən sonra faktiki olaraq aldığınız peçenyeləri istifadə edə bilərsiniz.

• Bu peçenyelərin hər biri yalnız bir əkizə verilə bilər.

Bu şərtlərə cavab verən hər hansı bir çıxış qəbul ediləcəkdir. Xüsusilə, seçilmiş peçenyeləri istənilən ardıcıllıqla çıxara bilərsiniz.

Son üç sətiri çıxardıqdan sonra sonuncu dəfə 'flush' əməliyyatını yerinə yetirin və sonra proqramı normal şəkildə tamamlayın.

Çıxış verilənləri

Proqramınız standart çıxışa bir və ya bir neçə sətir çıxardıqda, siz 'flush' əməliyyatını yerinə yetirməlisiniz. Bu, çıxardığınız məlumatların dərhal qiymətləndiriciyə çatmasını təmin etmək üçün lazımdır.

Bunu necə edəcəyinizə dair nümunələr:

• C++-da bunu etməyin bir neçə yolu var.

  • fflush(stdout);

  • std::cout << std::flush;

  • std::cout << std::endl; (bu əməliyyatın əlavə sətir çıxardığını unutmayın)

• Java-da System.out.flush() istifadə edə bilərsiniz

• Python-da sys.stdout.flush() istifadə edə bilərsiniz

Nümunələr

1
13
7
31
12
5
3

? 13
? 7
? 31
? 12
? 5
? 3
! 2 3
7 13
12 5 3

2
7
2
5

? 3 7
? 2 8
? 1 5
! 2 1
2 5
7

Qeyd

Giriş və çıxış nümunələri sətir-sətir oxunmalıdır. Proqramınız standart girişdən bir dəyər oxuyur və standart çıxışa bir sətir (və ya sonunda üç sətir) yazır.

Qiymətləndirici hansı peçenyənin qaytarılacağını özbaşına seçir. Bu o deməkdir ki, qiymətləndirici bəzi testlərdə sorğularınıza uyğunlaşa bilər, lakin digər testlərdə təsadüfi peçenyeləri də seçə bilər. Xüsusilə, $n=2$ üçün, ikinci nümunədəki eyni sifariş ardıcıllığını etsəniz, fərqli bir peçenye dəsti ala bilərsiniz.

Qiymətləndirmə

Blok 1 (8 bal): $n=1$

Blok 2 (9 bal): $1\le n\le 2$

Blok 3 (18 bal): $1\le n\le 25$

Blok 4 (16 bal): $1\le n\le 200$

Blok 5 (13 bal): $1\le n\le 1000$

Blok 6 (36 bal): $1\le n\le 5000$