FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 |

«Problem A: Movie The “Last ACM Contest” movie has been recently released and got the record of the highest worldwide gross. Gabby has been so ...»

-- [ Page 1 ] --

38th ACM International Collegiate

Programming Contest, 2013–2014

Asia Region, Tehran Site

Sharif University of Technology, 19–20 December 2013

Problem A: Movie

The “Last ACM Contest” movie has been recently released and got the record of the highest worldwide gross. Gabby

has been so busy due to his practicing for the ACM programming contest in Tehran site and hence, he has not

succeeded to watch the movie at a cinema. Like many other people, he has legally downloaded the movie to watch it using a smart phone or a tablet on the way back home from the Sharif University on 20 December 2013, the contest day. Unfortunately, he has neither a smart phone nor a tablet. He therefore has decided to buy a device from the following smart phones or tablets that are available in the market.

Device Price Resolution iPad Mini 319 1024×768 Galaxy Tab 419 1024×600 iPhone 4S 450 960×640 iPad4 519 2048×1536 iPhone 5C 599 1136×640 Galaxy Tab2 600 1280×800 Galaxy S4 630 1080×1920 iPhone 5S 719 1136×640 As you can see, each device has a known “height × width” resolution which is the number of distinct pixels in each dimension that can be displayed. Like the above devices, each movie has a known resolution and video players equally scale both dimensions of the movie resolution by a factor of to display it in a window where is the largest integer not greater than and is a rational number such that and are not greater than the height and width resolutions of the display, respectively. Indeed, video players zoom a movie in or out while preserving the aspect ratio (the ratio of the height resolution to the width resolution) of the movie. When a video player displays a movie in the full-screen window in a device, some parts of the device display may remain “blank” (or unused) due to the difference in the aspect ratios of the device display and the movie. For a movie resolution and a display resolution, the usage ratio is defined to be the ratio of the non-blank area of the full-screen video-player window showing the movie to the area of the device display. As all above devices can rotate the whole screen 90 degrees, they may increase their usage ratio for a movie. For instance, if the movie resolution is, the usage ratio of iPad4 is the maximum of an

–  –  –

Gabby is now looking for a device with the highest usage ratio for the “Last ACM Contest” movie which is stored with the resolution. He kindly asks you to report him this device before the end of the contest.

Input (Standard Input) There are multiple test cases in the input. Each test case consists of a line containing two integers which is the resolution of the “Last ACM Contest” movie. The input terminates with “0 0” which should not be processed.

Output (Standard Output) For each test case, output a line containing the price of the device which has the highest usage ratio for the given movie resolution. In case of a tie, output the smallest price. For example, if both iPad4 and iPad Mini have the highest usage ratio, output 319.

–  –  –

Problem B - Page 1 of 2 discarding duplicates SMSs. The format of the output must conform to the format indicated in the Standard Output below‎.

Sample Input and Output

–  –  –

Problem C: Traitor According to an intelligence source, we’ve got a traitor in ACM Security Agency (ASA). ASA has a hierarchical structure where each agent has a manager and there are also some (at least one) top managers who are not managed by anyone. Our source doesn’t exactly know the traitor, but he has a list of suspects. Therefore, all we know is that there is exactly one traitor in our agency and we have a list of suspects. In order to find that traitor, we want to assign a watcher

for each suspect, satisfying the following three conditions:

1. Two suspects cannot watch each other.

2. Each suspect should be watched by either his manager or one of his direct employees.

3. Nobody can watch more than one suspect.

If we want to satisfy all above conditions, it may be impossible to watch all suspects. Therefore, you should write a program that gets the structure of ASA and the list of suspects as the input and finds the maximum number of suspects for whom the watcher assignment is possible. In the following figure that illustrates the organizational structure of ASA with two top managers and eleven agents, the suspects are indicated with gray color. One watcher assignment covering 7 out of 8 suspects is possible in this case which is shown by arrows. An arrow from agent x to agent y, means agent x is supposed to watch agent y. It can be shown that in this example there is no watcher assignment covering all suspects.

Input (Standard Input) There are multiple test cases in the input. The first line of each test case contains two integers ( ) specifying the number of agents, and ( ) specifying the number of the suspected agents. The agents are numbered from to. On the second line there are space-separated integers, where the number is the number of agent who is the manger of the agent. A zero means the agent is a top manager. On the third line there are positive, indicating the numbers of the suspected agents. The input terminates with “0 0” which should not integers be processed.

Output (Standard Output) For each test case, output in a line the maximum number of suspects for whom the watcher assignment is possible.

–  –  –

Problem D: Intelligent Traffic Surveillance Recently, Mr. Hamsadeh is working as an IT engineer in the central traffic control department of Tehran municipality.

