시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 213 169 164 82.000%

문제

승혁이는 괴짜 교수이다. 그는 미래에 컴퓨터 프로그램을 만들기 위해서는 컴퓨터 프로그램을 병렬로 만들어야 한다고 믿는다. 그가 옳다는 것을 확신시키기 위해서 그는 실험을 진행 하길 원했다. 

실험과정은 다음과 같다: 그는 먼저 몇 개의 문제에 대해 이 프로그램이 다음 해 동안 실행 될 횟수를 예상한다. 그리고 그는 그의 조교에게 병렬버전의 프로그램을 개발하고, 그 프로그램을 개발하는 데 걸리는 시간을 측정하라고 지시한다. 마지막으로,  그들은 병렬버전과 직렬버전의 실행 시간을 측정한다. 

이 측정된 데이터를 기반으로, 승혁이는 어떤 경우에 병렬화를 통해 전반적인 작업량을 최소화하는지 알고 싶어한다. 이 일에 대한 작업량은 병렬버전을 개발하는 시간과 그 프로그램이 실행될 때까지 기다리는 시간이다. 

입력

첫째 줄에 입력으로 테스트케이스의 개수 T (T ≤ 1000)가 주어진다. 각각의 테스트케이스에 대해 정수 d, n, s, p가 한 칸의 공백을 사이로 주어진다. d (0 ≤ d ≤ 1000000)는 병렬 버전을 개발하는데 걸리는 시간이다.그리고 n (0 ≤ n ≤ 100000) 은 다음해 동안 이 프로그램이 실행되는 횟수이다. s와 p (0 ≤ s, p ≤ 1000) 는  각각 직렬버전과 병렬버전의 실행 시간이다. 

출력

각각의 테스트케이스에 대해 병렬화를 하는게 좋으면 "parallelize" 를 출력하고, 병렬화를 하는게 좋지 않으면 "do not parallelize" 를 출력한다. 만약 직렬화와 병렬화를 통한 시간이 같으면 "does not matter" 를 출력한다.

예제 입력 1

3
10 2 3 2
20 5 8 2
0 2 1 1

예제 출력 1

do not parallelize
parallelize
does not matter

힌트