He is now in charge of a new traffic surveillance system with which the law-breaking vehicles are going to be fined through automatic plate detection and issuing penalty tickets. The system has been running for a few weeks in the production environment and now is the time for Mr. Hamsadeh to issue the tickets. While he was preparing the system, the persistence storage of the database server came into a fatal hardware crash and all its data was disastrously lost.

Laughing at his own misery, misfortunate Mr. Hamsadeh started inspecting the other systems in hope of data-recovery.

The only available pieces of information are the log files remaining in the application server. Fortunately, all forms of data-entry are logged in the service layer of the application server, and thus, the lost information can be totally survived using the log files. But such data-recovery tasks are too complicated for Mr. Hamsadeh and there is not enough time to setup a new database, import the recovered data and reconfigure the whole architecture for issuing the tickets. With deep feelings of being squashed, Mr. Hamsadeh is asking you for help. You have to write a program that reads all the log files and issues the penalty tickets. In the following paragraphs, Mr. Hamsadeh describes Tehran traffic regulations, services provided by the traffic surveillance system, the format of log files, and the rules for issuing tickets.

Each road is considered in one of the three traffic-specific zones of Tehran:

 Central Traffic Restricted Zone (CTRZ)  Even/Odd Restricted Zone (EORZ)  Unrestricted Zone (UZ) Ordinary personal vehicles are not normally permitted to enter CTRZ

during these time intervals:

 Saturday through Wednesday from 06:30 to 17:00  Thursday from 06:00 to 13:30 Ordinary personal vehicles whose vehicle registration number ends with

an even digit are not permitted to enter EORZ during these time intervals:

 Sunday and Tuesday from 06:30 to 19:00  Thursday from 06:30 to 17:00 Ordinary personal vehicles whose vehicle registration number ends with an odd digit are not permitted to enter EORZ

during these time intervals:

 Saturday, Monday and Wednesday from 06:30 to 19:00 So, none of these zone restrictions are applied on Fridays (official weekends in Iran). Some vehicles (including public transportation and emergency services) are allowed to enter CTRZ and EORZ anytime with no restrictions. Ordinary vehicles can also enter these zones if they buy the permission for a single day, but you are not to consider buying permissions in this problem. If a vehicle enters CTRZ or EORZ unlawfully, it should be fined. Each vehicle must be fined at most once a day for zone restriction violations. If both CTRZ and EORZ violations happen for a vehicle on a single day, the CTRZ violation is considered which has naturally a higher penalty. Each road is initially considered to be in UZ, but this state may change based on announcements. The new rules of all such announcements must be applied from the day after the announcement. In the same way, no vehicles are initially exempt from zone regulations, but the exceptions are added and removed over time. Such modifications must also be considered from the next day.

The following are the services provided by the application server. Each service has a corresponding log message which is written on a single line starting with the service name followed by the parameters. As you will see in service definitions and examples, the parameters of a service are printed in a specific order. Independent of the service type, the parameter list of each log message starts with a special pair of parameters (called timestamp): “day” and “time”.

A timestamp naturally shows the exact time of its corresponding service request. Parameter “day” is a positive integer showing the number of days passed from the day of system deployment (called day 0). Parameter “time” shows the time of the request on that day in “ ” format (, ).

 setRoadZone(day, time, zone, roads) Parameter “zone” can be “UZ”, “CTRZ”, or “EORZ”. Parameter “roads” contains a non-empty list of not-necessarilydistinct road names. From the beginning of the next day, the corresponding roads must be considered in the given “zone” (overriding their former zone states). Log examples:

 setRoadZone 2 "09:12:53" "CTRZ" "Enghelab" "Sa'di" "Ferdowsi" "Ferdowsi"  setRoadZone 5 "14:32:01" "EORZ" "Resalat"  setRoadZone 12 "00:00:59" "UZ" "Persian_Gulf"  addZoneException(day, time, vehicles) | removeZoneException(day, time, vehicles) Problem D - Page 1 of 3 Parameter “vehicles” contains a non-empty list of not-necessarily-distinct vehicle registration numbers. From the beginning of the next day, the corresponding vehicles {must not | must} be fined in the case of entering CTRZ or EORZ during the forbidden times. These commands override the older state of the given vehicles (which might be the

same state). Log examples:

 addZoneException 1 "09:00:13" "1234567" "9876543"  removeZoneException 3 "15:33:02" "1234567" "9876345"  addPhotoInfo(day, time, photoId, road, vehicles) This is one of the key services of the system. It is not called from user interface layer. It is called by another complex system: the external image processing server which analyzes the pictures taken by the surveillance cameras. This service is called when a photo is taken and analyzed. The identifier of the analyzed photo is given in parameter “photoId”, a positive integer. Parameter “road” holds the name of the road from which the photo was taken. The image processing server detects the vehicles in the photo and extracts their registration number from their plates.