W3sicHJvYmxlbV9pZCI6IjExMTA5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZDM0XHVjOWRjIFx1YWQ1MFx1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMmI5XHVkNjAxXHVjNzc0XHViMjk0IFx1YWQzNFx1YzlkYyBcdWFkNTBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjI5NCBcdWJiZjhcdWI3OThcdWM1ZDAmbmJzcDtcdWNlZjRcdWQ0ZThcdWQxMzAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWJjZDFcdWI4MmNcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjJm5ic3A7XHVkNTVjXHViMmU0XHVhY2UwIFx1YmJmZlx1YjI5NFx1YjJlNC4gXHVhZGY4XHVhYzAwIFx1YzYzM1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVkNjU1XHVjMmUwXHVjMmRjXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFkZjhcdWIyOTQgXHVjMmU0XHVkNWQ4XHVjNzQ0IFx1YzljNFx1ZDU4OSZuYnNwO1x1ZDU1OFx1YWUzOCBcdWM2ZDBcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzJlNFx1ZDVkOFx1YWNmY1x1YzgxNVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0OiZuYnNwO1x1YWRmOFx1YjI5NCBcdWJhM2NcdWM4MDAgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM4MWNcdWM1ZDAgXHViMzAwXHVkNTc0Jm5ic3A7XHVjNzc0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWIyZTRcdWM3NGMmbmJzcDtcdWQ1NzQgXHViM2Q5XHVjNTQ4Jm5ic3A7XHVjMmU0XHVkNTg5Jm5ic3A7XHViNDIwIFx1ZDY5Zlx1YzIxOFx1Yjk3YyZuYnNwO1x1YzYwOFx1YzBjMVx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwJm5ic3A7XHVhZGY4XHViMjk0IFx1YWRmOFx1Yzc1OCBcdWM4NzBcdWFkNTBcdWM1ZDBcdWFjOGMgXHViY2QxXHViODJjXHViYzg0XHVjODA0XHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWFjMWNcdWJjMWNcdWQ1NThcdWFjZTAsIFx1YWRmOCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVhYzFjXHViYzFjXHVkNTU4XHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2UyMVx1YzgxNVx1ZDU1OFx1Yjc3Y1x1YWNlMCBcdWM5YzBcdWMyZGNcdWQ1NWNcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywmbmJzcDsgXHVhZGY4XHViNGU0XHVjNzQwIFx1YmNkMVx1YjgyY1x1YmM4NFx1YzgwNFx1YWNmYyBcdWM5YzFcdWI4MmNcdWJjODRcdWM4MDRcdWM3NTggXHVjMmU0XHVkNTg5IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNlMjFcdWM4MTVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWNlMjFcdWM4MTVcdWI0MWMgXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1YWUzMFx1YmMxOFx1YzczY1x1Yjg1YywgXHVjMmI5XHVkNjAxXHVjNzc0XHViMjk0IFx1YzViNFx1YjVhNCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViY2QxXHViODJjXHVkNjU0XHViOTdjIFx1ZDFiNVx1ZDU3NCBcdWM4MDRcdWJjMThcdWM4MDFcdWM3NzggXHVjNzkxXHVjNWM1XHViN2M5XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YjI5NFx1YzljMCBcdWM1NGNcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjNzdjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM3OTFcdWM1YzVcdWI3YzlcdWM3NDAgXHViY2QxXHViODJjXHViYzg0XHVjODA0XHVjNzQ0IFx1YWMxY1x1YmMxY1x1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgXHVhZGY4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWMyZTRcdWQ1ODlcdWI0MjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YWUzMFx1YjJlNFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQmbmJzcDsoVCZuYnNwOyZsZTsgMTAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwO1x1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzgxNVx1YzIxOCBkLCBuLCBzLCBwXHVhYzAwIFx1ZDU1YyBcdWNlNzhcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGQmbmJzcDsoMCAmbGU7IGQgJmxlOyAxMDAwMDAwKVx1YjI5NCBcdWJjZDFcdWI4MmMgXHViYzg0XHVjODA0XHVjNzQ0IFx1YWMxY1x1YmMxY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0XHViMmU0Llx1YWRmOFx1YjlhY1x1YWNlMCBuJm5ic3A7KDAgJmxlOyBuICZsZTsgMTAwMDAwKSZuYnNwO1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWQ1NzQmbmJzcDtcdWIzZDlcdWM1NDggXHVjNzc0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWMyZTRcdWQ1ODlcdWI0MThcdWIyOTQgXHVkNjlmXHVjMjE4XHVjNzc0XHViMmU0LiZuYnNwO3NcdWM2NDAgcCAoMCAmbGU7IHMsIHAgJmxlOyAxMDAwKSZuYnNwO1x1YjI5NCZuYnNwOyBcdWFjMDFcdWFjMDEmbmJzcDtcdWM5YzFcdWI4MmNcdWJjODRcdWM4MDRcdWFjZmMgXHViY2QxXHViODJjXHViYzg0XHVjODA0XHVjNzU4IFx1YzJlNFx1ZDU4OSBcdWMyZGNcdWFjMDRcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViY2QxXHViODJjXHVkNjU0XHViOTdjIFx1ZDU1OFx1YjI5NFx1YWM4YyBcdWM4OGJcdWM3M2NcdWJhNzQgJnF1b3Q7cGFyYWxsZWxpemUmcXVvdDsmbmJzcDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWJjZDFcdWI4MmNcdWQ2NTRcdWI5N2MgXHVkNTU4XHViMjk0XHVhYzhjIFx1Yzg4Ylx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgJnF1b3Q7ZG8gbm90IHBhcmFsbGVsaXplJnF1b3Q7IFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM5YzFcdWI4MmNcdWQ2NTRcdWM2NDAgXHViY2QxXHViODJjXHVkNjU0XHViOTdjIFx1ZDFiNVx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzE5XHVjNzNjXHViYTc0ICZxdW90O2RvZXMgbm90IG1hdHRlciZxdW90OyZuYnNwO1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTExMDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgbnV0dHkgcHJvZmVzc29yIiwiZGVzY3JpcHRpb24iOiI8cD5MYXNzZSBpcyBhIG51dHR5IHByb2Zlc3Nvci4gSGUgYmVsaWV2ZXMgc3Ryb25nbHkgdGhhdCBpbiBvcmRlciB0byBtYWtlIGNvbXB1dGVyIHByb2dyYW1zIGZvciB0aGUgZnV0dXJlLCBvbmUgc2hvdWxkIG1ha2UgdGhlbSBwYXJhbGxlbC4gSW4gb3JkZXIgdG8gY29udmluY2UgdGhlIHJlc3Qgb2YgdGhlIHdvcmxkIHRoYXQgaGUgaXMgY29ycmVjdCBoZSB3YW50cyB0byBjYXJyeSBvdXQgYW4gZXhwZXJpbWVudC4gVGhlIGV4cGVyaW1lbnQgcHJvY2VlZHMgYXMgZm9sbG93czogRm9yIGEgbnVtYmVyIG9mIHByb2JsZW1zIHdoZXJlIGEgc2VyaWFsIGltcGxlbWVudGF0aW9uIGlzIGF2YWlsYWJsZSwgaGUgZXN0aW1hdGVzIHRoZSBudW1iZXIgb2YgdGltZXMgdGhpcyBwcm9ncmFtIHdpbGwgYmUgZXhlY3V0ZWQgd2l0aGluIHRoZSBuZXh0IHllYXIgKHdoZW4gdGhlIHByb2dyYW0gd2lsbCBwcm9iYWJseSBiZSByZXdyaXR0ZW4pLiBIZSBvcmRlcnMgaGlzIHNsYXZlLCBNYWdudXMsIHRvIGRldmVsb3AgYSBwYXJhbGxlbCB2ZXJzaW9uIG9mIHRoZSBwcm9ncmFtIGFuZCBtZWFzdXJlcyB0aGUgYW1vdW50IG9mIHRpbWUgTWFnbnVzIHVzZXMgZGV2ZWxvcGluZyBpdC4gQXQgdGhlIGVuZCwgdGhleSBtZWFzdXJlIHRoZSBleGVjdXRpb24gdGltZSBvZiBib3RoIHRoZSBwYXJhbGxlbCBhbmQgdGhlIHNlcmlhbCB2ZXJzaW9uLjxcL3A+XHJcblxyXG48cD5CYXNlZCBvbiB0aGUgY29sbGVjdGVkIGRhdGEsIExhc3NlIHdhbnRzIHRvIGtub3cgaW4gd2hpY2ggY2FzZXMgdGhlIG92ZXJhbGwgbnVtYmVyIG9mIG1hbi1ob3VycyBzcGVudCBvbiB0aGlzIHByb2dyYW0gaXMgbWluaW1pemVkIGJ5IHBhcmFsbGVsaXppbmcuIE1hbi1ob3VycyBhcmUgc3BlbnQgZGV2ZWxvcGluZyB0aGUgcGFyYWxsZWwgdmVyc2lvbiBhbmQgd2FpdGluZyB3aGlsZSBwcm9ncmFtcyBleGVjdXRlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGhhcyB0ICZsZTsgMTAwMCBjYXNlcywgd2hlcmUgdCBpcyBnaXZlbiBieSB0aGUgZmlyc3QgbGluZSBvZiBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgaXMgZ2l2ZW4gYnkgYSBsaW5lIHdpdGggZm91ciBpbnRlZ2VycyBkLCBuLCBzIGFuZCBwIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gZCBpcyB0aGUgdGltZSBzcGVudCBkZXZlbG9waW5nIHRoZSBwYXJhbGxlbCB2ZXJzaW9uICgwICZsZTsgZCAmbGU7IDEwMDAwMDApLCBhbmQgbiBpcyB0aGUgZXhwZWN0ZWQgbnVtYmVyIG9mIHRpbWVzIHRoaXMgcHJvZ3JhbSB3aWxsIGJlIGV4ZWN1dGVkIGR1cmluZyB0aGUgbmV4dCB5ZWFyICgwICZsZTsgbiAmbGU7IDEwMDAwMCkuIHMgYW5kIHAgYXJlIHRoZSBydW5uaW5nIHRpbWVzIG9mIHRoZSBzZXJpYWwgYW5kIHBhcmFsbGVsIHZlcnNpb24gb2YgdGhlIHByb2dyYW0gcmVzcGVjdGl2ZWx5ICgwICZsZTsgcywgcCAmbGU7IDEwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBvdXRwdXQgJnJkcXVvO3BhcmFsbGVsaXplJnJkcXVvOyBvbiBhIHNpbmdsZSBsaW5lIGlmIGl0IGlzIGJlbmVmaWNpYWwgdG8gcGFyYWxsZWxpemUuIElmIGl0IGlzIG5vdCBiZW5lZmljaWFsIHRvIHBhcmFsbGVsaXplLCB0aGUgb3V0cHV0dGVkIGxpbmUgc2hvdWxkIGJlICZyZHF1bztkbyBub3QgcGFyYWxsZWxpemUmcmRxdW87LiBJZiB0aGUgZXhwZWN0ZWQgdG90YWwgdGltZSBzcGVudCB3aXRoIHRoZSBwcm9ncmFtIGlzIHNpbWlsYXIgcmVnYXJkbGVzcyBvZiB3aGV0aGVyIGl0IGlzIHBhcmFsbGVsaXplZCBvciBub3QsIHRoZSBvdXRwdXR0ZWQgbGluZSBzaG91bGQgYmUgJnJkcXVvO2RvZXMgbm90IG1hdHRlciZyZHF1bzsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > IDI Open Contest > IDI Open 2008 C번

  • 문제를 번역한 사람: tols91