Parameter “vehicles” provides the list of these vehicle registration numbers. It is possible for this list to be empty as there might be no vehicles in the photo. The “timestamp” parameter here refers to the moment of taking the

photo. Log examples:

 addPhotoInfo 18 "03:18:43" 3324249 "Pastor" "6256256" "8888310"  addPhotoInfo 4 "20:47:31" 54 "Mokhberoddoleh,_sar-e_Sa'di"  addPhotoInfo 27 "06:39:14" 112385612 "17-e_shahrivar" "1006016"

You can assume the following statements:

 Parameter objects are always in one of the following forms:

 Integer numbers: All nonnegative  Strings: Always surrounded with quotation marks ( " )  Lists: Always appearing as the last parameter, consisting of pace-separated strings through the end of the line  All tokens including service names and parameter objects (strings, integers, and list members) are separated with a single space.

 The “time” parameter which is in “ ” format, has exactly 8 characters and all its three parts are exactly 2 digits (padded with “0” in the case of being less than 10).

 Road names consist of English alphabet (both lowercase and uppercase letters), digits, dash ( - ), underscore ( _ ), dot (. ), comma (, ), and single quotation mark ( ' ). Road names are nonempty and no longer than 100 characters.

 All vehicle registration numbers are strings of exactly 7 digits.

 Each road or vehicle is always referenced with the same string.

 No two timestamps are exactly the same.

 If there are conflicting commands on the same day, the newer command (one with the bigger timestamp) must override the older one. You can assume that the “addPhotoInfo” service is called at most once for each photoId.

 Each vehicle registration number appears at most once in each photo.

 The running time of the system is at most days.

 A vehicle must be fined for outlawed zone entrance even if its photo was taken on the time boundaries (e.g. at Monday 6:30:00).

The vehicles must be fined based on photo analysis results. As stated before, zone-entrance penalty tickets should be issued for each vehicle at most once a day. All photos of such a violation in a day must be attached to its corresponding penalty ticket. Photo attachments of a ticket must be sorted in ascending order based on their times. Note that if both CTRZ and EORZ entrances happen together for a vehicle, all photos of both violations must be attached, but the ticket should be issued with the CTRZ penalty. The order of printed tickets is also important. Tickets must be primarily sorted based on their vehicles such that their registration numbers appear in lexicographic order. Tickets of a vehicle must then be sorted in ascending order based on the day of offence.

Pages:   || 2 | 3 |

Similar works:

«SWISS CORPORATE GOVERNANCE – AN OVERVIEW Peter V. Kunz* Swiss Corporate Governance – an Overview 1. Introduction The key focus of this publication shall be on corporations and, in particular, on listed companies. Thus, corporate governance aspects in other areas of the law (e.g. public enterprises, banks and other financial intermediaries) have to be neglected. Swiss company laws provide for the distinction between corporation organizations and partnership organizations.1 The latter are...»

«04. Oktober 2014 Gutachten über die Beurteilung der überhöhten Gleisneigung beim Bahnhofsprojekt Stuttgart 21 unter Berücksichtigung der Anforderungen aus der EBO und dem bisherigen Verfahrensablauf Von Dip.-Ing. Sven Andersen, BDir a.D. Im Auftrag von BUND Regionalgeschäftsstelle Stuttgart und Verkehrsclub Deutschland, Landesverband Baden-Württemberg e.V. (VCD) INHALTSVERZEICHNIS 1. Zusammenfassung 2. Einleitung 3. Rechtlicher Hintergrund – AEG und EBO 4. Physik, Risikoanalyse und...»

«Case 1:10-cv-00316-NT Document 44 Filed 07/19/11 Page 1 of 18 PageID #: 439 UNITED STATES DISTRICT COURT DISTRICT OF MAINE ASHLEY E. ALDEN, ) ) Plaintiff ) ) 1:10-cv-00316-GZS ) OFFICE FURNITURE DISTRIBUTORS ) OF NEW ENGLAND, INC., ) ) Defendant ) RECOMMENDED DECISION Ashley Alden has sued her former employer, Office Furniture Distributors of New England, Inc., alleging breach of contract, violation of 10 M.R.S. § 1342 (pertaining to sales representatives contracts), and defamation. Office...»

«AD HOC WORKING GROUP ON THE DURBAN PLATFORM FOR ENHANCED ACTION ADP.2015.8.InformalNote Non-paper Note by the Co-Chairs 5 October 2015 A. DRAFT AGREEMENT [ The Parties to this Agreement, Pp1 Being Parties to the United Nations Framework Convention on Climate Change, hereinafter referred to as “the Convention”, Pp2 In furtherance of the objective of the Convention, Pp3 Recalling decision 1/CP.17, whereby the Conference of the Parties to the Convention decided to adopt a protocol, another...»

«Curriculum Vitae Adrian Ritz [Updated: December 23, 2014] Nationality: Swiss Date of Birth: January 18, 1970 Address: University of Bern, Center of Competence for Public Management, Schanzeneckstrasse 1, P.B. 8573, CH-3001 Bern Phone: +41 (0)31 631 53 13, +41 (0)79 711 25 15 Email / Web: adrian.ritz@kpm.unibe.ch / www.kpm.unibe.ch Adrian Ritz is professor for Public Management and a member of the executive board of the interdisciplinary center of competence for public management at the...»

«Federal Environment Agency – Austria FISCHFAUNA IN ÖSTERREICH Ökologie – Gefährdung – Bioindikation Fischerei – Gesetzgebung Thomas Spindler MONOGRAPHIEN Band 87 M-087 Wien, 1997 Bundesministerium für Umwelt, Jugend und Familie für das Projekt verantwortlich Dr. Andreas Chovanec, Umweltbundesamt Autoren Dr. Thomas Spindler, allgem. beeideter gerichtlicher Sachverständiger f. Fischerei, Büro f. Fischerei und Gewässerökologie, Unterolberndorf 93, A-2123 Kreuttal Kap. 5: Dr....»

«HOW'S MY DRIVING? FOR EVERYONE (AND EVERYTHING?) LIOR JACOB STRAHILEVITZ* This is an Article about using reputation-trackingtechnologies to displace criminal law enforcement and improve the tort system. The Article contains an extended application of this idea to the regulation of motorist behavior and examines the broader case for using technologies that aggregatedispersed information in various settings where reputational concerns do not adequately deter uncooperative behavior. The Article...»

«What is Converging? Rules on Hostile Takeovers in Japan and the Convergence Debate Kenichi Osugi* I. INTRODUCTION II. SOME CRITICAL COMMENTS ON THE CONVERGENCE DEBATE. 144 A. Convergence at Various Levels B. Process of Transplanting Laws C. The Vague Line Between Corporate Law and Securities Regulation D. The Need for Multi-Dimensional Analysis. III. THE DEVELOPMENT OF A LEGAL FRAMEWORK: WANDERING BETWEEN THE UNITED STATES AND THE UNITED KINGDOM. 148 A. The Rules Before 1990 B. Before the...»

«Recommendations on the TRANSPORT OF DANGEROUS GOODS Manual of Tests and Criteria Fifth revised edition Amendment 2 UNITED NATIONS ST/SG/AC.10/11/Rev.5/Amend.2 Recommendations on the TRANSPORT OF DANGEROUS GOODS Manual of Tests and Criteria Fifth revised edition Amendment 2 UNITED NATIONS New York and Geneva, 2013 NOTE The designations employed and the presentation of the material in this publication do not imply the expression of any opinion whatsoever on the part of the Secretariat of the...»

«1 Право. Юридические науки 1. Administrative Law Reform in Uzbekistan. Experiences and Problems from the LeХ(Англ) gal Viewpoint : Collection of Seminar Papers / ed. M. H. Rustambaev, M. B. UsmaA21 nov, L. B. Khvan. Tashkent : Tashkent State Institute of Law, 2008. 179 p.; 21 cm. Перевод заглавия: Реформа административного права в Узбекистане. Опыт и проблемы с правовой точки...»

«Service provided by the Federal Ministry of Justice in cooperation with juris GmbH – www.juris.de Übersetzung durch Samson Übersetzungen GmbH, Dr. Carmen von Schöning Translation provided by Samson Übersetzungen GmbH, Dr. Carmen von Schöning © 2012 juris GmbH, Saarbrücken Code of Civil Procedure Full citation: Code of Civil Procedure as promulgated on 5 December 2005 (Bundesgesetzblatt (BGBl., Federal Law Gazette) I page 3202; 2006 I page 431; 2007 I page 1781), last amended by Article...»

«Legal OTHER ROUTES 1500 YEARS OF AFRICAN AND ASIAN TRAVEL WRITING 109234 eBook for free and you can read online at Online Ebook Library. Get OTHER ROUTES 1500 YEARS OF AFRICAN AND ASIAN TRAVEL WRITING 109234 PDF file for free from our online library OTHER ROUTES 1500 YEARS OF AFRICAN AND ASIAN TRAVEL WRITING 109234 PDF Are you looking for OTHER ROUTES 1500 YEARS OF AFRICAN AND ASIAN TRAVEL WRITING 109234 PDF?. If you are a reader who likes to download OTHER ROUTES 1500 YEARS OF AFRICAN AND...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.